Source-linked AI summary
Reasoning Effort and Problem Complexity: A Scaling Analysis in LLMs
Benjamin Estermann, Roger Wattenhofer
TL;DR
The paper examines how LLM reasoning effort scales with problem complexity, using the infinitely scalable Tents puzzle and measuring token use and success. Effort generally scales with size for solvable instances, but o3-mini’s effort peaks around size 100 and then declines, while no model solves puzzles above size 100.
Problem
How reasoning effort changes as problem complexity grows remains a central question for understanding reasoning efficiency and potential bottlenecks in LLMs.
Source: §1 · p. 1Method
The authors measure token use and success rates across increasing grid sizes in the infinitely scalable Tents puzzle, which has a known linear-time solution.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
The results indicate limits to LLM logical coherence on larger problems and motivate work on improving reasoning scalability and efficiency.
Source: §5 · p. 4The analysis uses Tents puzzles; the authors call for evaluation on a wider variety of puzzles with different algorithmic complexity.
Source: §5 · p. 4
Abstract
from arXiv · showhide
Large Language Models (LLMs) have demonstrated remarkable text generation capabilities, and recent advances in training paradigms have led to breakthroughs in their reasoning performance. In this work, we investigate how the reasoning effort of such models scales with problem complexity. We use the infinitely scalable Tents puzzle, which has a known linear-time solution, to analyze this scaling behavior. Our results show that reasoning effort scales with problem size, but only up to a critical problem complexity. Beyond this threshold, the reasoning effort does not continue to increase, and may even decrease. This observation highlights a critical limitation in the logical coherence of current LLMs as problem complexity increases, and underscores the need for strategies to improve reasoning scalability. Furthermore, our results reveal significant performance differences between current state-of-the-art reasoning models when faced with increasingly complex logical puzzles.
1 INTRODUCTION
The paper asks how LLM reasoning effort changes as problem complexity grows, a question relevant to understanding reasoning efficiency and bottlenecks. It investigates this with the scalable Tents puzzle and measures token use alongside success rate.
1 INTRODUCTION
- The motivating question is how reasoning effort scales with problem complexity when models use more test-time computation to explore solution spaces.The introduction describes this as a fundamental question about advanced reasoning models.Source: §1 · p. 1
- Characterizing how token use changes with problem difficulty can reveal reasoning efficiency and potential bottlenecks, beyond accuracy on isolated tasks.The authors also frame this scaling analysis as relevant to designing more effective, resource-efficient reasoning models.Source: §1 · p. 1
- The study uses the infinitely scalable Tents puzzle, which has a known linear-time solution, to examine reasoning effort as grid size grows.It measures generated tokens and success rates across puzzle sizes.Source: §1 · pp. 1–2
2 RELATED WORK
Prior work evaluates LLM reasoning across broad benchmarks and develops prompting and training approaches to improve it. This paper situates scalable puzzles as a testbed for extrapolative algorithmic reasoning and logical coherence.
2 RELATED WORK
- Existing reasoning benchmarks span mathematics, commonsense, coding, and other domains, while PUZZLES focuses on algorithmic and logical reasoning and offers scalable tasks for testing extrapolation.The authors argue that PUZZLES’ scalability makes it an ideal testbed for extrapolative reasoning in LLMs.Source: §2 · p. 2
- Chain-of-thought, least-to-most, and tree-of-thought prompting can improve traditional LLM reasoning, whose unprompted capabilities are described as limited (Huang & Chang, 2022; Wei et al., 2022; Zhou et al., 2022; Yao et al., 2023).The paper focuses on algorithmic reasoning as an aspect of logical coherence, following the three-property framing of Lee et al. (2024).Source: §2 · p. 2
- Newer reasoning models use test-time compute, generating thousands of tokens before answering rather than producing an answer directly or thinking for only a few steps.The passage links this approach to reinforcement-learning-based training strategies introduced with OpenAI’s o1.Source: §2 · p. 2
3 METHODS
The methods use a scalable Tents puzzle, a common text-based prompt, and token-use and success-rate measures to assess reasoning across four enhanced-reasoning LLMs.
3.1 THE TENTS PUZZLE PROBLEM
- The Tents puzzle scales by changing grid dimensions and requires tents to satisfy tree adjacency, non-adjacency, and row-and-column count constraints.The study uses the easy generator preset unless otherwise specified and frames larger, likely unseen instances as tests of extrapolative reasoning.Source: §3.1 · pp. 2–3
- Models receive the same one-shot textual prompt and must output a solved grid in JSON, separating puzzle solving from interactive planning or action selection.The prompt contains the rules and initial puzzle state.Source: §3.1 · p. 3
3.2 EVALUATION CRITERIA
- Problem size is rows × columns; reasoning effort is total generated tokens, and success is whether the output satisfies all puzzle constraints.The authors fit a linear model of tokens versus size, assess fit with R2, and track success percentages across sizes.Source: §3.2 · p. 3
3.3 CONSIDERED MODELS
- The evaluation covers Gemini 2.0 Flash Thinking, OpenAI o3-mini, DeepSeek R1, and Qwen/QwQ-32B-Preview.The paper identifies these as models with enhanced reasoning capabilities.Source: §3.3 · p. 3
4 RESULTS
Reasoning tokens generally rise with puzzle size for successful attempts, but solvability is bounded and o3-mini’s effort eventually declines. Higher effort strategies extend its solving range at an added token cost on easier puzzles.
4 RESULTS
- Above size 100, no model solved puzzles; o3-mini had the highest overall solvability, followed by DeepSeek R1 and Gemini 2.0 Flash Thinking.Qwen/QwQ-32B-Preview’s performance degraded with increasing size and it struggled beyond size 25.Source: Figure 2 · p. 3, §4 · p. 4
- DeepSeek R1 and o3-mini show roughly linear token growth with similar slopes, but R1 uses more tokens; Qwen/QwQ-32B-Preview has a weaker linear relationship.The authors attribute Qwen’s weaker relationship as likely due to few successfully solved larger puzzles.Source: §4 · pp. 3–4
- For o3-mini, higher reasoning-effort strategies have steeper token-use slopes and solve larger puzzles, up to 10x10, but use more tokens on smaller solvable puzzles.The reported trade-off is wider solving range against extra token use on simpler instances.Source: Figure 3 · p. 4, §4 · p. 4
- For o3-mini, reasoning effort peaks around size 100 and then decreases; the paper reports that this pattern was not observed for the other models.The authors suggest a possible “frustration” effect as complexity rises.Source: §4 · p. 4
5 CONCLUSION
The study finds generally linear reasoning-effort scaling on solvable Tents instances, alongside performance differences and limits in logical coherence on larger problems.
- Reasoning effort generally scales linearly with problem size for solvable Tents instances.Source: §5 · p. 4
- o3-mini and DeepSeek R1 perform better than Qwen/QwQ-32B-Preview and Gemini 2.0 Flash Thinking.Source: §5 · p. 4
- The authors identify limits in logical coherence on larger problems and propose extending analysis to more puzzles and exploring reasoning-length and prompting strategies.Source: §5 · p. 4
A.1 FULL PROMPT
The appendix gives the full prompt used to ask models to solve a sample 4×4 Tents puzzle and return the completed grid as JSON.
- The example provides a 4×4 grid, row and column constraints, and asks for the solved grid as a JSON array of arrays without explanation.Source: §A.1 · p. 7
- The prompt defines the puzzle using trees, tents, and grass, with row and column counts constraining tent placement.Source: §A.1 · p. 7
- It specifies that tents must match one-to-one with trees by orthogonal adjacency and that no two tents may touch, including diagonally.Source: §A.1 · p. 7
A.2.1 EASY VS. TRICKY PUZZLES
Figures 4–6 show o3-mini reasoning effort and solved percentage against problem size at low, medium, and high reasoning-effort settings.
- Figure 4 plots reasoning tokens against problem size for successful tries and solved percentage against problem size at low reasoning effort.Source: Figure 4 · p. 8
- Figure 5 uses the same token-effort and solved-percentage comparisons against problem size at medium reasoning effort.Source: Figure 5 · p. 8
- Figure 6 uses the same comparisons at high reasoning effort, with linear fits shown for reasoning effort.Source: Figure 6 · p. 8
A.2.2 REASONING EFFORT FOR ALL MODELS
The appendix presents reasoning-effort figures for Qwen QwQ, DeepSeek R1, and Gemini 2.0 Flash Thinking, and reports the experiment cost.
A.2.2 REASONING EFFORT FOR ALL MODELS
- Figure 7 presents Qwen QwQ reasoning effort in tokens.Source: Figure 7 · p. 9
- Figure 8 presents DeepSeek R1 reasoning effort in tokens.Source: Figure 8 · p. 9
- Figure 9 quantifies Gemini-2.0-flash-thinking reasoning effort by response time.Source: Figure 9 · p. 9
A.3 COST
- The experiments cost around 80 USD in API credits.Source: §A.3 · p. 9