acceptodds
Under review as a conference paper at ICLR 2027

Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?

12 views

Abstract

Reasoning models generate long chains of thought before they answer, yet it is debated whether the content of these chains does real computational work or is largely decorative. We study this question by viewing a transformer as a shallow circuit. One forward pass through a fixed number of layers has constant depth, so any procedure that runs the model a constant number of times is a shallow circuit. We call the best accuracy that a shallow circuit can reach on a task the ceiling of the task, and a task is serial if its ceiling lies below one. We prove three results on serial tasks that hold for every transformer, no matter how it was trained. Necessity: replacing the chain by anything that does not depend on its content, such as filler tokens or a restatement of the question, drives the accuracy down to the ceiling, and on a maximally serial task down to chance. Depth: no shallow computation can write the chain of a model whose accuracy exceeds the ceiling, not even approximately. Locality: the answer is one shallow pass away from the finished chain, so all of the serial reasoning happens in the chain. On word problems of finite groups, whose ceilings are known, small transformers trained from scratch, with or without reinforcement learning, attain the predicted numbers: chain-trained models solve every input length and fall to chance when the chain is erased, chainless models collapse to the ceiling as the input length grows, and open-weight reasoning models given the same problem in words return to the baseline without their chain. On MATH-500 and AIME, erasing the chain costs open reasoning models 0.52 to 0.82 accuracy, a sentence shuffle is harmless, and a token shuffle is as harmful as erasing; the same holds for checkpoints trained by GRPO with a correct or a random reward. The ceiling of a task therefore answers when a transformer can succeed without its chain of thought, no matter how the model was trained.

Primary area:
foundation or frontier models, including LLMs
Keywords:
chain-of-thought, reasoning, transformer expressivity

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_78QLOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper investigates when a transformer can solve a task without relying on the content of its chain of thought. It introduces a task-specific accuracy ceiling for shallow computation and shows, within its theoretical framework, that exceeding this ceiling requires sequential computation in the chain, regardless of how the model was trained. Experiments on synthetic tasks and mathematical benchmarks show that removing tokens or shuffle tokens in the chain reduces accuracy.

Critical strengths
  • A precise framework for when CoT is necessary. The task’s “ceiling” provides a quantitative criterion for the accuracy achievable through shallow computation.

  • Results that do not depend on a particular training method. Within its stated computational assumptions, the framework applies to any trained transformer. The necessity, depth, and locality results connect the importance of chain content, the computation needed to generate it, and the extraction of the final answer.

Critical weaknesses

The empirical interpretation is stronger than the evidence supports. The theory adresses what shallow computation can achieve, but the experiments measure what particular trained models achieve after their chain of thoughts are modified. These quantities need not coincide: a model may rely on its chain even when the task can be solved without one. Therefore, the accuracy drops on realistic benchmarks are consistent with the framework but do not establish that the task’s computational ceiling causes those drops. This distinction should be reflected more clearly in the main discussion, particularly when describing the experiments as matching theoretical predictions. Besides, a dedicated related work section is missing.

Questions for authors

None.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 78QL (1/2): What the theory bounds and what the experiments measure

We thank the reviewer for the careful reading, and we are glad that the reviewer found the framework precise and its independence from the training method useful.

1. What the theory bounds and what the experiments measure.

We thank the reviewer for stating this distinction clearly, and we agree with it. The ceiling is what the best shallow computation achieves on a task. An erasing experiment measures what one trained model achieves without its chain. Theorem 3.1 says that the second quantity is at most the first. A model can rely on its chain where the task does not require it, and the models in the paper did. They were trained only with the chain, and their answer head copies the last token of the chain, so they fall to the baseline even on groups whose ceiling is 1.

We therefore ran a new experiment that removes this dependence wherever it is only a habit, so that the two quantities can be compared directly. In half of the training examples we replace the chain with filler, in the same format as the erasure at test time, and we train the model to give the correct answer there. These models see the erased chain throughout training, so training pushes them to answer without the chain wherever one pass can compute the answer. We trained them from scratch with supervision, with four layers, on four groups, at five lengths from n = 8 to 128, and with three seeds. Each model trains for twice as many steps as the models in the paper. Before the main runs we fixed in writing the outcome that would contradict Theorem 3.1, which is an accuracy above 0.03 without the chain on A₅ at n = 64 or 128. It did not occur. The table reports the two longest inputs, n = 64 and 128. Ranges are over seeds.

GroupDegree of serialityCeilingCounting valueWith the chainWithout the chain
Z₆₀, commutativenot serial110.993 to 1.0000.996 to 1.000
A₄ × Z₅, solvable and not commutativenot serial11/40.994 to 0.9990.246 to 0.254
S₅average-case serial2/120 = 0.01672/1200.981 to 1.0000.009 to 0.019
A₅maximally serial1/60 = 0.01671/601.0000.016 to 0.020

The ceiling is the best accuracy that a shallow circuit of fixed depth and size reaches as the input grows. The counting value is the accuracy of a circuit that computes the commutative part of the product by counting and guesses the rest (Proposition D.2 and Table 3 of the revised paper). The accuracy without the chain is the better of the two predictions that a model makes in one pass, after the filler and at the last input token. The table covers the 22 of 24 models that learned the task with the chain, two of them after a longer run.

We evaluate each model on 10,000 fresh instances, so the standard error at 1/60 is 0.0013. The values slightly above 0.0167 in the last column are within this error. The largest, 0.0197, is 2.4 standard errors above 1/60 and inside the band of three standard errors that we fixed before the runs. The 12 one-pass predictions of the six A₅ models average 0.0163.

Where the ceiling is below 1, the theorem forces the drop, and the new models show it although they were trained against it. A₅ is maximally serial, and its ceiling is the guessing baseline 1/60. Every seed still falls from 1.000 to between 0.016 and 0.020. S₅ is average-case serial, since one pass can compute the sign of the product and nothing more, and no model exceeds its ceiling of 2/120 beyond sampling error. Where the ceiling is 1, the theorem forces no drop. Z₆₀ is commutative, one pass computes its product by counting, and the new models lose nothing. The drop on this group in the paper therefore reflected the trained model and not the task, as the reviewer describes. A₄ × Z₅ is solvable and not commutative. Counting gives the commutative part of its product, which narrows the answer to 4 candidates, and the models reach this value of 1/4.

Two controls show that the new training does teach the models to answer without the chain. On short inputs of A₅ one pass can still compute the product, and the accuracy without the chain is 1.000 at n = 8 in every seed. The length up to which one pass suffices also grows with the depth. With two layers every seed is at the baseline from n = 16, and with four layers from n = 64. With eight layers two of three seeds still answer without the chain at n = 128, with accuracy 0.995 and 0.999. This is what the theory says, since the ceiling of 1/60 is the limit for long inputs at a fixed depth.

On A₅ the link between the ceiling and the drop is therefore not an inference from one trained model. The theorem says that every model must fall to 1/60 on long inputs, and models that are trained to avoid the drop still fall to it.

AuthorsOpenReview ↗

Response to Reviewer 78QL (2/2): Changes in the revised paper, and related work

2. How the revised paper describes the experiments.

The revised paper reflects the distinction in the main text. At the start of Section 6 it states what the theory bounds and what each experiment measures, and Table 5 lists the statement that each experiment tests. It says that the measured accuracy matches the predicted value on the word problems, where the ceiling is known, and it reports the new experiment there. It describes the drops on MATH-500 and AIME as consistent with the theory, which is consistent with what the reviewer suggests.

The benchmark experiments are in the paper for what they establish without the value of the ceiling. The word problems are the controlled test, and the benchmarks show that the same behavior appears in the models that people use, which are pretrained reasoning LLMs with 1.5B to 32B parameters, including 19 checkpoints that we trained with GRPO. Tokens without content do not replace the chain, since filler, random tokens, and a template give the same accuracy as an empty chain within 0.11 (Figure 4c). The answer head reads the chain and does not continue the reasoning, since accuracy after truncation rises in step with how often the kept part already states the answer (Figure 4b). Training does not change this, since the checkpoints trained with a correct or a random reward behave alike (Figure 4d). The benchmarks also give a measurement. The accuracy that one pass reaches, 0.13 to 0.33 on MATH-500, is a lower bound on the ceiling.

3. Related work.

The revised paper has a dedicated related work section in the main text (Section 7). It places the paper against four lines of work. The first is the expressive power of transformers with and without a chain (Merrill and Sabharwal, 2023, 2024; Li et al., 2024; Liu et al., 2023; Amiri et al., 2025). These results are worst-case statements about what a transformer can compute, and we add the average-case ceiling and bounds for a trained model whose chain is modified. The second is intervention studies of faithfulness (Lanham et al., 2023; Turpin et al., 2023; Chen et al., 2025; Bentham et al., 2024; Chen et al., 2026; Ballon et al., 2026). These studies measure what happens when a chain is erased, truncated, or shuffled, and our theorems say how such measurements can be read. The third is methods that shorten or replace the chain. These are System One models (Almeida, 2026), filler and pause tokens (Pfau et al., 2024; Goyal et al., 2024), latent reasoning (Deng et al., 2024; Hao et al., 2025; Geiping et al., 2025), diffusion decoding (Nie et al., 2025), and chain compression (Xu et al., 2025). The ceiling bounds each of them when its number of steps is fixed (Appendix A). The fourth is the average-case complexity of group products (Barrington, 1989; Miles and Viola, 2013), which gives the ceilings of the tasks in our experiments.

The revised paper also states the computational model and the main definitions before the first claims that use them, and it uses the word problem of A₅ as a running example, which should reduce the effort that the first sections required. We hope that these answers resolve the reviewer's concerns, and we are glad to clarify any remaining point.

Additional References:

Bentham, Stringham, and Marasović. Chain-of-Thought Unfaithfulness as Disguised Accuracy. TMLR, 2024. Chen, Liao, Shiu, and Lee. Rethinking Dense Sequential Chains. arXiv 2605.07307, 2026.

Ballon, Verbeken, Ginis, and Algaba. Probing the Trajectories of Reasoning Traces in Large Language Models. NeurIPS 2026 (arXiv 2601.23163).

Dear Reviewer,

As the discussion period comes to a close, we wanted to make sure we have addressed all of your concerns. In our response we separated what the theory bounds from what each experiment measures, and the revised paper now describes the results on MATH-500 and AIME as consistent with the theory. It also has a dedicated related work section in the main paper. If any points remain unclear, or you would like us to expand on anything, please let us know. We would be glad to respond before the deadline.

Thank you for your time and for the feedback that has helped us improve the paper.

Best regards,

The Authors

Reviewer_3nhgOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper models a transformer forward pass as a shallow circuit and defines a task’s ceiling as the best accuracy any shallow circuit can achieve. It proves that, for any transformer, accuracy above the ceiling must come from the content of the chain of thought (Necessity, Depth, Locality), and tests this on finite-group word problems with small transformers and Qwen3 models, and with chain interventions on MATH-500 and AIME.

Critical strengths
  • The average-case notion of a task ceiling and the graded definition of seriality are a clean extension of prior worst-case results, and connect circuit complexity to accuracy, the quantity practitioners actually measure.
  • The appendix is transparent, reporting negative or unexpected results (e.g., Table 5) and limitations of the released records.
Critical weaknesses
  • While Theorem 3.1 establishes a theoretically meaningful upper bound on performance after CoT erasure, necessity experiments are confounded by train–test mismatch. Since the models are trained only on full chains, replacing the chain with filler/random tokens/templates puts the answer head off-distribution, so the observed drop to chance cannot be attributed to the task’s ceiling rather than to this mismatch.
  • The observation in Fig. 4c that sentence shuffling is harmless while token shuffling collapses accuracy has been reported in prior work (e.g., arXiv:2605.07307, arXiv:2601.23163), which is not cited. The empirical contribution here therefore seems incremental; the authors should clarify what additional insights their theoretical framework provides beyond these established empirical findings.
Questions for authors

What is the non-trivial theoretical contribution of the Locality theorem? Theorem 5.2 appears to follow directly from the fact that the answer is generated by a single transformer forward pass, which is already known to be representable by a shallow circuit. Could the authors clarify what additional insight this theorem provides beyond this established architectural property?

6 comments
AuthorsOpenReview ↗

Response to Reviewer 3nhg (1/4): Train-test mismatch, new experiment

We thank the reviewer for the careful reading, and we are glad that the reviewer found the ceiling and the graded definition of seriality a clean extension of the worst-case results. We answer the two weaknesses and the question in order. Point 1 uses a new experiment that we ran, and the revised paper reports it (Section 6.1 and Table 1, with details in Appendices G and H).

1. Train-test mismatch in the necessity experiments (Weakness 1).

We thank the reviewer for this point, which is the main concern of all three reviews. The reviewer is right about the models in the paper. They were trained only with the chain, so an erased chain puts their answer head off distribution. We checked what the head does there. When random tokens or a template replace the chain, it returns the last token of the replacement in 10,000 of 10,000 test instances. The drop of these models therefore cannot separate the ceiling of the task from the mismatch.

We therefore ran a new experiment in which the mismatch is absent by construction. In half of the training examples we replace the chain with filler, in the same format as the erasure at test time, and we train the model to give the correct answer there. The input after erasing is then an input that the model saw throughout training, with the correct answer as its target. Training also pushes the model to answer without the chain wherever one pass can compute the answer. We trained these models from scratch with supervision, with four layers, on four groups, at five lengths from n = 8 to 128, and with three seeds. Each model trains for twice as many steps as the models in the paper. Before the main runs we fixed in writing the outcome that would contradict Theorem 3.1, which is an accuracy above 0.03 without the chain on A₅ at n = 64 or 128. It did not occur. The table reports the two longest inputs, n = 64 and 128. Ranges are over seeds.

GroupDegree of serialityCeilingCounting valueWith the chainWithout the chain
Z₆₀, commutativenot serial110.993 to 1.0000.996 to 1.000
A₄ × Z₅, solvable and not commutativenot serial11/40.994 to 0.9990.246 to 0.254
S₅average-case serial2/120 = 0.01672/1200.981 to 1.0000.009 to 0.019
A₅maximally serial1/60 = 0.01671/601.0000.016 to 0.020

The ceiling is the best accuracy that a shallow circuit of fixed depth and size reaches as the input grows. The counting value is the accuracy of a circuit that computes the commutative part of the product by counting and guesses the rest (Proposition D.2 and Table 3 of the revised paper). The accuracy without the chain is the better of the two predictions that a model makes in one pass, after the filler and at the last input token. The table covers the 22 of 24 models that learned the task with the chain, two of them after a longer run.

We evaluate each model on 10,000 fresh instances, so the standard error at 1/60 is 0.0013. The values slightly above 0.0167 in the last column are within this error. The largest, 0.0197, is 2.4 standard errors above 1/60 and inside the band of three standard errors that we fixed before the runs. The 12 one-pass predictions of the six A₅ models average 0.0163.

AuthorsOpenReview ↗

Response to Reviewer 3nhg (2/4): Train-test mismatch, results for each group

1. Train-test mismatch in the necessity experiments (Weakness 1) (continued)

Every row in the table agrees with the theory, and the reason depends on the degree of seriality.

  • A₅ (maximally serial, ceiling 1/60). The ceiling is the guessing baseline, so Theorem 3.1 forces the whole drop. These models saw the erased chain in half of their training and were trained to answer it, and they still fall from 1.000 to between 0.016 and 0.020 in every seed.
  • S₅ (average-case serial, ceiling 2/120). A shallow circuit can compute the sign of the product and nothing more, which leaves 60 candidates. Every model stays at or below the ceiling within sampling error.
  • Z₆₀ (commutative, not serial, ceiling 1). One pass computes the product by counting how often each element occurs, so the theorem forces no drop. The new models lose nothing. The drop on this group in Figure 3a therefore came from the mismatch, as the reviewer suspected, and it disappears in the new models.
  • A₄ × Z₅ (solvable and not commutative, not serial, ceiling 1). The theorem again forces no drop. Counting gives the commutative part of the product, which narrows the answer to 4 candidates. The models identify this part with accuracy 0.969 to 1.000 and reach the counting value of 1/4. Two controls show that the new training does teach the models to answer without the chain. On short inputs of A₅ one pass can still compute the product, and the accuracy without the chain is 1.000 at n = 8 in every seed. The length up to which one pass suffices also grows with the depth. With two layers every seed is at the baseline from n = 16, and with four layers from n = 64. With eight layers two of three seeds still answer without the chain at n = 128, with accuracy 0.995 and 0.999. This is what the theory says, since the ceiling of 1/60 is the limit for long inputs at a fixed depth. A dependence that came from the mismatch would have no reason to follow the depth.

The mismatch therefore explains the drop on Z₆₀ in the paper. It does not explain the drop on A₅, which remains in full once the mismatch is removed.

The argument uses the filler erasure only. Random tokens and the template are made of the same symbols as a chain, so a model can mistake them for one, and they cannot separate the ceiling from the mismatch. One erasure that the model has seen in training is enough, since Theorem 3.1 bounds every erasure by the same ceiling.

AuthorsOpenReview ↗

Response to Reviewer 3nhg (3/4): Relation to Chen et al. (2026) and Ballon et al. (2026)

2. Prior reports of the shuffle and truncation effects (Weakness 2).

We thank the reviewer for the two references. The revised paper cites both (Section 7). Chen et al. (2026) observe that shuffling lines is harmless while shuffling tokens is not, and Ballon et al. (2026) observe that accuracy rises with the kept fraction of a truncated trace. Both are empirical studies. Our contribution is not these observations. It is a theory that predicts them, connects them, and shows that the conclusion suggested by them does not hold on serial tasks. Figures 4b and 4c are in the paper as tests of this theory, and the empirical contribution of the paper is the test of the predicted values on the word problems, where the ceilings are known (Section 6.1 and point 1 above).

Specifically, one inequality accounts for both observations. By Theorem 5.2, after any intervention the model is at most as accurate as a shallow reader of what the intervention leaves. For a shuffle, the reader sees only the bag of the shuffled units (Lemma F.1). A bag of lines still contains the line that states the answer, and a bag of tokens does not identify it. The bound can only decrease as the unit becomes finer, which gives the order line, word, token that Chen et al. measure. For truncation, the reader sees the kept prefix, so accuracy can survive only where the prefix already gives the answer. The bound can only increase with the kept fraction, which is the trend that Ballon et al. measure. The revised paper states both properties (Remark F.4).

Our theory also corrects the conclusion suggested by the observations. Chen et al. suggest that their findings open a path toward generating reasoning in parallel and with fewer tokens. On serial tasks this does not hold. By Theorem 4.1, a chain that lifts accuracy above the ceiling cannot be written in a constant number of parallel rounds, and it cannot be compressed into a constant number of tokens. The number of serial steps has to grow with the input, however the finished chain is read. Reading a finished chain is shallow and writing it is not, and the shuffle experiments test only the reading.

The same limit applies to every method that replaces serial reasoning with a fixed amount of computation, and this is where the framework is most useful in practice. It covers System One models such as Jev (Almeida, 2026), which answer in one pass. It covers latent reasoning with a fixed number of latent steps (Hao et al., 2025; Geiping et al., 2025) and masked diffusion language models with a fixed number of denoising steps (Nie et al., 2025). It covers filler and pause tokens, which add positions without content (Pfau et al., 2024; Goyal et al., 2024). Each of these is a constant number of passes, so its accuracy is at most the ceiling of the task, whether the passes exchange tokens or latent vectors (Lemma 2.3, Remark B.5, Appendix A). The ceiling therefore tells from the task alone when such a method suffices, which is when the ceiling is 1, and when its number of steps has to grow with the input.

Finally, our theory yields tests that the observations do not suggest. On A₅ we construct a chain whose bag determines the answer, and models on this chain keep 0.69 to 1.00 accuracy under a token shuffle and fall to chance under erasing (Proposition F.2, Table 7). We also construct two models with identical chains that react to the same shuffle in opposite ways (Proposition F.3), so a drop under a shuffle can come from the answer head alone.

Reviewer_xUgLOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when chain-of-thought (CoT) reasoning is necessary for transformers to solve certain computational problems. The main idea is to compare the accuracy of a transformer that generates intermediate reasoning tokens with what can be achieved using constant-depth circuits, which represent computations that can be performed without a growing number of sequential steps.

The authors define a shallow-circuit ceiling, which is the best accuracy achievable by constant-depth, polynomial-size circuits on a given task. They then study tasks for which this ceiling is bounded away from perfect accuracy. Their main theoretical results are organized around three properties: Necessity, which states that replacing the generated CoT with shallowly computed content cannot preserve accuracy above this ceiling; Depth, which shows that a shallow generator cannot closely reproduce the distribution of successful reasoning chains; and Locality, which states that the final answer can be computed from the completed chain and input using a shallow computation.

The authors evaluate these ideas on finite-group multiplication problems, particularly the A5A_5 group, and on reasoning benchmarks such as MATH-500 and AIME. They examine what happens when reasoning chains are erased, shortened, or shuffled. The experiments show that models often depend strongly on their generated chains, while also revealing differences between generating a solution and extracting an answer from an already completed chain.

Critical strengths

1. A useful perspective on the role of CoT in transformer computation.

The paper asks an interesting question about whether the intermediate reasoning tokens generated by a transformer are actually necessary for its performance. I find the distinction between generating a reasoning chain and using the completed chain to produce an answer useful. The theoretical framework provides a way to study this question using the computational limits of constant-depth circuits. The authors focus on the computational capabilities of models that have already been trained to solve the task successfully, rather than on the training process itself. In a sense they provide an intervention-based analysis of CoT.

2. Some thoughtful experiments on how models use their reasoning chains.

The experiments provide useful observations about the behavior of trained transformers. In particular, the results on the A5A_5 group show a substantial drop in accuracy when the generated reasoning chain is removed. The experiments on truncating and shuffling reasoning chains are also interesting. For example, shuffling complete sentences often has little effect on accuracy, whereas shuffling individual tokens can be much more damaging. This suggests that generating the answer and extracting it from the completed chain may involve different kinds of computation.

Critical weaknesses

1. The theoretical contribution seems somewhat limited compared to prior work, and the interpretation of the results could be clearer.

Li et al. (2024) already establish that generating intermediate tokens can increase the computational power of constant-depth transformers and allow them to solve problems requiring sequential computation. The present paper considers a different question, namely whether the generated reasoning content is necessary for an already successful model. However, the main Necessity result seems to follow fairly directly from the fact that combining a constant number of shallow computations still gives a shallow computation. The Depth result also appears to follow from this observation and standard properties of total-variation distance. Similarly, the Locality result seems fairly immediate from the fact that the final answer is generated using one transformer forward pass.

I also have some difficulty with the interpretation of the Necessity theorem. The authors compare an autoregressive CoT model that generates T(n)T(n) tokens sequentially with a replacement procedure that generates the same number of tokens using a constant-depth computation. Although the two procedures may use the same number of tokens and context length, they have very different computational capabilities. The original CoT can use each intermediate result to compute the next one, whereas the replacement cannot perform a growing sequence of dependent computations. As a result, the two procedures may produce very different kinds of useful information.

Therefore, the theorem seems to establish the necessity of additional sequential computation for certain tasks, rather than the necessity of CoT specifically. I would have liked a clearer discussion of what the results establish beyond the known computational advantage of sequential processing.

The presentation could also be improved. I found the initial sections somewhat difficult to follow, as several terms and claims are introduced informally before their precise definitions appear later. It took some effort to understand exactly what was being compared and what the different results were intended to establish. Introducing the computational model and the main definitions earlier, perhaps with a simple running example, would make the paper easier to understand.

2. The experiments are interesting, but their connection to the theoretical claims is not entirely clear.

The theoretical results concern how the best possible accuracy of shallow circuits behaves as the input length nn grows. However, the experiments only consider a limited range of finite input lengths, and the small transformers appear to be trained separately for different lengths. Since the theory is asymptotic and does not provide explicit thresholds for the tested architectures, it is difficult to tell whether the observed accuracy drops are caused by the predicted computational limits or simply by the behavior of the particular trained models.

This distinction is especially important because the authors also observe large accuracy drops after CoT removal on group problems that can, in principle, be solved by shallow circuits. This suggests that a model may depend heavily on its reasoning chain even when the underlying task does not require sequential computation. In other words, dependence on CoT may reflect the strategy learned by a particular model rather than an inherent property of the task.

The experiments on MATH-500 and AIME raise a similar question, since the shallow-circuit ceilings for these benchmarks are not known. While the results clearly show that the evaluated models use their reasoning chains, it is less clear how directly they support the proposed theory of task-level seriality.

I also think some of the more interesting experimental findings, particularly the effects of truncation and sentence shuffling, are not directly predicted by the theory. These observations are useful in their own right, but the paper could better distinguish between experiments that test its theoretical predictions and those that reveal additional properties of trained models.

Questions for authors

1. Could the authors clarify the theoretical novelty compared to Li et al. (2024) and the precise meaning of CoT necessity?

Li et al. already show that autoregressive generation increases the computational power of constant-depth transformers. In the present paper, the Necessity theorem compares sequentially generated reasoning tokens with replacement tokens produced by a shallow computation. Since the replacement has much less sequential computational depth, it seems natural that the two procedures cannot achieve the same accuracy on sufficiently hard tasks. What additional insight does this result provide beyond the known need for growing computational depth? In particular, can the framework distinguish the importance of CoT as an intermediate representation from the additional sequential computation used to produce it?

2. Could the authors clarify how the experiments support the asymptotic theoretical results?

The theory concerns the behavior of shallow-circuit accuracy as the input length grows, while the experiments use relatively small input lengths and, in some cases, separately trained models. Moreover, the authors observe strong CoT dependence even on tasks that admit shallow solutions. How can we distinguish an inherent computational limitation of the task from a limitation of the strategy learned by the model? Would evaluating a fixed trained model over a wider range of input lengths help clarify this? Also, given that the shallow-circuit ceilings of MATH-500 and AIME are unknown, what specific theoretical predictions are these experiments intended to test?

7 comments
AuthorsOpenReview ↗

Response to Reviewer xUgL (1/5): How the theorems differ from prior impossibility results

We thank the reviewer for the careful reading and the precise questions. We answer the points on the theory first (W1, Q1) and then the points on the experiments (W2, Q2). Point 4 describes the additional experiment we ran, and the revised paper reports it (Section 6.1 and Table 1, with details in Appendices G and H).

1. Worst-case versus average-case analysis (W1, Q1).

We thank the reviewer for asking how our results differ from those of Li et al. (2024). The content of our theorems is in the quantity that bounds them, the ceiling of the task, and this quantity is what separates the two analyses. The impossibility result of Li et al. is a worst-case statement. It shows that a constant-depth transformer without a chain cannot be correct on every input of an inherently serial problem. It does not say how accurate such a transformer can be, and its accuracy may be close to 1 or close to chance. Proposition C.6 gives a task of the first kind. The word problem of A₅, under a distribution concentrated on inputs with few non-identity elements, is inherently serial in the sense of Li et al., yet a shallow circuit solves it with accuracy 1 − 2⁻ⁿ. On this task the bound of Theorem 3.1 is close to 1, and erasing the chain need not cost anything. A worst-case analysis therefore cannot decide whether the content of a chain is needed for accuracy, which is the quantity that experiments measure. The ceiling can decide it, because the ceiling is the best accuracy that any shallow circuit reaches under the input distribution of the task, and Theorem 3.1 bounds every trained transformer by it once the content of its chain is removed. The step from the worst case to the average case is not automatic. For A₅ on uniform inputs it is the result of Miles and Viola (2013), which puts the ceiling at the guessing baseline 1/60 under the conjecture NC¹ ⊄ TC⁰. For S₅ the same argument stops at the sign of the product, and the ceiling is twice the guessing baseline, 2/120. A worst-case analysis labels S₅ and A₅ alike as inherently serial and predicts neither value. The chainless models in the paper fall to 1/60 on A₅ once the input outgrows their depth, and they reach 2/120 on S₅ when they find the sign (Figures 3c and 7).

2. A transformer without a chain versus a trained model under intervention (W1, Q1).

The reviewer describes the comparison correctly. The observation that only the original chain can use each intermediate result to compute the next is what Theorem 4.1 makes quantitative. What Theorem 3.1 adds is the object and the quantifier. Existing impossibility results concern a transformer that never writes a chain. In contrast, Theorem 3.1 concerns a trained reasoning model that has written its chain in T serial passes and then loses the content. One could expect such a model to retain part of what it computed, or to use the positions of the replaced chain as extra computation, which is the hope behind filler and pause tokens (Pfau et al., 2024; Goyal et al., 2024). The theorem shows that it retains nothing above the ceiling. Once an intervention replaces the content, the answer has the distribution of a two-stage pipeline, so the T passes contribute nothing to it.

This also answers the last part of Q1, which asks whether the framework can distinguish the chain as an intermediate representation from the sequential computation that produces it. The two theorems test each one without the other. Under erasing, the model keeps its sequential computation and loses the content, and its accuracy falls to the ceiling (Theorem 3.1). A shallow imitator supplies content without sequential computation, and the distance between its chains and those of the model is at least the accuracy that the model has above the ceiling (Theorem 4.1). In a fixed transformer, serial computation beyond one pass therefore exists only as the content of the chain.

Theorem 3.1 also does not depend on which replacement we choose. It holds for every replacement that a shallow computation can write from the input, including the most useful one. No content written without serial work can therefore lift the accuracy above the ceiling. We analyze this setting because it is the experiment that the community runs. Erasing, truncating, and perturbing the chain (Lanham et al., 2023) are the main evidence on whether models use their chains, and researchers disagree on how to read them. A drop can come from the chain or from the answer head, and Bentham et al. (2024) show that the faithfulness metric of Lanham et al. largely tracks accuracy. Theorem 3.1 fixes the reading for erasing. A model whose accuracy exceeds the ceiling must lose the difference, whatever its training, and the accuracy that survives is a lower bound on the ceiling.

AuthorsOpenReview ↗

Response to Reviewer xUgL (2/5): What the theorems imply for current reasoning methods

3. What the theorems tell us about reasoning models (W1, Q1).

The reviewer asks what the results establish beyond the known advantage of sequential computation. They establish bounds on the methods in use today, and this is where the framework reaches furthest. The theorems are not tied to a task, a model size, or a training method. They hold for every system that answers with a constant number of transformer passes, whether the passes exchange tokens or latent vectors (Remark B.5). The table lists what follows for each method (Appendix A and Table 4 of the revised paper).

Method or practiceWhat the theorems implyFrom
Answering in a constant number of passes. This covers System One models such as Jev (Almeida, 2026), a chain distilled into one pass (Deng et al., 2023, 2024), latent reasoning with a fixed number of latent steps (Hao et al., 2025; Geiping et al., 2025), and masked diffusion language models with a fixed number of denoising steps (Nie et al., 2025).The accuracy is at most the ceiling of the task. On a maximally serial task this is no better than guessing. To exceed the ceiling, the number of steps has to grow with the input.Lemma 2.3
Filler tokens (Pfau et al., 2024) and pause tokens (Goyal et al., 2024)They add width and no depth. They recover the benefit of a chain only on tasks whose ceiling is 1.Lemma 2.3, Theorem 3.1
Compressing the chain (Xu et al., 2025)No training compresses the reasoning for a serial task into a constant number of tokens or latent steps. A model whose chain is shallow on all but a fraction λ of its inputs exceeds the ceiling by at most λ.Theorem 4.1
One-pass verifiers and process reward models (Lightman et al., 2024)They can grade a chain only when each step follows from the input and a bounded number of earlier steps. They cannot grade a step that hides serial work without redoing that work.Theorem 5.2
Intervention studies of faithfulness (Lanham et al., 2023), such as erasing, truncation, shuffling, and paraphraseAccuracy that survives an intervention shows that the answer is readable from what the intervention keeps. A drop in accuracy is evidence about the chain only for erasing, since two models with identical chains can react to a shuffle in opposite ways.Theorems 3.1 and 5.2, Proposition F.3

For the first three rows, a worst-case result gives only a weaker form, which is that the method errs on at least one input. The ceiling turns this into a bound on accuracy, and accuracy is how these methods are evaluated. The ceiling also tells from the task alone which method fits. Where the ceiling is 1, a one-pass model can match a reasoning model, and the chain adds only cost. Where the ceiling is below 1, the serial steps have to be paid for, as tokens or as latent steps, and their number has to grow with the input.

Additional References:

Bentham, Stringham, and Marasović. Chain-of-Thought Unfaithfulness as Disguised Accuracy. TMLR, 2024.

AuthorsOpenReview ↗

Response to Reviewer xUgL (3/5): New experiment with models trained to answer without the chain

4. A limit of the task, or a habit of the trained model? (W2, Q2)

We thank the reviewer for raising this question, which is the central one about our experiments. When we erase the chain, accuracy falls to the guessing baseline. We agree with the reviewer that it is essential to distinguish whether this happens because the task cannot be solved without a chain, as Theorem 3.1 says, or because the model was simply trained to lean on its chain. The drop also appears on groups whose word problem needs no chain, so the drop alone cannot tell the two apart.

The reviewer is right about the models in the paper. They were trained only with the chain, and their answer head copies the last token of the chain, which is a habit. When random tokens or a template replace the chain, the answer head returns the last token of the replacement in 10,000 of 10,000 test instances, and this rule reproduces the accuracy after erasing of all 72 models of this kind.

We therefore trained new models that are taught to answer without the chain. In half of the training examples we replace the chain with filler, in the same format as the erasure at test time, and we train the model to give the correct answer there. In these models the dependence cannot come from unfamiliarity with an erased chain. They see the erased chain in half of their training examples, so training pushes them to answer without the chain wherever one pass can compute the answer. We trained these models from scratch with supervision, with four layers, on four groups, at five lengths from n = 8 to 128, and with three seeds. Each model trains for twice as many steps as the models in the paper. Before the main runs we fixed in writing the outcome that would contradict Theorem 3.1, which is an accuracy above 0.03 without the chain on A₅ at n = 64 or 128. It did not occur.

The table reports the two longest inputs, n = 64 and 128. Ranges are over seeds.

GroupDegree of serialityCeilingCounting valueWith the chainWithout the chain
Z₆₀, commutativenot serial110.993 to 1.0000.996 to 1.000
A₄ × Z₅, solvable and not commutativenot serial11/40.994 to 0.9990.246 to 0.254
S₅average-case serial2/120 = 0.01672/1200.981 to 1.0000.009 to 0.019
A₅maximally serial1/60 = 0.01671/601.0000.016 to 0.020

The ceiling is the best accuracy that a shallow circuit of fixed depth and size reaches as the input grows. The counting value is the accuracy of a circuit that computes the commutative part of the product by counting and guesses the rest (Proposition D.2 and Table 3 of the revised paper). The accuracy without the chain is the better of the two predictions that a model makes in one pass, after the filler and at the last input token. We evaluate each model on 10,000 fresh instances, so the standard error at 1/60 is 0.0013. The values slightly above 0.0167 in the last column are within this error. The largest, 0.0197, is 2.4 standard errors above 1/60 and inside the band of three standard errors. The 12 one-pass predictions of the six A₅ models average 0.0163.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We thank all reviewers for their constructive feedback. We summarize our response below. Changes in the revised paper are marked in red.

1. Concerns addressed. All reviewers asked whether the drop after erasing the chain is a limit of the task or an effect of training. We trained new models that answer both with and without their chain. On A₅ they reach 1.000 with the chain and 0.016 to 0.020 without it (ceiling 1/60), while on Z₆₀, where the theorem forces no drop, they lose nothing. We also clarified what the theory bounds and what each experiment measures, and how the results relate to prior work.

2. Main changes. A new experiment (Section 6.1, Table 1, Appendices G and H); a related work section (Section 7); a table that lists the statement each experiment tests (Table 5).

3. Contribution. Prior theory says what a transformer can compute in the worst case. We bound how accurate any transformer can be without its chain of thought, however it is trained. It also applies to methods in current use: it limits filler tokens, latent reasoning, and chain compression on serial tasks, and it gives rule for reading intervention experiments on faithfulness.

We are glad to answer any 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.