ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cost of improved performance through extended internal reasoning scales poorly.
“Frontier reasoning-tuned language models still fail on deductive tasks at depth, and the cost of improved performance through extended internal reasoning scales poorly.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [4]
Section 6 reports that o1-preview uses more hidden reasoning tokens as puzzles grow harder, but that this scaling plateaus for highly complex puzzles; it also reports more tokens on mistakes than on correct solutions. The Introduction says o1 models use nearly ten times as many hidden reasoning tokens as other models. These findings support a concern about the compute required for gains on difficult puzzles, but the paper does not establish a general cost-versus-performance scaling rule and describes expanded reasoning as promising. (LLM, conf=0.82)
Experimental — accuracy not yet measuredAccuracy degrades on long deductive chains, even for strong reasoning-tuned models.
“First, accuracy degrades on long deductive chains, even for strong reasoning-tuned models.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [4]
Section 3.2 reports that accuracy drops as the search space grows, and Section 3.1 shows that reasoning-tuned models, including o1 and DeepSeek-R1, struggle on larger puzzles. The paper measures puzzle complexity and search-space size, not deductive-chain length specifically, so the claim’s reference to long chains is more specific than the reported finding. (LLM, conf=0.82)
Experimental — accuracy not yet measuredZebraLogic identifies sharp accuracy decline in constraint-satisfaction once the search space exceeds 10^7 possibilities.
“ZebraLogic (Lin et al., 2025) identifies sharp accuracy decline in constraint-satisfaction once the search space exceeds 10 7 possibilities.”
From Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog (2026) · cites this paper as Lin et al., 2025
Frontier reasoning-tuned language models still fail on deductive tasks at depth.
“Frontier reasoning-tuned language models still fail on deductive tasks at depth, and the cost of improved performance through extended internal reasoning scales poorly.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [4]
Current reasoning-tuned models attempt to improve reliability by allocating more internal reasoning, or thinking, tokens.
“Current reasoning-tuned models attempt to improve reliability by allocating more internal reasoning, or thinking , tokens.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [4]
Lin et al. [4] demonstrate this collapse on grid-style logic puzzles, where frontier reasoning models suffer significant accuracy drops as problem complexity increases.
“Lin et al. [4] demonstrate this collapse on grid-style logic puzzles, where frontier reasoning models suffer significant accuracy drops as problem complexity increases.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [4]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
No citation lists for this paper
No citation lists for this paper yet — checked again daily.
Cited by 1
Research works printed but not linked: 33
- AI@Meta. The llama 3 herd of models. 2024. URL https: //arxiv.org/abs/2407.21783.
- Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lund- berg, S., Nori, H., Palangi, H., Ribeiro, M. T., and Zhang, Y. Sparks of artificial general intelligence: Early ex- periments with gpt-4. arXiv preprint arXiv:2303.12712, 2023. · arXiv
- 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., Austin, J., Isard, M., Gur-Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., García, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pel- lat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Saeta, B., Díaz, M., Fi- rat, O., Catasta, M., Wei, J., Meier-Hellstern, K. S., Eck, D., Dean, J., Petrov, S., and Fiedel, N. Palm: Scaling lan- guage modeling with pathways. ArXiv, abs/2204.02311, 2022. URL https://api.semanticscholar. org/CorpusID:247951931. · arXiv
- Clark, P., Tafjord, O., and Richardson, K. Trans- formers as soft reasoners over language. In Inter- national Joint Conference on Artificial Intelligence, 2020. URL https://api.semanticscholar. org/CorpusID:211126663.
- Colbourn, C. J. The complexity of completing par- tial latin squares. Discret. Appl. Math., 8:25-30, 1984. URL https://api.semanticscholar. org/CorpusID:33813226.
- de Moura, L. M. and Bjørner, N. S. Z3: An efficient smt solver. In International Conference on Tools and Algorithms for Construction and Analysis of Systems, 2008. URL https://api.semanticscholar. org/CorpusID:15912959.
- Dechter, R. Constraint Processing. Morgan Kaufmann, 2003.
- DeepSeek-AI. DeepSeek-R1: Incentivizing reasoning ca- pability in LLMs via reinforcement learning. arXiv, abs/2501.12948, 2025. · arXiv
- 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., Har- chaoui, Z., and Choi, Y. Faith and fate: Limits of trans- formers on compositionality. ArXiv, abs/2305.18654, 2023. URL https://api.semanticscholar. org/CorpusID:258967391. · arXiv
- 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.
- Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring math- ematical problem solving with the math dataset. NeurIPS, 2021.
- 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 eval- uation of large language models for code. arXiv preprint arXiv:2403.07974, 2024. · arXiv
- 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.
- 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: Pushing frontiers in open language model post-training. ArXiv, abs/2411.15124, 2024a. URL https://api.semanticscholar. org/CorpusID:274192505. · arXiv
- Lambert, N., Pyatkin, V., Morrison, J. D., Miranda, L. J. V., Lin, B. Y., Chandu, K. R., Dziri, N., Ku- mar, S., Zick, T., Choi, Y., Smith, N. A., and Ha- jishirzi, H. Rewardbench: Evaluating reward mod- els for language modeling. ArXiv, abs/2403.13787, 2024b. URL https://api.semanticscholar. org/CorpusID:268537409. · arXiv
- 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. · arXiv
- Liu, H., Liu, J., Cui, L., Teng, Z., Duan, N., Zhou, M., and Zhang, Y. Logiqa 2.0-an im- proved dataset for logical reasoning in natural lan- guage understanding. IEEE/ACM Transactions on Au- dio, Speech, and Language Processing, 31:2947-2962, 2023. URL https://api.semanticscholar. org/CorpusID:259515154.
- Liu, J., Cui, L., Liu, H., Huang, D., Wang, Y., and Zhang, Y. Logiqa: A challenge dataset for machine reading compre- hension with logical reasoning. ArXiv, abs/2007.08124, 2020. URL https://api.semanticscholar. org/CorpusID:220483148. · arXiv
- 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 Confer- ence of the European Chapter of the Association for Com- putational Linguistics, pp. 3539-3550, Dubrovnik, Croa- tia, May 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.eacl-main.257. URL https: //aclanthology.org/2023.eacl-main.257. · DOI
- Madusanka, T., Pratt-Hartmann, I., and Batista-Navarro, R. Natural language satisfiability: Exploring the prob- lem distribution and evaluating transformer-based lan- guage models. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 15278-15294, Bangkok, Thailand, August 2024. Association for Computational Linguis- tics. doi: 10.18653/v1/2024.acl-long.815. URL https: //aclanthology.org/2024.acl-long.815. · DOI
- Mitra, A. and Baral, C. Learning to automatically solve logic grid puzzles. In Conference on Empirical Methods in Nat- ural Language Processing, 2015. URL https://api. semanticscholar.org/CorpusID:2684696.
- OpenAI. Openai o1 system card. arXiv, abs/2412.16720, 2024. · arXiv
- 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.
- Parmar, M., Patel, N., Varshney, N., Nakamura, M., Luo, M., Mashetty, S., Mitra, A., and Baral, C. Log- icbench: Towards systematic evaluation of logical rea- soning ability of large language models. In Annual Meet- ing of the Association for Computational Linguistics, 2024. URL https://api.semanticscholar. org/CorpusID:269330143.
- Prosser, P. Hybrid algorithms for the constraint sat- isfaction problem. Computational Intelligence, 9, 1993. URL https://api.semanticscholar. org/CorpusID:36951414.
- Richardson, K. and Sabharwal, A. Pushing the limits of rule reasoning in transformers through natural language satis- fiability. In AAAI Conference on Artificial Intelligence, 2022. URL https://api.semanticscholar. org/CorpusID:245219217.
- Ryu, H., Kim, G., Lee, H. S., and Yang, E. Divide and translate: Compositional first-order logic trans- lation and verification for complex logical reasoning. 2024. URL https://api.semanticscholar. org/CorpusID:273233577.
- 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.
- Sempolinski, P. Automatic solutions of logic puzzles. 2009. URL https://api.semanticscholar. org/CorpusID:125304065.
- Tyagi, N., Parmar, M., Kulkarni, M., Rrv, A., Pa- tel, N., Nakamura, M., Mitra, A., and Baral, C. Step-by-step reasoning to solve grid puzzles: Where do llms falter? In Conference on Em- pirical Methods in Natural Language Processing, 2024. URL https://api.semanticscholar. org/CorpusID:271329041.
- 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. · arXiv
- Xie, C., Huang, Y., Zhang, C., Yu, D., Chen, X., Lin, B. Y., Li, B., Ghazi, B., and Kumar, R. On memo- rization of large language models in logical reasoning. 2024. URL https://api.semanticscholar. org/CorpusID:273695832.
- 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
- Authors
- Lin, B. Y., Bras, R. L., Richardson, K., Sabharwal, A., Poovendran, R., Clark, P., & Choi, Y.
- Affiliations
- University of Washington (US)
- Allen Institute for Artificial Intelligence (US)
- Stanford University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2025
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2502.01100
- OpenAlex
- W4407129134
- Cited by
- 1
- References
- 0
- Citations by year
- 2025: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Funders
- National Science Foundation (2134012)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- large language models, logical reasoning, nonmonotonic reasoning, constraint satisfaction, scaling limits, puzzle generation, best-of-N sampling, backtracking, LLM evaluation framework
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
