The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling

# A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling
Source: [https://arxiv.org/html/2606.29278](https://arxiv.org/html/2606.29278)
## The Complexity Ceiling Benchmark: A Multi\-Domain Evaluation of Sequential Reasoning Under Depth Scaling

###### Abstract

We introduce the Complexity Ceiling Benchmark \(CCB\), a controlled evaluation of how language\-model reasoning decays as the number of required sequential steps grows\.CCBfixes the semantic content of a task and varies only its depthN∈\{5,…,50\}N\{\\in\}\\\{5,\\dots,50\\\}across three structurally distinct regimes: grounded spatial state\-tracking, abstract symbolic pointer manipulation, and transitive relational inference\. Across 6,000 trials over five frontier and open\-weight LLMs we find a consistent pattern of geometric per\-step decay with widely separated domain ceilings: on the first two regimes the strongest models retainpd\>0\.92p\_\{d\}\>0\.92acrossN=50N\{=\}50; on the third every model collapses byN=5N\{=\}5, with the best model’s 50%\-success horizon atH0\.5≈4\.7H\_\{0\.5\}\{\\approx\}4\.7steps despitepd=0\.863p\_\{d\}\{=\}0\.863\. A trace\-level metric \(TFBC\) shows that14\.5%14\.5\\%of correct answers across the benchmark are reached via incorrect intermediate reasoning\. Forced verbose state\-tracking does not move the ceiling \(McNemarp=1\.000p\{=\}1\.000\), and the mean step at which reasoning first diverges,k∗k^\{\*\}, predicts within\-domain accuracy better than parameter count\.CCBand the geometric decay model together reduce a model’s long\-horizon reasoning profile to one interpretable number per task family\.

Reasoning, Benchmarks, LLMs, Depth Scaling, Geometric Decay

5515152525353545450252550507575100100DepthNNAccuracy \(%\)D1 Spatial state\-tracking5515152525353545450252550507575100100DepthNND2 Symbolic pointer tracking5515152525353545450252550507575100100H0\.5≈4\.7H\_\{0\.5\}\{\\approx\}4\.7DepthNND3 Transitive social logicClaude 3\.7Gemini 2\.0FDeepSeekGPT\-4o\-miniLLaMA\-3\.3Figure 1:The Complexity Ceiling\.Accuracy as a function of depthNNacross three structurally distinct reasoning regimes, with semantic content held fixed\. Markers: empirical accuracy atn=40n\{=\}40trials per cell\. Thin solid curves in D1 and D2: fitted geometric model100⋅pdN100\{\\cdot\}p\_\{d\}^\{N\}for the top frontier model \(Gemini in D1, Claude in D2\)\. On D1 and D2 frontier models track the geometric decay withpd∈\[0\.92,0\.99\]p\_\{d\}\{\\in\}\[0\.92,0\.99\], leaving meaningful accuracy atN=50N\{=\}50\. On transitive social logic \(D3\) every model collapses pastN=5N\{=\}5regardless of capability tier; even the best model’s50%50\\%\-success horizon isH0\.5≈4\.7H\_\{0\.5\}\{\\approx\}4\.7steps\. Solid lines: frontier or competitive open\-weight; dashed: smaller models\.6,0006\{,\}000trials total\.## 1Introduction

When a language model fails on a long reasoning task, current benchmarks cannot tell us why\. The model may lack knowledge, misread the prompt, exhaust its context window, or simply lose its place across the intermediate steps\. These failure modes have different remedies and different implications for deploying LLMs as agents, but aggregate accuracy on a fixed\-difficulty benchmark sees only the union: a single number that says the model got it wrong\. The most consequential of these modes for agentic use; the cumulative loss of coherence as the number of sequential steps grows; is also the one least visible to such benchmarks\([3](https://arxiv.org/html/2606.29278#bib.bib3),[12](https://arxiv.org/html/2606.29278#bib.bib12)\)\.

This paper treats depth as the controlled experimental variable\. Figure[1](https://arxiv.org/html/2606.29278#S0.F1)shows the central result of doing so\. The Complexity Ceiling Benchmark \(CCB\) holds task semantics fixed and sweeps the number of required reasoning stepsNNfrom 5 to 50 across three structurally distinct regimes: grounded spatial state\-tracking \(D1\), abstract symbolic pointer manipulation \(D2\), and transitive relational inference \(D3\)\. Six thousand trials over five frontier and open\-weight LLMs reveal a consistent pattern; per\-step retention decays geometrically inNN; and a striking dissociation between domains\. On D1 and D2 the strongest models hold retention probabilitypd\>0\.92p\_\{d\}\>0\.92across the full depth range, leaving meaningful accuracy atN=50N\{=\}50\. On D3, every model collapses pastN=5N\{=\}5, regardless of capability tier; the best evaluated model’s 50%\-success horizon is onlyH0\.5≈4\.7H\_\{0\.5\}\{\\approx\}4\.7steps\. Tracing the intermediate reasoning adds a second result that aggregate accuracy hides: across the benchmark,14\.5%14\.5\\%of correct answers come from traces that diverged from the canonical reasoning, and the share is highest on the hardest domain\.

#### Contributions\.

The geometric decay model and the trace\-level metric we introduce together let us summarise a \(model, task\-family\) pair with two numbers: a per\-step retention probabilitypdp\_\{d\}and a mean trace\-divergence stepk∗k^\{\*\}\. Both connect to deployment:pdp\_\{d\}feeds the horizon\-length framework ofSinha et al\. \([12](https://arxiv.org/html/2606.29278#bib.bib12)\)and determines the depth at which sustained accuracy crosses any chosen threshold, andk∗k^\{\*\}predicts within\-domain accuracy more faithfully than parameter count\. The findings in this paper are scoped to vanilla autoregressive inference on the five evaluated models; evaluating process\-supervised and tool\-augmented systems is the obvious next step and is one of the usesCCBis built to serve\.

## 2Related Work

#### Depth\-scaling and compositional generalisation\.

Most prior work treats reasoning failure as an aggregate property of a task\. SCAN\([8](https://arxiv.org/html/2606.29278#bib.bib8)\)and BIG\-Bench\([14](https://arxiv.org/html/2606.29278#bib.bib14)\)probe compositional generalisation at roughly constant difficulty, providing a strong test of out\-of\-distribution generalisation but limited leverage for a scaling analysis\. CLUTRR\([13](https://arxiv.org/html/2606.29278#bib.bib13)\)comes closest to our setting; multi\-hop relational reasoning over kinship graphs; and motivates D3, but gives only final\-answer judgements and a small fixed range of hops\.Dziri et al\. \([3](https://arxiv.org/html/2606.29278#bib.bib3)\)showed transformers unroll memorised subgraphs with catastrophic failure at compositional out\-of\-distribution depths;Hou et al\. \([5](https://arxiv.org/html/2606.29278#bib.bib5)\)tied this to cumulative state\-tracking load; SokoBench\([11](https://arxiv.org/html/2606.29278#bib.bib11)\)isolates planning depth in Sokoban, TopoBench\([9](https://arxiv.org/html/2606.29278#bib.bib9)\)shows structured state aids reasoning\.CCBdiffers from all of these by making depth a continuous parametric axis across three heterogeneous domains and by recovering a single one\-parameter summary statistic that lets us compare*how*a model fails, not just whether it does\.

#### Trace\-level evaluation and structural uncertainty\.

A parallel line of work evaluates the reasoning chain itself rather than the answer\. ROSCOE\([4](https://arxiv.org/html/2606.29278#bib.bib4)\), ReCEval\([10](https://arxiv.org/html/2606.29278#bib.bib10)\), and MME\-CoT\([6](https://arxiv.org/html/2606.29278#bib.bib6)\)introduce trace\-quality metrics, but mostly rely on LLM\-as\-judge or learned rubrics whose own reliability is contested\([1](https://arxiv.org/html/2606.29278#bib.bib1)\)\.CCBsidesteps this by comparing against a deterministically generated canonical trace; theTFBCmetric below requires no external scorer\.

#### Process supervision and horizon connection\.

Finally, ourpdNp\_\{d\}^\{N\}model is the empirical counterpart of the horizon\-length framework ofSinha et al\. \([12](https://arxiv.org/html/2606.29278#bib.bib12)\), which derives an effective task horizonHs≈ln⁡\(s\)/ln⁡\(pd\)H\_\{s\}\{\\approx\}\\ln\(s\)/\\ln\(p\_\{d\}\)from per\-step accuracy\.Cobbe et al\. \([2](https://arxiv.org/html/2606.29278#bib.bib2)\)showed that process\-level supervision shifts the relevant quantity; recursive scaffolds\([16](https://arxiv.org/html/2606.29278#bib.bib16)\)and fast\-slow recurrence\([15](https://arxiv.org/html/2606.29278#bib.bib15)\)target the same bottleneck through architecture\.Kim et al\. \([7](https://arxiv.org/html/2606.29278#bib.bib7)\)argue that autoregressive token ordering is itself an inductive bias on what reasoning patterns are accessible\. Extended discussion appears in Appendix[C](https://arxiv.org/html/2606.29278#A3)\.

## 3Benchmark Design

CCBconsists of three task domains, a deterministic generator that produces ground\-truth reasoning traces, a strict parser\-based pipeline, and a one\-parameter decay model fit per \(model, domain\) cell\. The components are designed jointly: the failure taxonomy isolates the events the decay model is meant to describe, the parser produces the event counts the likelihood consumes, and the trace metric below operates on the same parsed structure\. Figure[2](https://arxiv.org/html/2606.29278#S3.F2)summarises the end\-to\-end evaluation flow, from dataset generation through the strict parsing hierarchy that routes each trial into one of the disjoint outcome categories used by the decay model\.

Dataset Generation\(N=5​…​50N=5\\dots 50\)LLM Inference\(T=0T=0\)Regex Trace ParsingFormat OK?Format Fail / TruncatedAns OK?CorrectComputek∗k^\{\*\}\(TFBC\)Constraint / Reasoning FailNoYesYesNo

Figure 2:The CCB evaluation pipeline\.LLM outputs are routed through a strict parsing hierarchy to prevent confounding reasoning decay with structural output deviations\. Constraint violations are explicitly separated from format failures\.#### Domains\.

The three domains share an experimental contract; semantic content held fixed, depthNNvaried over\{5,10,…,50\}\\\{5,10,\\dots,50\\\}; but stress structurally distinct facets of long\-horizon reasoning, together approximating a minimal basis for the regimes most often encountered in agentic settings: grounded spatial, abstract symbolic, and nested relational\.*D1 Alien Grid*is a3×33\{\\times\}3grid subjected toNNdiscrete transformations \(Rotate,Swap Corners,Shift\) under a grid\-integrity constraint preventing entity collision; it tests grounded spatial state\-tracking, and its errors compound deterministically because a misplaced entity at stepkkinvalidates every state after it\.*D2 Symbolic Pointer Tracking*asks the model to maintain seven variablesAA–GGholding distinct digits 0–9 underNNcyclic\-shift and modular\-arithmetic operations subject to an assignment\-uniqueness constraint; its dominant failure mode is register corruption via illegal re\-assignment, which accounts for69\.5%69\.5\\%of D2 failures and reflects the difficulty of maintaining disjoint symbolic mappings over long contexts\.*D3 Social Logic*runs a diplomatic graph over ten agents under transitive\-closure rules: at each ofNNupdate steps a new alliance or rivalry edge is added, the closure is recomputed, and all implied relationships are updated\. The model is queried on the final pairwise state in a Theory\-of\-Mind\-style format \(“what does agentiibelieve about agentjj?”\), and must maintain global pairwise consistency overO​\(n2\)O\(n^\{2\}\)relationships per step\. Its dominant failure mode is*cascade collapse*; a single misclassified edge propagates by transitivity to every reachable node and is irrecoverable within the context window, which is what makes D3 a structurally distinct difficulty regime rather than a harder version of D1 or D2 \(Section[4](https://arxiv.org/html/2606.29278#S4)\)\. We evaluate each domain atn=40n\{=\}40independently seeded trials per \(model, depth\) cell, for2,0002\{,\}000trials per domain and6,0006\{,\}000in total\. All inference is atT=0T\{=\}0via OpenRouter, onclaude\-3\.7\-sonnet,gemini\-2\.0\-flash\-001,deepseek\-chat,gpt\-4o\-mini, andllama\-3\.3\-70b\-instruct\. Reasoning\-specialised models \(o1/o3, DeepSeek\-R1\) were not accessible at submission time and are addressed in Section[5](https://arxiv.org/html/2606.29278#S5)\.

#### Failure taxonomy and parser design\.

Every trial falls into one of six disjoint categories:*Correct*\(final answer and every step exact\),*Reasoning*\(parses cleanly but diverges from the canonical trace at some stepk∗≤Nk^\{\*\}\{\\leq\}N\),*Constraint*\(violates a structural task rule\),*Format*\(unparseable\),*Truncation*\(output ends mid\-stream\), and*API*\(network error, auto\-retried\)\. Only the first three carry information about per\-step retention; the rest are treated as missing data\. The parser is regex\-based and deliberately so: AST\-based parsing and LLM\-as\-judge scoring were both considered and rejected to keep the evaluation deterministic and reproducible, and to remove any dependency on an external scoring model whose own reliability would have to be defended\. The parser prioritises precision over recall; minor format deviations are flagged as Format failures rather than silently corrected, so the resultingpdp\_\{d\}estimates are mildly conservative for models with idiosyncratic output styles\. This is the bias direction we want because it cannot inflate reported accuracy orpdp\_\{d\}\. A manual audit of 150 edge\-case outputs found no false positives in correctness classification and a small \(≈2%\\approx 2\\%\) false\-negative rate from non\-standard separators\. The six\-way classification is invariant to reordering of unrelated key/value pairs and to whitespace differences, so layout\-only output changes do not affect the reportedk∗k^\{\*\}distributions\.

#### The TFBC metric\.

Correct final answers do not imply correct intermediate reasoning\. We define*Trace First Branch Correct*\(TFBC\) to flag any trial whose final answer matches the ground truth but whose trace first diverges from the canonical reasoning at some stepk∗\>0k^\{\*\}\{\>\}0\. Algorithm[1](https://arxiv.org/html/2606.29278#alg1)walks the trace from step 1 and returns the first divergence; for incorrect parseable trials,k∗k^\{\*\}records the depth at which the model’s working state first decohered\. As a concrete illustration, a typicalk∗=2k^\{\*\}\{=\}2event on D1 atN=10N\{=\}10has ground truth Step 2=\[\[7,4,1\],\[8,5,2\],\[9,6,3\]\]=\[\[7,4,1\],\[8,5,2\],\[9,6,3\]\]\(a90∘90^\{\\circ\}clockwise rotation\) and model output\[\[3,2,1\],\[6,5,4\],\[9,8,7\]\]\[\[3,2,1\],\[6,5,4\],\[9,8,7\]\]\(a horizontal flip\); the trace diverges immediately at the first transformation and the error propagates deterministically through the rest of the trial, even when the final answer happens to coincide by chance\. Three human annotators independently labelled traces against the automated extractor on subsets of each domain, with Cohen’sκ\\kappaof0\.9770\.977\(D1,n=50n\{=\}50\),0\.9780\.978\(D2,n=50n\{=\}50\), and0\.9380\.938\(D3,n=65n\{=\}65\), all above the conventional defensibility threshold of0\.800\.80\. D3 admits multiple valid reasoning paths in principle; a targeted audit of 20 randomly sampled D3 TFBC cases found no genuine alternative\-path correctness, supporting the lucky\-guess interpretation\. Constraint violations and TFBC events are measured on different conditioning sets \(TFBC is defined only over parseable correct outputs; constraint violations are a disjoint failure category\) and so the high D2 constraint\-violation share and the per\-model TFBC rates in Table[1](https://arxiv.org/html/2606.29278#S4.T1)are not in tension\.

Algorithm 1TFBC andk∗k^\{\*\}extractor\.1:Input:model trace

TT, ground\-truth trace

GG, depth

NN
2:

L←ParseSteps​\(T\)L\\leftarrow\\text\{ParseSteps\}\(T\);

k∗←−1k^\{\*\}\\leftarrow\-1
3:if

\|L\|<N\|L\|<Nand missing answerthen

4:returnFormat Error

5:endif

6:for

i=1i=1to

NNdo

7:if

L​\[i\]≠G​\[i\]L\[i\]\\neq G\[i\]then

8:

k∗←ik^\{\*\}\\leftarrow i;break

9:endif

10:endfor

11:

is\_TFBC←\(k∗≠−1\)∧\(Amodel=Atrue\)\\text\{is\\\_TFBC\}\\leftarrow\(k^\{\*\}\\neq\-1\)\\land\(A\_\{\\text\{model\}\}=A\_\{\\text\{true\}\}\)
12:return

k∗k^\{\*\},is\_TFBC

#### Geometric decay model\.

Letpdp\_\{d\}denote the probability that the model correctly computesSk→Sk\+1S\_\{k\}\{\\to\}S\_\{k\+1\}given thatSkS\_\{k\}was maintained\. Under independence of per\-step errors \(Assumption[1](https://arxiv.org/html/2606.29278#Thmassumption1)\),

P​\(correct∣N\)=∏i=1NP​\(stepi​correct\)=pdN\.P\(\\text\{correct\}\\mid N\)\\;=\\;\\prod\_\{i=1\}^\{N\}P\(\\text\{step\}\_\{i\}\\text\{ correct\}\)\\;=\\;p\_\{d\}^\{N\}\.\(1\)The expressionpdNp\_\{d\}^\{N\}is a discrete survival function with constant per\-step hazard1−pd1\{\-\}p\_\{d\}; the interpretation we want is that a single free parameter per \(model, domain\) cell captures both the per\-step failure rate and the resulting horizon at which any chosen success threshold is crossed\. We fitpdp\_\{d\}per cell by maximising the binomial log\-likelihood∑N\[cN​ln⁡pdN\+\(n−cN\)​ln⁡\(1−pdN\)\]\\sum\_\{N\}\\bigl\[c\_\{N\}\\ln p\_\{d\}^\{N\}\+\(n\{\-\}c\_\{N\}\)\\ln\(1\{\-\}p\_\{d\}^\{N\}\)\\bigr\]overcNc\_\{N\}correct trials out ofn=40n\{=\}40at each depth, constrained topd∈\[0\.5,1\.0\]p\_\{d\}\{\\in\}\[0\.5,1\.0\]; 95% confidence intervals are from2,0002\{,\}000parametric bootstrap resamples\. The lower bound keeps the estimator in a meaningful regime: models driven to it \(GPT\-4o\-mini and LLaMA on D3\) should be read as exhibiting no statistically identifiable step\-retention rather than as literal50%50\\%per\-step\.

###### Assumption 1\(Independent per\-step failures\)\.

The probability of a state\-transition error at stepkkis independent of whether an error occurred at stepk−1k\{\-\}1\.

S0S\_\{0\}S1S\_\{1\}S2S\_\{2\}⋯\\cdotsSNS\_\{N\}E1E\_\{1\}E2E\_\{2\}pdp\_\{d\}pdp\_\{d\}pdp\_\{d\}pdp\_\{d\}1−pd1\{\-\}p\_\{d\}1−pd1\{\-\}p\_\{d\}Cascading failure\(correlated in reality\)Figure 3:The state\-retention process of Assumption[1](https://arxiv.org/html/2606.29278#Thmassumption1)\.Under independence, a single step error transitions the system to an absorbing failure state with per\-step probability1−pd1\{\-\}p\_\{d\}\. In reality, errors at stepk∗k^\{\*\}corrupt allk\>k∗k\{\>\}k^\{\*\}\(Remark[1](https://arxiv.org/html/2606.29278#Thmremark1)\), so the true decay is faster thanpdNp\_\{d\}^\{N\}predicts\.
#### Alternative decay models\.

Assumption[1](https://arxiv.org/html/2606.29278#Thmassumption1)is wrong in a known direction \(Figure[3](https://arxiv.org/html/2606.29278#S3.F3)\)\. Autoregressive transformers are not Markov: an error at stepk∗k^\{\*\}corrupts context for allk\>k∗k\{\>\}k^\{\*\}, so per\-step errors are positively correlated and Equation[1](https://arxiv.org/html/2606.29278#S3.E1)tends to*overestimate*sustained accuracy\. The TFBC phenomenon \- partial recovery from a corrupted trace to a correct final answer \- softens but does not eliminate this bias, and we treatpdNp\_\{d\}^\{N\}as an optimistic envelope throughout\. We considered two alternative forms before adopting the geometric model: an acceleratingpdNγp\_\{d\}^\{N^\{\\gamma\}\}that would capture attention fatigue, and a linear1−λ​N1\{\-\}\\lambda Ndrift\. The linear form fails to capture the non\-linear collapse observed at moderateNN; the accelerating form adds a free parameter without empirical motivation in theN≤50N\{\\leq\}50regime\. Across all three domains the one\-parameter geometric form fits without exception and explains\>90%\>90\\%of accuracy variance on D1 and D2 \(a residual analysis confirms no systematic structure in the depth\-wise residuals\)\. Formal AIC/BIC selection between these formulations beyondN=50N\{=\}50, where positional\-embedding saturation may shift the dominant failure mechanism, is left for future work\.

#### Horizon connection\.

The decay model also feeds the horizon\-length analysis ofSinha et al\. \([12](https://arxiv.org/html/2606.29278#bib.bib12)\): for minimum success thresholdss, the effective task horizon isHs≈ln⁡\(s\)/ln⁡\(pd\)H\_\{s\}\{\\approx\}\\ln\(s\)/\\ln\(p\_\{d\}\)\. For Claude on D3 withpd=0\.863p\_\{d\}\{=\}0\.863,H0\.5≈4\.7H\_\{0\.5\}\{\\approx\}4\.7steps, which matches both the depth at which observed accuracy crosses50%50\\%and the meank∗=4\.30k^\{\*\}\{=\}4\.30on incorrect D3 trials\. The empiricalpdp\_\{d\}thus has a deployment\-facing reading: the depth at which a model’s expected accuracy on a task family falls below any chosen threshold\.

## 4Results

Table[1](https://arxiv.org/html/2606.29278#S4.T1)summarises all 6,000 evaluations and Figure[1](https://arxiv.org/html/2606.29278#S0.F1)shows the depth\-resolved accuracy\. The data support three claims: per\-step retention decays geometrically across all five models and three domains; the D3 ceiling is qualitatively different from the D1/D2 ceiling and is not movable by prompt\-level intervention; and the trace\-divergence stepk∗k^\{\*\}ranks models more faithfully within domain than parameter count or aggregate accuracy\.

Table 1:CCBmaster results\.Aggregate accuracy, the geometric step\-retention MLEpdp\_\{d\}, and the trace\-level lucky\-guess rateTFBC, per \(model, domain\) cell\. Best per domain inbold; per\-depth tables with 95% bootstrap CIs are in Appendix[A](https://arxiv.org/html/2606.29278#A1)\.†At the optimiser lower bound; no statistically identifiable step\-retention\.ModelD1 SpatialD2 SymbolicD3 Social LogicAvgAccpdp\_\{d\}TFBCAccpdp\_\{d\}TFBCAccpdp\_\{d\}TFBCFrontier / closed\-weightClaude 3\.718\.2%0\.92921%71\.2%0\.9878%6\.2%0\.86356%31\.9%Gemini 2\.0F22\.0%0\.9301%30\.0%0\.95029%3\.2%0\.73662%18\.4%GPT\-4o\-mini1\.5%0\.68817%1\.2%0\.63420%0\.2%0\.500†–1\.0%Open\-weightDeepSeek19\.8%0\.9246%31\.3%0\.95512%2\.0%0\.68413%17\.7%LLaMA\-3\.31\.3%0\.6340%4\.3%0\.76718%0\.0%0\.500†–1\.9%D1 Alien Grid5101520253035404550DepthNNClaude582515820101581510Gemini6555351018101883DeepSeek7043231023810103GPT\-4o\-m1033LLaMA13D2 Symbolic Pointers5101520253035404550DepthNNClaude98908568805870585355Gemini5553504325202351018DeepSeek38304553303530182313GPT\-4o\-m13LLaMA403D3 Social Logic5101520253035404550DepthNNClaude35558335Gemini33DeepSeek20GPT\-4o\-m3LLaMA0%50%100%AccuracyFigure 4:Per\-depth accuracy across models and domains\.Rows are models, columns are depthN∈\{5,…,50\}N\{\\in\}\\\{5,\\dots,50\\\}, cells show observed accuracy \(%\), darker = higher\. The qualitative difference between domains is immediate: D1 and D2 retain non\-trivial gradients at largeNNfor frontier models, while D3 is essentially a single column of non\-zero values atN=5N\{=\}5\. The view complements Table[1](https://arxiv.org/html/2606.29278#S4.T1)\(which aggregates across depths\) and Figure[1](https://arxiv.org/html/2606.29278#S0.F1)\(which shows decay curves\)\.#### D1 and D2: per\-step retention\.

The decay curves separate the five models cleanly on D1 and D2\. The three strongest models cluster aroundpd∈\[0\.92,0\.93\]p\_\{d\}\\in\[0\.92,0\.93\]on D1 while GPT\-4o\-mini \(pd=0\.688p\_\{d\}\{=\}0\.688\) and LLaMA\-3\.3 \(pd=0\.634p\_\{d\}\{=\}0\.634\) collapse byN=15N\{=\}15\. D1 format adherence is essentially perfect \(0–2% format failures\), so the gap between tiers is in per\-step retention rather than output structure\. D2 sharpens the picture: Claude reachespd=0\.987p\_\{d\}\{=\}0\.987and71\.2%71\.2\\%aggregate accuracy, more than double Gemini \(30\.0%30\.0\\%\) or DeepSeek \(31\.3%31\.3\\%\), and retains55%55\\%accuracy atN=50N\{=\}50\. Claude’s D2 decay curve is visibly shallower than the non\-frontier models’; apd=0\.987p\_\{d\}\{=\}0\.987vs\.pd=0\.634p\_\{d\}\{=\}0\.634gap corresponds to roughly a28×28\{\\times\}lower per\-step error rate, which is exactly the regime in which long\-horizon agentic use becomes plausible\. Of all D2 failures,69\.5%69\.5\\%are constraint violations \- illegal re\-assignments of variables already bound\. A canonical instance is a trace that producesStep 4: var\_A=10,Step 5: var\_B=var\_A\(sovar\_Bshould hold 10 for the rest of the trial\), then writesStep 6: var\_A=15, silently violating uniqueness onvar\_A\. The model is performing arithmetic correctly at each step but failing to keep its bindings disjoint over the longer horizon, which is exactly the failure mode the assignment\-uniqueness constraint was designed to expose\. The occasional non\-monotonic accuracy upticks atN=25N\{=\}25–3535on D1 and D2 are within the per\-cell Clopper\-Pearson half\-CI of±12\\pm 12–16%16\\%atn=40n\{=\}40and do not reflect generator artefacts: operation distributions are stationary acrossNNby construction, and the monotonepdNp\_\{d\}^\{N\}fit explains\>90%\>90\\%of variance on these domains\.

#### D3 \(transitive closure\)\.

D3 is qualitatively different\. Across all five models and ten depth levels,1,9531\{,\}953of2,0002\{,\}000attempts fail\. Only Claude achieves any sustained accuracy \(6\.2%6\.2\\%overall, concentrated atN=5N\{=\}5\); every other model collapses to near\-zero past depth 5 regardless of capability tier\. The mean step at which reasoning first diverges,k∗k^\{\*\}, is uniformly low on D3 \(2\.88–4\.30\) across*all*models, including Claude; which carriesk∗=17\.67k^\{\*\}\{=\}17\.67on D2 yet diverges after only 4\.30 steps on D3 \(Table[3](https://arxiv.org/html/2606.29278#S4.T3)\)\. The uniformity ofk∗k^\{\*\}across models with markedly different capability on other domains is direct evidence that D3 poses a qualitatively distinct difficulty\.

#### Why does D3 collapse early?

This is consistent with the computational structure of D3, which differs from D1 and D2 along three dimensions\. First, transitive closure is not decomposable into independent per\-step updates: a single misclassified edge at stepkkpropagates by transitivity to everykk\-hop reachable node, so unlike D1 \(where errors compound locally\) or D2 \(where bindings can in principle be reread\), the D3 state offers no per\-step recovery path\. Second, the task requires maintaining global pairwise consistency overO​\(n2\)O\(n^\{2\}\)relationships per update, which competes for representational capacity with the linear context attention exposes\. Third; and this is the operative mechanical claim; standard attention flattens sequence hierarchy into linear context, providing no mechanism for the kind of recursive stack management that transitive closure demands; asNNgrows the representations of distinct agents’ relationship sets mix in the attention pattern rather than remaining cleanly partitioned, and the divergence stepk∗∈\[2\.88,4\.30\]k^\{\*\}\{\\in\}\[2\.88,4\.30\]across models of very different capability is consistent with the prediction that this ceiling reflects an architectural rather than a capacity bottleneck\. We offer this as an account of the collapse, not a proof of impossibility: tool\-augmented systems with explicit graph state, or process\-supervised models with step\-level reward, could plausibly move the ceiling\([16](https://arxiv.org/html/2606.29278#bib.bib16),[15](https://arxiv.org/html/2606.29278#bib.bib15)\)\.CCBprobes reasoning without such scaffolding; quantifying whether the ceiling moves when scaffolding is added is one of the uses the benchmark is built to serve\. As a concrete illustration of the failure mode, a representative D3 cascade trace from DeepSeek atN=10N\{=\}10processes the first update correctly but omits a transitive closure propagation at step 2 \(failing to mark a pair as allied that inherits the relation through a newly added edge\); every subsequent pair classification inherits this corruption, and the model has no mechanism for retroactively correcting the state from within the context window\.

Table 2:Per\-domain results with format\-failure rates andpdp\_\{d\}bootstrap 95% CI widths\.The three domains are broken out separately so the per\-domain spread, the uncertainty onpdp\_\{d\}, and the format\-failure share are all directly inspectable\. CI widths \(Δ​pd\\Delta p\_\{d\}\) are the full 95% interval widths from 2,000 parametric bootstrap resamples; intervals straddle the point estimate symmetrically except where the optimiser lower boundpd=0\.5p\_\{d\}\{=\}0\.5truncates them\.κ\\kappavalues are inter\-annotator agreement on thek∗k^\{\*\}extractor\. Best per domain inbold\.pd†\{\}^\{\\dagger\}p\_\{d\}at the optimiser lower bound \(no statistically identifiable step\-retention\)\.Table 3:Mean divergence stepk∗k^\{\*\}for incorrect trials\. Within domain,k∗k^\{\*\}tracks accuracy; across models, parameter count does not; LLaMA\-3\.3 \(70B\) sits below Claude on every domain\.
#### Trace\-faithful vs\. lucky\-guess correctness\.

A second axis of dissociation appears when we look at correct outputs rather than incorrect ones\. A trace\-level view reveals two qualitatively different populations among the answers an output\-only evaluator would treat identically\.*Trace\-faithful correctness*\(k∗=−1k^\{\*\}\{=\}\{\-\}1, TFBC false\) is correctness with intact intermediate reasoning;*lucky\-guess correctness*\(TFBC true\) is correctness despite demonstrably divergent reasoning\. The dominant population shifts with domain\. On D2, where Claude operates nearpd=0\.99p\_\{d\}\{=\}0\.99, only8%8\\%of its correct outputs are TFBC and the rest are genuinely faithful \(262 of 285 traces match the canonical reasoning\); D2 is dominated by trace\-faithful correctness\. On D3 the picture inverts:56%56\\%–62%62\\%of correct outputs from Claude and Gemini are TFBC, and the targeted audit \(Section[3](https://arxiv.org/html/2606.29278#S3)\) found no genuine alternative\-path correctness in this group, so D3 correctness is dominated by lucky\-guess events\. Aggregated across the benchmark,14\.5%14\.5\\%of correct outputs are TFBC, so output\-only evaluation overstates reasoning quality*and*does so differentially; with the overstatement concentrated on precisely the harder domains where it most matters\. A reader of the aggregate scores would conclude that Claude’s6\.2%6\.2\\%D3 accuracy reflects real partial competence; the trace\-level evidence says that conclusion would be wrong for most of that6\.2%6\.2\\%\.

#### k∗k^\{\*\}as a coherence\-depth statistic\.

The distribution ofk∗k^\{\*\}, not just its mean, carries information\. Figure[5](https://arxiv.org/html/2606.29278#S4.F5)shows D2 stratified by model: LLaMA fails early at the first symbolic transition, while Claude maintains accuracy across∼\\sim17 steps before failing on global consistency\. Early\-heavy and late\-heavy failure modes are qualitatively different and would call for different mitigations even at matched aggregate accuracy\.

Taken together,k∗k^\{\*\}functions as a*working\-memory\-coherence depth statistic*: an operational measurement of how many sequential state updates a model can compose before its working representation decoheres\. This framing explains the empirical regularity that parameter count is a poor cross\-model predictor\. LLaMA\-3\.3\-70B has7070B parameters; more than most of the closed\-weight comparators in this study; yetkLLaMA∗<kClaude∗k^\{\*\}\_\{\\text\{LLaMA\}\}\{<\}k^\{\*\}\_\{\\text\{Claude\}\}on every domain \(3\.453\.45vs\.8\.458\.45on D1,3\.913\.91vs\.17\.6717\.67on D2,3\.013\.01vs\.4\.304\.30on D3\)\. Within a domain,k∗k^\{\*\}tracks accuracy because the depth at which a trace first decoheres mechanically lower\-bounds the accuracy achievable beyond that depth; across models, thek∗k^\{\*\}ranking tracks the kind of reasoning capability that drives long\-horizon agentic performance more faithfully than scale\. We therefore proposek∗k^\{\*\}as a complement, not a replacement, to aggregate accuracy: a single \(model, task\-family\) cell reports bothpdp\_\{d\}\(the per\-step retention\) andk∗k^\{\*\}\(the typical coherence depth\) without requiring per\-depth evaluation at use time\.

0101020203030404050506060707080809090100100LLaMAGPT\-4o\-mDeepSeekGeminiClaude% of D2 failuresEarly \(k∗≤3k^\{\*\}\{\\leq\}3\)MidLate \(k∗\>10k^\{\*\}\{\>\}10\)Figure 5:Divergence\-step distribution on D2 by model\. LLaMA fails at the first symbolic transition; Claude maintains accuracy across∼\\sim17 steps before failing on global consistency\.
#### Verbosity ablation\.

A natural objection is that the D3 collapse reflects prompt phrasing rather than a genuine reasoning limit, since prompt sensitivity in LLM benchmarks is well documented and the cliff appears uniformly atN=5N\{=\}5\. We tested this with a paired ablation atN=15N\{=\}15on Claude, the only model with any D3 signal\. The Standard condition lets the model infer state naturally; the Verbose condition prepends acriticalinstruction forcing it to restate the entire agent belief array after every operation\. Both conditions yielded0\.0%0\.0\\%accuracy across alln=20n\{=\}20paired instances, with the McNemar contingency in Table[4](https://arxiv.org/html/2606.29278#S4.T4): zero discordant pairs and McNemarp=1\.000p\{=\}1\.000\. Token usage tells the same story; the Verbose condition spent∼\\sim1,362 tokens to the Standard’s∼\\sim1,282 \(a6%6\\%overhead\)\. The model acknowledged the instruction but spent the extra tokens restating beliefs it could not compute correctly, not on doing the computation differently\. With zero discordant pairs the McNemar test confirms equipotence rather than distinguishing architecturally caused failure from coincidentally uniform failure, so we treat the result as suggestive rather than dispositive\.

Table 4:D3 verbosity ablation contingency,N=15N\{=\}15, Claude,n=20n\{=\}20paired\. McNemarp=1\.000p\{=\}1\.000\.
#### Prompt\-structure ablation\.

To check whether*any*prompt structure shifts the ceiling we ran three further variants at the sameN=15N\{=\}15:Var Aimposes a strict output schema,Var Badds positional formatting \(P\#\#slot markers identifying each agent position\), andVar Cadds an explicit logical mapping of the alliance/rivalry update rule \(Figure[6](https://arxiv.org/html/2606.29278#S4.F6)\)\. Variants A and C remain at0\.0%0\.0\\%\. Variant B reaches20\.0%20\.0\\%; a 20\-point absolute spread that demonstrates D3 is prompt\-sensitive in principle, but still falls far below practical utility\. We do not yet have a mechanistic account of why slot\-based positional formatting partially succeeds where the other variants do not, and whether the benefit extends toN\>15N\{\>\}15or to other models is reserved for the next iteration\. The qualitative takeaway is the same as the Standard/Verbose result: prompt\-level interventions can move the D3 ceiling by a few percentage points but do not change the underlying regime\.

StandardVerboseVar AVar BVar C02020404000020200Accuracy \(%\)Figure 6:D3 prompt\-sensitivity atN=15N\{=\}15\(Claude 3\.7,n=20n\{=\}20per condition\)\. Standard/Verbose yield identical0%0\\%\(McNemarp=1\.000p\{=\}1\.000\); onlyVar B\(positional slot formatting\) reaches non\-zero accuracy, and at20\.0%20\.0\\%this still falls far short of practical utility on long\-horizon tasks\.
#### Summary of regimes\.

Pulled together, the three domains identify three structurally distinct failure regimes that aggregate accuracy collapses into a single number: per\-step retention bottleneck on D1 \(where the frontier\-vs\.\-non\-frontier gap lies inpdp\_\{d\}, not formatting\); a constraint\-management bottleneck on D2 \(where69\.5%69\.5\\%of failures are illegal re\-assignments and the dominant error is state\-keeping rather than arithmetic\); and a structurally distinct cascade collapse on D3 \(wherek∗k^\{\*\}is essentially uniform across capability tiers and accuracy is dominated by lucky\-guess events\)\. No model dominates all three: Gemini leads on D1 \(22\.0%22\.0\\%\), Claude leads on D2 \(71\.2%71\.2\\%\) and D3 \(6\.2%6\.2\\%\), and the within\-tier gaps shrink sharply as the load shifts from per\-step retention to structural consistency; Claude’s∼\\sim53 pp lead on D2 collapses to a∼\\sim3 pp lead on D3, evidence that the D3 ceiling is not a simple translation of the D2 ranking\. The deployment\-facing implication is direct: a model withpd<0\.93p\_\{d\}\{<\}0\.93should not be relied on for tasks requiring more than∼\\sim20 sequential steps, with the optimism caveat of Remark[1](https://arxiv.org/html/2606.29278#Thmremark1)in mind\.

## 5Discussion

#### Three failure regimes, three mitigations\.

The combined empirical and analytical picture supports a*state\-drift*view of autoregressive failure under depth scaling: each of the three CCB domains stresses a different facet of the same underlying step\-retention bottleneck, and the three resulting failure regimes call for qualitatively different mitigations\. Output\-format retraining is the natural target for D1 \(where the gap is inpdp\_\{d\}and format\-failure rates are already at0–2%2\\%\); constraint\-reminder prompting or scratchpad\-augmented decoding is the natural target for D2 \(where the dominant failure is illegal re\-assignment under a uniqueness rule\); and architectural or training\-level intervention; process supervision, recursive scaffolding, or explicit graph state; is the indicated direction for D3, since the verbosity ablation shows no movement from prompt\-level changes alone\. Becausepdp\_\{d\}is a single interpretable number per \(model, domain\) cell, it can be reported alongside aggregate accuracy on deployment dashboards without re\-running depth\-stratified evaluation at use time\.

#### The D1 ceiling is not a formatting artefact\.

A skeptical reading of these results turns naturally to the D1 result\. Format adherence is uniformly high across all five models \(0–2%2\\%format failures\), which rules out the obvious confound that the frontier\-vs\.\-non\-frontier gap is an artefact of structured output\. Frontier models maintainpd∈\[0\.924,0\.930\]p\_\{d\}\\in\[0\.924,0\.930\]; GPT\-4o\-mini \(pd=0\.688p\_\{d\}\{=\}0\.688\) and LLaMA \(pd=0\.634p\_\{d\}\{=\}0\.634\) collapse on per\-step retention, not on formatting\. The implication is that the D1 ceiling is not closeable by output\-format prompting alone, and the right diagnostic target for closing it is per\-step retention rather than output adherence\. Whether targeted format\-aware fine\-tuning shiftspdp\_\{d\}on D1 is a clean empirical question we leave open\.

#### Missing reasoning\-specialised baselines\.

The principal limitation of this work is the absence of reasoning\-specialised baselines\. Process\-level supervision\([2](https://arxiv.org/html/2606.29278#bib.bib2)\)is the most plausible single intervention for shiftingpdp\_\{d\}beyond the frontier tier on D2 or for reducing the D3 cascade; if process\-supervised models achievek∗\>10k^\{\*\}\{\>\}10on D3 it would substantially qualify the architectural reading of our findings\. We commit to evaluating o1/o3, DeepSeek\-R1, recursive scaffold models\([16](https://arxiv.org/html/2606.29278#bib.bib16)\), and fast\-slow recurrent mechanisms\([15](https://arxiv.org/html/2606.29278#bib.bib15)\)alongside tool\-augmented systems with explicit graph state in the next iteration\. This is the single most informative follow\-up experiment available, and the one most likely to sharpen or falsify the structural reading of D3\.

#### Limitations\.

The remaining limitations are quantitative and we have tried to bound them rather than eliminate them\. The independence assumption behindpdNp\_\{d\}^\{N\}is wrong in a known direction \(Assumption[1](https://arxiv.org/html/2606.29278#Thmassumption1), Remark[1](https://arxiv.org/html/2606.29278#Thmremark1)\); real autoregressive decoding produces positively correlated errors, so the model’s predictions should be read as an optimistic envelope on sustained accuracy rather than a guarantee\. The synthetic generators produce structurally controlled tasks but their generalisation to naturalistic agentic settings requires further study\. The strict regex parser may under\-count valid traces with idiosyncratic formatting \(we measured≈2%\\approx 2\\%false\-negative rate in the 150\-case audit\)\. All evaluations were performed atT=0T\{=\}0via OpenRouter; provider\-specific optimisations may shift profiles slightly\. The D3 prompt ablation is preliminary \(one model,n=20n\{=\}20paired\) and a broader sweep over prompt structures is needed to distinguish architectural from coincidental failure cleanly\. Formal AIC/BIC selection between geometric, acceleratingpdNγp\_\{d\}^\{N^\{\\gamma\}\}, and linear1−λ​N1\{\-\}\\lambda Ndecay forms atN\>50N\{\>\}50; where positional\-embedding saturation may shift the dominant failure mechanism; remains future work\. Finally, TFBC assumes a single canonical reasoning trace per trial; alternative valid traces would be misclassified, though the 20\-case D3 audit found no such cases\. The150150\-case parser audit and theκ≥0\.938\\kappa\{\\geq\}0\.938inter\-annotator agreement support that the reported numbers are not parser artefacts\.

## 6Conclusion

The Complexity Ceiling Benchmark isolates reasoning depth as a controlled experimental variable and reveals three structurally distinct failure regimes that aggregate accuracy collapses into a single number: per\-step retention collapse on grounded spatial reasoning, constraint\-management collapse on abstract symbolic reasoning, and a transitive\-closure cascade on relational reasoning that persists uniformly across all five evaluated models regardless of parameter count\. The trace\-level TFBC analysis shows that14\.5%14\.5\\%of correct outputs across the benchmark are reached via demonstrably divergent intermediate reasoning, so trace\-faithful and lucky\-guess correctness must be distinguished for benchmark scores to remain meaningful on long\-horizon tasks\. The mean trace\-divergence stepk∗k^\{\*\}predicts within\-domain accuracy more faithfully than parameter count, supporting a state\-drift rather than a capacity\-limit account of autoregressive failure under depth scaling\. The most urgent open question is whether process\-supervised or recursive architectures dissolve the D3 ceiling; if they do, the structural reading of these findings requires substantial revision; if they do not,CCBprovides a principled diagnostic for the next generation of memory\-augmented systems\.

## References

- Chaudhury et al\. \(2026\)B Chaudhury, M F Wang, H H Park, R Ghosh, S Hong, and J O Woo\.Quantifying consistency in LLM logical reasoning via structural uncertainty\.In*ICLR 2026 Workshop on Logical Reasoning of Large Language Models*, 2026\.Best Paper Award\.
- Cobbe et al\. \(2021\)Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, et al\.Training verifiers to solve math word problems\.*arXiv preprint arXiv:2110\.14168*, 2021\.
- Dziri et al\. \(2023\)Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Bhatt, Lianhui Jiang, et al\.Faith and fate: Limits of transformers on compositionality\.In*Advances in Neural Information Processing Systems*, volume 36, 2023\.
- Golovneva et al\. \(2022\)Olga Golovneva, Moya Chen, Spencer Poff, Martin Corredor, Luke Zettlemoyer, Maryam Fazel\-Zarandi, and Asli Celikyilmaz\.Roscoe: A suite of metrics for scoring step\-by\-step reasoning\.*arXiv preprint arXiv:2212\.07919*, 2022\.
- Hou et al\. \(2026\)Dengzhe Hou, Lingyu Jiang, Deng Li, Zirui Li, Fangzhou Lin, and Kazunori D\. Yamada\.Wmf\-am: Probing llm working memory via depth\-parameterized cumulative state tracking\.*arXiv preprint arXiv:2603\.27343*, 2026\.
- Jiang et al\. \(2025\)Dongzhi Jiang, Renrui Zhang, Ziyu Guo, Yanwei Li, Yu Qi, Xinyan Chen, Liuhui Wang, Jianhan Jin, Claire Guo, Shen Yan, et al\.Mme\-cot: Benchmarking chain\-of\-thought in large multimodal models for reasoning quality, robustness, and efficiency\.In*Proceedings of the 42nd International Conference on Machine Learning*, 2025\.
- Kim et al\. \(2025\)Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham Kakade, and Sitan Chen\.Train for the worst, plan for the best: Understanding token ordering in masked diffusions\.In*Proceedings of the 42nd International Conference on Machine Learning*, 2025\.
- Lake and Baroni \(2018\)Brenden M Lake and Marco Baroni\.Generalization without systematicity: On the compositional skills of sequence\-to\-sequence recurrent networks\.*International Conference on Machine Learning*, pages 2873–2882, 2018\.
- Maniparambil et al\. \(2026\)Mayug Maniparambil, Nils Hoehing, Janak Kapuriya, Arjun Karuvally, Ellen Rushe, Anthony Ventresque, Noel O’Connor, and Fergal Reid\.Topobench: Benchmarking llms on hard topological reasoning\.2026\.URL[https://arxiv\.org/abs/2603\.12133](https://arxiv.org/abs/2603.12133)\.
- Prasad et al\. \(2023\)Archiki Prasad, Swarnadeep Saha, Xiang Zhou, and Mohit Bansal\.Receval: Evaluating reasoning chains via correctness and informativeness\.*arXiv preprint arXiv:2304\.10703*, 2023\.
- Sebastiano Monti et al\. \(2026\)Gianni Pellegrini Sebastiano Monti, Carlo Nicolini et al\.SokoBench: Evaluating long\-horizon planning and reasoning in large language models\.*arXiv preprint arXiv:2601\.20856*, 2026\.
- Sinha et al\. \(2025\)Akshit Sinha, Arvindh Arun, Shashwat Goel, Steffen Staab, and Jonas Geiping\.The illusion of diminishing returns: Measuring long horizon execution in llms\.*arXiv preprint arXiv:2509\.09677*, 2025\.
- Sinha et al\. \(2019\)Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L\. Hamilton\.Clutrr: A diagnostic benchmark for inductive reasoning from text\.*arXiv preprint arXiv:1908\.06177*, 2019\.
- Srivastava et al\. \(2022\)Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, et al\.Beyond the imitation game: Quantifying and extrapolating the capabilities of language models\.*arXiv preprint arXiv:2206\.04615*, 2022\.
- Takashiro et al\. \(2026\)Shota Takashiro, Masanori Koyama, Takeru Miyato, Yusuke Iwasawa, Yutaka Matsuo, and Kohei Hayashi\.Thinking while listening: Fast\-slow recurrence for long\-horizon sequential modelling\.*arXiv preprint arXiv:2604\.01577*, 2026\.
- Yang et al\. \(2026\)Chenxiao Yang, Nathan Srebro, and Zhiyuan Li\.Recursive models for long\-horizon reasoning\.*arXiv preprint arXiv:2603\.02112*, 2026\.

## Appendix ADetailed Results

This appendix supplements the per\-cell summary in Table[1](https://arxiv.org/html/2606.29278#S4.T1)and the per\-depth heatmap in Figure[4](https://arxiv.org/html/2606.29278#S4.F4)with full numeric values: Tables[5](https://arxiv.org/html/2606.29278#A1.T5)–[7](https://arxiv.org/html/2606.29278#A1.T7)summarise across depths with 95% bootstrap CIs, and Tables[8](https://arxiv.org/html/2606.29278#A1.T8)–[10](https://arxiv.org/html/2606.29278#A1.T10)give the underlying depth\-wise accuracies with Clopper\-Pearson half\-CIs\.

Table 5:D1 Alien Grid results \(n=400n\{=\}400/model, LLaMAn=395n\{=\}395\)\.pdp\_\{d\}95% CI in brackets\. Humanκ=0\.977\\kappa\{=\}0\.977,n=50n\{=\}50\.Table 6:D2 Symbolic Pointer Tracking \(n=400n\{=\}400/model, DeepSeekn=399n\{=\}399, LLaMAn=392n\{=\}392\)\. Humanκ=0\.978\\kappa\{=\}0\.978,n=50n\{=\}50\.Table 7:D3 Social Logic \(n=400n\{=\}400/model\)\. Humanκ=0\.938\\kappa\{=\}0\.938,n=65n\{=\}65\. McNemar verbosity ablationp=1\.0p\{=\}1\.0\.pdp\_\{d\}at0\.5000\.500is at the optimiser lower bound\.Table 8:D1 Alien Grid: Acc%±\\pmClopper\-Pearson half\-CI by depth\. AvgTok = mean response tokens\.Table 9:D2 Symbolic Pointers: Acc%±\\pmhalf\-CI by depth\.Table 10:D3 Social Logic: Acc%±\\pmhalf\-CI by depth\.
## Appendix BFailure Mode Examples and Prompt Templates

### Failure Mode Examples

#### D1 early divergence \(LLaMA,N=10N\{=\}10\)\.

```
Ground Truth:
  Step 1: [[1,2,3],[4,5,6],[7,8,9]]
  Step 2: [[7,4,1],[8,5,2],[9,6,3]]
Model Output:
  Step 1: [[1,2,3],[4,5,6],[7,8,9]]
  Step 2: [[3,2,1],[6,5,4],[9,8,7]]
            <- DIVERGENCE (k*=2)
```

Horizontal flip instead of90∘90^\{\\circ\}CW rotation;k∗=2k^\{\*\}\{=\}2\.

#### D2 constraint failure \(Gemini,N=25N\{=\}25\)\.

After twenty correct steps the model illegally re\-assigns variableAA, violating uniqueness\. Classified Constraint, not Reasoning\.

#### D3 cascade collapse \(DeepSeek,N=10N\{=\}10\)\.

The model processes step 1 correctly but omits a transitive closure propagation at step 2\. Every subsequent pair classification is wrong; recovery is impossible within the context window\.

### Exact Prompt Templates

#### D1\.

```
You are a spatial reasoning engine.
Track a 3x3 grid
(Initial: [[1,2,3],[4,5,6],[7,8,9]]).
OPERATIONS:
  ROTATE_90_CW: Rotate 90 deg clockwise.
  SHIFT_ROW_2_LEFT: Shift middle row left,
                    wrapping.
Output:
  TRACE: ["Step 1:[[...]]", ...]
  ANSWER: [[...]]
```

#### D2\.

```
You track 7 variables A-G holding
distinct digits 0-9. Apply N operations:
SHIFT_RIGHT, SET X TO Y PLUS Z mod 10.
Output:
  TRACE: ["Step 1:{A:v,...}", ...]
  ANSWER: {A:v, B:v, ...}
```

#### D3 verbose ablation addition\.

```
CRITICAL ABLATION INSTRUCTION: After EVERY
single operation, you MUST explicitly
restate the entire agent belief state array
before proceeding to the next step.
```

## Appendix CExtended Related Work

#### Depth\-scaling and compositional generalisation\.

SCAN\([8](https://arxiv.org/html/2606.29278#bib.bib8)\)and BIG\-Bench\([14](https://arxiv.org/html/2606.29278#bib.bib14)\)hold difficulty roughly constant and probe systematic generalisation to novel compositions\.CCBcomplements that line by providing a continuous, parametric depth axis across three heterogeneous domains and a single\-parameter decay model\. SokoBench\([11](https://arxiv.org/html/2606.29278#bib.bib11)\)isolates planning depth in Sokoban; TopoBench\([9](https://arxiv.org/html/2606.29278#bib.bib9)\)focuses on topological reasoning and shows that structured state aids reasoning, motivating tool\-augmented D3 extensions\.

#### Relational benchmarks\.

CLUTRR\([13](https://arxiv.org/html/2606.29278#bib.bib13)\)tests multi\-hop relational reasoning on kinship graphs and is the closest prior work to D3\.CCBextends that line by providing deterministic ground\-truth traces \(not only final answers\), enabling TFBC\-level diagnostics; by applying a continuous depth axis fromN=5N\{=\}5toN=50N\{=\}50; and by integrating relational inference with spatial and symbolic regimes under a unified evaluation framework\.

#### State tracking and systematic failures\.

Dziri et al\. \([3](https://arxiv.org/html/2606.29278#bib.bib3)\)showed LLMs unroll memorised subgraphs with catastrophic failure at compositional OOD depths\.Hou et al\. \([5](https://arxiv.org/html/2606.29278#bib.bib5)\)showed performance degrades under cumulative state\-tracking load\.CCBquantifies these phenomena via thek∗k^\{\*\}distribution and thepdp\_\{d\}summary statistic\.

#### Trace\-level evaluation and structural uncertainty\.

Golovneva et al\. \([4](https://arxiv.org/html/2606.29278#bib.bib4)\)andPrasad et al\. \([10](https://arxiv.org/html/2606.29278#bib.bib10)\)evaluate reasoning chains for correctness and informativeness; MME\-CoT\([6](https://arxiv.org/html/2606.29278#bib.bib6)\)introduces precision and recall metrics for multimodal chain\-of\-thought\.Chaudhury et al\. \([1](https://arxiv.org/html/2606.29278#bib.bib1)\)show that unstable self\-preference rankings signal unreliable inference\.CCBprovides a complementary, ground\-truth\-grounded operationalisation that requires no LLM\-as\-judge\.

#### Process supervision and long\-horizon execution\.

Process\-supervised models\([2](https://arxiv.org/html/2606.29278#bib.bib2)\)are trained with step\-level reward signals that incentivise intermediate\-state correctness; their evaluation is the most consequential extension of this work\.Sinha et al\. \([12](https://arxiv.org/html/2606.29278#bib.bib12)\)analytically links per\-step accuracy to an effective task horizonHs≈ln⁡\(s\)/ln⁡\(pd\)H\_\{s\}\{\\approx\}\\ln\(s\)/\\ln\(p\_\{d\}\);CCB’s empiricalpdp\_\{d\}values feed directly into that framework\. Recursive scaffolds\([16](https://arxiv.org/html/2606.29278#bib.bib16)\)and fast\-slow recurrence\([15](https://arxiv.org/html/2606.29278#bib.bib15)\)target the same state\-management bottleneck from the architecture side, andKim et al\. \([7](https://arxiv.org/html/2606.29278#bib.bib7)\)argue that autoregressive token ordering is itself an inductive bias on accessible reasoning patterns\.