- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the execution efficiency of chain-of-thought and looped Transformers under a common computational model. It establishes mutual simulations with explicit overhead and a separation in sequential steps at linear total work. Its main result characterizes the optimal trade-off among work, workspace capacity, and per-row access-cost imbalance for parity, under an additional restriction on retained input-dependent state. Validation consists of a single-GPU study of parity constructions, illustrating how workspace size and access patterns affect source reads, call counts, and latency.
Critical strengths
-
The paper establishes the optimal trade-off between total work and loop calls for parity, with matching lower bounds and constructions that account for workspace size and access-cost imbalance.
-
The results offer insights into the organization of loop computations. A larger workspace does not necessarily improve resource efficiency, while concentrating expensive operations in fewer positions can change the work required to reduce call counts.
Critical weaknesses
-
The significance of the central resource trade-off for existing looped architectures is insufficiently established. Independently choosing workspace size and controlling the concentration of per-row access costs are central to the main result, but their connection to concrete architectural or execution choices in representative looped models remains unclear. A more explicit connection would help establish what these refinements teach us beyond the known benefits of parallel computation.
-
The strongest result has a narrow demonstrated scope. The matching frontier relies on a fixed finite alphabet for retained input-dependent data and is established for parity; the ordered-group extension covers the same-work comparison. The CUDA experiments illustrate the explicit constructions but provide limited evidence that the identified trade-offs extend to broader tasks or learned computations. Although these limitations are acknowledged, they leave the generality of the main insights insufficiently supported.
Questions for authors
Could the authors give a concrete example of how workspace capacity and row-cost imbalance correspond to design choices in a representative looped architecture? What does the analysis suggest choosing in that example, and what additional insight does it provide beyond the known benefits of parallel computation?
6 comments
Rebuttal (2/3)
W1. Connection to existing architectures and execution choices
Response. We have made the architectural connection explicit in Q1's latent-array example and added a learned-checkpoint control that implements the physical access choice. Together, these explain which design decisions the model represents and what the new experiments establish.
Concrete architectural and execution choices
In Q1's example, the allocated latent count determines how many positions execute on every call, while each row's source list determines its reading cost. The matching bounds show why these choices matter beyond parallelism: under the stated assumptions, filling the workspace can increase optimal work without improving the asymptotic call order, and allowing concentrated access costs can change that order.
We instantiate unequal source lists in small GPT-Neo adaptations on bAbI two-fact QA and a ProPara existence-event diagnostic (Appendix K.3, p. 45). Every eighth latent row reads all frozen-input and latent sources; the other rows read up to 16 centered input slots and their own latent. Packed execution scans each useful list at its own length; padded execution additionally reads masked dummy slots. This gives a concrete implementation of the access distinction in Q1.
What the controlled comparison establishes
Holding weights, ordered useful source lists, allocated rows, and calls fixed, packed execution reduced source-slot visits by 52–54.5% at batches 1 and 32. Logits were bitwise identical on the full validation splits and timed test inputs. Thus, physical execution can change the access cost while preserving the learned computation. The control does not establish that the chosen sparse routing policy is optimal.
Scope and design implication
The control uses one checkpoint per task at , one call after encoding; both missed their quality targets. Warmed single-GPU median latency changes of −2.87% to +0.11% are descriptive, without paired confidence intervals. Visits measure neither DRAM traffic nor complete work. The separate full/compact workspace comparisons also establish no matched-quality efficiency benefit (Appendix K.2, pp. 44–45).
The supported design implication is to evaluate workspace size and physical source-list execution independently. The theory establishes their effect on optimal resource costs within its model, and the control demonstrates an executable access choice. Although learning useful recurrent computations that realize these gains remains open, our cost model, matching bounds, and explicit constructions provide a foundation for investigating how training can achieve them.
Rebuttal (3/3)
W2. Scope of the frontier and transfer to learned computation
Response. We agree that the strongest frontier has a restricted scope. We clarify below which conclusions survive without the retained-state restriction, its role in the proof, and the evidence for learned computation.
Results that hold without the retained-state restriction
The following results permit full admitted numerical records while retaining the paper's common architectural and access assumptions:
| Result | Established scope |
|---|---|
| Same-work comparison | At linear work, parity requires linear CoT tokens versus logarithmic balanced-loop calls with sufficient capacity (Theorems 4–5, Corollary 6). |
| Unrestricted access-cost imbalance | For parity at linear work and capacity , the optimal call count is (Proposition 20, p. 31). Capacity need not be fully allocated. |
| Extension beyond parity | The balanced same-work comparison extends to ordered products, where input order matters (Proposition 23, p. 34). A group budget frontier is not established. |
Thus, both the compact-workspace benefit and the faster linear-work call order under unrestricted imbalance survive removal of the retained-state restriction. The finer matching frontier across intermediate budgets remains open for full numerical records.
Where the retained-state restriction enters the proof
The lower-bound proof translates executions into Boolean formulas whose depth and size are controlled by calls and charged accesses. The fixed alphabet bounds each row's retained labels, including controller fields, keeping this translation controlled across call boundaries. Parity formula lower bounds then yield the work–call constraint (Appendix E). Within-call arithmetic still uses the full admitted precision.
With full numerical retained states, the number of possible labels can grow with input length, so this argument no longer establishes the same sharp frontier. Whether that frontier extends remains open; we do not claim that it must differ (§6.1, p. 7; §8, p. 9).
Role and scope of the experiments
The paper's primary contribution is theoretical. The empirical study complements the analysis by checking explicit constructions, measuring their execution costs, and exploring whether the resource effects appear in learned models. Within the available computational resources, we focused on controlled construction studies and small learned-model diagnostics.
The padding control provides one concrete connection to learned computation. With weights, useful source lists, rows, and calls fixed, packed execution reduced source-slot visits by 52–54.5% on bAbI two-fact QA and a ProPara existence-event diagnostic. Logits were bitwise identical on the full validation splits and timed test inputs (Appendix K.3, p. 45). This supports the access mechanism in learned checkpoints. Both checkpoints used one call after encoding and missed their quality targets, and the broader learned comparisons did not establish an efficiency advantage at matched quality (Appendix K.2, pp. 44–45).
A foundation for broader theoretical and empirical study
We agree that broader theoretical guarantees and stronger evidence from learned tasks would strengthen the conclusions. The present work provides a common cost model, matching bounds under explicit assumptions, and executable constructions that make the effects of workspace and access choices precise. These results give subsequent studies concrete resource relationships to examine. Extending the guarantees to richer models and learning useful recurrent computations that realize the predicted trade-offs are natural next steps.
In the end, thank you again for your thoughtful feedback. We hope our responses address your concerns, and we would be happy to clarify any remaining points or discuss further questions.
Rebuttal (1/3)
Thank you for your thoughtful review and for recognizing the value of the matching trade-off. Your comments have helped us clarify its architectural implications and the scope of the experimental evidence. We address your questions and concerns below, with corresponding changes highlighted in red in the revised paper.
Response. The analysis separates two design choices: how many latent positions to update and which sources each position physically reads. Revised §§3.1–3.2 (pp. 4–5) and §5.2 (p. 7) now explain their architectural meaning and give concrete examples.
Architectural meaning of workspace and row costs
Consider a loop that retains an input representation and repeatedly updates a separate latent array. Perceiver illustrates this separation of input storage and latent positions (Jaegle et al., Figure 1). Every allocated latent position executes on every call; the input remains stored and charged even when the latent array is smaller.
This connection is architectural. Our quantitative guarantees apply to parity under the stated assumptions, including hard attention and certified indexed reads; they do not prescribe an optimal latent count for standard softmax Perceiver.
Choosing the workspace size
For parity in our model, at linear work and comparable row costs, Corollary 6 proves that choosing
m=Θ(min{Mrow,n/logn})minimizes calls up to constant factors. Once sufficient capacity is available, about n/logn rows suffice for logarithmic calls at linear work. Section 5.2 (p. 7) illustrates the choice at n=1,024 using a construction that loads the input and then combines partial answers pairwise:
The larger array saves four calls but performs substantially more row evaluations because every allocated row executes on every call. These construction counts illustrate the workspace trade-off; full work also charges setup, readout, accesses, and local operations, and neither count alone predicts latency.
Choosing the physical access layout
Section 3.2 (p. 5) considers four single-head rows scanning lists of lengths (16,1,1,1). Including one baseline unit per row gives charges (17,2,2,2), totaling 23, with maximum-to-mean ratio 68/23. Padding every list to length 16 makes the charges equal but raises their total to 68 without changing the useful computation.
This example motivates evaluating the physical source lists independently of workspace size. Removing padding can save accesses while preserving the call count; unequal attention weights alone do not save physical reads. The cap κ describes permitted cost concentration, not GPU utilization or a guaranteed latency improvement.
What the theory adds beyond parallelism
Theorem 5 identifies the best attainable costs across all algorithms allowed by the model. With comparable row costs, the optimal work for a loop with m=n rows is Θ(nlogn). About n/logn rows suffice for linear work, while both workspace choices achieve logarithmic calls. The additional work from allocating all n rows is therefore unavoidable under these assumptions, even when the algorithm is chosen optimally. These results allow full numerical records.
The finer frontier in §6 (pp. 7–8) explains when concentrating expensive accesses can reduce calls below logarithmic order. Under the additional fixed-alphabet retained-state condition and with sufficient capacity, our construction achieves Θ(logn/loglogn) calls at linear work. With a constant imbalance cap, no fixed polylogarithmic work overhead suffices to reach that call order. Achieving fewer calls requires organizing the reductions differently. Removing padding alone saves accesses while leaving the call count unchanged.