Elamur Research⌕
☰
home / papers / 2025 / ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning

Paper · 2025 · Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson et al.

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 UniversityStanford · United States506 works · 330,052 citations🎓University of WashingtonSeattle · United States402 works · 212,762 citations🔬Allen Institute for Artificial IntelligenceSeattle · United States304 works · 106,138 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Networks and Communications · 100 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksReasoning · 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. DOI 10.48550/arxiv.2502.01100 · arXiv 2502.01100

@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}
}

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
  2. AI@Meta. The llama 3 herd of models. 2024. URL https://arxiv.org/abs/2407.21783. ↗
  3. DeepSeek-AI. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. 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
  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. ArXiv, abs/2305.18654, 2023. URL 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. 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. ↗
  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
  9. Clark, P., Tafjord, O., and Richardson, K. Transformers as soft reasoners over language. In International Joint Conference on Artificial Intelligence, 2020. URL 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. ↗
  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. 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. 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: 270219176. ↗
  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
  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. org/CorpusID… ↗
  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. 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. ↗
  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. ArXiv, abs/2007.08124, 2020. URL 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
  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. In Annual Meeting of the Association for Computational Linguistics, 2024. URL https://api.semanticschola… ↗
  21. Prosser, P. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9, 1993. URL 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. ↗
  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. ↗
  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: 253446947. ↗
  25. Sempolinski, P. Automatic solutions of logic puzzles. 2009. URL 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
  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. ↗
  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. ↗
  29. OpenAI. 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. ↗
  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. URL 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. 2024. URL 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. — [arXiv:2402.12091](https://arxiv.org/abs/2402.12091) ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lin-2025-zebralogic-scaling-limits-llms-logical/