Standard finite element or boundary element methods for high frequency scattering problems, with piecewise polynomial approximation spaces, suffer from the limitation that the number of degrees of freedom required to achieve a prescribed level of accuracy grows at least linearly with respect to the frequency. Here we present a new boundary element method for problems of acoustic scattering by convex polygons for which, by including in the approximation space the products of plane wave basis functions with piecewise polynomials supported on a graded mesh, we can demonstrate a computational cost that grows only logarithmically with respect to the frequency.