Stochastic tomography, made possible by dense deployments of seismic sensors, is used to identify previously undetected and poorly detected changes in the composition and mineral structure of Earth’s mantle. This technique inverts the spatial coherence of amplitudes and travel times of body waves to determine the depth and lateral dependence of the spatial spectrum of seismic velocity. The inverted spectrum is interpreted using predictions from the thermodynamic stability of different compositions and mineral phases as a function of temperature and pressure, in which the metamorphic temperature derivative of seismic velocities can be used as a proxy for the effects of heterogeneity induced in a region undergoing a phase change. Peaks in the metamorphic derivative of seismic velocity are found to closely match those found from applying stochastic tomography to elements of Earthscope and FLEX arrays. Within ± 12 km, peaks in the fluctuation of P velocity at 425, 500, and 600 km depth beneath the western US agree those predicted by a mechanical mixture of harzburgite and basalt in a cooler mantle transition zone. A smaller peak at 250 km depth may be associated with chemical heterogeneity induced by dehydration of subducted oceanic sediments, and a peak at 775 km depth with a phase change in subducted basalt. Non-detection of a predicted endothermic phase change near 660 km is consistent with its width being much less than 10 km. These interpretations of the heterogeneity spectrum are consistent with the known history of plate subduction beneath North America.