acceptodds
Under review as a conference paper at ICLR 2027

Test-Time Compute in Chain-of-Thought and Looped Transformers: Simulation and Resource Trade-offs

Abstract

Increasing test-time compute can improve the reasoning capabilities of large language models. Two prominent approaches are chain-of-thought (CoT), which generates intermediate tokens, and looped Transformers, which repeatedly update a latent workspace. We theoretically compare their execution efficiency at fixed correctness, allowing each architecture to choose its own algorithm. Our main contribution is a matching work–call trade-off for parity that accounts for workspace capacity and the concentration of access costs across rows. In a finite-precision hard-attention/ReLU model with a fixed finite alphabet for retained data, we show that, with sufficient workspace, polylogarithmic work overhead is insufficient to attain the fastest call order under balanced row costs. Concentrating costly reductions in fewer rows can attain this order at linear work. Work includes all evaluated rows, and the lower bound applies to all algorithms in the stated class. Supporting results establish mutual simulation of finite deterministic computations with explicit overhead and a linear-work separation allowing full admitted numerical states: CoT requires linearly many tokens, whereas a compact loop needs logarithmically many calls. A single-GPU study of the explicit constructions illustrates that reducing source reads does not necessarily reduce latency, with the outcome depending on batch size. Learned reasoning quality is outside the scope of this comparison.

Primary area:
learning theory
Keywords:
CoT, Loop Transformer, Theoretical Comparison, Test-time Compute

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FUwLOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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.

Q1. Architectural meaning, design choices, and insight beyond parallelism

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.

Design choiceModel quantity
Number of latent positions updated on every callAllocated workspace m≤Mrowm\le M_{\rm row}; available capacity need not be filled
Source lists and how they are executedPer-row access charge, including physically read padding
Allowed concentration of access costs across rowsCap κ\kappa on the maximum-to-mean row-charge ratio at each stage

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/log⁡n})m=\Theta\!\left(\min\{M_{\rm row},n/\log n\}\right)

minimizes calls up to constant factors. Once sufficient capacity is available, about n/log⁡nn/\log n rows suffice for logarithmic calls at linear work. Section 5.2 (p. 7) illustrates the choice at n=1,024n=1{,}024 using a construction that loads the input and then combines partial answers pairwise:

Latent rowsCalls: loading + reductionLoading/reduction row evaluations
1281288+7=158+7=15128×15=1,920128\times15=1{,}920
1,0241{,}0241+10=111+10=111,024×11=11,2641{,}024\times11=11{,}264

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)(16,1,1,1). Including one baseline unit per row gives charges (17,2,2,2)(17,2,2,2), totaling 23, with maximum-to-mean ratio 68/2368/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 κ\kappa 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=nm=n rows is Θ(nlog⁡n)\Theta(n\log n). About n/log⁡nn/\log n rows suffice for linear work, while both workspace choices achieve logarithmic calls. The additional work from allocating all nn 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 Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) 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.

AuthorsOpenReview ↗

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 h=1h=1, 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.

AuthorsOpenReview ↗

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:

ResultEstablished scope
Same-work comparisonAt linear work, parity requires linear CoT tokens versus logarithmic balanced-loop calls with sufficient capacity (Theorems 4–5, Corollary 6).
Unrestricted access-cost imbalanceFor parity at linear work and capacity Mrow=nM_{\rm row}=n, the optimal call count is Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) (Proposition 20, p. 31). Capacity need not be fully allocated.
Extension beyond parityThe balanced same-work comparison extends to ordered S5S_5 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.

Reviewer_2hA8OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The authors study the cost of CoT and looped transformers on the parity task. They define a model of looped transformers and CoT that counts computational cost in terms of the number of accesses to the input as well as the number of operations performed. They show that CoT and looped transformers, under their model, can mutually simulate each other. On the parity task, they show that CoT requires linearly many CoT steps and Θ(n+mlog⁡n)\Theta(n + m\log n) total work for a looped transformer that has mm mutable positions. They extend their parity analysis to account for how imbalanced the distribution of looped transformer work is across positions, which they show influences the number of loop steps. They implement their parity algorithms on a GPU to test how their loop vs CoT analysis manifests in latency.

Critical strengths
  1. The paper takes a granular approach to comparing the cost of CoT and looped transformers. This has the potential to be an interesting research contribution. Unfortunately the issues below make it difficult to evaluate the merit of this contribution.
Critical weaknesses
  1. Undefined notation and jargon make the technical contributions extremely difficult for a reader to understand. This severely limits the current utility of the paper, as the purpose of a paper is to effectively communicate its findings. The paper needs a thorough rewrite with careful attention to clarity and human-readability.
  2. The modeling choices of the paper are very strange and not motivated. It's not clear why the number of "mutable rows" in the looped transformer is limited to m≤nm \le n, where the "row costs" come from, or why a cap κ\kappa is placed on the imbalance of row costs. As a result, it's not clear what we learn about CoT or looped transformers in practice.
Questions for authors
  1. What is the motivation for the model of costs and work? Why does balance matter? What does it correspond to in real models? Why should there be different access costs across rows?
  2. What does theorem 3 provide over known results from Saunshi et al. 2025 and Xu and Sato 2026?
  3. That does theorem 4 provide over the known Ω(n)\Omega(n) CoT lower bound of Amiri et al 2025?
  4. The modeling choice of mm mutable rows is very strange; a real looped transformer updates every position at every round. Shouldn't we have m=nm=n always?
  5. What is a "visit" in the experiment and why does it matter?
7 comments
AuthorsOpenReview ↗

Rebuttal (1/3)

Thank you for your careful review and detailed questions. We apologize that our original presentation did not make the motivation and modeling choices sufficiently clear. Your feedback has helped us improve these explanations and the presentation of our results. We address related concerns together below, with corresponding revisions highlighted in red in the revised paper.

Motivated by growing interest in looped Transformers, our main objective is to address an open question: how do looped Transformers compare with CoT in the fewest sequential steps needed to solve the same task under a common work budget and correctness requirement? We allow each architecture to choose its own algorithm and establish matching bounds under our stated computational assumptions. For parity, these bounds show when additional workspace increases work without improving the asymptotic call count and when concentrating source accesses in fewer rows reduces that count.

Q1/Q4/W2: Motivation, workspace, and access costs

Response. The model studies two related design choices: how many recurrent positions to allocate and how much source reading each position performs. We explain why both choices matter when comparing CoT and loops under a common work budget.

1. The problem we study. We ask how few sequential steps CoT and looped Transformers need to solve the same task at the same correctness level under a common total-work budget. Each architecture may choose its own algorithm. We study parity as a concrete task for which matching lower bounds and constructions let us characterize how workspace and access patterns affect this optimum.

2. What the workspace represents and why it incurs work. A CoT step evaluates one new position; a loop call updates every allocated recurrent position. Here nn is the input length and mm is the number of recurrent positions. A full-sequence loop has m=nm=n and is included. A model can also store its input separately and repeatedly update a smaller latent array that reads from that representation. All mm rows still execute on every call. Figure 1 in [1] illustrates this separation between input size and latent workspace, although our hard-attention guarantees do not transfer to its standard softmax implementation.

The range 1≤m≤n1\le m\le n covers workspaces from one recurrent position to one per input position. It defines the analyzed regime; the interface permits larger workspaces as well. Because reducing calls can increase the work performed in each call, our accounting charges all evaluated rows and source accesses. Input encoding, frozen-input storage and reads, routing, source-list construction, and final readout remain charged.

3. Why row costs differ and balance matters. A certified indexed read visits one source; a scan processes every executed slot, including padding. Scanning the same dense source array gives rows equal access charges. Executing source lists of different lengths allows unequal charges even when every row applies the same shared block. Padding those lists to a common length equalizes the charges but adds reads without adding information.

The cap κ\kappa bounds the largest row access charge relative to the stage mean. With a small cap, an expensive scan in one row requires a comparable average charge across the array; a larger cap permits a few expensive scans alongside many cheap updates. We vary this constraint to determine how concentrating access costs changes the work needed to reduce calls. It is not an architectural necessity or a measure of GPU utilization. Revised §§3.1–3.2 (pp. 4–5) clarify these interpretations of workspace and access costs.

4. What the comparison tells us. The matching bounds establish two consequences for parity. Under bounded row-cost imbalance, about n/log⁡nn/\log n rows attain logarithmic calls at linear work. Allocating nn rows raises optimal work to Θ(nlog⁡n)\Theta(n\log n), with logarithmic calls still optimal at that work order. This result permits full numerical records (Theorem 5; §5.2, p. 7).

With the additional fixed-alphabet restriction on retained data and sufficient capacity, concentrated accesses attain Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) calls at linear work. Comparable row costs require an overhead greater than any fixed power of log⁡n\log n to reach that call order (Theorem 8; §6, pp. 7–8).

These results motivate varying workspace size and access layout independently. The guarantees use our hard-attention execution model; transfer to learned or softmax models and implications for GPU latency remain open (§8, p. 9).

[1] Perceiver: General Perception with Iterative Attention

AuthorsOpenReview ↗

Rebuttal (2/3)

Q2. Simulation and prior work

Response. Thank you for asking us to clarify the additional contribution. Theorem 3 quantifies the resources needed to implement these simulations under our finite-precision execution rules. It makes explicit how converting a fixed computation between the two architectures changes its workspace, storage, and source-access costs.

We build on the TT-step-to-TT-loop construction of Saunshi et al., Theorem 5.4, and the graph size/depth perspective of Xu and Sato, §3, which also considers model size and precision. Our addition is a set of explicit resource bounds for both directions of exact simulation of finite deterministic computations under the declared execution model.

1. What resources the conversion uses. In the CoT-to-loop direction, preserving TT sequential steps uses n+Tn+T recurrent positions, all evaluated on every call. Theorem 3 specifies the resulting dense-work bound together with the required width, block depth, and precision. Thus the TT-to-TT correspondence comes with a quantified cost for repeatedly evaluating the padded workspace.

In the reverse direction, let G0G_0, GG, and GoutG_{\rm out} count the elementary NAND gates implementing initialization, one loop transition, and final readout. A constant-width, constant-depth CoT decoder reproduces the final Boolean answer after RR calls using at most

Tsim=G0+RG+Gout+2T_{\rm sim}=G_0+RG+G_{\rm out}+2

binary tokens. The decoder evaluates the circuit one gate at a time. Keeping its width and depth constant still requires growing storage for intermediate results and a positional program specifying which previous results each gate reads. The theorem accounts for this storage and charges program preparation.

2. What the access implementation changes. For this reverse construction, the same gate computation and binary-token sequence have inference work bounds of O(Nc2)O(N_c^2) with dense attention and O(Nc)O(N_c) with certified indexed reads, where Nc=n+2+TsimN_c=n+2+T_{\rm sim}. Dense attention scans previous positions to retrieve operands; indexed access reads the required operands directly. This gives a concrete consequence beyond the token bound: even after the computation and token count are fixed, the access implementation changes the work of executing the simulation. These bounds count word operations during inference; program preparation and storage are also charged.

These are sufficient resource bounds for the stated constructions, not claims that every simulation must incur those costs. Revised §4 (pp. 5–6) clarifies this contribution; the optimal task-level comparisons are established separately in Theorems 5 and 8.

Q3. The parity lower bound

Response. Thank you for asking us to clarify the distinction. Theorem 4 extends the deterministic lower bound of Amiri et al. to bounded-error randomized CoT with local adaptive stopping. The additional insight is that, under our stated assumptions, sampling tokens and allowing early termination cannot reduce the worst-case expected token requirement for parity below linear order.

1. The additional guarantee. Under fixed-architecture, deterministic-prefill, and hard-attention assumptions, consider a decoder that generates a single trajectory and may decide when to stop from its local state. If its error is at most a fixed δ<1/2\delta<1/2 on every input, then there is an input on which it generates Ω(n)\Omega(n) tokens in expectation over its random choices. Thus the same input remains expensive when averaged over repeated randomized runs; the claim does not require every run to be long. The decoder may retain its full numerical key–value (KV) cache at the declared precision, without the additional fixed-alphabet restriction used for the later frontier.

2. Why this requires an additional argument. Fixing the random choices of a bounded-error decoder need not produce a deterministic procedure that is correct on every input. Even where a deterministic lower bound applies, its hard input could depend on those choices. Consequently, applying the earlier bound separately after fixing randomness does not establish the expected-token guarantee for a single input.

We build on Amiri et al.'s restriction lemma, which fixes some input bits while leaving at least half free and makes each input/prefill cache record depend on only a constant number of free bits. Our Lemma 12 supplies the additional step: it simulates the decoder's attention queries using a constant expected number of newly revealed bits per query, while preserving token sampling and the local stopping decision. Under uniformly random free bits, stopping with any bit unrevealed leaves parity equally likely to be zero or one. The error guarantee therefore forces linearly many revealed bits in expectation and, with fixed numbers of layers and heads, linearly many tokens.

Revised §5.1 (p. 6) states this distinction from the deterministic result; Appendix B.2 (pp. 19–20) gives the proof.

AuthorsOpenReview ↗

Rebuttal (3/3)

Q5. What a visit measures

Response. A visit is one executed source-slot read, including repeated, masked, and padded slots. A certified indexed read counts as one visit; scanning kk slots counts as kk visits.

Visits matter because fewer calls can still require more source reads. At n=4096n=4096, the compact loop uses 24 calls and 16,384 visits, while the full loop uses 13 calls and 110,592 visits (Table 3). These counts include encoding and omit final readout. Reporting visits alongside calls reveals this difference in access cost.

Visits measure the source-access component of work, not total work, DRAM traffic, or latency. Row updates and other computation also incur costs, and latency is measured separately. Revised §7 (pp. 8–9) clarifies this definition and interpretation.

W1. Definitions and exposition

Response. We agree that the research question, basic objects, and assumptions should be clear before the technical results. We have revised the main text to follow that order and to explain the computational meaning of the notation.

1. Introduce the question through a concrete computation. Section 1 (pp. 1–2) now opens by asking how many positions a recurrent model should update on each pass. It explains that these positions are the rows, one pass is a loop call, and every allocated position incurs work. Figure 1 (p. 2) then illustrates an eight-bit parity computation: CoT forms successive running parities, while a four-row loop forms partial answers and combines them. Placing this example before the formal model gives the reader a computation to connect to the later definitions.

2. Define the resources and explain when each assumption is needed. The new symbol guide (§3, p. 3) distinguishes allocated workspace mm from available capacity MrowM_{\rm row}, tokens TT from calls RR, and total work CC from its budget BB. Sections 3.1–3.2 (pp. 4–5) connect these quantities to recurrent latent positions and the source lists they process.

Section 6.1 (p. 7) explains the frontier's additional retained-data restriction in concrete terms: at initialization and after each call, a row's input-dependent data must come from a fixed set, such as the two possible values of a parity bit. The size of this set does not grow with input length or work budget. Calculations within a call may still use the declared numerical precision. We clarify that Theorems 4–5 allow the full numerical records specified by the model without this additional restriction.

These revisions are intended to make the design question, the meaning of the resources, and the scope of each result understandable before the reader turns to the proofs.

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.

Reviewer_2frdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper compares the execution efficiency of two prominent inference time compute mechanisms, CoT and looped transformers. They use symbolic tasks such as parity checks to analyze the pure execution efficiency using custom transformers architecture. Overall they find that CoT needs linear amount of tokens while looped transformers can do similar work with logarithmic passes. They also characterize how many loop passes are needed for a task as a function of the work budget, the number of rows, etc.

Critical strengths

The authors do a great job counting all the compute aspects. Every row, scanned slot, unused computation and setup step counts toward cost. The paper separates passes, total work, and memory as distinct resources while accounting for cost, and shows that cutting the number of passes can cost extra work. This can be a useful construct for designing looped models.

Critical weaknesses

My main concern is the choice of the task and its generalization. Parity is perhaps easy to analyze and make sense theoretically, but it would help if the authors could show some small experiments to demonstrate the benefits in practice. Currently, it is unclear whether the conclusions actually carry over to real-world tasks that people actually care about. And the GPU experiments don't test the main theory.

It seems the conclusions heavily depend on the choice of attention model. Everything assumes hard attention, where each head reads exactly one position. With softmax, parity can be computed in a constant number of layers, so the gap between CoT and loops could vanish.

I'm also concerned about the appropriateness of this paper for ICLR. Given the almost pure theoretical analysis, it might be hard to follow for a general ICLR audience.

Questions for authors

NA

2 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

Thank you for recognizing the value of accounting for evaluated rows, source accesses, and setup costs. This accounting yields our main contribution: matching bounds that explain when fewer loop calls require more work and which workspace choices avoid that cost. Changes are highlighted in red in the revised manuscript.

W1. Task choice, generalization, and the GPU evidence

Response. We agree that the original GPU experiments illustrate the costs of explicit constructions but do not establish the main work–call frontier or its transfer to learned tasks. We have clarified the purpose of parity in §1 (pp. 1–2) and added experiments addressing both the constructions and learned computation in Appendix K (pp. 43–45).

Why we study parity

We use parity because it enables a sharp comparison of optimal costs at fixed correctness: every input bit can change the answer, the output is one bit, and each architecture chooses its own algorithm. This lets us identify unavoidable costs. Under hard attention, comparable row costs, and certified indexed reads, about n/log⁡nn/\log n rows achieve logarithmic calls at linear work, whereas allocating nn rows raises optimal work to Θ(nlog⁡n)\Theta(n\log n) without improving the asymptotic call order (§5, pp. 6–7). Thus, the analysis identifies when additional workspace increases work without improving the scaling of sequential computation.

What generalizes beyond parity

The theoretical generalization is limited but explicit. These same-work results allow full numerical records and extend to ordered products of permutations of five objects, where input order matters (Proposition 23). The finer matching frontier in Theorem 8 remains a parity result under a fixed-alphabet retained-state condition. Neither result establishes transfer to general learned reasoning tasks.

What the learned-task experiments show

To investigate practical transfer, we added learned comparisons on bAbI two-fact QA and a ProPara existence-event diagnostic. None of the 12 three-seed comparisons met the prespecified quality criterion, and the selected CoT settings used no intermediate scratchpad tokens (Appendix K.2, pp. 44–45). These runs therefore do not establish an efficiency advantage at matched task quality.

A separate padding control tests whether changing physical source access can preserve a learned computation (Appendix K.3, p. 45). With weights, ordered useful source lists, rows, and calls fixed, packed execution reduced source-slot visits by 52–54.5%, with bitwise-identical logits on full validation splits and timed test inputs. This demonstrates the access mechanism in learned checkpoints. Its scope is narrow: we used one checkpoint per task, both missed their quality targets, and both used only one loop call after encoding (h=1h=1). Median latency changes of −2.87% to +0.11% are descriptive single-GPU measurements without paired confidence intervals.

What experiments can verify about the main results

Finite experiments can check the constructions' correctness and resource counts, but cannot establish an asymptotic optimum over all algorithms in the stated class. The matching lower bounds require proofs; experiments test finite consequences and implementation behavior.

We added a CPU sweep over input lengths from 2102^{10} to 2182^{18} (Appendix K.1, p. 43). On this grid, the capped construction needs at least 32 loading calls, while the full binary control needs only 11–19 calls in total. These construction constants prevent a call advantage at the tested sizes: binary controls won every tested budget cell, and no capped configuration fit the source-visit budgets. Thus, the sweep does not demonstrate the asymptotic frontier; its visit ledger also does not measure complete work. Sections 7–8 (pp. 8–9) make these limits explicit.

AuthorsOpenReview ↗

Rebuttal (2/2)

W2. Dependence on the attention model

Response. We agree that hard attention is essential to the current proof. Section 5.1 (p. 6) now states this beside Theorem 4, and §8 (p. 9) explains the failed step: softmax aggregates many values, invalidating our simulation by a constant expected number of input-bit reads. [1] uses this aggregation.

The same-work softmax comparison remains open. Constant depth alone does not settle it: a causal-decoder comparison must also account for source accesses, evaluated positions, preprocessing, and precision.

Within the stated model, both architectures use the same attention rules and pay for every scanned candidate. The CoT bound permits the full numerical cache, sampling, and adaptive stopping. The result therefore identifies a resource separation under shared assumptions, including randomized decoding; the revised paper makes that scope explicit.

[1] Overcoming a Theoretical Limitation of Self-Attention

W3. Accessibility for a general ICLR audience

Response. Thank you for encouraging us to make the paper more accessible to ICLR's broad readership. We have rewritten the opening around the workspace design question (§1, pp. 1–2), moved the eight-bit example before the formal model (Figure 1, p. 2), and added a symbol guide (§3, p. 3). These changes introduce the question, intuition, and main consequences before the formal definitions.

The revised presentation emphasizes a concrete inference question: when does additional workspace improve computation under a fixed work budget? The matching bounds show that more rows can increase optimal work without improving the asymptotic call order, and identify when concentrated access costs change that order. This connects our work to the theoretical study of Transformer computation represented by recent ICLR papers such as [2] and [3]. We hope the revisions make these insights easier to follow and assess across the ICLR community.

[2] Transformers are Inherently Succinct

[3] Diffusion Language Models are Provably Optimal Parallel Samplers

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.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.