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

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