Proof of Thought : Neurosymbolic Program Synthesis allows Robust and Interpretable Reasoning

Debargha Ganguly, Srinivasan Iyengar, Vipin Chaudhary, Shivkumar Kalyanaraman

Introduction

Large Language Models (LLMs) have demonstrated remarkable capabilities in creative text generation, yet they often falter in tasks requiring rigorous logical consistency. The Proof of Thought (PoT) framework addresses this by bridging the gap between the intuitive generation of LLMs and the formal verification of symbolic logic. By translating natural language reasoning into a structured, verifiable "thought program," PoT ensures that AI outputs are logically sound and human-auditable.

The Challenge of LLM Reasoning

Traditional Chain-of-Thought (CoT) prompting encourages models to "think out loud," but these explanations are often post-hoc justifications rather than true logical derivations. In high-stakes domains like healthcare or industrial safety, the "stochastic parrot" nature of LLMs—where they rely on superficial heuristics—poses significant risks. There is a critical need for a system where the reasoning process itself is a verifiable proof.

The Proof of Thought (PoT) Framework

The PoT framework treats reasoning as a program synthesis task. It consists of three primary stages: a Logical Representation Generator, an Interpreter, and a Theorem Prover.

The Proof of Thought architecture integrates natural language reasoning with a formal verification loop.
  1. Logical Representation Generator ($G$): An LLM translates a natural language prompt into a "thought program" using a custom JSON-based Domain-Specific Language (DSL).
  2. Interpreter ($I$): This component parses the DSL, enforces type-checking, and converts the program into First-Order Logic (FOL) constructs.
  3. Theorem Prover ($T$): Utilizing the Z3 theorem prover, the system checks if the conclusion logically follows from the provided facts and rules.

The JSON-based DSL and Program Components

A key innovation of PoT is its "near-English" DSL, designed to be both machine-executable and human-readable.

Detailed breakdown of Thought Program Components, including Sorts, Knowledge Bases, and the verification flow.

The DSL utilizes Sorts to define a robust type system (e.g., distinguishing between a Person and a Machine). This prevents semantic hallucinations, such as assigning human attributes to inanimate objects. The system explicitly separates the Knowledge Base (static facts) from Rules (inferential logic), allowing for modular updates and easier auditing.

Experimental Evaluation

The researchers tested PoT on two benchmarks:

  • StrategyQA: A multi-hop reasoning dataset requiring implicit factual knowledge.
  • Reddit-OSHA: A novel multimodal dataset consisting of 103 real-world images of workplace hazards. This dataset tests the model's ability to apply safety regulations to visual contexts.

Key Results and Insights

  • Reliability: On StrategyQA, PoT successfully executed 82.4% of queries, achieving a 91.40% recall.
  • Error Correction: The iterative feedback loop proved highly effective. In the OSHA task, compilation errors dropped from 14.6% to 0% after three attempts, and identification accuracy rose from 72% to 81.55%.
  • Interpretability: Because the intermediate JSON is human-readable, experts can verify the specific rules the model used to reach a safety conclusion.

Conclusion

Proof of Thought moves AI from "guessing" to "proving." By enforcing type-safe reasoning and symbolic verification, it provides a path toward "System 2" thinking in LLMs. Future work will focus on expanding the DSL to handle non-boolean responses and scaling the framework to larger, more complex datasets.

Summary updated

BibTeX
@inproceedings{ganguly2024proof,
  author = {Debargha Ganguly and Srinivasan Iyengar and Vipin Chaudhary and Shivkumar Kalyanaraman},
  title = {{Proof of Thought : Neurosymbolic Program Synthesis allows Robust and Interpretable Reasoning}},
  booktitle = {Sys2-Reasoning @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=Pxx3r14j3U},
}
Figure