The electronic and structural properties of a material are strongly determined by its symmetry. Changing the symmetry via a photoinduced phase transition offers new ways to manipulate material properties on ultrafast timescales. However, in order to identify when and how fast these phase transitions occur, methods that can probe the symmetry change in the time domain are required. We show that a time-dependent change in the coherent phonon spectrum can probe a change in symmetry of the lattice potential, thus providing an all-optical probe of structural transitions. We examine the photoinduced structural phase transition in VO2 and show that, above the phase transition threshold, photoexcitation completely changes the lattice potential on an ultrafast timescale. The loss of the equilibrium-phase phonon modes occurs promptly, indicating a non-thermal pathway for the photoinduced phase transition, where a strong perturbation to the lattice potential changes its symmetry before ionic rearrangement has occurred.