Characterizing Pauli Propagation via Operator Complexity

Pauli-propagation simulation represents observables in the Pauli basis and evolves their coefficients in the Heisenberg picture. Its efficiency depends on whether the evolving operator can be accurately compressed by retaining only a limited number of Pauli terms. In this work, we bridge operator complexity and the resource cost of Pauli-propagation methods by proving that the truncation error is governed by the Operator Stabilizer R\'enyi entropy (OSE) $\mathcal{S}^\alpha(O)$. Our a priori bounds quantify how OSE controls the compressibility of the evolving operator and give explicit prescriptions for the Top-$K$ budget required to achieve a target accuracy. As an analytic test case, we prove that for the 1D Heisenberg model at $J_z=0$, the number of non-zero Pauli coefficients generated from a local operator grows at most quadratically with the number of Trotter steps. We then benchmark the Top-$K$ Pauli propagation on XXZ Heisenberg chains. The numerical results show high accuracy with a small truncation number $K$ in the free regime ($J_z=0$) and competitive performance against tensor-network methods, such as TDVP, in the interacting case ($J_z=0.5$). These results position OSE as a resource measure for Pauli-propagation methods.