Microstructure reconstruction is a key enabler of process-structure–property linkages, a central topic in materials engineering. Revisiting classical optimization-based reconstruction techniques, they are recognized as a powerful framework to reconstruct random heterogeneous media, especially due to their generality and controllability. The stochasticity of the available approaches is, however, identified as a performance bottleneck. In this work, reconstruction is approached as a differentiable optimization problem, where the error of a generic prescribed descriptor is minimized under consideration of its derivative. As an exemplary descriptor, a suitable differentiable version of spatial correlations is formulated, along with a multigrid scheme to ensure scalability. The applicability of differentiable optimization realized through this descriptor is demonstrated using a wide variety of heterogeneous media, achieving exact statistical equivalence with errors as low as 0% in a short time. We conclude that, while still in an early stage of development, this approach has the potential to significantly alleviate the computational effort currently associated with reconstructing general random heterogeneous media.