acceptodds
Under review as a conference paper at ICLR 2027

CoT-Depth: Instance-Level Serial Depth Governs Chain-of-Thought Budget

Abstract

Chain-of-thought (CoT) theory assigns a single worst-case budget to every instance of a problem class, yet sequential difficulty within a class spans orders of magnitude: on - connectivity, a star graph resolves in one step while a length- path demands steps at the same encoding length. We introduce instance serial depth —the minimum depth of a computation-trace DAG under a canonical rule system—as the first per-instance CoT complexity measure, and prove matching upper and lower bounds on the CoT budget in terms of . A constant-depth log-precision Transformer solves any instance in CoT steps, extending to for layers. Within the bounded-state, local-prefill class , correctness on pointer-chasing instances forces steps unconditionally across the full depth range, and full prompt-to-prompt attention preserves the linear rate. Class-level budgeting therefore wastes steps relative to instance-adaptive allocation—a depth–size separation. Experiments on three synthetic task families (- connectivity, multi-digit addition, Boolean formula evaluation) confirm -linear scaling in every one of 21 modeltask configurations (), with the per-instance slope reaching in a wider model. A depth probe on hidden states cuts MAE by up to 67% over length baselines and, plugged into an instance-adaptive allocator, saves 19.6% of inference steps on STCON at 100% accuracy. The law extends beyond training from scratch: a LoRA-fine-tuned Qwen2.5-7B carries -linear step counts to templated multi-hop QA, and off-the-shelf 7–8B instruction models allocate depth-proportional CoT under mere few-shot prompting—Qwen3-8B emits CoT steps per unit depth (, ), independently reproduced on Qwen2.5-7B (, ).

Primary area:
learning theory
Keywords:
chain-of-thought, computational complexity, instance difficulty, reasoning budget, transformer expressiveness

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_8pcaOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper defines instance serial depth d_R(x), the derivation depth of input x under a fixed rule system, arguing that it governs the number of CoT steps a problem needs. The authors prove an upper bound of steps for poly-width Transformers, as well as a lower bound for restricted hard-attention models on pointer chasing, and they claim a O(n log n) "waste" of class-level budgets. Experiments are conducted on 3.2M parameter Transformer models on three synthetic tasks, reporting that the minimal CoT budget grows linearly with d(x). Further small LLM experiments are presented as evidence that the effect transfers to large scale.

Critical strengths
  1. The question of per-instance CoT budget instead of per-class budget is relevant
Critical weaknesses
  1. The presented theorems are overall very poor
  • Thm 3.15 lacks a proof
  • Some rely on unstated restrictions, e.g. the key step in Cor. D.4 / Lemma E.3 holds only if every attention key names a single edge endpoint
  • Others contradict each other, namely M.3 claims O(1)-step ADD/BFE shortcuts inside M^loc while the footnote to Table 1 says they are blocked there. App. R also contradicts remark RE-D4 on whether positional keys break the bound.
  • Theorems in part present false claims, e.g. the main text says that d_R(x) coincides with the shallowest evidence depth "in any bounded-fan-in circuit" for the task. However, carry-lookahead and ripple-carry circuits for addition are a counterexample, and App. Q even admits this point. Additionally, Lemma E.1 is false for generated positions. It treats generated positions as having no input dependence whereas each generated token's embedding depends on the previous position's output.
  1. Experiments do not support claims
  • The main evidence comes from 3.2M param models trained on three synthetic tasks with depth at most 8. At this scale the O(log n) slack in the bounds dominates, so the theory is not tested, as App. J even admits. Nonetheless, the paper presents d(x) as governing CoT budgets in general. Real-world CoT has no canonical rule system, no computable d(x) and none of the controlled structure these tasks rely on. Nothing here supports transfer to that setting.
  • The larger model evidence neither provide any evidence. The 7B finetuned models have 1000 slope with R^2=1000 because the training traces contain exactly one sentence per step. In the few-shot runs, step counts follow the step by step examples. DeepSeek-R1-8B shows no scaling, and Qwen-2.5-7B has random performance.
  • Models are trained with one rule step per CoT token and then forced to answer after k steps, so the "law" k* = d(x) is built into the training.
Questions for authors
  1. Where is the proof of Theorem 3.15? Do its upper and lower bounds hold for the same model class? T1's construction uses poly(n)-bit per-position state, which lies outside M^loc_{L,b}.

  2. In Definition 3.9, what exactly can an exact-match key match? If keys may match full edge content (u, v), Corollary D.4 fails. If they are restricted to single endpoint names, please state this in the definition.

  3. Apps. T and U show that the depth dependence follows the length of the training traces. Is there any experiment where the supervision does not encode depth-proportional length and depth-dependent budgets still emerge?

  4. §4.5 reports ρ = 0.20 / 0.60 / 1.07 and says it "correctly ranks" the families. App. K reports 0.20 / 1.07 / 0.60 and says it does not. Which is correct?

Reviewer_XS5gOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper defines instance serial depth d_R(x): the depth of the shallowest derivation of an instance's answer under a fixed rule system (Def. 3.2). It claims a Transformer upper bound of d_R(x)+O(log n) CoT tokens, or ⌈d_R(x)/L⌉+O(log n) with L layers (Thm. 3.6, Cor. 3.7), and a pointer-chasing lower bound for bounded-state models with exact-match hard lookups (Thm. 3.10, Prop. 3.14), presented together as matching bounds (Eq. 5). Experiments train small Transformers on STCON, addition, and Boolean formulas, regress the minimal stable budget on d_R(x), and use a hidden-state probe to allocate budgets, saving 19.6% of allocated steps on STCON at 100% accuracy (Table 9).

Critical strengths
  1. A concrete, computable notion of instance-level depth. Fixing the rule system makes "difficulty" testable, and Appendix Q's BFS vs. transitive-closure comparison makes clear that the metric is rule-relative.

  2. Strong, honest controls. The mean-matched filler controls (Table 15), self-termination tests (Table 16), the negative BFE savings, and a disjoint-pool rerun (~20% on STCON) make clear what the measurements do and do not show.

Critical weaknesses
  1. The upper-bound proof does not hold under the paper's own model. Definition B.1 says layer ℓ reads layer ℓ−1 of earlier positions, but Lemma B.4 has each position read D_(i−1) at layer ℓ* and write D_i back at the same ℓ*. That requires climbing layers with every token, and the emitted ⟨step⟩ token carries no state; Appendix M.2 notes this same obstruction for C2. Separately, T1 (poly-width state) and T3 (polylog state, hard lookups) cover different model classes, so Eq. 5 does not bound a single quantity, and the trained models use soft attention (transformer.py), outside both. This is a gap in the proof, not proof that no corrected theorem exists.

  2. The experiments do not show that depth governs necessary compute. Removing the length–depth correlation in filler traces flattens the slope (STCON 0.332→0.005, BFE 0.673→0.006) at unchanged accuracy (Table 15), and self-terminated budgets follow training-trace length (Table 16). The units also differ from the theory: one semantic STCON step is n+2 generated tokens (cot_traces.py, eval_min_steps.py), so the "forward passes, not tokens" claim (§4.4) is unsupported, and Table 9 sums allocated caps (eval_e2e_budget.py) rather than tokens actually emitted, so it does not show real savings.

Questions for authors
  1. What layer-indexed construction implements Lemma B.4 under Definition B.1, given that ⟨step⟩ carries no state?
  2. Which single model class supports both sides of Eq. 5, and which assumptions hold for the soft-attention models you trained?
  3. In Table 9, how many tokens are actually emitted per strategy, and what is the total cost including the probe?
  4. Can §4.3 and §4.5 be reconciled with Appendices I and K? Appendix I shows most slopes above the achievability envelope, and Appendix K says ρ does not order the savings.
Reviewer_YouXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers the problem of deriving upper and lower bounds of the required CoT tokens, T(x), for Transformers as a function of the serial depth needed to solve a particular instance, called d(x), (and other architectural variables), rather than at the task-level worst case analysis which is what prior work has shown. For the problems considered, d(x) is shown to be computable efficiently. The upper bound shows how T(x) and d(x) are related. They also prove a lower bound for a restricted class of Transformers for the pointer-chasing task. The experimental results show that the depth needed by the model to solve a task can be well correlated with the theoretically obtained d(x), and that with an additional module, the model itself can estimate the needed CoT tokens and lead to some inference compute savings.

Critical strengths
  1. The paper tackles an interesting question. The bounds should indeed be instance-specific rather than at the task-level as there can be a very large range of problems for a task in terms of the serial depth needed to solve it.

  2. I liked the formalization for computing d(x) and showing that it can be performed efficiently.

  3. Both the upper and lower bounds are intuitive, and the upper bound does seem to apply to commonly used Transformer models.

  4. The experiment that shows inference compute savings using an additional module to estimate the required CoT budget is interesting and should be of value practically.

Critical weaknesses
  1. While I agree that knowing the bounds is interesting theoretically, I find that it should be straightforward to observe that easier problems need fewer CoT tokens than harder problems.

  2. The upper bound only says that there exists some Transformer that makes the bound valid. It is not clear how easy it is to learn it.

  3. The lower bound applies to only one problem, and appears to have a lot of restrictions on the architecture of the Transformer, which are not applicable in practice.

  4. One important issue is with the experiments. The supervision signals are the CoT steps that are correlated with d(x). So, it may not at all be interesting that the trained Transformer needs a CoT budget that is correlated with d(x).

Also, the experiment in Appendix U is important here that shows that this correlation disappears when the supervision signal does not tell the model how many steps to use. I hope I am understanding this correctly, but this makes the experimental results underwhelming.

Related to the above, the authors may be interested in this paper, where the Transformer is not told while training how many steps are needed to solve the problem, but still appears to allocate compute in a meaningful manner: Moosa et al., "Understanding Dynamic Compute Allocation in Recurrent Transformers", ICML 2026

  1. I do think the writing needs to be improved significantly. It may be due to the LLMs writing parts of the paper and/or because I am not an expert in developing this type of theory, but it is quite difficult to follow the notation and explanations of the various definitions and theorems. It would be good to provide intuitions, if possible.
Questions for authors

It appears that all the proofs were generated using AI and I have not gone through all the proofs in full detail. The authors do say that they have ensured that the proofs spanning more than a dozen pages are correct.

But I noticed that for the upper bound theorem, Theorem 3.6 on page 5, do the authors assume that the Transformer is a recurrent model when they write Di+1=Φx(Di)D_{i+1} = \Phi_x(D_i)? I am confused by this. In the appendix, where the full proof is provided, In Definition B.1 it says correctly that for causal attention "position p at layer ℓ reads layer-(ℓ−1) outputs of positions ≤ p". But then Lemma B.4 appears to be incorrect to me as it says something like position p at layer l reads layer l output of the previous position. Can you please provide clarification on this?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.