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

arXiv: https://arxiv.org/abs/2606.29278 · HTML: https://mlsanity.com/paper/2606.29278/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 15 of its 17 references that are in the map.
- First posted on arXiv 28 Jun 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 15 of 15)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [ROSCOE: A Suite of Metrics for Scoring Step-by-Step Reasoning](https://mlsanity.com/paper/2212.07919/) (2022)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [MME-CoT: Benchmarking Chain-of-Thought in Large Multimodal Models for Reasoning Quality, Robustness, and Efficiency](https://mlsanity.com/paper/2502.09621/) (2025)
- [ReCEval: Evaluating Reasoning Chains via Correctness and Informativeness](https://mlsanity.com/paper/2304.10703/) (2023)
- [The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs](https://mlsanity.com/paper/2509.09677/) (2025)
- [Recursive Models for Long-Horizon Reasoning](https://mlsanity.com/paper/2603.02112/) (2026)
- [WMF-AM: Probing LLM Working Memory via Depth-Parameterized Cumulative State Tracking](https://mlsanity.com/paper/2603.27343/) (2026)
- [TopoBench: Benchmarking LLMs on Hard Topological Reasoning](https://mlsanity.com/paper/2603.12133/) (2026)
- [SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models](https://mlsanity.com/paper/2601.20856/) (2026)
- [Exploration of Fast-Slow Latent Recurrence for Train-Short, Test-Long Generalization](https://mlsanity.com/paper/2604.01577/) (2026)
- [Quantifying Consistency in LLM Logical Reasoning via Structural Uncertainty](https://mlsanity.com/paper/2606.17312/) (2026)

## Abstract (arXiv)

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.