acceptodds
Withdrawn from ICLR 2027

THE ILLUSION OF COMPUTATION: A CIRCUIT-COMPLEXITY ACCOUNT OF STATE-TRACKING FAILURE

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Large language models (LLMs) reliably fail at core algorithmic tasks — multidigit arithmetic, sorting, recursive procedures — commonly attributed to insufficient scale or context length. We argue these failures are consistent with a proven computational ceiling: bounded-precision transformers are contained in TC0, and parallel-scan state-space models (SSMs) inherit essentially the same ceiling (one plausible explanation among several, not an automatic theory-topractice inference, Section 3.2). We derive a falsifiable budget prediction — a task is out of reach unless realized scratchpad depth Drealized meets task-inherent depth Dtask — and test it with a benchmark that independently manipulates Dtask and Drealized: three depth-parameterized task forms under four prompting conditions, K ∈ 2, . . . , 128, paired with linear probing, across three open-weight transformers (Qwen2.5-0.5B/3B/14B) and an SSM control (Mamba-2.8B). Every CoT-based condition collapses to near-floor accuracy by moderate K, but the mechanism differs by task form and size: modular’s failure is genuine arithmetic error surviving full format compliance at 3B/14B, not the compliance collapse driving 0.5B’s failure; register shows the smooth per-step decay our auxiliary noise model predicts; and permutation is clearest at 14B, where tool-augmented accuracy reaches near-ceiling (1.00 for K ≤ 16) while all CoT-based conditions stay at floor — direct evidence of a genuine propagation failure, not a miscalibrated task. Linear probing shows hidden states retain decodable state well past behavioral collapse, most durably for permutation. Mamba-2.8B replicates the same form-dependent split, evidence the ceiling is architecture-general rather than attention-specific

Primary area:
learning theory
Keywords:
algorithmic reasoning, transformers, state space models, computational limits, TC0, chain of thought, scratchpad depth, arithmetic, sorting, recursion, reasoning failure, Mamba, language models, effective depth, linear probing. Provide your feedback on BizChat

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_Hi4XOpenReview ↗
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 TC0\mathrm{TC}^0, 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 KK, 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
  1. 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.

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

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

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

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

The paper investigates why LLMs struggle to maintain and update state across sequential computations. It proposes an explanation based on existing circuit-complexity bounds and evaluates modular arithmetic, register simulation, and permutation composition across three transformer sizes and a Mamba model. The results reveal different failure patterns across tasks, which the authors interpret as evidence of limitations in reliable state propagation.

Critical strengths
  • I find the problem interesting and well motivated, since understanding failures in sequential computation is important for assessing LLM reliability.
  • I also appreciate the breadth of the empirical study, which examines several tasks, model sizes, and prompting conditions.
Critical weaknesses
  • In my opinion, the contribution is limited. Much of Sections 2 and 3 presents established theoretical results, so the main contribution appears to be the benchmark and its connection to those results. However, I am not convinced that the experiments establish this connection convincingly enough to provide a substantial new explanation of state-tracking failure.
  • More specifically, I am unsure whether the measurements in Section 4.2 establish the proposed mismatch between task depth and model depth. A task may contain many instructions even when fewer sequential steps would suffice to obtain the answer. Similarly, counting the updates written by the model tells us how long its trace is, but does not directly measure how much sequential computation it performs internally. Consequently, I find it difficult to distinguish the proposed architectural explanation from other execution difficulties.
Questions for authors

Could you clarify how the number of state updates specified in a task and the number of update lines written by the model support the claimed mismatch between required and realized computational depth in Section 4.2?

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

The paper argues that LLMs fail at multi-step algorithmic tasks because they cannot carry exact state from one step to the next, not because of insufficient scale or context length. It bases this on known circuit-complexity results:

Bounded-precision transformers (Merrill & Sabharwal, 2023b) and parallel-scan SSMs (Merrill et al., 2024) lie in TC⁰. Chain-of-thought (CoT) adds expressive power in proportion to the number of generated steps (Merrill & Sabharwal, 2024).

From this the authors derive a "budget" prediction: a task that needs DtaskD_{task} sequential steps is out of reach unless the model writes at least Drealized≥DtaskD_{realized} \ge D_{task} steps.

The benchmark has three tasks with depth K∈2,…,128K \in {2,\dots,128}:

iterated affine updates modulo 97; register-machine simulation; composition of permutations of six elements.

Each task is run under four prompting conditions: no scratchpad, free CoT, a forced trace with one line per step, and code execution. The models are Qwen2.5-0.5B/3B/14B-Instruct and Mamba-2.8B (base).

Critical strengths
  • The question matters, and testing circuit-complexity theory against a controlled benchmark is a worthwhile goal.
  • The design keeps the task family fixed while changing depth, and it separates three kinds of realized depth: DpromptedD_{prompted}: the number of steps the prompt asks for. DemittedD_{emitted}: the number of steps the model writes. DvalidD_{valid}: the number of steps that are correct from the start.
  • Separating format failure (0.5B stops writing the trace) from computation failure (3B/14B write every step but get them wrong) is a useful diagnostic that many benchmark papers skip.
Critical weaknesses
  1. The paper is highly suspicious to be written by pure AI without human proofreading. Evidence:

Some key issues I found that indicates that the paper is AI written:

"modular’s failure is genuine arithmetic error surviving full format compliance at 3B/14B, not the compliance collapse driving 0.5B’s failure" in the abstraction has no context at all... They are AI generated content.

“Two implementation bugs, both disclosed as corrections rather than footnotes since they changed reported numbers, were found and fixed during the pilo“ L285-286, this is implementation.

Also, these tables are all obviously AI-written text

PointLinesQuote
Describes itself as a pilotL59–61"We report a completed pilot (Section 5)… with only a frontier closed-model arm still to be run and marked explicitly as pending"
Frontier model "not started"L278–280"Table 1's remaining row (a frontier closed model) is not yet started."
L300 (Table 1)"Frontier closed model … Not started"
WMF-AM comparison "not yet done"L454–456"Comparison with WMF-AM, not yet done… we have neither yet, and defer"
[TODO: repo URL]L501–502 (Reproducibility Statement)"pipeline are released at [TODO: repo URL]"
Claims the code "is released"L199–200 (Sec. 4)"Full implementation is released alongside this paper"
  1. The theory is not sufficiently significant
  • The theory allows the failures but doesn't predict them. Composing 128 steps takes log⁡2128=7\log_2 128=7log2​128=7 rounds, well within the 24–48 layers these models have, and the models already fail at K=2K=2K=2.

  • One task is mislabeled. The modular task can be solved in TC⁰ via a closed formula. The paper's claim "Sorting is NC¹ … ruled out" mixes up "in NC¹" with "NC¹-hard." Only the permutation task is truly beyond TC⁰, yet modular fails just as badly, so the results don't follow the theory.

  • The failure is on single operations. Models get only the trivial first step right (Dvalid≈1D_{\text{valid}}\approx1Dvalid​≈1), so they fail the first real operation rather than losing state over many steps.

Questions for authors

Do you agree that the modular task (fixed m = 97) is in TC⁰? If so: How does Proposition 1 explain the model's failure on it?

What in your theory distinguishes it from the permutation task? What is single-step accuracy (K=1K = 1, from a random state given in the prompt) for each task and model, and how does accuracy at depth KK compare with p1Kp_1^K?

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

Related papers

Discussion (0)

Sign in to comment.