- 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
- The question of per-instance CoT budget instead of per-class budget is relevant
Critical weaknesses
- 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.
- 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
-
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}.
-
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.
-
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.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?