---
title: "ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning"
description: "The authors treat logic grid puzzles (Zebra or Einstein-style riddles) as constraint satisfaction… 33 references, cited by 59 papers here."
authors: ["Bill Yuchen Lin", "Ronan Le Bras", "Kyle Richardson", "Ashish Sabharwal", "Radha Poovendran", "Peter Clark", "Yejin Choi"]
year: 2025
venue: "arXiv:2502.01100"
source: "https://arxiv.org/abs/2502.01100"
doi: "10.48550/arxiv.2502.01100"
arxiv: "2502.01100"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/lin-2025-zebralogic-scaling-limits-llms-logical/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/lin-2025-zebralogic-scaling-limits-llms-logical/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2025](https://md.research.elamur.ai/free/en/papers/2025/page/2/) / ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning

# ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning

**Authors:** [Bill Yuchen Lin](https://md.research.elamur.ai/free/en/authors/bill-yuchen-lin/), [Ronan Le Bras](https://md.research.elamur.ai/free/en/authors/ronan-le-bras/), [Kyle Richardson](https://md.research.elamur.ai/free/en/authors/kyle-richardson/), [Ashish Sabharwal](https://md.research.elamur.ai/free/en/authors/ashish-sabharwal/), [Radha Poovendran](https://md.research.elamur.ai/free/en/authors/radha-poovendran/), [Peter Clark](https://md.research.elamur.ai/free/en/authors/peter-clark/) and [Yejin Choi](https://md.research.elamur.ai/free/en/authors/yejin-choi/) · **Year:** 2025 · **Venue:** arXiv:2502.01100 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2502.01100) · [PDF](https://arxiv.org/pdf/2502.01100) · [DOI 10.48550/arxiv.2502.01100](https://doi.org/10.48550/arxiv.2502.01100) · [arXiv 2502.01100](https://arxiv.org/abs/2502.01100) · [OpenAlex](https://openalex.org/W4407129134)

**Citations:** 1 citations (OpenAlex, 2026-10-14) · [59](https://md.research.elamur.ai/free/en/papers/lin-2025-zebralogic-scaling-limits-llms-logical/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
It is still unclear how well large language models handle real deductive reasoning, and how that ability changes as models or compute grow. The authors treat logic grid puzzles (Zebra or Einstein-style riddles) as constraint satisfaction problems and build ZebraLogic, a puzzle generator and benchmark. Each puzzle has N houses, M attributes and K clues, and its single correct answer can be checked automatically. Difficulty is measured in two ways: the size of the search space and the number of conflicts the Z3 SMT solver hits while solving.

The authors tested Llama models, GPT-4o, o1 and DeepSeek-R1. Accuracy falls sharply as puzzles get harder, which the authors call the "curse of complexity." Neither larger models nor more samples remove this barrier. Models trained to produce long reasoning chains with backtracking, such as o1 and R1, cope noticeably better. Self-verification prompts add only small gains.

ZebraLogic needs no domain knowledge, resists memorization and lets difficulty be tuned precisely. This makes it a clean tool for locating where LLM reasoning fails and for judging which scaling strategies are worth pursuing.

## Key points
- **Dataset and access:** ZebraLogic contains 1,000 logic grid puzzles across many complexity levels. It is published as an ICML 2025 paper and is available as a Hugging Face Space (allenai/ZebraLogic).
- **Failure threshold:** Most models break down once the search space exceeds roughly 10^7 configurations (about a 4x5 grid) or once Z3 records more than about 20 conflicts.
- **Model size and sampling:** Scaling to Llama-3.1-405B does not overcome the complexity barrier. Repeated sampling helps only partly: even pass@128 fails, and practical answer selection (majority voting, reward models) gives limited improvement.
- **Reasoning tokens:** The o1 models generate nearly 10x more hidden reasoning tokens than other models, and this amount grows with puzzle difficulty. The authors find that there is an ideal balance between how many reasoning tokens a model spends and how many conflicts Z3 encounters, and o1-like models fall short of this balance on the hardest puzzles.
- **Self-verification:** Multi-turn self-verification prompting gives only marginal benefit. For example, GPT-4o rises from 31.7 to 33.0 after one round, then drops to 32.1.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 506 works · 330,053 citations
- [University of Washington](https://md.research.elamur.ai/free/en/universities/university-of-washington/) — University, Seattle, United States · 402 works · 212,763 citations
- [Allen Institute for Artificial Intelligence](https://md.research.elamur.ai/free/en/labs/allen-institute-for-artificial-intelligence/) — Research institute, Seattle, United States · 304 works · 106,137 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works · [🌐 Computer Networks and Communications](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-networks-and-communications/) · 100 works

🧭 Topics (2): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,894 works · [🧮 Reasoning](https://md.research.elamur.ai/free/en/topics/reasoning/) · 1,685 works

## Cite

Cite as: Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark and Yejin Choi. 2025. ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning. arXiv:2502.01100.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{lin2025zebralogic,
  title = {{ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning}},
  author = {Bill Yuchen Lin, Ronan {Le Bras}, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark and Yejin Choi},
  year = {2025},
  doi = {10.48550/arxiv.2502.01100},
  eprint = {2502.01100},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2502.01100}
}
```

- [← previous ToRL: Scaling Tool-Integrated RL](https://md.research.elamur.ai/free/en/papers/li-2025-torl-scaling-tool-integrated-rl/)
- [next → Zep: A Temporal Knowledge Graph Architecture for Agent Memory](https://md.research.elamur.ai/free/en/papers/rasmussen-2025-zep-temporal-knowledge-graph-architecture/)
- [↑ back to papers of 2025](https://md.research.elamur.ai/free/en/papers/2025/page/2/)

## References

33 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Dechter, R. Constraint Processing. Morgan Kaufmann, 2003. [find](https://scholar.google.com/scholar?q=Dechter%2C+R%2E+Constraint+Processing%2E+Morgan+Kaufmann%2C+2003%2E)
2. AI@Meta. [The llama 3 herd of models](https://md.research.elamur.ai/free/en/papers/grattafiori-2024-llama-3-herd-models/). 2024. URL https://arxiv.org/abs/2407.21783. [↗](https://arxiv.org/abs/2407.21783)
3. DeepSeek-AI. [DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning](https://md.research.elamur.ai/free/en/papers/deepseek-ai-2025-deepseek-r1-incentivizing-reasoning-capability/). arXiv, abs/2501.12948, 2025.
4. Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Ch… — [Language Models are Few-Shot Learners](https://md.research.elamur.ai/free/en/papers/brown-2020-language-models-few-shot-learners/)
5. Dziri, N., Lu, X., Sclar, M., Li, X. L., Jian, L., Lin, B. Y., West, P., Bhagavatula, C., Le Bras, R., Hwang, J. D., Sanyal, S., Welleck, S., Ren, X., Ettinger, A., Harchaoui, Z., and Choi, Y. [Faith and fate: Limits of transformers on compositionality](https://md.research.elamur.ai/free/en/papers/dziri-2023-faith-fate-limits-transformers-compositionality/). ArXiv, abs/2305.18654, 2023. URL [https://api.se…](https://api.se…) [↗](https://api.se…)
6. Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., Nori, H., Palangi, H., Ribeiro, M. T., and Zhang, Y. [Sparks of artificial general intelligence: Early experiments with gpt-4](https://md.research.elamur.ai/free/en/papers/bubeck-2023-sparks-artificial-general-intelligence-early/). arXiv preprint arXiv:2303.12712, 2023.
7. Gomes, C. P. and Shmoys, D. B. Completing quasigroups or latin squares: A structured graph coloring problem. 2002. URL [https://api.semanticscholar.org/CorpusID:10410543](https://api.semanticscholar.org/CorpusID:10410543). [↗](https://api.semanticscholar.org/CorpusID:10410543)
8. Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N. M., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B., Pope, R., Bradbury, J., A… — [PaLM: Scaling Language Modeling with Pathways](https://md.research.elamur.ai/free/en/papers/chowdhery-2022-palm-scaling-language-modeling-pathways/)
9. Clark, P., Tafjord, O., and Richardson, K. [Transformers as soft reasoners over language](https://md.research.elamur.ai/free/en/papers/clark-2020-transformers-soft-reasoners-over-language/). In International Joint Conference on Artificial Intelligence, 2020. URL [https://api.semanticscholar.org/CorpusID:211126663](https://api.semanticscholar.org/CorpusID:211126663). [↗](https://api.semanticscholar.org/CorpusID:211126663)
10. Colbourn, C. J. The complexity of completing partial latin squares. Discret. Appl. Math., 8:25–30, 1984. URL [https://api.semanticscholar.org/CorpusID:33813226](https://api.semanticscholar.org/CorpusID:33813226). [↗](https://api.semanticscholar.org/CorpusID:33813226)
11. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. [Measuring mathematical problem solving with the math dataset](https://md.research.elamur.ai/free/en/papers/hendrycks-2021-measuring-mathematical-problem-solving-math/). NeurIPS, 2021.
12. Jain, N., Han, K., Gu, A., Li, W.-D., Yan, F., Zhang, T., Wang, S., Solar-Lezama, A., Sen, K., and Stoica, I. [Livecodebench: Holistic and contamination free evaluation of large language models for code](https://md.research.elamur.ai/free/en/papers/jain-2024-livecodebench-holistic-contamination-free-evaluation/). arXiv preprint arXiv:2403.07974, 2024.
13. Lam, L. H. M., Thatikonda, R. K., and Shareghi, E. A closer look at logical reasoning with llms: The choice of tool matters. 2024. URL [https://api.semanticscholar.org/CorpusID:](https://api.semanticscholar.org/CorpusID:) 270219176. [↗](https://api.semanticscholar.org/CorpusID:)
14. Lambert, N., Morrison, J. D., Pyatkin, V., Huang, S., Ivison, H., Brahman, F., Miranda, L. J. V., Liu, A., Dziri, N., Lyu, X., Gu, Y., Malik, S., Graf, V., Hwang, J. D., Yang, J., Le Bras, R., Tafjord, O., Wilhelm, C., Soldaini, L., Smith, N. A., Wang, Y., Dasigi, P., and Hajishirzi, H. Tülu 3: Pus… — [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://md.research.elamur.ai/free/en/papers/lambert-2024-tulu-3-pushing-frontiers-open/)
15. Lambert, N., Pyatkin, V., Morrison, J. D., Miranda, L. J. V., Lin, B. Y., Chandu, K. R., Dziri, N., Kumar, S., Zick, T., Choi, Y., Smith, N. A., and Hajishirzi, H. Rewardbench: Evaluating reward models for language modeling. ArXiv, abs/2403.13787, 2024b. URL [https://api.semanticscholar](https://api.semanticscholar). org/CorpusID… [↗](https://api.semanticscholar)
16. Liu, C. Y., Zeng, L., Liu, J., Yan, R., He, J., Wang, C., Yan, S., Liu, Y., and Zhou, Y. [Skywork-reward: Bag of tricks for reward modeling in llms](https://md.research.elamur.ai/free/en/papers/liu-2024-skywork-reward-bag-tricks/). arXiv preprint arXiv:2410.18451, 2024.
17. Liu, H., Liu, J., Cui, L., Teng, Z., Duan, N., Zhou, M., and Zhang, Y. Logiqa 2.0—an improved dataset for logical reasoning in natural language understanding. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 31:2947–2962, 2023. URL [https://api.semanticscholar.org/CorpusID:259515154](https://api.semanticscholar.org/CorpusID:259515154). [↗](https://api.semanticscholar.org/CorpusID:259515154)
18. Liu, J., Cui, L., Liu, H., Huang, D., Wang, Y., and Zhang, Y. [Logiqa: A challenge dataset for machine reading comprehension with logical reasoning](https://md.research.elamur.ai/free/en/papers/liu-2020-logiqa-challenge-dataset-machine-reading/). ArXiv, abs/2007.08124, 2020. URL [https://api.semanticscholar.org/CorpusID:220483148](https://api.semanticscholar.org/CorpusID:220483148). [↗](https://api.semanticscholar.org/CorpusID:220483148)
19. Madusanka, T., Batista-navarro, R., and Pratt-hartmann, I. Identifying the limits of transformers when performing model-checking with natural language. In Vlachos, A. and Augenstein, I. (eds.), Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistic… [find](https://scholar.google.com/scholar?q=Madusanka%2C+T%2E%2C+Batista%2Dnavarro%2C+R%2E%2C+and+Pratt%2Dhartmann%2C+I%2E+Identifying+the+limits+of+transformers+when+performing+model%2Dchecking+with+natural+language%2E+In+Vlachos%2C+A%2E+and+Augenstein%2C+I%2E+%28eds%2E%29%2C+Procee)
20. Parmar, M., Patel, N., Varshney, N., Nakamura, M., Luo, M., Mashetty, S., Mitra, A., and Baral, C. [Logicbench: Towards systematic evaluation of logical reasoning ability of large language models](https://md.research.elamur.ai/free/en/papers/parmar-2024-logicbench-systematic-evaluation-logical-reasoning/). In Annual Meeting of the Association for Computational Linguistics, 2024. URL [https://api.semanticschola…](https://api.semanticschola…) [↗](https://api.semanticschola…)
21. Prosser, P. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9, 1993. URL [https://api.semanticscholar.org/CorpusID:36951414](https://api.semanticscholar.org/CorpusID:36951414). [↗](https://api.semanticscholar.org/CorpusID:36951414)
22. Richardson, K. and Sabharwal, A. Pushing the limits of rule reasoning in transformers through natural language satisfiability. In AAAI Conference on Artificial Intelligence, 2022. URL [https://api.semanticscholar.org/CorpusID:245219217](https://api.semanticscholar.org/CorpusID:245219217). [↗](https://api.semanticscholar.org/CorpusID:245219217)
23. Ryu, H., Kim, G., Lee, H. S., and Yang, E. Divide and translate: Compositional first-order logic translation and verification for complex logical reasoning. 2024. URL [https://api.semanticscholar.org/CorpusID:273233577](https://api.semanticscholar.org/CorpusID:273233577). [↗](https://api.semanticscholar.org/CorpusID:273233577)
24. Schlegel, V., Pavlov, K. V., and Pratt-Hartmann, I. Can transformers reason in fragments of natural language? In Conference on Empirical Methods in Natural Language Processing, 2022. URL [https://api.semanticscholar.org/CorpusID:](https://api.semanticscholar.org/CorpusID:) 253446947. [↗](https://api.semanticscholar.org/CorpusID:)
25. Sempolinski, P. Automatic solutions of logic puzzles. 2009. URL [https://api.semanticscholar.org/CorpusID:125304065](https://api.semanticscholar.org/CorpusID:125304065). [↗](https://api.semanticscholar.org/CorpusID:125304065)
26. Madusanka, T., Pratt-Hartmann, I., and Batista-Navarro, R. Natural language satisfiability: Exploring the problem distribution and evaluating transformer-based language models. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computati… [find](https://scholar.google.com/scholar?q=Madusanka%2C+T%2E%2C+Pratt%2DHartmann%2C+I%2E%2C+and+Batista%2DNavarro%2C+R%2E+Natural+language+satisfiability%3A+Exploring+the+problem+distribution+and+evaluating+transformer%2Dbased+language+models%2E+In+Ku%2C+L%2E%2DW%2E%2C+Martins%2C+)
27. Tyagi, N., Parmar, M., Kulkarni, M., Rrv, A., Patel, N., Nakamura, M., Mitra, A., and Baral, C. Step-by-step reasoning to solve grid puzzles: Where do llms falter? In Conference on Empirical Methods in Natural Language Processing, 2024. URL [https://api.semanticscholar.org/CorpusID:271329041](https://api.semanticscholar.org/CorpusID:271329041). [↗](https://api.semanticscholar.org/CorpusID:271329041)
28. Mitra, A. and Baral, C. Learning to automatically solve logic grid puzzles. In Conference on Empirical Methods in Natural Language Processing, 2015. URL [https://api.semanticscholar.org/CorpusID:2684696](https://api.semanticscholar.org/CorpusID:2684696). [↗](https://api.semanticscholar.org/CorpusID:2684696)
29. OpenAI. [Openai o1 system card](https://md.research.elamur.ai/free/en/papers/openai-2024-openai-o1-system-card/). arXiv, abs/2412.16720, 2024.
30. Pan, L., Ganesh, V., Abernethy, J., Esposo, C., and Lee, W. Can transformers reason logically? a study in sat solving. 2024. URL [https://api.semanticscholar.org/CorpusID:273234137](https://api.semanticscholar.org/CorpusID:273234137). [↗](https://api.semanticscholar.org/CorpusID:273234137)
31. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E. H., Xia, F., Le, Q., and Zhou, D. Chain of thought prompting elicits reasoning in large language models. ArXiv, abs/2201.[11903, 2022](https://md.research.elamur.ai/free/en/papers/wei-2022-chain-thought-prompting-elicits-reasoning/). URL [https://api.semanticscholar.org/CorpusID:246411621](https://api.semanticscholar.org/CorpusID:246411621). [↗](https://api.semanticscholar.org/CorpusID:246411621)
32. Xie, C., Huang, Y., Zhang, C., Yu, D., Chen, X., Lin, B. Y., Li, B., Ghazi, B., and Kumar, R. [On memorization of large language models in logical reasoning](https://md.research.elamur.ai/free/en/papers/xie-2025-memorization-large-language-models-logical/). 2024. URL [https://api.semanticscholar.org/CorpusID:273695832](https://api.semanticscholar.org/CorpusID:273695832). [↗](https://api.semanticscholar.org/CorpusID:273695832)
33. Yan, J., Wang, C., Huang, J., and Zhang, W. Do large language models understand logic or just mimick context? ArXiv, abs/2402.12091, 2024. URL [https://api.semanticscholar.org/CorpusID:267751049](https://api.semanticscholar.org/CorpusID:267751049). — [arXiv:2402.12091](https://arxiv.org/abs/2402.12091) [↗](https://api.semanticscholar.org/CorpusID:267751049)

*Updated 2 November 2026*