Source-linked AI summary
ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark, Yejin Choi
TL;DR
The paper asks how well LLMs scale on complex logical reasoning and introduces ZebraLogic, a controllable CSP-based benchmark of logic grid puzzles. Evaluations across complexity levels and model or inference scaling reveal a pronounced accuracy decline that larger models and sampling do not eliminate, while expanded backtracking-based reasoning improves accuracy. The findings characterize limits of current LLM reasoning and motivate further study of non-monotonic reasoning.
Problem
Evidence about LLM performance and scalability on complex deductive reasoning remains limited, motivating evaluations that isolate logic, control complexity, reduce leakage, and objectively verify answers.
Method
The paper introduces ZebraLogic, a controlled benchmark of CSP-derived logic grid puzzles with adjustable complexity, and evaluates Llama, o1, and R1 across model size, sampling, reasoning tokens, and self-refinement.
Results
Performance drops sharply as complexity increases; this curse persists despite larger models and sampling, whereas backtracking with expanded reasoning steps significantly boosts accuracy.
Takeaways & Limitations
The results spotlight non-monotonic reasoning and provide a framework for studying approaches that may advance logical reasoning beyond model scaling alone.
Takeaways & Limitations
Model-size scaling reaches diminishing returns in complex search spaces, and visible reasoning chains can be incomplete or incorrect for larger problems requiring backtracking.
Abstract
from arXiv · showhide
We investigate the logical reasoning capabilities of large language models (LLMs) and their scalability in complex non-monotonic reasoning. To this end, we introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM reasoning performance on logic grid puzzles derived from constraint satisfaction problems (CSPs). ZebraLogic enables the generation of puzzles with controllable and quantifiable complexity, facilitating a systematic study of the scaling limits of models such as Llama, o1 models, and DeepSeek-R1. By encompassing a broad range of search space complexities and diverse logical constraints, ZebraLogic provides a structured environment to evaluate reasoning under increasing difficulty. Our results reveal a significant decline in accuracy as problem complexity grows -- a phenomenon we term the curse of complexity. This limitation persists even with larger models and increased inference-time computation, suggesting inherent constraints in current LLM reasoning capabilities. Additionally, we explore strategies to enhance logical reasoning, including Best-of-N sampling, backtracking mechanisms, and self-verification prompts. Our findings offer critical insights into the scalability of LLM reasoning, highlight fundamental limitations, and outline potential directions for improvement.
1. Introduction
The paper introduces ZebraLogic, a controlled framework for evaluating LLM logical reasoning on logic grid puzzles with adjustable complexity. Its experiments identify a pronounced performance decline as complexity increases and examine model-size, sampling, and reasoning-token scaling as possible responses.
- Framework: ZebraLogic formulates logic grid puzzles as CSP-based evaluations with controllable, quantifiable complexity and automatically verifiable solutions.The framework targets reasoning independent of domain-specific knowledge and heavy numerical computation.
- Findings: Performance declines dramatically as puzzle complexity increases, with most models struggling beyond 10^7 search possibilities or 20 Z3 conflicts.The paper terms this pattern the “curse of complexity for reasoning.”
- Scaling analysis: The study examines three scaling dimensions: model size, candidate-sample count, and reasoning-token computation during inference.These dimensions organize the analysis of how LLM reasoning behaves under increased resources.
- Framework: The benchmark evaluates scaling limits using search-space size and Z3 conflict count as complexity metrics.These metrics support systematic comparisons across increasing puzzle difficulty.
- Scaling analysis: Larger models and enhanced training data do not remove the complexity-related limitation, while sampling and backtracking-based reasoning offer different degrees of improvement.The paper reports limited practical gains from selection methods and stronger gains from expanded reasoning steps with backtracking.
2. Problem Formulation of Logical Reasoning
ZebraLogic formulates logic grid puzzles as constraint satisfaction problems whose unique assignments must satisfy attribute uniqueness and clue-derived logical constraints. The dataset generator constructs diverse, minimally clued puzzles that require deduction and, in harder cases, non-monotonic reasoning.
- 2.1. Logic Grid Puzzles: Each puzzle assigns N distinct values for each of M attributes across N houses using K clues to determine a unique solution.The assignment must satisfy both uniqueness requirements and logical conditions derived from the clues.
- 2.2. Problem Formulation: CSP variables x_a,k represent the value of attribute a in house k, while uniqueness constraints require {x_a,k | k ∈ H} = V_a for every attribute.The formulation defines houses, attributes, value domains, and one-to-one assignments across houses.
- 2.2. Problem Formulation: Clues become logical and positional constraints, including exclusions, equivalences, direct-left/right relations, adjacency, and specified numbers of houses between values.Implicit spatial constraints supplement the explicit verbal clues when translating puzzles into formal constraints.
- 2.2. Problem Formulation: The task is to find the attribute assignment consistent with all constraints, with the result guaranteed to be unique and representable as a solution table.Figure 2 illustrates the background, clues, and resulting assignment for a 3-house, 3-attribute, 6-clue puzzle.
- 2.3. ZebraLogic Dataset Creation: ZebraLogic includes attributes with at least 6 possible values and uses weighted clue sampling to balance puzzle complexity while preserving solvability and challenge.The Name attribute is always included, and simpler clue types receive higher sampling probabilities than harder types.
- 2.3. ZebraLogic Dataset Creation: Its clue vocabulary spans FOUNDAT, SAMEHOUSE, NOTAT, DIRECTLEFT/RIGHT, SIDEBYSIDE, LEFT/RIGHTOF, and ONE/TWOBETWEEN relations.These templates encode diverse relationships between attributes and houses.
- 2.3. ZebraLogic Dataset Creation: The generator samples attributes, randomly initializes a solution grid, creates comprehensive clues, and removes clues while a SAT solver verifies that the original solution remains unique.The iterative procedure returns the solution together with a minimal clue set.
3. Evaluation
The evaluation uses one-shot prompting and puzzle-level accuracy to compare open-weight and proprietary LLMs on ZebraLogic. Reasoning models perform best overall, but accuracy declines sharply with increasing search-space complexity, and model size alone does not ensure strong performance on large puzzles.
- 3. Evaluation: The evaluation uses one-shot in-context learning, JSON-formatted reasoning and answers, and puzzle-level accuracy requiring every grid cell to be correct.Models receive one solved example, while answers are parsed using a common format.
- 3. Evaluation: Models are compared with identical prompts, greedy decoding, and parsing scripts, except o1 is run three times and scored by its best result.The comparison includes open-weight Llama and Qwen models and proprietary GPT-4o, o1, and Claude APIs.
- 3.1. Main results: 81.0% overall accuracy makes o1 the top model, followed by DeepSeek-R1 at 78.7%, while Sonnet-3.5-1022 reaches 36.2%.DeepSeek-R1 performs slightly better than o1-full on Small and Medium puzzles but worse on Large and X-Large puzzles.
- 3.1. Main results: 17.0% X-Large accuracy for O1-Preview contrasts with other models struggling to achieve any correct solutions in that category.The performance gap becomes more pronounced as the search space grows.
- 3.1. Main results: Model rankings on ZebraLogic align with MATH and LiveCodeBench rankings, suggesting that logical reasoning ability correlates with performance on other reasoning tasks.This is reported as a cross-benchmark alignment rather than a causal relationship.
- 3.2. Curse of Complexity in Reasoning with LLMs: Reasoning performance drops significantly as search-space size increases, with worse models below 5% accuracy on Medium puzzles and almost no correct Large or X-Large solutions.The study examines model-size scaling and test-time-compute scaling, including candidate samples, reasoning tokens, and repeated sampling.
- 3.2. Curse of Complexity in Reasoning with LLMs: 32.6% overall accuracy is achieved by Llama-3.1-405B, but its accuracy falls from 22.5% on Medium puzzles to 1.5% on Large and 0.0% on X-Large puzzles.The results indicate that scaling model size does not necessarily improve reasoning on large search spaces.
4. Scaling Model Size Can Hardly Break the Curse of Complexity in Reasoning
Increasing model size improves accuracy in relatively small search spaces, but these benefits diminish as complexity grows, leaving performance to decline beyond a threshold.
- All model sizes experience a rapid accuracy decline as Z3-conflict complexity increases.The largest model, Llama-3.1-405B, also fails to sustain high accuracy once search-space complexity becomes sufficiently large.
- Larger models substantially outperform 3B and 8B models when search space size is ≤10^6.Llama-3.1-405B and Llama-3.1-70B show the clearest gains in these simpler search spaces.
- Figure 3 compares accuracy against search-space size while varying model size and test-time compute, showing diminishing returns as complexity grows.The figure separates model-size scaling on the left from pass@k sampling and chain-of-thought-length scaling on the right.
- Beyond 10^6 search-space possibilities, the accuracy advantage of larger models diminishes and eventually plateaus.This limits the utility of parameter scaling for highly complex reasoning tasks.
- Model-size scaling reaches diminishing returns beyond a complexity threshold and cannot prevent performance decline in complex search spaces.The passage identifies this as a limitation of current scaling strategies rather than a complete solution to high-complexity reasoning.
5. Scaling Test-Time Compute with Repeated Sampling: Promises & Challenges
The paper evaluates repeated sampling and other test-time compute strategies, finding that oracle selection can substantially improve coverage while practical selection methods face limitations as complexity increases.
- BoN-Oracle measures whether the correct answer appears among repeated samples, equivalent to pass@k under oracle selection.The method uses oracle knowledge of the correct answer to choose the best candidate from the sample pool.
- 69.1% overall accuracy for GPT-4o with BoN-Oracle_N=128 exceeds O1-mini’s 59.7% and approaches O1-preview’s 71.4%.On Medium-size examples, GPT-4o reaches 92.9% with BoN-Oracle_N=128 versus O1-preview’s 88.2%.
- Majority Voting improves GPT-4o’s overall accuracy from 31.7 to 38.0 at sample size N=32.Further increases in sample size do not necessarily improve performance.
- Figure 4 plots hidden chain-of-thought tokens against Z3 conflicts, with each point representing an example and larger conflict counts indicating harder problems.The figure links test-time reasoning allocation with solver-based problem difficulty.
- BoN-RM_N=32 reaches 33.9, underperforming Majority Voting and suggesting current reward models may not transfer directly to logical reasoning.The reward model used was designed primarily for chat or general instruction-following tasks.
6. Scaling Test-Time Compute with Extensive Chain-of-Thoughts Tokens
The paper examines scaling inference-time reasoning tokens and self-refinement as ways to improve LLM performance on increasingly complex logic puzzles. o1 scales hidden reasoning tokens with complexity, but token scaling eventually plateaus and self-verification yields only modest gains.
- Scaling reasoning tokens: Increasing reasoning-token generation is presented as a test-time compute strategy for logical reasoning.The paper treats chain-of-thought tokens as an inference-time resource that can be scaled.
- Scaling reasoning tokens: o1-mini and o1-preview generate about 5,144.6 and 5,346.3 hidden reasoning tokens on average, respectively.These averages are contrasted with 502.9 and 543.7 visible reasoning tokens for GPT-4o-mini and GPT-4o.
- Scaling reasoning tokens: o1-preview’s hidden reasoning tokens increase with Z3 conflicts below 20 conflicts but plateau beyond 30.The paper estimates roughly 400 hidden reasoning tokens per conflict below 20 conflicts and reports about 5,000 average hidden tokens for o1-full.
- Scaling reasoning tokens: o1-preview usually generates more hidden reasoning tokens when it makes mistakes than when it solves puzzles correctly.The authors relate this pattern to harder, more complex puzzles receiving more reasoning tokens.
- Self-refinement: Self-refinement asks models to revisit clues and constraints, with oracle and non-oracle settings for checking an initial answer.The procedure is implemented through follow-up queries in a multi-turn conversation.
- Self-refinement: Self-verification produces modest improvements, including 4o’s change from 31.7 to 33.0 before decreasing to 32.1 without oracle knowledge.The reported result illustrates that gains are limited and not uniformly sustained.
7. Related Work
Related work evaluates logical reasoning through benchmarks, formalization, transformer-based reasoning, and analyses of model errors and limitations. These studies span logic comprehension, grid puzzles, SAT solving, and the distinction between learned correlations and genuine reasoning.
- Logical reasoning benchmarks: Prior benchmarks study logical comprehension, language-to-formal translation, compositionality, and reasoning-chain errors in LLMs.The cited work includes LogiQA, grid-puzzle datasets, compositionality analyses, and error taxonomies.
- Approaches to logical reasoning: Some approaches train or analyze transformers as soft theorem provers or systems that parallel SAT-solving procedures such as DPLL.These studies extend transformer applications toward formal logical problem solving.
- Evidence of limitations: Empirical studies question whether LLMs genuinely understand logical rules rather than relying on probabilistic correlations or memorized training data.The cited literature examines the interaction between memorization and reasoning ability as logical complexity increases.
8. Conclusion
ZebraLogic is introduced as a controlled logic-grid benchmark for studying how LLM reasoning scales with adjustable complexity. Experiments show that increasing complexity sharply reduces performance, while expanded reasoning steps through backtracking substantially improve accuracy.
- Contribution: ZebraLogic controls logic-grid puzzle complexity to expose scaling limits in LLM-based reasoning.The benchmark is designed around carefully adjustable problem difficulty.
- Findings: Performance drops sharply as complexity increases, overshadowing gains from model growth or training-data expansion.The conclusion characterizes this pattern as a pronounced decline in performance.
- Findings: Increasing generation sample size yields modest improvements, whereas backtracking with expanded reasoning steps significantly boosts accuracy.The comparison highlights different outcomes for sampling-based and reasoning-step-based test-time scaling.
- Implications: The results highlight the importance of non-monotonic reasoning for advancing logical-reasoning research.This conclusion follows the benchmark’s findings on complexity and backtracking-based reasoning.
A. Additional Experimental Results and Analysis
Figure 5 compares hidden and visible reasoning-token distributions across o1 and GPT-4o models. Hidden-token counts are shown for o1 models, while visible-token counts are shown across all four models.
- Figure 5: The top panel shows hidden reasoning-token distributions for o1-mini and o1-preview, while the bottom panel shows visible-token distributions for four models.The visible-token comparison includes GPT-4o-mini, GPT-4o, o1-mini, and o1-preview.
- Figure 5: Mean hidden reasoning tokens are 5,144.6 for o1-mini and 5,346.3 for o1-preview.These values summarize the top-panel distributions.
- Figure 5: Mean visible reasoning tokens are 502.9 for GPT-4o-mini, 543.7 for GPT-4o, 305.7 for o1-mini, and 402.4 for o1-preview.These values summarize the bottom-panel distributions.
B. Details of the ZebraLogic Dataset
ZebraLogic characterizes each puzzle using search-space size and average Z3 conflict count, capturing complementary dimensions of logical complexity across house and attribute configurations.
- Puzzle Attributes: The dataset supports puzzles built from diverse attribute types, including names, colors, nationalities, animals, drinks, occupations, hobbies, and other categories.The listed attribute types span personal characteristics, preferences, objects, and activities.
- Complexity Metrics: Each problem instance uses search-space size and average Z3 conflicts as complementary complexity metrics.The conflict count measures the average number of conflicts encountered by the SMT solver while solving a puzzle.
- Complexity Metrics: The metrics vary across the number of houses (N) and attributes (M) in each grid configuration.Figure 7 visualizes how both complexity measures change as puzzle dimensions increase.
C. Additional Analysis
Additional analyses examine how models use inference-time computation, how puzzle complexity is measured, and how benchmark performance relates to broader evaluations. They find that more reasoning tokens do not guarantee success on larger search spaces, while o1’s hidden reasoning scales with difficulty.
- Visible Reasoning: GPT-4o generates more visible reasoning tokens than o1, especially when the search space is large, yet still fails on larger puzzles.The comparison concerns visible output tokens; o1 instead uses more hidden chain-of-thought tokens.
- Inference-Time Compute: Best-of-N sampling evaluates inference-time compute scaling separately for Small, Medium, Large, and X-Large puzzle groups.Figure 6 plots performance as the number of generated samples increases for each size category.
- Puzzle Complexity: Figure 7 maps log-scaled search-space size and average Z3 conflicts across puzzle sizes, with higher conflict counts indicating greater logical complexity.The heatmaps organize complexity from Small to X-Large using house-by-attribute grid configurations.
- Benchmark Comparisons: ZebraLogic rankings generally align with LMSYS Arena rankings but also reveal notable discrepancies between the evaluations.The supplied passage introduces GPT-4o-mini’s higher Arena Elo relative to several models before contrasting its ZebraLogic performance.
- Hidden Reasoning: o1’s hidden chain-of-thought token count scales with search-space size, averaging 5,144.6 tokens for o1-mini and 5,346.3 for o1-preview.These averages are about ten times GPT-4o-mini’s 502.9 and GPT-4o’s 543.7 reasoning tokens.
D. Further Discussion on o1’s Reasoning
The discussion examines whether visible outputs or summaries reveal o1’s reasoning process. It finds that hidden reasoning expands with complexity and may include reflection, while visible explanations often remain incomplete and unreliable for large puzzles.
- Hidden Reasoning: o1’s hidden reasoning tokens scale with search-space size, indicating more reasoning steps for more complex puzzles.The paper investigates visible outputs and hidden-token summaries because the hidden chain of thought is inaccessible.
- Visible Reasoning: o1’s visible reasoning chains are often incomplete for larger search spaces, especially when solving requires backtracking.Examples omit why alternatives are excluded even when the final solution is correct, and some visible steps can be incorrect.
- Visible Reasoning: Incomplete visible reasoning makes o1’s explanations unreliable and limits their usefulness for understanding complex reasoning.The paper also states that distilling these reasoning steps may not reliably improve other language models.
- Hidden Reasoning: Hidden-token summaries may show reflection behaviors such as recognizing contradictions, reevaluating assumptions, and revisiting clues.The discussion identifies these behaviors as potentially relevant to o1’s success on complex puzzles.
- Example Puzzle: The example puzzle uses three houses, unique names and drinks, and clues linking house position, water, and milk.Its stated clues place Peter in the second house, Arnold directly left of water, and water directly left of milk.
- Example Puzzle: The worked solution assigns Arnold tea to House 1, Peter water to House 2, and Eric milk to House 3.The reasoning derives Arnold’s first-house placement from the left-of relation and then assigns the remaining names and drinks.