Dephasing representation of fidelity, also known as the phase averaging method, can be considered as a special case of Miller's linearized semiclassical initial value representation and belongs among the most efficient approximate semiclassical approaches for the calculation of ultrafast time-resolved electronic spectra. Recently it has been shown that the number of trajectories required for convergence of this method is independent of the system's dimensionality. Here we propose a further accelerated version of the dephasing representation in the spirit of Heller's cellular dynamics. The basic idea of the ‘cellular dephasing representation’ is to decompose the Wigner transform of the initial state into a phase space Gaussian basis and then evaluate the contribution of each Gaussian to the relevant correlation function approximately analytically, using numerically acquired information only along the trajectory of the Gaussian's centre. The approximate nature of the DR classifies it among semiclassical perturbation approximations proposed by Miller and Smith, and suggests its limited accuracy. Yet, the proposed method turns out to be sufficiently accurate whenever the interaction with the environment diminishes the importance of recurrences in the correlation functions of interest. Numerical tests on a collinear NCO molecule indicate that even results based on a single classical trajectory are in a remarkable agreement with the fully converged DR requiring approximately 104 trajectories.