How Much Can Loops Replace Parameters? Sharp Storage–Computation Frontiers for Looped Neural Networks

Reusing neural modules across depth is common in recurrent networks, iterative refinement, and recurrent-depth language models, as it enables more computation without a proportional increase in parameter storage. Despite promising recent results, how the amount and timing of reuse jointly determine approximation accuracy remains largely open. We study multi-stage looped ReLU networks with $J$ stored modules and $T$ total calls. We first establish a sharp *storage–computation frontier*: for bounded unit-Lipschitz functions on $[0,1{]}^d$, the optimal worst-case uniform error is of order $(JT{)}^{-1/d}$ for fixed $d$ and every $1\le J\le T$, achieved by an explicit recurrent construction with $\tilde{O}(d^2)$ parameters per module, where $\tilde{O}$ hides logarithmic factors in $d$. Keeping the product $JT$ fixed allows fewer stored modules to be offset by proportionally more calls, preserving the approximation order. We then show that this frontier is sensitive to *loop allocation*—how calls are distributed and ordered across modules: even two schedules with identical per-module call counts can attain different rates. The optimal $(JT{)}^{-1/d}$ rate is achieved precisely when a constant fraction of the call budget remains after a constant fraction of the modules has been visited. In particular, both calling each module for an equal number of consecutive steps and repeatedly cycling through the modules meet this condition, whereas spending most calls before reaching later modules may not. Together, these results characterize how parameter sharing and call order shape approximation under exact arithmetic.