Within the AdS/CFT correspondence, we identify a class of CFT operators which represent diff-invariant and approximately local observables in the gravitational dual. Provided that the bulk state breaks all asymptotic symmetries, we show that these operators commute to all orders in 1/N with asymptotic charges, thus resolving an apparent tension between locality in perturbative quantum gravity and the gravitational Gauss law. The interpretation of these observables is that they are not gravitationally dressed with respect to the boundary, but instead to features of the state. We also provide evidence that there are bulk observables whose commutator vanishes to all orders in 1/N with the entire algebra of single-trace operators defined in a space-like separated time-band. This implies that in a large N holographic CFT, the algebra generated by single-trace operators in a short-enough time-band has a non-trivial commutant when acting on states which break the symmetries. It also implies that information deep in the interior of the bulk is invisible to single-trace correlators in the time-band and hence that it is possible to localize information in perturbative quantum gravity.