cs.CLApr 15, 2026
SaveEmpirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
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
Abstract
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 ( ) and 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 red and blue checkers on a -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 ) 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 and , illustrating permissible operations (fill, empty, pour).
Figure 10: Sudoku grid structure: digits must satisfy row, column, and 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 and each region has exactly cells |
| 3 | Validate digit domain; enforce completeness if required |
| 4 | Enforce puzzle clues if provided |
| 5 | Check each row for duplicates (ignore zeros) |
Table 2: General Sudoku validator pipeline.
| Step | Check / Action |
|---|---|
| 0 | Verify and lengths |
| 1 | Alphabet check on , |
| 2 | (Optional) Verify color counts ( per color) |
| 3 | Tokenize move string into |
| 4 | Enforce each |
| 5 | Simulate for all |
Table 3: Rubik’s Cube validator pipeline (deterministic simulation).
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 | Move list |
| 1D Checkers Swap | Planning | Board, per color | Move list |
| River Crossing | Planning | Pairs , boat cap. | 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 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: = pass, = fail, and = 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. |
| Constraint-Dense Compositionality (e.g., Sudoku, SAT, Graph Coloring) | 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 – , unstable reasoning at – , and sharp degradation at , 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.
More in this topic
LLM Evaluation
Large language model evaluation measures what models can do, how reliably they do it, and whether benchmark scores predict real-world performance.
See all 2,355 papers