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

A new benchmark reveals that large language models exhibit geometric per-step reasoning decay as task depth increases, with performance ceilings varying sharply by domain, according to a preprint posted to arXiv on June 28 [1]. The Complexity Ceiling Benchmark (CCB) fixes a task's semantic content and varies only the number of required sequential steps, N, from 5 to 50 across three structurally distinct regimes: grounded spatial state-tracking, abstract symbolic pointer manipulation, and transitive relational inference [1][2]. Researchers ran 6,000 trials over five frontier and open-weight LLMs [1][2]. They found a consistent pattern of geometric per-step decay with widely separated domain ceilings [1][2]. In the first two regimes, the strongest models retained a per-step probability of success (pd) greater than 0.92 across N=50 [1][2]. In the third regime, every model collapsed by N=5; the best model's 50%-success horizon reached only H0.5~4.7 steps, even though its pd was 0.863 [1][2]. A trace-level metric called TFBC showed that 14.5% of correct answers across the benchmark were reached via incorrect intermediate reasoning [1][2]. The study also found that forcing models to produce verbose state-tracking did not move the ceiling, with a McNemar test yielding p=1.000 [1][2]. The mean step at which reasoning first diverges, denoted k*, predicted within-domain accuracy better than parameter count [1][2]. The authors state that CCB and the geometric decay model together reduce a model's long-horizon reasoning profile to one interpretable number per task family [1][2]. The paper was submitted to arXiv's Artificial Intelligence section [1]. arXiv, which began on August 14, 1991, serves as an open-access repository of electronic preprints and postprints that are moderated but not peer-reviewed [6]. As of November 2024, the repository receives about 24,000 new articles per month [6]. The CCB preprint appears alongside experimental community tools developed under the arXivLabs framework, which arXiv launched in 2020 to enable collaborations that add value for readers and authors while adhering to values of openness, community, excellence, and user data privacy [4][5].