We propose a new physically based multifractal stress activation model of earthquake interaction and triggering based on two simple ingredients: (1) a seismic rupture results from activated processes giving an exponential dependence on the local stress and (2) the stress relaxation has a long memory. The combination of these two effects predicts in a rather general way that seismic decay rates after main shocks follow the Omori law ~1/tp with exponents p linearly increasing with the magnitude ML of the main shock. We carefully test the prediction on the magnitude dependence of p by a detailed analysis of earthquake sequences in the southern California earthquake catalog. We find power law relaxations of seismic sequences triggered by main shocks with exponents p increasing with the main shock magnitude by approximately 0.1--0.15 for each magnitude unit increase, from p(ML = 3) ≈ 0.6 to p(ML = 7) ≈ 1.1, in good agreement with the prediction of the multifractal model. The results are robust with respect to different time intervals, magnitude ranges, and declustering methods. When applied to synthetic catalogs generated by the epidemic-type aftershock sequence (ETAS) model constituting a strong null hypothesis with built-in magnitude-independent p values, our procedure recovers the correct magnitude-independent p values. Our analysis thus suggests that a new important fact of seismicity has been unearthed. We discuss alternative interpretations of the data and describe other predictions of the model.