Extended dynamical mean-field theory (EDMFT) is insufficient to describe non-local effects in strongly correlated systems, since corrections to the mean-field solution are generally large. We present an efficient scheme for the construction of diagrammatic extensions of EDMFT that avoids usual double counting problem by using an exact change of variables (the dual boson formalism) to distinguish the correlations included in the mean-field solution and those beyond. With a computational efficiency comparable to EDMFT+GW approach, our scheme significantly improves on the charge order transition phase boundary in the extended Hubbard model.