We emphasize the existence of stress-dependent microscopic heterogeneities in granular media and their influence on macroscopic property estimation using numerical simulations. Although numerical simulations based on contact mechanics successfully reproduce experimental stress-dependent acoustic response of granular media, most contact-mechanics-based effective medium theories (EMTs) fail. We have determined that the main reason for this discrepancy is an inadequate theoretical treatment of micro-heterogeneities in structure, force, and stress. Under infinitesimal perturbations used for estimating elastic moduli, microheterogeneities lead to displacements or relaxations — typically ignored in EMT. These infinitesimal granular relaxations are necessary to comply with detailed force balance, but do not involve grain slip and hence do not depend on friction. Furthermore, we have found that these relaxations primarily depend on the “amount” of heterogeneity, which to a first order are dependent on stress only and are independent of mineralogy. In the absence of an effective medium framework to estimate such relaxation corrections, we have provided simulation-based corrections to account for the impact of heterogeneity on elastic moduli calculations in EMT.