- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies state-tracking failures of large language models on arithmetic, sorting, and recursive tasks. Drawing on circuit-complexity results, the authors note that a log-precision, no-CoT single-pass Transformer lies in , that CoT extends expressive power only up to its generated length, and that parallel-scan SSMs face similar limits. They propose a depth-parameterized benchmark that fixes task semantics across modular accumulation, register-machine simulation, and permutation composition, sweeps depth , and separates task-inherent depth from realized depth under four conditions: no scratchpad, free CoT, forced full-trace CoT, and tool augmentation. Linear probes are paired with behavioral accuracy. Experiments cover Qwen2.5-0.5B/3B/14B-Instruct and Mamba-2.8B. Results show CoT conditions collapse with depth, modular and permutation remain hard for 3B/14B even with compliance, register improves with scale, 14B tool augmentation succeeds on permutation while CoT fails, probes retain hidden-state information beyond behavioral collapse, and Mamba shows similar form dependence. The contribution is a testable translation of complexity bounds, a benchmark with pilot evidence, and disclosed corrections. Limitations include limited architecture coverage, one base SSM checkpoint, no positive control, task-familiarity confounds, and the unrun frontier closed model.
Critical strengths
-
The paper converts circuit-complexity upper bounds into testable predictions over a depth sweep, and clearly separates the necessary budget condition from the auxiliary per-step error envelope.
-
The authors disclose and fix implementation bugs that affected numbers, report compliance rates, degenerate instances, retry results, and residuals, and release task generators, prompt templates, scoring code, a tool sandbox, and the probing pipeline, giving strong reproducibility.
Critical weaknesses
-
Architecture and experimental coverage are limited. The SSM arm has only one Mamba-2.8B base checkpoint, confounded with the Qwen instruct models; there is no looped or universal transformer positive control; free-CoT realized-depth estimation is an unvalidated heuristic; decoding is greedy only; the frontier closed model is not run; the three task forms are confounded by operation familiarity, with the register form resembling variable mutation in code, and permutation’s low- floor possibly reflecting task calibration; and why tool-augmented gains on permutation far exceed those on modular and register remains unexplained. These limitations weaken the claims of architecture generality and the robustness of the conclusions.
-
The manuscript exhibits clear signs of being incomplete. The final row of Table 1 lists a "Frontier closed model" without specifying the actual model used, and its status is marked as "Not started," implying that the authors likely failed to complete the evaluation for this model. Furthermore, the "REPRODUCIBILITY STATEMENT" contains an obvious formatting error—red text reading "[TODO: repo URL]"—and page 9 explicitly states, "Comparison with WMF-AM, not yet done." There are also multiple other indications that the authors did not fully carry out the experiments claimed in the paper.
Questions for authors
-
Could the authors add SSM checkpoints across multiple scales and an instruction-tuned SSM to separate architectural effects from the base-versus-instruct training confound? Could you add a looped/universal transformer or ACT positive control to test whether the theory-implied fix of making step count input-dependent actually works?
-
Can the authors provide complete experimental details and supply the missing sections in their response? The evidence regarding these incomplete parts appears quite solid; failing to include them reflects a lack of responsibility toward their own paper. I particularly hope for a direct response from the authors on this point.