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

arXiv: https://arxiv.org/abs/2409.17270 · HTML: https://mlsanity.com/paper/2409.17270/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 25 Sep 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 20 of 20)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Interpretability Beyond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV)](https://mlsanity.com/paper/1711.11279/) (2017)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Visual Programming: Compositional visual reasoning without training](https://mlsanity.com/paper/2211.11559/) (2022)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Concept Whitening for Interpretable Image Recognition](https://mlsanity.com/paper/2002.01650/) (2020)
- [A Survey of the State of Explainable AI for Natural Language Processing](https://mlsanity.com/paper/2010.00711/) (2020)
- [The Next Decade in AI: Four Steps Towards Robust Artificial Intelligence](https://mlsanity.com/paper/2002.06177/) (2020)
- [Transfer Learning for Low-Resource Neural Machine Translation](https://mlsanity.com/paper/1604.02201/) (2016)
- [Rethinking Knowledge Graph Propagation for Zero-Shot Learning](https://mlsanity.com/paper/1805.11724/) (2018)
- [A Benchmark for Learning to Translate a New Language from One Grammar Book](https://mlsanity.com/paper/2309.16575/) (2023)
- [Scallop: A Language for Neurosymbolic Programming](https://mlsanity.com/paper/2304.04812/) (2023)
- [Interpretable Neural-Symbolic Concept Reasoning](https://mlsanity.com/paper/2304.14068/) (2023)
- [BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts](https://mlsanity.com/paper/2402.12240/) (2024)
- [GENOME: GenerativE Neuro-symbOlic visual reasoning by growing and reusing ModulEs](https://mlsanity.com/paper/2311.04901/) (2023)

## Built on by (most cited first, 19 of 19)

- [Solver-Aided Verification of Policy Compliance in Tool-Augmented LLM Agents](https://mlsanity.com/paper/2603.20449/) (2026)
- [Towards Reliable Code-as-Policies: A Neuro-Symbolic Framework for Embodied Task Planning](https://mlsanity.com/paper/2510.21302/) (2025)
- [Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks](https://mlsanity.com/paper/2505.20047/) (2025)
- [A Neurosymbolic Approach to Natural Language Formalization and Verification](https://mlsanity.com/paper/2511.09008/) (2025)
- [Position: Foundation Models for Tabular Data within Systemic Contexts Need Grounding](https://mlsanity.com/paper/2505.19825/) (2025)
- [Toward Guarantees for Clinical Reasoning in Vision Language Models via Formal Verification](https://mlsanity.com/paper/2602.24111/) (2026)
- [Trust The Typical](https://mlsanity.com/paper/2602.04581/) (2026)
- [Path-Lock Expert: Separating Reasoning Mode in Hybrid Thinking via Architecture-Level Separation](https://mlsanity.com/paper/2604.27201/) (2026)
- [ATA: A Neuro-Symbolic Approach to Implement Autonomous and Trustworthy Agents](https://mlsanity.com/paper/2510.16381/) (2025)
- [RepV: Safety-Separable Latent Spaces for Scalable Neurosymbolic Plan Verification](https://mlsanity.com/paper/2510.26935/) (2025)
- [Bonsai: Interpretable Tree-Adaptive Grounded Reasoning](https://mlsanity.com/paper/2504.03640/) (2025)
- [Context Determines Optimal Architecture in Materials Segmentation](https://mlsanity.com/paper/2602.04154/) (2026)
- [Reliability-Gated Source Anchoring for Continual Test-Time Adaptation](https://mlsanity.com/paper/2605.14063/) (2026)
- [Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy](https://mlsanity.com/paper/2604.02709/) (2026)
- [Agentic Federated Learning: The Future of Distributed Training Orchestration](https://mlsanity.com/paper/2604.04895/) (2026)
- [Forethought: Verifiable Reasoning from Neurosymbolic Primitive Programming](https://mlsanity.com/paper/2607.04096/) (2026)
- [Program Learning with Verifiable Rewards: Symbolic Backpropagation for Post-Training LLMs](https://mlsanity.com/paper/2608.28421/) (2026)
- [Sequent-Prover: Training Agents for Formal, Checkable SMT-based Reasoning](https://mlsanity.com/paper/2610.15258/) (2026)
- [Compiling Expert Procedures into Verified Programs: When a Small Model Is Enough](https://mlsanity.com/paper/2610.19148/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have revolutionized natural language processing, yet they struggle with inconsistent reasoning, particularly in novel domains and complex logical sequences. This research introduces Proof of Thought, a framework that enhances the reliability and transparency of LLM outputs. Our approach bridges LLM-generated ideas with formal logic verification, employing a custom interpreter to convert LLM outputs into First Order Logic constructs for theorem prover scrutiny. Central to our method is an intermediary JSON-based Domain-Specific Language, which by design balances precise logical structures with intuitive human concepts. This hybrid representation enables both rigorous validation and accessible human comprehension of LLM reasoning processes. Key contributions include a robust type system with sort management for enhanced logical integrity, explicit representation of rules for clear distinction between factual and inferential knowledge, and a flexible architecture that allows for easy extension to various domain-specific applications. We demonstrate Proof of Thought's effectiveness through benchmarking on StrategyQA and a novel multimodal reasoning task, showing improved performance in open-ended scenarios. By providing verifiable and interpretable results, our technique addresses critical needs for AI system accountability and sets a foundation for human-in-the-loop oversight in high-stakes domains.