Research map / Large language models / Agents, code and math
ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces ZebraLogic, a generated benchmark of 1,000 logic grid puzzles from CSPs with controllable complexity, and evaluates LLMs and test-time compute scaling, finding a "curse of complexity" where accuracy collapses on large search spaces.
Problem
Understanding how well LLMs perform pure logical deduction and how their reasoning scales with problem complexity, independent of domain knowledge and with verifiable answers.
Approach
Generate logic grid (Zebra/Einstein) puzzles from CSPs with a SAT-based minimal-clue procedure, so that complexity is controlled by search space size and Z3 conflict count, and use this to study model size, repeated sampling, and hidden reasoning-token scaling.
Key results
- o1-full achieves 81.0% overall puzzle accuracy on ZebraLogic, while DeepSeek-R1 reaches 78.7% and the best non-reasoning model Claude Sonnet 3.5 reaches 36.2%.
- Accuracy collapses on X-Large puzzles (search space >=10^10): o1-full 42.5%, DeepSeek-R1 28.5%, and most non-reasoning models near 0%; Llama-3.1-405B gets 32.6% overall but 0.0% on X-Large.
- GPT-4o with Best-of-N oracle selection at N=128 reaches 69.1% overall, while majority voting only improves GPT-4o from 31.7% to 38.0% and self-verification to 33.0%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase puzzle search-space complexity | LLMs evaluated on ZebraLogic · ZebraLogic, Small to X-Large | puzzle-level accuracy: o1-full: 97.2 -> 42.5; DeepSeek-R1: 98.4 -> 28.5 | Hurt |
| Scale model size from smaller Llama models to Llama-3.1-405B | Llama models · ZebraLogic Large and X-Large | puzzle-level accuracy: Llama-3.1-405B: 1.5 Large, 0.0 X-Large | No clear effect |
| Use oracle selection among 128 samples instead of one greedy GPT-4o answer | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 69.1 | Helped |
| Use majority voting across 32 samples instead of one greedy GPT-4o answer | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 38.0 | Helped |
| Increase majority-vote sample count from 32 to 128 | GPT-4o · ZebraLogic | puzzle-level accuracy: 38.0 -> 37.6 | Hurt |
| Select among 32 samples using a reward model instead of one greedy GPT-4o answer | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 33.9 | Helped |
| Add one self-verification turn | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 33.0 | Helped |
| Repeat self-verification twice rather than using the original GPT-4o answer | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 32.1 | Helped |
| Use oracle-guided self-verification instead of one greedy GPT-4o answer | GPT-4o · ZebraLogic | puzzle-level accuracy: 31.7 -> 34.8 | Helped |
| Use oracle selection among 128 samples instead of one greedy GPT-4o-mini answer | GPT-4o-mini · ZebraLogic | puzzle-level accuracy: 20.1 -> 51.2 | Helped |
| Use majority voting across 32 samples instead of one greedy GPT-4o-mini answer | GPT-4o-mini · ZebraLogic | puzzle-level accuracy: 20.1 -> 24.5 | Helped |
| Generate substantially more hidden reasoning tokens at inference | o1 models versus GPT-4o models · ZebraLogic | mean hidden reasoning tokens: 5,144.6; 5,346.3; 502.9; 543.7 | Mixed |
Surprising findings
- Scaling model size from 8B to 405B yields little gain on large search spaces, and even pass@128 with GPT-4o does not break the curse of complexity on X-Large puzzles.
- Reward model selection (Skywork-Reward) underperforms majority voting on logic puzzles, suggesting chat-oriented RMs do not transfer to reasoning.
Limitations
- Visible reasoning from o1 is incomplete and cannot fully explain its reasoning on complex puzzles
- Evaluation limited to one-shot prompting with greedy decoding for most models, and o1 run three times
- Puzzles are restricted to a single logic grid puzzle format with a fixed clue-type set
Experimental setup
Datasets: ZebraLogic
Benchmarks: ZebraLogic
Metrics: puzzle-level accuracy cell-level accuracy pass@k
Baselines: GPT-4o GPT-4o-mini Claude Sonnet 3.5 Gemini-1.5-Pro Mistral-Large-2 Qwen2.5-72B DeepSeek-v2.5 Gemma-2-27B Phi-3.5
Builds on: Z3 Best-of-N sampling chain-of-thought
Closest papers by meaning
- GSM-$\infty$: How Do your LLMs Behave over Infinitely Increasing Reasoning Complexity and Context Length? (ICML 2025 · similarity 0.92)
- Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning (NeurIPS 2025 · similarity 0.91)
- Logic.py: Bridging the Gap between LLMs and Constraint Solvers (NeurIPS 2025 · similarity 0.91)
- The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity (NeurIPS 2025 · similarity 0.91)
- Enhancing Reasoning Capabilities of LLMs via Principled Synthetic Logic Corpus (NeurIPS 2024 · similarity 0.91)
- Reasoning-as-Logic-Units: Scaling Test-Time Reasoning in Large Language Models Through Logic Unit Alignment (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.