Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought

Abulhair Saparov, He He

TL;DR

While Large Language Models (LLMs) can perform impressive logical deductions using Chain-of-Thought (CoT) prompting, they act as "greedy reasoners"—capable of making individual correct steps but failing to plan or backtrack when multiple valid paths exist. By introducing ProntoQA, a synthetic dataset derived from formal logic, researchers can now precisely diagnose where the reasoning chain breaks down.

The Problem: Are LLMs Actually Reasoning?

We know that Chain-of-Thought (CoT) prompting—asking a model to "show its work"—dramatically improves performance on reasoning tasks. However, it remains unclear why this works. Is the model actually reasoning through the problem, or is it merely retrieving memorized patterns from its massive training data?

Existing benchmarks like GSM8K (math word problems) are messy. They rely on real-world knowledge, which allows models to "cheat" by remembering facts rather than deriving them. Furthermore, these benchmarks usually only evaluate the final answer, ignoring whether the intermediate steps were logically sound. This paper aims to peel back the curtain by creating a controlled environment where reasoning can be analyzed step-by-step using formal logic.

Methods: A Framework for Formal Analysis

The authors developed a framework to systematically analyze the "logic" inside an LLM's head by mapping natural language to formal symbolic logic.

ProntoQA Generation Pipeline
  1. Synthetic Generation: They generate an ontology (a hierarchy of concepts and properties) and a specific question with a unique logical proof.
  2. Natural Language Translation: This formal proof is translated into simple English sentences for the model to process.
  3. Formal Parsing: After the LLM generates its Chain-of-Thought, the researchers use a recursive-descent parser to turn that English back into symbolic logic.
  4. Step-by-Step Evaluation: They categorize every single step the model takes based on:
  5. Validity: Is the step actually provable from previous facts?
  6. Atomicity: Is it a single logical leap, or did the model skip steps?
  7. Utility: Even if the step is true, does it actually help reach the final goal, or is it a "misleading" distraction?

The ProntoQA Dataset

To power this analysis, the paper introduces ProntoQA (Proof and Ontology-Generated Question-Answering).

Unlike datasets like FOLIO or ProofWriter, ProntoQA is fully synthetic and highly controllable. Researchers can adjust the number of "hops" (proof length), the order of information (top-down vs. bottom-up), and the "fictionality" of the content. It includes "True" (cats are mammals), "False" (mammals are cats), and "Fictional" (wumpuses are numpuses) settings to test if the model relies on its pre-trained knowledge or the logic provided in the prompt.

Key Insights: The "Greedy" Nature of LLMs

The core finding of the paper is that LLMs are greedy reasoners. When a model reaches a fork in the road where two different logical steps are both "true," it often picks the one that doesn't lead to the answer. Because LLMs generate text token-by-token, they lack a global "proof plan" and cannot backtrack once they've started down a dead-end path.

Other major insights include:

  • Reasoning vs. Retrieval: LLMs perform significantly better on "True" ontologies than "Fictional" ones. This suggests that while they can reason, they are heavily propped up by the facts they memorized during pre-training.
  • The Scaling Wall: Only the largest models (like text-davinci-002) showed any real ability to reason through multiple steps. Smaller models often produced "invalid" steps or hallucinated facts entirely.
  • Order Matters: If the facts in the prompt are ordered in a way that doesn't match the logical flow of the proof (top-down traversal), the model's accuracy plummets. They struggle to "search" through the context for the right premise.

Key Results

Strict Proof Accuracy vs. Label Accuracy
  • Individual Step Competence: On 5-hop fictional proofs, text-davinci-002 produced "strictly-valid" steps 93.2% of the time. This proves LLMs can execute basic logic.
  • Planning Failure: Despite being good at individual steps, the model's "strict proof accuracy" (getting the whole chain right) was much lower than its label accuracy (getting the final True/False right). The main culprit was "misleading steps"—valid logic that went in the wrong direction.
  • The 5-Hop Limit: Accuracy for 1-hop and 3-hop proofs was high, but it fell toward chance levels on 5-hop proofs when the information was presented in a difficult order.
  • Self-Consistency Doesn't Fix Planning: Even using "Self-Consistency" (sampling 40 different paths and picking the most common) didn't significantly improve proof accuracy, because the model consistently assigned higher probability to the "greedy" (but wrong) paths.

Limitations and Future Work

The study was limited to Modus Ponens (if A then B; A; therefore B) and relatively short proofs (up to 5 hops). Real-world reasoning is far more complex, involving negation, disjunction, and much longer chains.

The authors suggest that because LLMs are "greedy," they might need to be paired with more sophisticated search or planning algorithms (like neurosymbolic approaches) to handle complex reasoning. Simply asking a model to "think step-by-step" isn't enough if the model doesn't know which step to take next.

Summary updated

Abstract

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.
BibTeX
@inproceedings{saparov2023language,
  author = {Abulhair Saparov and He He},
  title = {{Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=qFVVBzXxR2V},
}
Figure