Paper deep dive
The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling
Shubh Chapra, Dhruv Kumar, Murari Mandal, Yash Sinha
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 7/5/2026, 1:46:18 AM
Summary
The paper introduces the Complexity Ceiling Benchmark (CCB), a controlled evaluation designed to measure how language model reasoning decays as the number of sequential steps (N) increases from 5 to 50. The benchmark tests three distinct reasoning regimes: grounded spatial state-tracking (D1), abstract symbolic pointer manipulation (D2), and transitive relational inference (D3). The researchers found that while frontier models exhibit geometric per-step decay in D1 and D2, they suffer a catastrophic collapse in D3 due to the structural complexity of transitive closure. The study introduces the Trace First Branch Correct (TFBC) metric to identify 'lucky guesses' where models reach correct answers via incorrect intermediate steps, and demonstrates that the mean step of divergence (k*) is a more reliable predictor of within-domain accuracy than parameter count.
Entities (11)
Relation Signals (5)
Complexity Ceiling Benchmark → evaluates → Grounded Spatial State-Tracking
confidence 100% · CCB consists of three task domains... grounded spatial state-tracking (D1), abstract symbolic pointer manipulation (D2), and transitive relational inference (D3).
Complexity Ceiling Benchmark → evaluates → Abstract Symbolic Pointer Manipulation
confidence 100% · CCB consists of three task domains... abstract symbolic pointer manipulation (D2)...
Complexity Ceiling Benchmark → evaluates → Transitive Relational Inference
confidence 100% · CCB consists of three task domains... transitive relational inference (D3).
Claude 3.7 → istestedon → Complexity Ceiling Benchmark
confidence 100% · We evaluate each domain... on claude-3.7-sonnet, gemini-2.0-flash-001, deepseek-chat, gpt-4o-mini, and llama-3.3-70b-instruct.
TFBC → measures → Trace Divergence
confidence 100% · A trace-level metric (TFBC) shows that 14.5% of correct answers across the benchmark are reached via incorrect intermediate reasoning.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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. CCB fixes the semantic content of a task and varies only its depth N in {5,...,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 retain pd>0.92 across N=50; on the third every model collapses by N=5, with the best model's 50%-success horizon at H0.5~4.7 steps despite pd=0.863. A trace-level metric (TFBC) shows that 14.5% of correct answers across the benchmark are reached via incorrect intermediate reasoning. Forced verbose state-tracking does not move the ceiling (McNemar p=1.000), and the mean step at which reasoning first diverges, k*, predicts within-domain accuracy better than parameter count. CCB and the geometric decay model together reduce a model's long-horizon reasoning profile to one interpretable number per task family.
Tags
Links
- Source: https://arxiv.org/abs/2606.29278v1
- Canonical: https://arxiv.org/abs/2606.29278v1
Trouble viewing inline? Open PDF directly →
Full Text
51,301 characters extracted from source content.
Expand or collapse full text
The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling Shubh Chapra Dhruv Kumar Murari Mandal Yash Sinha 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. CCB fixes the semantic content of a task and varies only its depth N∈5,…,50N∈\5,…,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 retain pd>0.92p_d>0.92 across N=50N=50; on the third every model collapses by N=5N=5, with the best model’s 50%-success horizon at H0.5≈4.7H_0.5≈4.7 steps despite pd=0.863p_d=0.863. A trace-level metric (TFBC) shows that 14.5%14.5\% of correct answers across the benchmark are reached via incorrect intermediate reasoning. Forced verbose state-tracking does not move the ceiling (McNemar p=1.000p=1.000), and the mean step at which reasoning first diverges, k∗k^*, predicts within-domain accuracy better than parameter count. CCB and 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 5515152525353545450252550507575100100Depth NNAccuracy (%)D1 Spatial state-tracking5515152525353545450252550507575100100Depth NND2 Symbolic pointer tracking5515152525353545450252550507575100100H0.5≈4.7H_0.5≈4.7Depth NND3 Transitive social logicClaude 3.7Gemini 2.0FDeepSeekGPT-4o-miniLLaMA-3.3 Figure 1: The Complexity Ceiling. Accuracy as a function of depth N across three structurally distinct reasoning regimes, with semantic content held fixed. Markers: empirical accuracy at n=40n=40 trials per cell. Thin solid curves in D1 and D2: fitted geometric model 100⋅pdN100·p_d^N for the top frontier model (Gemini in D1, Claude in D2). On D1 and D2 frontier models track the geometric decay with pd∈[0.92,0.99]p_d∈[0.92,0.99], leaving meaningful accuracy at N=50N=50. On transitive social logic (D3) every model collapses past N=5N=5 regardless of capability tier; even the best model’s 50%50\%-success horizon is H0.5≈4.7H_0.5≈4.7 steps. Solid lines: frontier or competitive open-weight; dashed: smaller models. 6,0006,000 trials total. 1 Introduction 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, 12). This paper treats depth as the controlled experimental variable. Figure 1 shows the central result of doing so. The Complexity Ceiling Benchmark (CCB) holds task semantics fixed and sweeps the number of required reasoning steps N from 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 in N; and a striking dissociation between domains. On D1 and D2 the strongest models hold retention probability pd>0.92p_d>0.92 across the full depth range, leaving meaningful accuracy at N=50N=50. On D3, every model collapses past N=5N=5, regardless of capability tier; the best evaluated model’s 50%-success horizon is only H0.5≈4.7H_0.5≈4.7 steps. 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 probability pdp_d and a mean trace-divergence step k∗k^*. Both connect to deployment: pdp_d feeds the horizon-length framework of Sinha et al. (12) and determines the depth at which sustained accuracy crosses any chosen threshold, and k∗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 uses CCB is built to serve. 2 Related Work Depth-scaling and compositional generalisation. Most prior work treats reasoning failure as an aggregate property of a task. SCAN (8) and BIG-Bench (14) 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) 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) showed transformers unroll memorised subgraphs with catastrophic failure at compositional out-of-distribution depths; Hou et al. (5) tied this to cumulative state-tracking load; SokoBench (11) isolates planning depth in Sokoban, TopoBench (9) shows structured state aids reasoning. CCB differs 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), ReCEval (10), and MME-CoT (6) introduce trace-quality metrics, but mostly rely on LLM-as-judge or learned rubrics whose own reliability is contested (1). CCB sidesteps this by comparing against a deterministically generated canonical trace; the TFBC metric below requires no external scorer. Process supervision and horizon connection. Finally, our pdNp_d^N model is the empirical counterpart of the horizon-length framework of Sinha et al. (12), which derives an effective task horizon Hs≈ln(s)/ln(pd)H_s≈ (s)/ (p_d) from per-step accuracy. Cobbe et al. (2) showed that process-level supervision shifts the relevant quantity; recursive scaffolds (16) and fast-slow recurrence (15) target the same bottleneck through architecture. Kim et al. (7) argue that autoregressive token ordering is itself an inductive bias on what reasoning patterns are accessible. Extended discussion appears in Appendix C. 3 Benchmark Design CCB consists 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 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… 50) LLM Inference (T=0T=0) Regex Trace Parsing Format OK? Format Fail / Truncated Ans OK? Correct Compute k∗k^* (TFBC) Constraint / Reasoning Fail NoYesYesNo 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, depth N varied over 5,10,…,50\5,10,…,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 a 3×33×3 grid subjected to N discrete 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 step k invalidates every state after it. D2 Symbolic Pointer Tracking asks the model to maintain seven variables A–G holding distinct digits 0–9 under N cyclic-shift and modular-arithmetic operations subject to an assignment-uniqueness constraint; its dominant failure mode is register corruption via illegal re-assignment, which accounts for 69.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 of N update 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 agent i believe about agent j?”), and must maintain global pairwise consistency over O(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). We evaluate each domain at n=40n=40 independently seeded trials per (model, depth) cell, for 2,0002,000 trials per domain and 6,0006,000 in total. All inference is at T=0T=0 via OpenRouter, on claude-3.7-sonnet, gemini-2.0-flash-001, deepseek-chat, gpt-4o-mini, and llama-3.3-70b-instruct. Reasoning-specialised models (o1/o3, DeepSeek-R1) were not accessible at submission time and are addressed in Section 5. 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 step k∗≤Nk^*≤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 resulting pdp_d estimates are mildly conservative for models with idiosyncratic output styles. This is the bias direction we want because it cannot inflate reported accuracy or pdp_d. A manual audit of 150 edge-case outputs found no false positives in correctness classification and a small (≈2%≈ 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 reported k∗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 step k∗>0k^*>0. Algorithm 1 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 typical k∗=2k^*=2 event on D1 at N=10N=10 has ground truth Step 2 =[[7,4,1],[8,5,2],[9,6,3]]=[[7,4,1],[8,5,2],[9,6,3]] (a 90∘90 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 κ of 0.9770.977 (D1, n=50n=50), 0.9780.978 (D2, n=50n=50), and 0.9380.938 (D3, n=65n=65), all above the conventional defensibility threshold of 0.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 are not in tension. Algorithm 1 TFBC and k∗k^* extractor. 1: Input: model trace T, ground-truth trace G, depth N 2: L←ParseSteps(T)L (T); k∗←−1k^*←-1 3: if |L|<N|L|<N and missing answer then 4: return Format Error 5: end if 6: for i=1i=1 to N do 7: if L[i]≠G[i]L[i]≠ G[i] then 8: k∗←ik^*← i; break 9: end if 10: end for 11: is_TFBC←(k∗≠−1)∧(Amodel=Atrue)is\_TFBC←(k^*≠-1) (A_model=A_true) 12: return k∗k^*, is_TFBC Geometric decay model. Let pdp_d denote the probability that the model correctly computes Sk→Sk+1S_k→S_k+1 given that SkS_k was maintained. Under independence of per-step errors (Assumption 1), P(correct∣N)=∏i=1NP(stepi correct)=pdN.P(correct N)\;=\; _i=1^NP(step_i correct)\;=\;p_d^N. (1) The expression pdNp_d^N is a discrete survival function with constant per-step hazard 1−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 fit pdp_d per cell by maximising the binomial log-likelihood ∑N[cNlnpdN+(n−cN)ln(1−pdN)] _N [c_N p_d^N+(n-c_N) (1-p_d^N) ] over cNc_N correct trials out of n=40n=40 at each depth, constrained to pd∈[0.5,1.0]p_d∈[0.5,1.0]; 95% confidence intervals are from 2,0002,000 parametric 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 literal 50%50\% per-step. Assumption 1 (Independent per-step failures). The probability of a state-transition error at step k is independent of whether an error occurred at step k−1k-1. S0S_0S1S_1S2S_2⋯·sSNS_NE1E_1E2E_2pdp_dpdp_dpdp_dpdp_d1−pd1-p_d1−pd1-p_dCascading failure(correlated in reality) Figure 3: The state-retention process of Assumption 1. Under independence, a single step error transitions the system to an absorbing failure state with per-step probability 1−pd1-p_d. In reality, errors at step k∗k^* corrupt all k>k∗k>k^* (Remark 1), so the true decay is faster than pdNp_d^N predicts. Alternative decay models. Assumption 1 is wrong in a known direction (Figure 3). Autoregressive transformers are not Markov: an error at step k∗k^* corrupts context for all k>k∗k>k^*, so per-step errors are positively correlated and Equation 1 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 treat pdNp_d^N as an optimistic envelope throughout. We considered two alternative forms before adopting the geometric model: an accelerating pdNγp_d^N^γ that would capture attention fatigue, and a linear 1−λN1-λ N drift. The linear form fails to capture the non-linear collapse observed at moderate N; the accelerating form adds a free parameter without empirical motivation in the N≤50N≤50 regime. 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 beyond N=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 of Sinha et al. (12): for minimum success threshold s, the effective task horizon is Hs≈ln(s)/ln(pd)H_s≈ (s)/ (p_d). For Claude on D3 with pd=0.863p_d=0.863, H0.5≈4.7H_0.5≈4.7 steps, which matches both the depth at which observed accuracy crosses 50%50\% and the mean k∗=4.30k^*=4.30 on incorrect D3 trials. The empirical pdp_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. 4 Results Table 1 summarises all 6,000 evaluations and Figure 1 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 step k∗k^* ranks models more faithfully within domain than parameter count or aggregate accuracy. Table 1: CCB master results. Aggregate accuracy, the geometric step-retention MLE pdp_d, and the trace-level lucky-guess rate TFBC, per (model, domain) cell. Best per domain in bold; per-depth tables with 95% bootstrap CIs are in Appendix A. † At the optimiser lower bound; no statistically identifiable step-retention. Model D1 Spatial D2 Symbolic D3 Social Logic Avg Acc pdp_d TFBC Acc pdp_d TFBC Acc pdp_d TFBC Frontier / closed-weight Claude 3.7 18.2% 0.929 21% 71.2% 0.987 8% 6.2% 0.863 56% 31.9% Gemini 2.0F 22.0% 0.930 1% 30.0% 0.950 29% 3.2% 0.736 62% 18.4% GPT-4o-mini 1.5% 0.688 17% 1.2% 0.634 20% 0.2% 0.500† – 1.0% Open-weight DeepSeek 19.8% 0.924 6% 31.3% 0.955 12% 2.0% 0.684 13% 17.7% LLaMA-3.3 1.3% 0.634 0% 4.3% 0.767 18% 0.0% 0.500† – 1.9% D1 Alien Grid5101520253035404550Depth NNClaude582515820101581510Gemini6555351018101883DeepSeek7043231023810103GPT-4o-m1033LLaMA13D2 Symbolic Pointers5101520253035404550Depth NNClaude98908568805870585355Gemini5553504325202351018DeepSeek38304553303530182313GPT-4o-m13LLaMA403D3 Social Logic5101520253035404550Depth NNClaude35558335Gemini33DeepSeek20GPT-4o-m3LLaMA0%50%100%Accuracy Figure 4: Per-depth accuracy across models and domains. Rows are models, columns are depth N∈5,…,50N∈\5,…,50\, cells show observed accuracy (%), darker = higher. The qualitative difference between domains is immediate: D1 and D2 retain non-trivial gradients at large N for frontier models, while D3 is essentially a single column of non-zero values at N=5N=5. The view complements Table 1 (which aggregates across depths) and Figure 1 (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 around pd∈[0.92,0.93]p_d∈[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 by N=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 reaches pd=0.987p_d=0.987 and 71.2%71.2\% aggregate accuracy, more than double Gemini (30.0%30.0\%) or DeepSeek (31.3%31.3\%), and retains 55%55\% accuracy at N=50N=50. Claude’s D2 decay curve is visibly shallower than the non-frontier models’; a pd=0.987p_d=0.987 vs. pd=0.634p_d=0.634 gap corresponds to roughly a 28×28× 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 produces Step 4: var_A=10, Step 5: var_B=var_A (so var_B should hold 10 for the rest of the trial), then writes Step 6: var_A=15, silently violating uniqueness on var_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 at N=25N=25–3535 on D1 and D2 are within the per-cell Clopper-Pearson half-CI of ±12± 12–16%16\% at n=40n=40 and do not reflect generator artefacts: operation distributions are stationary across N by construction, and the monotone pdNp_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,953 of 2,0002,000 attempts fail. Only Claude achieves any sustained accuracy (6.2%6.2\% overall, concentrated at N=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 carries k∗=17.67k^*=17.67 on D2 yet diverges after only 4.30 steps on D3 (Table 3). The uniformity of k∗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 step k propagates by transitivity to every k-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 over O(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; as N grows the representations of distinct agents’ relationship sets mix in the attention pattern rather than remaining cleanly partitioned, and the divergence step k∗∈[2.88,4.30]k^*∈[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, 15). CCB probes 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 at N=10N=10 processes 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 and pdp_d bootstrap 95% CI widths. The three domains are broken out separately so the per-domain spread, the uncertainty on pdp_d, and the format-failure share are all directly inspectable. CI widths (Δpd 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 bound pd=0.5p_d=0.5 truncates them. κ values are inter-annotator agreement on the k∗k^* extractor. Best per domain in bold. pd† p_d at the optimiser lower bound (no statistically identifiable step-retention). D1 Alien Grid (κ=0.977κ=0.977) D2 Symbolic Pointers (κ=0.978κ=0.978) D3 Social Logic (κ=0.938κ=0.938) Model Acc pdp_d Δpd p_d TFBC Model Acc pdp_d Δpd p_d TFBC Model Acc pdp_d Δpd p_d TFBC Gemini 22.0% 0.930 0.018 1% Claude 71.2% 0.987 0.004 8% Claude 6.2% 0.863 0.046 56% DeepSeek 19.8% 0.924 0.021 6% DeepSeek 31.3% 0.955 0.012 12% Gemini 3.2% 0.736 0.118 62% Claude 18.2% 0.929 0.019 21% Gemini 30.0% 0.950 0.012 29% DeepSeek 2.0% 0.684 0.167 13% GPT-4o-m 1.5% 0.688 0.165 17% LLaMA 4.3% 0.767 0.099 18% GPT-4o-m 0.2% 0.500† – – LLaMA 1.3% 0.634 0.205 0% GPT-4o-m 1.2% 0.634 0.208 20% LLaMA 0.0% 0.500† – – Table 3: Mean divergence step k∗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. Model D1 k∗k^* D2 k∗k^* D3 k∗k^* Claude 3.7 8.45 17.67 4.30 Gemini 2.0F 9.22 11.85 3.36 DeepSeek 8.10 9.92 3.45 LLaMA-3.3 3.45 3.91 3.01 GPT-4o-mini 3.21 3.30 2.88 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 near pd=0.99p_d=0.99, only 8%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) 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’s 6.2%6.2\% D3 accuracy reflects real partial competence; the trace-level evidence says that conclusion would be wrong for most of that 6.2%6.2\%. k∗k^* as a coherence-depth statistic. The distribution of k∗k^*, not just its mean, carries information. Figure 5 shows D2 stratified by model: LLaMA fails early at the first symbolic transition, while Claude maintains accuracy across ∼ 17 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 has 7070B parameters; more than most of the closed-weight comparators in this study; yet kLLaMA∗<kClaude∗k^*_LLaMA<k^*_Claude on every domain (3.453.45 vs. 8.458.45 on D1, 3.913.91 vs. 17.6717.67 on D2, 3.013.01 vs. 4.304.30 on 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, the k∗k^* ranking tracks the kind of reasoning capability that drives long-horizon agentic performance more faithfully than scale. We therefore propose k∗k^* as a complement, not a replacement, to aggregate accuracy: a single (model, task-family) cell reports both pdp_d (the per-step retention) and k∗k^* (the typical coherence depth) without requiring per-depth evaluation at use time. 0101020203030404050506060707080809090100100LLaMAGPT-4o-mDeepSeekGeminiClaude% of D2 failuresEarly (k∗≤3k^*≤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 ∼ 17 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 at N=5N=5. We tested this with a paired ablation at N=15N=15 on Claude, the only model with any D3 signal. The Standard condition lets the model infer state naturally; the Verbose condition prepends a critical instruction forcing it to restate the entire agent belief array after every operation. Both conditions yielded 0.0%0.0\% accuracy across all n=20n=20 paired instances, with the McNemar contingency in Table 4: zero discordant pairs and McNemar p=1.000p=1.000. Token usage tells the same story; the Verbose condition spent ∼ 1,362 tokens to the Standard’s ∼ 1,282 (a 6%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=20 paired. McNemar p=1.000p=1.000. Verbose Correct Verbose Wrong Standard Correct 0 0 Standard Wrong 0 20 Prompt-structure ablation. To check whether any prompt structure shifts the ceiling we ran three further variants at the same N=15N=15: Var A imposes a strict output schema, Var B adds positional formatting (P## slot markers identifying each agent position), and Var C adds an explicit logical mapping of the alliance/rivalry update rule (Figure 6). Variants A and C remain at 0.0%0.0\%. Variant B reaches 20.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 to N>15N>15 or 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 at N=15N=15 (Claude 3.7, n=20n=20 per condition). Standard/Verbose yield identical 0%0\% (McNemar p=1.000p=1.000); only Var B (positional slot formatting) reaches non-zero accuracy, and at 20.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 in pdp_d, not formatting); a constraint-management bottleneck on D2 (where 69.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 (where k∗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 ∼ 53 p lead on D2 collapses to a ∼ 3 p 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 with pd<0.93p_d<0.93 should not be relied on for tasks requiring more than ∼ 20 sequential steps, with the optimism caveat of Remark 1 in mind. 5 Discussion 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 in pdp_d and format-failure rates are already at 0–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. Because pdp_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 maintain pd∈[0.924,0.930]p_d∈[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 shifts pdp_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) is the most plausible single intervention for shifting pdp_d beyond the frontier tier on D2 or for reducing the D3 cascade; if process-supervised models achieve k∗>10k^*>10 on D3 it would substantially qualify the architectural reading of our findings. We commit to evaluating o1/o3, DeepSeek-R1, recursive scaffold models (16), and fast-slow recurrent mechanisms (15) 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. Remark 1 (The bound is optimistic). An error at step k∗k^* corrupts context for all k>k∗k>k^*, so per-step errors are positively correlated and the true decay is faster than pdNp_d^N predicts. The TFBC phenomenon; partial recovery from a corrupted context to a correct final answer - softens but does not eliminate this effect. Limitations. The remaining limitations are quantitative and we have tried to bound them rather than eliminate them. The independence assumption behind pdNp_d^N is wrong in a known direction (Assumption 1, Remark 1); 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%≈ 2\% false-negative rate in the 150-case audit). All evaluations were performed at T=0T=0 via OpenRouter; provider-specific optimisations may shift profiles slightly. The D3 prompt ablation is preliminary (one model, n=20n=20 paired) and a broader sweep over prompt structures is needed to distinguish architectural from coincidental failure cleanly. Formal AIC/BIC selection between geometric, accelerating pdNγp_d^N^γ, and linear 1−λN1-λ N decay forms at N>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. The 150150-case parser audit and the κ≥0.938κ≥0.938 inter-annotator agreement support that the reported numbers are not parser artefacts. 6 Conclusion 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 that 14.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 step k∗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, CCB provides 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. 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 A Detailed Results This appendix supplements the per-cell summary in Table 1 and the per-depth heatmap in Figure 4 with full numeric values: Tables 5–7 summarise across depths with 95% bootstrap CIs, and Tables 8–10 give the underlying depth-wise accuracies with Clopper-Pearson half-CIs. Table 5: D1 Alien Grid results (n=400n=400/model, LLaMA n=395n=395). pdp_d 95% CI in brackets. Human κ=0.977κ=0.977, n=50n=50. Model Acc. pdp_d [95% CI] TFBC Fmt% Gemini 2.0F 22.0% 0.930 [0.920, 0.938] 1% 0.0% DeepSeek 19.8% 0.924 [0.912, 0.933] 6% 0.0% Claude 3.7 18.2% 0.929 [0.918, 0.937] 21% 0.0% GPT-4o-mini 1.5% 0.688 [0.581, 0.746] 17% 0.0% LLaMA-3.3 1.3% 0.634 [0.500, 0.705] 0% 2.0% Table 6: D2 Symbolic Pointer Tracking (n=400n=400/model, DeepSeek n=399n=399, LLaMA n=392n=392). Human κ=0.978κ=0.978, n=50n=50. Model Acc. pdp_d [95% CI] TFBC Fmt% Claude 3.7 71.2% 0.987 [0.985, 0.989] 8% 0.0% DeepSeek 31.3% 0.955 [0.948, 0.960] 12% 5.5% Gemini 2.0F 30.0% 0.950 [0.943, 0.955] 29% 4.2% LLaMA-3.3 4.3% 0.767 [0.705, 0.804] 18% 1.0% GPT-4o-mini 1.2% 0.634 [0.500, 0.708] 20% 1.2% Table 7: D3 Social Logic (n=400n=400/model). Human κ=0.938κ=0.938, n=65n=65. McNemar verbosity ablation p=1.0p=1.0. pdp_d at 0.5000.500 is at the optimiser lower bound. Model Acc. pdp_d [95% CI] TFBC Fmt% Claude 3.7 6.2% 0.863 [0.836, 0.882] 56% 0.2% Gemini 2.0F 3.2% 0.736 [0.663, 0.781] 62% 0.2% DeepSeek 2.0% 0.684 [0.576, 0.743] 13% 4.8% GPT-4o-mini 0.2% 0.500† [0.500, 0.611] ∗* 0.0% LLaMA-3.3 0.0% 0.500† [0.500, 0.611] – 0.0% ∗* Single correct instance; TFBC unreliable. Table 8: D1 Alien Grid: Acc% ± Clopper-Pearson half-CI by depth. AvgTok = mean response tokens. N Claude Gemini DeepSeek GPT-4o-m LLaMA AvgTok 5 57.5± 16.0 65.0± 15.5 70.0± 15.0 10.0± 10.4 12.5± 11.3 183 10 25.0± 14.3 55.0± 16.1 42.5± 16.0 2.5± 6.5 0.0± 4.4 345 15 15.0± 12.1 35.0± 15.5 22.5± 13.8 2.5± 6.5 0.0± 4.4 497 20 7.5± 9.4 10.0± 10.4 10.0± 10.4 0.0± 4.4 0.0± 4.4 636 25 20.0± 13.3 17.5± 12.7 22.5± 13.8 0.0± 4.4 0.0± 4.4 772 30 10.0± 10.4 10.0± 10.4 7.5± 9.4 0.0± 4.4 0.0± 4.4 912 35 15.0± 12.1 17.5± 12.7 10.0± 10.4 0.0± 4.4 0.0± 4.4 1033 40 7.5± 9.4 7.5± 9.4 10.0± 10.4 0.0± 4.4 0.0± 4.4 1204 45 15.0± 12.1 2.5± 6.5 2.5± 6.5 0.0± 4.4 0.0± 4.4 1320 50 10.0± 10.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 1497 Table 9: D2 Symbolic Pointers: Acc% ± half-CI by depth. N Claude Gemini DeepSeek GPT-4o-m LLaMA AvgTok 5 97.5± 6.5 55.0± 16.1 37.5± 15.7 12.5± 11.3 40.0± 15.9 ∼ 205 10 90.0± 10.4 52.5± 16.2 30.0± 15.0 0.0± 4.4 2.5± 6.5 ∼ 380 15 85.0± 12.1 50.0± 16.2 45.0± 16.1 0.0± 4.4 0.0± 4.4 ∼ 555 20 67.5± 15.3 42.5± 16.0 52.5± 16.2 0.0± 4.4 0.0± 4.4 ∼ 725 25 80.0± 13.3 25.0± 14.3 30.0± 15.0 0.0± 4.4 0.0± 4.4 ∼ 895 30 57.5± 16.0 20.0± 13.3 35.0± 15.5 0.0± 4.4 0.0± 4.4 ∼ 1053 35 70.0± 15.0 22.5± 13.8 30.0± 15.0 0.0± 4.4 0.0± 4.4 ∼ 1235 40 57.5± 16.0 5.0± 8.2 17.5± 12.7 0.0± 4.4 0.0± 4.4 ∼ 1410 45 52.5± 16.2 10.0± 10.4 22.5± 13.8 0.0± 4.4 0.0± 4.4 ∼ 1580 50 55.0± 16.1 17.5± 12.7 12.5± 11.3 0.0± 4.4 0.0± 4.4 ∼ 1755 Table 10: D3 Social Logic: Acc% ± half-CI by depth. N Claude Gemini DeepSeek GPT-4o-m LLaMA AvgTok 5 35.0± 15.5 32.5± 15.3 20.0± 13.3 2.5± 6.5 0.0± 4.4 ∼ 130 10 5.0± 8.2 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 390 15 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 735 20 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 1265 25 5.0± 8.2 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 1730 30 7.5± 9.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 2170 35 2.5± 6.5 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 2780 40 2.5± 6.5 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 3195 45 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 3562 50 5.0± 8.2 0.0± 4.4 0.0± 4.4 0.0± 4.4 0.0± 4.4 ∼ 4317 Appendix B Failure 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 of 90∘90 CW rotation; k∗=2k^*=2. D2 constraint failure (Gemini, N=25N=25). After twenty correct steps the model illegally re-assigns variable A, 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 C Extended Related Work Depth-scaling and compositional generalisation. SCAN (8) and BIG-Bench (14) hold difficulty roughly constant and probe systematic generalisation to novel compositions. CCB complements that line by providing a continuous, parametric depth axis across three heterogeneous domains and a single-parameter decay model. SokoBench (11) isolates planning depth in Sokoban; TopoBench (9) focuses on topological reasoning and shows that structured state aids reasoning, motivating tool-augmented D3 extensions. Relational benchmarks. CLUTRR (13) tests multi-hop relational reasoning on kinship graphs and is the closest prior work to D3. CCB extends that line by providing deterministic ground-truth traces (not only final answers), enabling TFBC-level diagnostics; by applying a continuous depth axis from N=5N=5 to N=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) showed LLMs unroll memorised subgraphs with catastrophic failure at compositional OOD depths. Hou et al. (5) showed performance degrades under cumulative state-tracking load. CCB quantifies these phenomena via the k∗k^* distribution and the pdp_d summary statistic. Trace-level evaluation and structural uncertainty. Golovneva et al. (4) and Prasad et al. (10) evaluate reasoning chains for correctness and informativeness; MME-CoT (6) introduces precision and recall metrics for multimodal chain-of-thought. Chaudhury et al. (1) show that unstable self-preference rankings signal unreliable inference. CCB provides a complementary, ground-truth-grounded operationalisation that requires no LLM-as-judge. Process supervision and long-horizon execution. Process-supervised models (2) 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) analytically links per-step accuracy to an effective task horizon Hs≈ln(s)/ln(pd)H_s≈ (s)/ (p_d); CCB’s empirical pdp_d values feed directly into that framework. Recursive scaffolds (16) and fast-slow recurrence (15) target the same state-management bottleneck from the architecture side, and Kim et al. (7) argue that autoregressive token ordering is itself an inductive bias on accessible reasoning patterns.