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

Abulhair Saparov, He He

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.

Introduction

While Large Language Models (LLMs) have become surprisingly adept at "Chain-of-Thought" (CoT) reasoning, their underlying logic remains opaque. Prompting a model to "show its work" improves performance, but it is often unclear if the model is truly following a logical chain or merely employing clever heuristics to guess the final answer. Existing benchmarks, such as math word problems, are often "noisy" because models may have encountered similar problems during training, allowing for retrieval rather than reasoning from scratch. Furthermore, these benchmarks typically only evaluate the final answer, ignoring the logical integrity of intermediate steps.

This paper addresses these issues by introducing a formal, systematic framework to analyze the internal logic of LLM reasoning. The core finding is that LLMs act as "greedy reasoners": while they can reliably perform individual deduction steps, they struggle with proof planning—the ability to look ahead and select the correct logical path when multiple valid options are present.

The PrOntoQA Framework

To enable rigorous analysis, the authors developed PrOntoQA (Proof and Ontology-Generated Question-Answering). Unlike human-annotated datasets, PrOntoQA is fully synthetic and programmable, allowing researchers to control variables such as the number of reasoning steps (hops), the order of facts, and the "truthfulness" of the world (True, False, or Fictional).

The PrOntoQA generation pipeline: from formal ontology to natural language question and proof.

The generation process involves four key steps: creating a world model (ontology) in first-order logic, generating a unique symbolic proof for a specific query, translating that proof into a natural language context, and finally parsing the model's generated CoT back into symbolic logic to evaluate its validity, atomicity, and utility.

Analysis of Reasoning Capabilities

The systematic analysis reveals that LLMs are surprisingly capable of local deduction but fail at global strategy. In fictional settings requiring 5-hop reasoning, InstructGPT achieved a high local validity rate—93.2% of its individual steps were logically sound. However, the models frequently failed the overall task because they chose "misleading" steps that, while valid in isolation, did not lead toward the final goal.

Correlation between valid proof accuracy and final label accuracy across different model configurations.

Key Insights

  • Greedy Logic: LLMs do not "plan" or search through a space of possible proofs. If presented with multiple valid logical steps, they often pick the first one they see, even if it leads to a dead end.
  • Knowledge as a Crutch: Reasoning performance is significantly higher in "True" worlds compared to "Fictional" ones. This suggests that pre-trained world knowledge acts as a guide for reasoning; when this knowledge is removed, the model's inherent planning ability is revealed to be weak.
  • Scaling and Sensitivity: Only the largest models (e.g., text-davinci-002) perform significantly better than chance on multi-hop reasoning. Furthermore, models are highly sensitive to the order of facts; they perform best when facts are presented in a "bottom-up" order matching the proof's natural flow.

Conclusion and Future Directions

The study highlights a fundamental limitation in current LLM architectures: the lack of a systematic search or planning mechanism. While they excel at Modus Ponens in a local context, they cannot navigate complex logical landscapes. Future research might explore more complex logical rules, such as induction or proof by contradiction, and longer reasoning chains.

The authors suggest that the path forward may lie in neuro-symbolic approaches. In such systems, the LLM would handle natural language processing and individual deduction steps, while a symbolic "planner" would manage the overall search for a valid proof, overcoming the "greedy" limitations of current models.

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