Organizations: Department of Information and Communication Engineering, University of Rajshahi, Bangladesh · College of Engineering and Computer Sciences, Marshall University, Huntington, WV, USA · Department of Computer Science and Engineering, University of Rajshahi, Bangladesh
Large Language Models (LLMs) are increasingly described as possessing strong reasoning capabilities, supported by high performance on mathematical, logical, and planning benchmarks. However, most existing evaluations rely on aggregate accuracy over fixed datasets, obscuring how reasoning behavior evolves as task complexity increases. In this work, we introduce a controlled benchmarking framework to systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity. We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube, each parameterized to precisely control complexity while preserving underlying semantics. Using deterministic validators, we evaluate multiple open and proprietary LRMs across low, intermediate, and high complexity regimes, ensuring that only fully valid solutions are accepted. Our results reveal a consistent phase transition like behavior: models achieve high accuracy at low complexity but degrade sharply beyond task specific complexity thresholds. We formalize this phenomenon as reasoning collapse. Across tasks, we observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs. Increased reasoning length does not reliably improve correctness, and gains in one problem family do not generalize to others. These findings highlight the need for evaluation methodologies that move beyond static benchmarks and explicitly measure reasoning robustness under controlled complexity.
Figures & tables
Model
Context Length (Tokens)
Parameters
Qwen Plus 0728 (Thinking) Alibaba Cloud (2025)
1,000,000
3.6B
Kimi K2 (Thinking) Moonshot AI (2025)
128,000
1T (32B active)
Claude 3.7 Sonnet (Thinking) Anthropic (2025)
200,000
approx. 175B
Gemini 3 Pro Preview Google DeepMind (2026)
1,048,576
>1T
GPT-5 Pro OpenAI (2026)
400,000
approx. 1.8T
DeepSeek V3.2 DeepSeek-AI (2025)
163,840
671B (37B active)
Table 1: Context window size and total parameter count of evaluated models.
Figure 1: Tower of Hanoi setup with three pegs ( A,B,C ) and n disks; only the top disk may be moved, and no larger disk may be placed on a smaller disk.
Figure 2: Checker Jumping initial configuration for n red and n blue checkers on a (2n+1) -cell board with a single empty space.
Figure 3: Valid local moves in Checker Jumping: (i) slide into adjacent empty space; (ii) jump over one opposing checker into the empty space.
Figure 4: River Crossing: example goal configuration where all actors and agents are safely transported to the right bank.
Figure 5: Valid boat moves in River Crossing: the boat carries a non-empty subset of entities (up to capacity k ) between banks while maintaining safety constraints.
Figure 6: Boolean Satisfiability (SAT): CNF formula structure with variables, literals, and clause interactions.
Figure 7: Cryptarithmetic (alphametic) puzzle: each letter must map to a unique digit, and the decoded arithmetic expression must hold exactly.
Figure 8: Graph Coloring example: each vertex receives a color from a fixed palette such that adjacent vertices do not share the same color.
Figure 9: Water Jug setup with two jugs of capacities c1 and c2 , illustrating permissible operations (fill, empty, pour).
Figure 10: Sudoku grid structure: digits must satisfy row, column, and 3×3 subgrid uniqueness constraints.
Figure 11: Rubik’s Cube representation and face-turn notation used to describe legal moves.
Step
Check / Action
0
Validate shapes of grid , puzzle , regions
1
Build region partition (jigsaw, rectangular, or inferred square blocks)
2
Verify region count =N and each region has exactly N cells
3
Validate digit domain; enforce completeness if required
Figure 12: Prompt template for the Tower of Hanoi puzzle, including role specification, rule definitions, and required move-list output format.
Figure 13: Prompt template for the 1D Checkers Swap puzzle, specifying legal moves and an index-based output schema.
Figure 14: Prompt structure for the River Crossing puzzle, emphasizing capacity limits and the jealous-husbands safety constraint.
Figure 15: Prompt template for Boolean SAT, showing the CNF array encoding and dictionary-based assignment output.
Figure 16: Prompt template for Cryptarithmetic puzzles, outlining digit-uniqueness, leading-zero constraints, and mapping output format.
Figure 17: Prompt template for Graph Coloring, specifying allowed colors, node sets, and adjacency constraints.
Figure 18: Prompt template for the Water Jug puzzle, including the fixed action space and structured move-list format.
Figure 19: Prompt template for Sudoku, using the 81-character string representation for puzzle input and output.
Figure 20: Prompt template for the 3 × 3 Rubik’s Cube, using WCA notation for all legal face-turns.
Task
Structure
Inputs
Required Output
Tower of Hanoi
Recursion
Disks n
Move list
1D Checkers Swap
Planning
Board, N per color
Move list
River Crossing
Planning
Pairs n , boat cap. k
Transfers
Boolean SAT
Constraints
CNF clauses
Boolean assignment
Cryptarithmetic
Symbolic CSP
Letter–digit equation
Letter → digit map
Graph Coloring
Constraints
Nodes, edges, colors
Node → color map
Table 4: Prompt structure, inputs, and required outputs for all benchmark tasks (ordered consistently with the experimental pipeline).
Figure 21: LLM task performance across Tower of Hanoi complexity levels.
Figure 22: LLM outcomes on the Water Jug task across increasing difficulty.
Figure 23: Model robustness on Boolean SAT across clause-complexity levels.
Figure 24: Performance trajectories on the Checker Jumping puzzle.
Figure 25: Graph Coloring pass/fail/collapse profiles across complexity levels.
Figure 26: LLM performance on River Crossing under escalating multi-agent constraints.
Figure 27: Rubik’s Cube performance across permutation-complexity levels.
Figure 28: Sudoku performance, illustrating extreme sensitivity to symbolic-consistency violations.
Figure 29: Mean pass rate across tasks (lower mean indicates higher difficulty).
Figure 30: Global mean pass rate as a function of complexity level.
Figure 31: Global error distribution per model, showing proportions of correct outputs, incorrect outputs, and collapses across all tasks and complexity levels.
Figure 32: Global collapse threshold summary showing, for each model, the highest complexity level Lk at which valid solutions are reliably produced across all nine reasoning tasks.
Figure 33: Global Failure Mode Map across tasks and difficulty levels. Outcomes are encoded as: 1 = pass, 0 = fail, and −1 = collapse.
Figure 34: Global mean-performance heatmap aggregating pass rates across all models and tasks. Higher values indicate stronger and more consistent reasoning ability.
Figure 35: Success Score Matrix showing normalized mean pass rates per task–model pair.
Figure 36: Aggregate model strength, measured as overall mean pass rate across all tasks and complexity levels.
Failure Mechanism
Description and Typical Manifestation
Long-Horizon State Degradation
Breakdown of state tracking over extended sequences: illegal transitions, cyclic regressions, or references to nonexistent state elements (e.g., Tower of Hanoi, Rubik’s Cube). This pattern is consistent with limited effective state retention under autoregressive generation.
Constraint Propagation Failure
Inability to maintain global consistency across interacting constraints: models describe rules correctly yet output contradictory or invalid assignments (e.g., Sudoku duplicates, violated SAT clauses, graph coloring conflicts).
Unstable Feasibility Planning
Failure to preserve feasibility under sequential or safety constraints: unsafe intermediate states, deadlocks, or incomplete plans (e.g., River Crossing, Checker Jumping), indicating difficulty coordinating branching actions with global invariants.
Non-Scaling of Reasoning with Token Length
Increased verbosity does not yield improved correctness: at higher complexity, traces may become longer but remain invalid, or degrade into repetition/truncation despite large budgets, suggesting limits beyond token availability.
Table 5: Core mechanisms of reasoning failure in LRMs, identified through validator-grounded analysis across tasks.
Structural Regime
Impact on Scaling and Collapse Behavior
Recursive Structure (e.g., Tower of Hanoi)
Often supports deeper scaling relative to other families: self-similar, rule-driven templates are easier to extend before catastrophic drift, though horizons still eventually exceed reliable state tracking.
Sequential Deterministic Dynamics (e.g., Water Jug)
Enables moderate scaling when branching is low and transitions are predictable, but failures emerge as long-range dependencies accumulate and arithmetic/state drift compounds.
Tends to collapse earlier: models can verbalize constraints yet struggle to jointly enforce global consistency under increasing density and coupling, leading to subtle but fatal violations.
High-Branching / High-Dimensional State Spaces (e.g., Rubik’s Cube, River Crossing)
Often collapses earliest: large action spaces, safety predicates, and entangled state representations amplify error propagation and overwhelm reliable state maintenance.
Table 6: Structural factors governing reasoning scalability and collapse thresholds across tasks.
Regularity
Description
Uniform Three-Phase Trajectory
Most models exhibit reliable success at L1 – L2 , unstable reasoning at L3 – L4 , and sharp degradation at L5+ , consistent with shared limits in state tracking and constraint enforcement.
Robustness on Template-Based Tasks
Tasks with strong templates (e.g., Tower of Hanoi; to some extent Checker Jumping) show more stable behavior, consistent with pattern imitation outperforming open-ended search under complexity.
Early Collapse on Dense or High-Dimensional Tasks
Constraint-dense and high-dimensional domains (e.g., Sudoku/SAT/Graph Coloring; Rubik’s Cube/River Crossing) induce similar collapse regimes across models, suggesting that structure dominates over model-specific differences.
Token Length Not Predictive of Success
Additional chain-of-thought length does not reliably improve correctness at higher complexity; verbosity varies, but validity does not track it consistently once tasks exceed effective capacity.
Convergent Failure Modes
Similar structural errors recur across architectures: contradictory assignments (SAT), repeated digits (Sudoku), illegal transitions or unsafe states (planning tasks), indicating shared bottlenecks.
Table 7: Cross-model regularities observed across evaluated LRMs. Convergent patterns across tasks and regimes suggest shared structural constraints rather than model-specific idiosyncrasies.
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.
While Large Language Models (LLMs) achieve high performance on standard mathematical benchmarks, their problem-solving abilities depend on the context and textual formatting. We introduce the Robust Reasoning Benchmark (RRB), a pipeline of 13 deterministic textual perturbations applied to AIME 2024 and AIME 2025. Evaluating 8 state-of-the-art models, we find that frontier models are largely resilient, with the notable exception of Claude, which categorically refuses many transformed prompts. Open-weights reasoning models exhibit a range of failure modes under structural noise (cognitive thrashing, tokenization breakdown, and reasoning collapse), with up to 54% average accuracy drops across perturbations and up to 100% on some. We further study one of these failure modes in isolation: attention dilution caused by the model's own chain-of-thought. By tasking models with solving multiple independent mathematical problems sequentially within a single context window, we identify Intra-Query Attention Dilution. Open-weights models ranging from 7B to 120B parameters exhibit accuracy decay on subsequent problems, suggesting that intermediate reasoning steps progressively pollute standard dense attention mechanisms. We argue that in order to achieve reliable reasoning, future architectures need to integrate explicit contextual resets within models' own chain-of-thought, leading to open research questions regarding the optimal granularity of reasoning tasks.
Pavel Golikov, Evgenii Opryshko, Gennady Pekhimenko +1
Recent advances in large language models (LLMs) have brought impressive performance across diverse tasks; however, shortcomings remain in logical reasoning, including inconsistencies under linguistic variation. To improve the reasoning capacity of LLMs, we must be able to accurately measure their reasoning capacity. Current benchmarks primarily report single accuracy numbers on selected reasoning tasks. Such a performance-based evaluation methodology says little about a model's generalization capacity in reasoning. To address this limitation, we argue for a different evaluation paradigm, called competence-based evaluation (CBE), which tests whether models reliably apply the same competence across a family of problems. A parameterized generator scales complexity while keeping the required competence fixed, and matched answer-preserving presentations test correctness beyond one formulation. We instantiate CBE on elementary ordering tasks, scaling input size while varying presentations of the same ordering rule. Across six GPT and Qwen models, performance is reasonably good over bounded complexity ranges, but even strong models fail the competence condition across the tested family. Chain-of-thought and GRPO extend strong performance without resolving all tested failures; supervised LoRA shows little held-out transfer. CBE provides diagnostic profiles and an evaluation protocol that can grow with future models.