acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 stored modules and total calls. We first establish a sharp *storage–computation frontier*: for bounded unit-Lipschitz functions on , the optimal worst-case uniform error is of order for fixed and every , achieved by an explicit recurrent construction with parameters per module, where hides logarithmic factors in . Keeping the product 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 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.

Primary area:
learning theory
Keywords:
Looped Neural Network, Parameter Sharing, Universal Approximation Theory, Approximation Rate

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SRQ8OpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how repeated computation (looping) can substitute for stored parameters in looped ReLU networks. The model has J separately stored modules evaluated through T total calls (1 <= J <= T). Each module size depends only on the input dimension d, not on J, T or the target accuracy, and the call sequence is fixed independently of the input and the target. The target class is bounded unit-Lipschitz functions on [0,1]^d.

The paper makes in my understanding three contributions.

  1. Storage-computation frontier (Theorem 1). For multi-stage networks, where each module is called in one contiguous stage, the optimal worst-case error is of order (JT)^{-1/d}, with matching upper and lower bounds for every 1 <= J <= T. The product JT acts as the effective budget, so a network can store fewer modules if it makes proportionally more calls. This recovers results from previous works: the T^{-1/d} rate of a single repeated module (J = 1) and the T^{-2/d} rate of untied deep ReLU networks (J = T).

  2. Effect of call order (Theorem 2). For any prescribed call sequence, including returns to earlier modules, the error is bounded above and below by two quantities of the so-called "access curve," which counts the distinct modules reached by each call: its largest right-aligned rectangle H and its total area W. The frontier is retained if and only if a constant fraction of the calls remains after a constant fraction of the modules has been visited. Balanced grouped calls and repeated cycles both meet this condition. Two sequences with identical per-module call counts can still attain different rates.

  3. Extensions. The results extend to finite L^p error and to Holder targets. For bit-limited descriptions with I bits, extra calls stop helping once the available target information is used up.

The validation is purely theoretical. The appendix gives full proofs for results. There are no experiments. The authors state that the results concern best approximation under exact arithmetic and say nothing about trainability or how trained networks behave, or what happens under finite-precision execution.


I am not an expert in approximation theory for neural networks or in VC-dimension techniques. I read the paper carefully and could follow the main arguments and the proof sketches in Sections 4.1 and 5.1, but I did not check the appendix proofs in detail. Please weigh my assessment accordingly. Several of my comments below are questions, not firm criticisms. My poor knowledge of this literature also make difficult for me to assess if the results are really "new" and if the related work section covers correctly the field.

Critical strengths

Critrical strengths

  1. Sharp, matching bounds that unify known results. Theorem 1 gives upper and lower bounds of the same order for every combination of stored modules and calls. Both known endpoints are special cases: a single repeated module and fully untied deep ReLU networks. This weighs in my assessment because the common intuition that loops trade parameters for compute becomes a precise statement. In this model, the budget that matters is the product of the number of stored modules and the number of calls, so fewer modules can be compensated by proportionally more calls (at least under the assumptions they made).

  2. A simple, new criterion for call order. Theorem 2 shows that, once the number of modules and calls is fixed, the approximation rate depends on when each module is first reached. The authors capture this with the access curve and two area quantities. The frontier is retained if and only if a constant fraction of the calls remains after a constant fraction of the modules has been visited, which seems easy to check for a given sequence. The sigma_A vs sigma_B example shows that two sequences with identical per-module call counts can reach different rates. I find this the most original part of the paper. It relates to choices practitioners can make, such as grouped vs interleaved calls or where to place the loop.

The figures make both results accessible. They are of very good quality in the sense of transmitting their message. Figure 1 is very pedagogical and shows the model and its two “extreme” endpoints, and Figures 3 and 6 make the access curve and its area quantities intuitive. Is space allowed, i would have prefered to see figure 6 in the main text. As a non-expert, I found the paper much easier to follow because of them. My one reservation is that the colours are not colour-blind friendly. The legends and line styles partly compensate, but a colour-blind-safe palette would improve them further.

Critical weaknesses

I take here the time to restate that my points are more questions than real weaknesses. If i’m wrong in any sense, please take time to correct me.

  1. The frontier counts real-valued parameters, not stored information, and the paper does not make this visible enough. The upper-bound construction stores a long sequence of digits in a single real coefficient per block, and the repeated calls mostly read these digits out one at a time.

    Appendix D shows what happens when the weights can only be described with a finite number of bits. Extra calls stop helping once the available bits are used up, and to retain the frontier each module then needs a description that grows with the number of calls. If I read this correctly, loops can replace parameters but not stored information. This is consequential because the title asks how much loops can replace parameters, and a reader could take the answer to mean that computation substitutes for storage in a practical sense. I would like it stated in the introduction or right after Theorem 1. I see this mainly as a presentation issue, and it is the main reason my score is not higher.

  2. The results assume exact arithmetic with unrestricted coefficient magnitude and precision, and several fixed coefficients in the construction grow with the resolution. The authors say plainly that the bounds do not show that training can find such weights, or that they hold under finite-precision execution. There is also no experiment, even a toy one, to check whether the call-order effect has a counterpart in trained networks. This matters to me because the motivation draws heavily on practical architectures (recurrent-depth language models, grouped vs interleaved calls), and the call-order criterion is the part most likely to interest that audience. For now, its relevance to those architectures remains a hypothesis. For a theory paper I do not consider this disqualifying, which is why I still recommend acceptance, but a short toy experiments in the main could help to understand how practical/mature this theory already is.

Questions for authors
  • Clarification: How large do the coefficients in the Theorem 1 construction become as functions of J, T and d, and how many bits per module are needed to reach the (JT)^{-1/d} rate? If Appendix D implies that no construction with a T-independent bit budget per module can achieve the frontier, could you say so in the main text, for example right after Theorem 1?
  • Suggestion: Have you tried even a small experiment, such as training looped ReLU networks on a low-dimensional Lipschitz target under the sigma_A and sigma_B call orders, to see whether the predicted rate gap appears after training? A positive or negative result would help me judge how far the call-order criterion is relevant beyond best approximation.
12 comments
AuthorsOpenReview ↗

Response (Part 1)

We thank the reviewer for the time and effort devoted to reviewing our work. We appreciate the recognition that the joint frontier makes the parameter–computation tradeoff precise, and the positive assessment of the call-order criterion and the illustrations. We address the questions point by point below, with clearer statements of the storage and precision requirements and a new training comparison motivated by the reviewer’s suggestion.


C1

Weaknesses (W1): The frontier counts real-valued parameters, not stored information, and the paper does not make this visible enough. The upper-bound construction stores a long sequence of digits in a single real coefficient per block, and the repeated calls mostly read these digits out one at a time. [...] If I read this correctly, loops can replace parameters but not stored information. This is consequential because the title asks how much loops can replace parameters, and a reader could take the answer to mean that computation substitutes for storage in a practical sense. I would like it stated in the introduction or right after Theorem 1. I see this mainly as a presentation issue [...].

Response. We agree that fewer stored weights need not mean fewer stored bits, and that this distinction should be clear when introducing parameter storage. The title refers to parameter counts under the real-parameter, exact-arithmetic convention of quantitative ReLU approximation (Yarotsky 2018; Zhang et al. 2023).

  • What loops replace. Additional calls can compensate for fewer stored modules while preserving the best worst-case approximation order. Our encoding–decoding construction provides one way to attain this tradeoff. The matching lower bound shows that no other encoding or construction can improve the worst-case approximation order under the same module-size bounds, stored-module budget, and call budget.

  • What the submitted bit-budget result establishes. The reviewer's reading of Appendix D is correct. With II bits available to specify the target-dependent weights and a fixed module count JJ, extra calls improve the error order until JTJT reaches the scale of II. Beyond that point, the weight description limits the error order (Corollary 17, Eq. (38), p. 38). To attain the full frontier, the common bit cap for selecting each component's weights from its codebook must be at least of order TT (Theorem 18, Eq. (40), and Section D.2.4, p. 40).

  • What this means for actual storage. To quantify the storage cost, we additionally count the total budget SS for storing the full coefficient arrays. Under the specified encoding and exact evaluation, the best worst-case error is of order [1+min⁡(S,JT)]−1/d[1+\min(S,JT)]^{-1/d} for 1≤J≤T1\le J\le T and S≥CdJS\ge C_dJ (revised Appendix D.1.1, Proposition 19, p. 44). A storage budget of order JTJT bits is necessary and sufficient to attain the full frontier. At fixed JTJT, fewer modules and more calls preserve the approximation order, but also preserve the order of the required stored-bit budget.

We now explain the weight-count convention in the introduction (revised p. 1) and state the bit-storage result and per-component description requirement after Theorem 1 (revised pp. 5--6).

AuthorsOpenReview ↗

Response (Part 2)

C2

Weaknesses (W2): The results assume exact arithmetic with unrestricted coefficient magnitude and precision, and several fixed coefficients in the construction grow with the resolution. The authors say plainly that the bounds do not show that training can find such weights, or that they hold under finite-precision execution.

Question: How large do the coefficients in the Theorem 1 construction become as functions of J, T and d, and how many bits per module are needed to reach the (JT)−1/d(JT)^{-1/d} rate? If Appendix D implies that no construction with a T-independent bit budget per module can achieve the frontier, could you say so in the main text, for example right after Theorem 1?

Response. The coefficient bounds, storage requirements, and training question concern different aspects of the result. We address them separately below.

  • Best approximation and training. Our construction proves that networks attaining the upper bound exist. The matching lower bound establishes the optimal approximation order within the admissible class. Whether training finds comparably accurate networks is a separate question, which motivates the paired experiment in C3.

  • Coefficient magnitude. After normalization and layer assembly, all coefficients are rational and have magnitude at most Cd(T+2)adC_d(T+2)^{a_d} for every 1≤J≤T1\le J\le T, with CdC_d and ada_d depending only on dd. For example, the slope used to select a coarse block before normalization is bounded by 4(2d+1)(JT)1/d4(2d+1)(JT)^{1/d} (revised Appendix B.2.3, Proposition 7).

  • Bits to store a module.

    • Sufficient bits for our construction. Within each module, the target-independent coefficients require Od(log⁡(T+2))O_d(\log(T+2)) bits in total, while the target-dependent codes require Od(T)O_d(T) bits. Thus our exact encoding stores the complete module using Od(T)O_d(T) bits (revised Appendix B.2.3, Proposition 7).

    • A necessary condition for any construction. If a common cap of ℓ\ell bits selects the weights of each module and end map from a fixed codebook, the entire network has at most (J+2)ℓ(J+2)\ell bits of target information. Attaining the frontier requires Ωd(JT)\Omega_d(JT) bits, so the common cap must be Ωd(T)\Omega_d(T). Consequently, no construction under a TT-independent common cap can retain the frontier as TT grows (submitted Appendix D.2).

  • Precision during evaluation. The exact-arithmetic construction can also be evaluated with rounding if the precision grows with the call budget. Storing the coefficients accurately is not sufficient by itself: rounding errors must also be controlled as the state passes through repeated calls. Under the specified fixed-point or binary floating-point rules, with state projection after initialization and each module call, Od(T)O_d(T) bits per scalar suffice to preserve the construction’s (JT)−1/d(JT)^{-1/d} approximation order (revised Appendix D.4, Proposition 23).

The revision states the necessary growth of the per-component bit budget immediately after Theorem 1 (pp. 5–6). Appendix B.2.3 gives the coefficient and storage bounds, and Appendix D.4 establishes the rounded execution guarantee. The paired training comparison is reported in Appendix E and discussed in C3 below.

AuthorsOpenReview ↗

Response (Part 3)

C3

Weaknesses (W2): There is also no experiment, even a toy one, to check whether the call-order effect has a counterpart in trained networks. This matters to me because the motivation draws heavily on practical architectures (recurrent-depth language models, grouped vs interleaved calls), and the call-order criterion is the part most likely to interest that audience. For now, its relevance to those architectures remains a hypothesis.

Question: Have you tried even a small experiment, such as training looped ReLU networks on a low-dimensional Lipschitz target under the sigma_A and sigma_B call orders, to see whether the predicted rate gap appears after training? A positive or negative result would help me judge how far the call-order criterion is relevant beyond best approximation.

Response. To examine whether the call-order effect also appears in trained networks, we added a paired experiment (revised Appendix E, pp. 49–50). Across all six settings, σB\sigma_B (earlier-access order) had lower mean test-grid errors, which is consistent with the direction of Theorem 2’s comparison.

  • We trained both orders on the same data with identical initial weights, parameter counts, and per-module call counts. The extra calls to G1G_1 occur before visiting the other modules in σA\sigma_A and after in σB\sigma_B. We used three budgets each in 2D and 3D with Lipschitz targets built from 100 localized pyramids with random signed heights. We calibrated the scale of the 2D targets using the test function in Zhang et al. (2023, sec. 4.1).

  • The table reports mean errors over three targets and five training seeds per target, in units of 10−310^{-3}. Bold indicates the lower mean within each pair of call orders. Maximum error is computed per fit and then averaged.

dd(J,T)(J,T)Train RMSE σA\sigma_ATrain RMSE σB\sigma_BTrain Max. error σA\sigma_ATrain Max. error σB\sigma_BTest RMSE σA\sigma_ATest RMSE σB\sigma_BTest Max. error σA\sigma_ATest Max. error σB\sigma_B
2(4,16)(4,16)6.5676.17533.96530.3486.7876.41338.61234.762
2(5,25)(5,25)6.1445.46132.34128.7336.4305.77336.76133.427
2(6,36)(6,36)5.6775.13129.05127.1755.9825.47534.57932.578
3(4,16)(4,16)5.9625.48930.52629.9247.0906.61944.00543.332
3(5,25)(5,25)5.4404.96130.62728.2476.7436.22543.14040.762
3(6,36)(6,36)5.3364.97330.32529.2176.7056.23842.95641.729

Across the six settings, σB\sigma_B reduced mean test-grid RMSE by 5.5–10.2% and mean test-grid maximum absolute error by 1.5–10.0%. The lower mean errors for the earlier-access order are consistent with the direction of Theorem 2’s comparison.

The code and saved results are available in the anonymous repository.


C4

Suggestions in Critical Strengths: Is space allowed, i would have prefered to see figure 6 in the main text. [...] My one reservation is that the colours are not colour-blind friendly. The legends and line styles partly compensate, but a colour-blind-safe palette would improve them further.

Response. We moved the two panels from the submitted Figure 6 that compare orders with identical per-module call counts into the main text, next to the example they illustrate (revised Figure 4, p. 9). The complete four-panel comparison, including grouped and cyclic calls, remains in Appendix C.3 (revised Figure 7, p. 38).

We replaced the blue–teal shading with blue and rose in the access-curve figures. The rectangle for HH is hatched and labeled, and WW is identified as the full area under the curve. These cues keep the two quantities distinguishable in grayscale.


References

  • D. Yarotsky. (2018). Optimal Approximation of Continuous Functions by Very Deep ReLU Networks. COLT.
  • S. Zhang, J. Lu, and H. Zhao. (2023). On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network. ICML.
Reviewer_Epi1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies an important topic area, namely how parameter sharing impacts approximation accuracy of a neural model, especially, when we are permitted to make space-time tradeoffs, in which we can trade some additional computation in favor of reduced storage but without hurting the approximation accuracy that much. In particular, the paper focuses on uniform approximation of bounded Lipschitz functions on a d-dimensional box using J ReLU modules and at most T calls. The paper establishes matching upper and lower bounds of order (JT)−1/d(JT)^{-1/d}. Another result in the paper allows the set of available modules to change from call to call, and provides a more refined bound. The proofs seem correct (though I did not check super carefully).

Critical strengths
  • Matching upper and lower bounds (for the first main result)
  • Clean work, and the paper is honest about its limits
  • The O(d^2 log d) parameters needed per module seems reasonable (from a theoretical perspective)
Critical weaknesses
  • Novelty might be lesser than what is claimed; the endpoint results are known, but more importantly not clear to me how much of a heavy lift on top of the cited Zhang (2026) work the current paper is, because having a joint (JT) interpolation result is to be expected, but it is not quite clear why it is "challenging" -- conditioned on the existing literature
Questions for authors
  • The complexity description and messaging is slightly unclean because when one talks about loops replacing parameters, I'd expect loops to be replacing literally parameters, but digging deeper it seems one has to worry about "T" bits, so that a total of JT bits are split between storage and calls? Could the authors explain this a bit better? (The bitwise count is not unsurprising, and it seems previous works have also gone that route, but then at that point, one could ask whether the joint JT result is truly different from just the usual result by more carefully viewing everything in terms of "total bits" from the start, instead of making a storage-compute dichotomy?
  • For schedules with first visits \approx T-T/j, H=T, but W = T log J. Which rate is correct here? Also, how would first-access timing matter for looped transformers?
5 comments
AuthorsOpenReview ↗

Response (Part 1)

We thank the reviewer for the time and effort devoted to reviewing our work, and for highlighting the importance of the storage–computation question, the matching bounds, and the reasonable per-module complexity. The questions about prior work and bit complexity help us explain more precisely what the module-and-call constraints add. We address these concerns and the questions about call sequences and Transformers point by point below.


C1

Weaknesses: Novelty might be lesser than what is claimed; the endpoint results are known, but more importantly not clear to me how much of a heavy lift on top of the cited Zhang (2026) work the current paper is, because having a joint (JT) interpolation result is to be expected, but it is not quite clear why it is "challenging" -- conditioned on the existing literature

Response. We agree that the endpoint rates are known (Zhang et al. 2023; Yarotsky 2018). Concurrent affine-latent theory also gives an analogous joint rate (Zhang 2026, Corollary 3.2 and Theorem 3.3). For networks that reuse modules across depth, the question is how far additional computation can compensate for fewer stored parameters under fixed module-size constraints. We establish the sharp tradeoff for this architecture with small reusable modules and determine how the arrangement of calls affects whether it is attained.

  • Attaining the frontier with small reusable modules. Zhang's construction already provides a target-independent prefix decoder (Zhang 2026, Lemma 4.6). In our setting, the same TT calls must select and load the relevant block code and then decode it, while retaining uniform accuracy near grid boundaries.

    • The explicit affine-latent construction. Boundary correction uses 3d3^d shifted copies, yielding a feedforward width bound of O(d3d)O(d3^d) (Zhang 2026, Eq. (7) and Lemma 4.10).

    • Our module construction. Sharing coordinate computations across shifted grids attains the (JT)−1/d(JT)^{-1/d} rate with width O(d)O(d) and O~(d2)\widetilde O(d^2) parameters per module (Section 4.1 and Appendix B.2).

  • Determining which call orders retain the frontier. The joint budget rate alone does not determine whether a particular call sequence attains it. Zhang’s affine-latent result gives the best rate over admissible architectures and affine maps (Zhang 2026, Eq. (12)). Unrolling a prescribed sequence gives affine weight tying, with every deployed copy counted, but fixes a particular sharing pattern. Theorem 2 determines when such a sequence retains the frontier. A sequence retains the joint rate precisely when a constant fraction of the calls remains after a constant fraction of the modules has been reached. Our example shows that changing this timing can change the approximation rate even when every module is called the same number of times in both sequences (Appendix C.3).

The submission compares the two models in Section 2 and Table 1. Revised Section 2 compares the widths of the two explicit constructions, and Appendix A.5 details the parameter cost of unrolling.

AuthorsOpenReview ↗

Response (Part 2)

C2

Question: The complexity description and messaging is slightly unclean because when one talks about loops replacing parameters, I'd expect loops to be replacing literally parameters, but digging deeper it seems one has to worry about "T" bits, so that a total of JT bits are split between storage and calls? Could the authors explain this a bit better? (The bitwise count is not unsurprising, and it seems previous works have also gone that route, but then at that point, one could ask whether the joint JT result is truly different from just the usual result by more carefully viewing everything in terms of "total bits" from the start, instead of making a storage-compute dichotomy?

Response. The bits are not split between storage and calls: they specify the stored weights, while calls provide computation. Counting total bits captures the information constraint, but does not remove the separate limits imposed by the module and call budgets. We explain below where the TT-bit scale comes from and why the same total storage budget can still give different approximation rates.

  • Where the TT-bit scale comes from. The full (JT)−1/d(JT)^{-1/d} frontier requires Ωd(JT)\Omega_d(JT) bits of target description (submitted Appendix D.1, Corollary 17). If the same cap of ℓ\ell bits applies to each of the JJ modules and two end maps, the total is at most (J+2)ℓ(J+2)\ell. The common cap therefore has to be at least of order TT (Appendix D.2).

  • From target description to total storage. As the reviewer notes, prior work has studied approximation under bit budgets (Yarotsky and Zhevnerchuk 2020; Gühring and Raslan 2021). The submitted Appendix D.1 counts the II bits used to specify the target-dependent weight assignment and gives error of order [1+min⁡(I,JT)]−1/d[1+\min(I,JT)]^{-1/d} under exact evaluation (Eq. (38), p. 38). To address the reviewer's question about total storage, we now also count the SS bits used to store the full coefficient arrays, including fixed entries, both end maps, and separately stored copies.

  • Why JJ and TT still matter at fixed total storage. Under the specified encoding and exact evaluation, the best worst-case error is of order [1+min⁡(S,JT)]−1/d[1+\min(S,JT)]^{-1/d} for S≥CdJS\ge C_dJ (revised Appendix D.1.1, Proposition 19). For example, fix TT and give both networks the same storage budget SS, chosen as a sufficiently large multiple of T2T^2. One shared module gives error of order T−1/dT^{-1/d}, while TT separately stored modules called once each give T−2/dT^{-2/d}.

The revised discussion after Theorem 1 defines both bit budgets and explains why the same total storage budget can give different error rates.


C3

Question: For schedules with first visits ≈T−T/j\approx T-T/j, H=T, but W = T log J. Which rate is correct here?

Response. For the sequence raised by the reviewer, the correct error order is (Tlog⁡J)−1/d(T\log J)^{-1/d}.

The submitted Theorem 2 gives lower and upper bounds of orders W−1/dW^{-1/d} and H−1/dH^{-1/d}. For the reviewer’s sequence, module jj is first reached with Rj=⌊T/j⌋R_j=\lfloor T/j\rfloor calls remaining. As the reviewer notes, this gives H=max⁡jjRj=TH=\max_j jR_j=T and W=∑jRj≍Tlog⁡JW=\sum_jR_j\asymp T\log J, so the submitted bounds differ in scale by (log⁡J)1/d(\log J)^{1/d}.

  • Why the submitted bounds leave a gap. This gap arises because the submitted construction starts a single shared decoding window only after the last selected code is loaded. With the first jj modules selected, this leaves at most RjR_j calls for each of their jj blocks, so the best such product is HH. Codes loaded early may therefore wait many calls before decoding begins. Starting to decode those blocks during the wait gives them more time and offers a way to close the gap.

  • A matching upper bound. Following this idea, we obtain a matching Od(W−1/d)O_d(W^{-1/d}) upper bound. We group modules by the calls remaining at their first visit. Each group shares a decoding window because an input needs only one block per shifted grid. Longer windows let earlier modules cover larger blocks at the same resolution, giving order WW fine cells in total. Revised Appendix C.5 (pp. 40–43) proves the bound for every prescribed sequence under exact evaluation with the original module-size bounds.

The main text retains the original proof sketch, which uses the decoder (with a single shared decoding window) from Theorem 1 and illustrates directly why that construction is controlled by HH. Appendix C.5 gives the sharper W−1/dW^{-1/d} result and its multi-window construction. We plan to integrate the strengthened theorem into the main exposition in the final version.

AuthorsOpenReview ↗

Response (Part 3)

C4

Question: how would first-access timing matter for looped transformers?

Response. In our ReLU model, reaching a module earlier leaves more calls to use the information it contributes. For looped Transformers, this suggests asking how many loops remain once the hidden state contains the context needed for the task.

  • With a single shared block, the weights are available from the first call, and the context can take several loops to form. For example, one approximation construction uses repeated attention updates to form context-dependent token identifiers, which subsequent loops map to output embeddings (Xu and Sato 2025, sec. 3.4).

  • With several shared blocks, the call order can also change when each block first contributes to the state. Empirical comparisons of middle and full-stack looping find performance differences at matched parameter and FLOP budgets (Saunshi et al. 2025, arXiv v1, Section 3.3 and Table 3). A comparison of interleaved and grouped calls to two shared layers also finds that the order affects language-model performance (Csordás et al. 2024, sec. 3 and Figure 6).

A theoretical counterpart to Theorem 2 for looped Transformers would need to characterize how attention and block order determine when task-relevant context becomes available and how the remaining loops affect the best attainable approximation error. We leave this architecture-specific extension to future work (revised Section 7, p. 10).


References

  • R. Csordás, K. Irie, J. Schmidhuber, C. Potts, and C. D. Manning. (2024). MoEUT: Mixture-of-Experts Universal Transformers. NeurIPS.
  • I. Gühring and M. Raslan. (2021). Approximation Rates for Neural Networks with Encodable Weights in Smoothness Spaces. Neural Networks, 134, 107–130.
  • N. Saunshi, N. Dikkala, Z. Li, S. Kumar, and S. J. Reddi. (2025). Reasoning with Latent Thoughts: On the Power of Looped Transformers. ICLR.
  • K. Xu and I. Sato. (2025). On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding. ICML.
  • D. Yarotsky. (2018). Optimal Approximation of Continuous Functions by Very Deep ReLU Networks. COLT.
  • D. Yarotsky and A. Zhevnerchuk. (2020). The Phase Diagram of Approximation Rates for Deep Neural Networks. NeurIPS.
  • S. Zhang. (2026). Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations. arXiv:2608.31157.
  • S. Zhang, J. Lu, and H. Zhao. (2023). On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network. ICML.
Reviewer_ycx8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addressed the advantage of loops in the context of approximation theory of Lipschitz functions by deep ReLU neural networks. The loops are represented by repeated blocks of layer modules. The paper keeps track of the total number of blocks and the number of distinct blocks, and derives upper and lower bounds on the approximation error. There are two main results. The first (Theorems 1) examines the setting of consecutive repetition of each block and derives matching upper and lower error bounds. The second (Theorem 2) relaxes the setting, allowing arbitrary nonconsecutive positions of different blocks. In this case different upper and lower bounds are obtained, involving two geometric characteristics of the block distribution. It is then discusses when the bounds are sharp and which distributions produce better approximations. In particular, a simple example is given in which changing the order of blocks provably degrades the approximation rate.

Critical strengths

High readability

The paper is quite easy to read. The setting and the addressed question (advantage of loops) are clearly explained. The obtained results answer the addressed question. The statements of the theorems are clear. The theorems are provided with sketches of proof in the main text and with detailed proofs in the appendix. I didn't study the appendix, but it seems well-organized and to contain all relevant details. There are several helpful illustrations and explanations on simple examples. The prior work is properly cited and a fair comparison is provided.

Interesting contributions

While the overall topic of approximation of Lipschitz functions by deep ReLU networks is already well-explored, the particular question addressed by the paper (the advantage of loops or, more generally, repeated blocks, for the approximation accuracy) and the specific associated mathematical settings proposed in the paper seem new, especially the setting of Theorem 2 in which an arbitrary order of blocks is analyzed. The characterization of convergence rates in terms of simple geometric quantities WW and HH is convenient and interesting. While the overall idea that it is beneficial to have variable weights early in the network is known, the general quantitative result provided by Theorem 2 looks new. The simple specific example following Theorem 2 in which changing the order of blocks provably degrades approximation rates is interesting and probably will be useful in future research.

Critical weaknesses

Lack of clarity regarding indefinite weight/computation precision

As far as I understand, the paper treats network weights as reals of unlimited precision, and this is essential for the established results, as some of the contructions require the weights to contain large amounts of information. This obviously limits the immediate practical relevance of the results, and this point does not seem to be sufficiently well discussed. While there are some comments in Discussion, and Appendix D is all about that, I think the paper should be more clear about that, especially in the begining. When speaking about "parameter storage", it should be made clear that it is understood in terms of the number of weights, not the total number of occupied bits, and these two metrics are very different in the present context.

Questions for authors

Theorem 2 shows that higher accuracy requires to have many different modules early in the network (and quantifies this conclusion). Does this conclusion remain valid with respect to the associated information rather than just the number of modules, and/or if we work in a fixed-precision arithmetic?

4 comments
AuthorsOpenReview ↗

Response (Part 1)

We thank the reviewer for the time and effort devoted to reviewing our work. We appreciate the recognition of the clear presentation and the novelty of the arbitrary-call-order analysis, including the potential value of the same-count example. We respond point by point below, clarifying the storage convention and extending the analysis to information budgets and rounded execution.


C1

Weaknesses: Lack of clarity regarding indefinite weight/computation precision. As far as I understand, the paper treats network weights as reals of unlimited precision, and this is essential for the established results, as some of the contructions require the weights to contain large amounts of information. This obviously limits the immediate practical relevance of the results, and this point does not seem to be sufficiently well discussed. [...] When speaking about "parameter storage", it should be made clear that it is understood in terms of the number of weights, not the total number of occupied bits, and these two metrics are very different in the present context.

Response. We agree that parameter counts and occupied bits must be distinguished when introducing parameter storage. The main results count real-valued weights under exact evaluation, following the convention of quantitative ReLU approximation (Yarotsky 2018; Zhang et al. 2023). Below, we clarify what this tradeoff establishes and what realizing it requires in bits.

  • What the parameter-count frontier establishes. Theorem 1 quantifies how far additional calls can compensate for fewer stored parameters under fixed module-size constraints. Our encoding–decoding construction provides one way to attain this tradeoff. In this construction, fewer weights carry longer codes, which take more calls to decode. The matching lower bound shows that no other encoding or construction can improve the worst-case approximation order under the same module-size bounds, stored-module budget, and call budget.

  • Target-description bits: the submitted result. The submission already quantifies the information needed for this tradeoff. If II bits select the complete target-dependent parameter assignment through a fixed rule, the best worst-case error under exact evaluation is of order [1+min⁡(I,JT)]−1/d[1+\min(I,JT)]^{-1/d} for JJ stored modules and TT calls (Appendix D.1, Corollary 17, Eq. (38), p. 38). Thus attaining the (JT)−1/d(JT)^{-1/d} frontier requires Ωd(JT)\Omega_d(JT) bits of target description, and a fixed II eventually limits the benefit of extra calls.

  • Stored coefficient bits: the additional analysis. To address the reviewer's concern about actual storage cost, we now also count the SS bits used to store the full coefficient arrays, including fixed entries, the input and output maps, and separately stored copies. Under the specified encoding and exact evaluation, the best worst-case error is of order [1+min⁡(S,JT)]−1/d[1+\min(S,JT)]^{-1/d} for 1≤J≤T1\le J\le T and S≥CdJS\ge C_dJ (revised Appendix D.1.1, Proposition 19). A stored-bit budget of order JTJT is therefore necessary and sufficient to attain the frontier. Trading fewer modules for more calls at fixed JTJT preserves the approximation order, but does not reduce the order of the required bit storage.

To make these distinctions clear from the outset, we now state the parameter-count convention in the introduction and model definition (revised pp. 1 and 4), and explain both bit budgets immediately after Theorem 1 (revised pp. 5--6).

AuthorsOpenReview ↗

Response (Part 2)

C2

Question: Theorem 2 shows that higher accuracy requires to have many different modules early in the network (and quantifies this conclusion). Does this conclusion remain valid with respect to the associated information rather than just the number of modules, and/or if we work in a fixed-precision arithmetic?

Response. Under exact evaluation, the first-visit criterion extends to unequal module bit budgets. In the rounded model, fixed precision limits the attainable rate, and increasing precision can preserve the constructive upper bound.

  • Information and first access. Theorem 2 allows target-specific weights under the prescribed sequence, so the distribution of target information across modules is part of the best-approximation problem.

    • When the frontier is attainable. Under exact evaluation, when the modules carry all target-dependent information, suitably chosen fixed codebooks attain the full (JT)−1/d(JT)^{-1/d} frontier precisely when a fixed fraction of the modules each have a bit budget of at least a constant multiple of TT and are first reached with at least a fixed fraction of the calls remaining (revised Appendix D.3, Proposition 21).

    • Why the distribution matters. A module's contribution is limited by both its bit budget and the calls remaining after its first visit. Even if a total of order JTJT bits is concentrated in k=o(J)k=o(J) early modules (meaning k/J→0k/J\to0 as JJ grows), their combined contribution is at most kT=o(JT)kT=o(JT), which falls short of the full frontier.

  • Precision during execution. The information analysis above assumes exact evaluation. Under rounded execution, the answer depends on how precision scales with TT.

    • Fixed precision. If all target-dependent choices are encoded in the Od(J)O_d(J) stored coefficients and each coefficient has a fixed bit length, the target description has at most Od(J)O_d(J) bits. Reaching the full frontier requires order JTJT bits, so every sequence falls short as TT grows. This counting bound applies uniformly across sequences (revised Appendix D.4, Eq. (45)); it does not compare their relative performance under rounding.

    • Precision growing with TT. With the specified fixed-point or binary floating-point rounding and state projection after initialization and each call, Od(T)O_d(T) bits per scalar suffice to preserve the constructive upper bound Od(H(σ)−1/d)O_d(H(\sigma)^{-1/d}). Here H(σ)H(\sigma) is the largest product of the number of modules reached and the remaining calls, including the current call (revised Appendix D.4, Proposition 23). A matching lower bound based on first visits under rounded evaluation remains open.

We now discuss unequal bit budgets alongside the first-visit criterion in revised Section 5 and explain the implications for rounded evaluation in revised Section 7.


References

  • D. Yarotsky. (2018). Optimal Approximation of Continuous Functions by Very Deep ReLU Networks. COLT.
  • S. Zhang, J. Lu, and H. Zhao. (2023). On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network. ICML.
AuthorsOpenReview ↗

Official Comment by Authors

We hope our rebuttal and the revisions to the manuscript have helped address your concerns. With the discussion period nearing its end, we would appreciate any additional comments or questions you may have. Thank you very much for your time and valuable feedback.

I thank the authors for answering my question and addressing my concerns. I maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.