Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought
Open accessAbstract
Large language models (LLMs) have shown remarkable reasoning capabilities given chain-of-thought prompts (examples with intermediate reasoning steps). Existing benchmarks measure reasoning ability indirectly, by evaluating accuracy on downstream tasks such as mathematical reasoning. However, it is unclear how these models obtain the answers and whether they rely on simple heuristics rather than the generated chain-of-thought. To enable systematic exploration of the reasoning ability of LLMs, we present a new synthetic question-answering dataset called PrOntoQA, where each example is generated from a synthetic world model represented in first-order logic. This allows us to parse the generated chain-of-thought into symbolic proofs for formal analysis. Our analysis on InstructGPT and GPT-3 shows that LLMs are quite capable of making correct individual deduction steps, and so are generally capable of reasoning, even in fictional contexts. However, they have difficulty with proof planning: When multiple valid deduction steps are available, they are not able to systematically explore the different options.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
ProsQA's DAG structure introduces complex exploration paths, making it particularly challenging for models to identify the correct reasoning chain.
“Unlike previous logical reasoning datasets like ProntoQA (Saparov and He, 2022), ProsQA's DAG structure introduces complex exploration paths, making it particularly challenging for models to identify the correct reasoning chain.”
From Training Large Language Models to Reason in a Continuous Latent Space (2024) · cites this paper as Saparov and He, 2022
Cites
Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity
Lu, Y., Bartolo, M., Moore, A., Riedel, S., & Stenetorp, P. (2021) · arXiv · doi:10.48550/arxiv.2104.08786 · Cited by 615 · cited 1× · see citing works
“Recent work has examined in-context learning and found that performance on certain tasks is sensitive to the prompt (Razeghi et al., 2022; Lu et al., 2022).”
Background
Flagged first, then by citations
Cited by
Sorted by citations
A Categorical Archive of ChatGPT Failures
Borji, A. (2023) · doi:10.21203/rs.3.rs-2895792/v1 · Cited by 514 · see citing works
Towards Reasoning in Large Language Models: A Survey
Huang, J., & Chang, K. C.-C. (2023) · Findings of the Association for Computational Linguistics: ACL 2023 · doi:10.18653/v1/2023.findings-acl.67 · Cited by 428 · see citing works
Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models
Wang, L., Xu, W., Lan, Y., Hu, Z., Lan, Y., Lee, R. K.-W., & Lim, E.-P. (2023) · Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2023.acl-long.147 · Cited by 344 · see citing works
Reasoning with Language Model is Planning with World Model
Hao, S., Gu, Y., Ma, H., Hong, J., Wang, Z., Wang, D., & Hu, Z. (2023) · Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2023.emnlp-main.507 · Cited by 168 · see citing works
Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning
Pan, L., Albalak, A., Wang, X., & Wang, W. Y. (2023) · arXiv · doi:10.48550/arxiv.2305.12295 · Cited by 144 · see citing works
“, 2021), PrOntoQA (Saparov and He, 2023), FOLIO (Han et al.”
BackgroundInfluentialFaith and Fate: Limits of Transformers on Compositionality
Dziri, N., Lu, X., Sclar, M., Li, X. (., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Bras, R. L., et al. (2023) · Advances in Neural Information Processing Systems 36 · doi:10.52202/075280-3081 · Cited by 124 · see citing works
“Challenges of Transformers in compositional tasks Transformers perform fairly well in singlestep reasoning tasks [52], but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems [38, 48, 62].”
BackgroundTowards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters
Wang, B., Min, S., Deng, X., Shen, J., Wu, Y., Zettlemoyer, L., & Sun, H. (2023) · Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2023.acl-long.153 · Cited by 120 · see citing works
Language Model Behavior: A Comprehensive Survey
Chang, T. A., & Bergen, B. K. (2024) · Computational Linguistics · doi:10.1162/coli_a_00492 · Cited by 105 · see citing works
Wu, Z., Qiu, L., Ross, A., Akyürek, E., Chen, B., Wang, B., Kim, N., Andreas, J., & Kim, Y. (2024) · Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers) · doi:10.18653/v1/2024.naacl-long.102 · Cited by 58 · see citing works
Large Language Models Can Learn Temporal Reasoning
Xiong, S., Payani, A., Kompella, R., & Fekri, F. (2024) · Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2024.acl-long.563 · Cited by 47 · see citing works
PlanGenLLMs: A Modern Survey of LLM Planning Capabilities
Wei, H., Zhang, Z., He, S., Xia, T., Pan, S., & Liu, F. (2025) · Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2025.acl-long.958 · Cited by 36 · see citing works
Training Large Language Models to Reason in a Continuous Latent Space
Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., & Tian, Y. (2024) · arXiv · doi:10.48550/arxiv.2412.06769 · Cited by 18 · see citing works
“We found that the generation process of ProntoQA could be more challenging, especially since the size of distracting branches in the ontology is always small, reducing the need for complex planning.”
InfluentialHow Many Demonstrations Do You Need for In-context Learning?
Chen, J., Chen, L., Zhu, C., & Zhou, T. (2023) · Findings of the Association for Computational Linguistics: EMNLP 2023 · doi:10.18653/v1/2023.findings-emnlp.745 · Cited by 12 · see citing works
Davinci Goes to Bebras: A Study on the Problem Solving Ability of GPT-3
Bellettini, C., Lodi, M., Lonati, V., Monga, M., & Morpurgo, A. (2023) · Proceedings of the 15th International Conference on Computer Supported Education · doi:10.5220/0012007500003470 · Cited by 10 · see citing works
BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystack
Kuratov, Y., Bulatov, A., Anokhin, P., Rodkin, I., Sorokin, D., Sorokin, A., & Burtsev, M. (2024) · arXiv · doi:10.48550/arxiv.2406.10149 · Cited by 19 · see citing works
“Additionally, we release the predictions of all models used in our study to ensure that all re-ported results can be reproduced and verified: https://github.com/booydar/babilong/tree/ predictions_06_2024 .”
MethodOn scalable oversight with weak LLMs judging strong LLMs
Kenton, Z., Siegel, N. Y., Kramár, J., Brown-Cohen, J., Albanie, S., Bulian, J., Agarwal, R., Lindner, D., Tang, Y., Goodman, N. D., et al. (2024) · arXiv · doi:10.48550/arxiv.2407.04622 · Cited by 6 · see citing works
When Can AI Models Explain Learning? Validity Criteria for AI as Cognitive Models in Education
Wang, P., Viberg, O., Law, E. L.-C., & Greiff, S. (2026) · Educational Psychology Review · doi:10.1007/s10648-026-10202-y · Cited by 3 · see citing works
Reason Popper-ly: Patching In-Context Reasoning with Inductive Logic Programming
Chen, Z., & Ma, M. (2026) · arXiv · doi:10.48550/arxiv.2607.23019
“Prior work shows that CoT explanations can be plausible while remaining unfaithful Turpin et al. [2023], Lanham et al. [2023], and that reasoning quality degrades substantially as compositional depth increases Saparov and He [2023].”
Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog
Al-Negheimish, H., Ilieva, J., & Kim, Y. (2026) · arXiv · doi:10.48550/arxiv.2610.11592
“This process is algorithmic; a model that has learned a robust implementation of this algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks (Clark et al., 2020; Tafjord et al., 2021; Saparov and He, 2023).”
- Authors
- Saparov, A., & He, H.
- Affiliations
- New York University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2022
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2210.01240
- OpenAlex
- W4302305823
- Cited by
- 46
- References
- 1
- Citations by year
- 2026: 2 · 2025: 9 · 2024: 11 · 2023: 24
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- Cisco Systems
- Samsung Advanced Institute of Technology
- Open Philanthropy Project
- Samsung
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Keywords
- chain-of-thought prompting, large language models, formal reasoning, proof planning, first-order logic, mathematical reasoning, heuristics, GPT-3
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
