# Graph of States: Solving Abductive Tasks with Large Language Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 22 Mar 2026.

## Placed in

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

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Exams](https://mlsanity.com/paper/2009.13081/) (2020)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [MedMCQA : A Large-scale Multi-Subject Multi-Choice Dataset for Medical domain Question Answering](https://mlsanity.com/paper/2203.14371/) (2022)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [Benchmarking Retrieval-Augmented Generation for Medicine](https://mlsanity.com/paper/2402.13178/) (2024)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [MDAgents: An Adaptive Collaboration of LLMs for Medical Decision-Making](https://mlsanity.com/paper/2404.15155/) (2024)
- [Verify-and-Edit: A Knowledge-Enhanced Chain-of-Thought Framework](https://mlsanity.com/paper/2305.03268/) (2023)
- [Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning](https://mlsanity.com/paper/2412.09078/) (2024)
- [Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition](https://mlsanity.com/paper/2206.05871/) (2022)
- [MAM: Modular Multi-Agent Framework for Multi-Modal Medical Diagnosis via Role-Specialized Collaboration](https://mlsanity.com/paper/2506.19835/) (2025)
- [Flow-of-Action: SOP Enhanced LLM-Based Multi-Agent System for Root Cause Analysis](https://mlsanity.com/paper/2502.08224/) (2025)
- [D-Bot: Database Diagnosis System using Large Language Models](https://mlsanity.com/paper/2312.01454/) (2023)
- [mABC: multi-Agent Blockchain-Inspired Collaboration for root cause analysis in micro-services architecture](https://mlsanity.com/paper/2404.12135/) (2024)
- [Drift No More? Context Equilibria in Multi-Turn LLM Interactions](https://mlsanity.com/paper/2510.07777/) (2025)
- [Eadro: An End-to-End Troubleshooting Framework for Microservices on Multi-source Data](https://mlsanity.com/paper/2302.05092/) (2023)
- [Constructing Large-Scale Real-World Benchmark Datasets for AIOps](https://mlsanity.com/paper/2208.03938/) (2022)
- [LogLM: From Task-based to Instruction-based Automated Log Analysis](https://mlsanity.com/paper/2410.09352/) (2024)
- [Aristotle: Mastering Logical Reasoning with A Logic-Complete Decompose-Search-Resolve Framework](https://mlsanity.com/paper/2412.16953/) (2024)
- [TrioXpert: An Automated Incident Management Framework for Microservice System](https://mlsanity.com/paper/2506.10043/) (2025)
- [OpsAgent: An Evolving Multi-agent System for Incident Management in Microservices](https://mlsanity.com/paper/2510.24145/) (2025)

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

- [Wiring the 'Why': A Unified Taxonomy and Survey of Abductive Reasoning in LLMs](https://mlsanity.com/paper/2604.08016/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [OpsMem: Dual-Memory Reasoning with Cross-Memory Resonance for Failure Diagnosis](https://mlsanity.com/paper/2607.11357/) (2026)
- [Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States](https://mlsanity.com/paper/2610.01415/) (2026)
- [SHELDON: Reasoning through Dual Search over Hypothesis and Observation Spaces](https://mlsanity.com/paper/2610.18025/) (2026)

## Abstract (arXiv)

Logical reasoning encompasses deduction, induction, and abduction. However, while Large Language Models (LLMs) have effectively mastered the former two, abductive reasoning remains significantly underexplored. Existing frameworks, predominantly designed for static deductive tasks, fail to generalize to abductive reasoning due to unstructured state representation and lack of explicit state control. Consequently, they are inevitably prone to Evidence Fabrication, Context Drift, Failed Backtracking, and Early Stopping. To bridge this gap, we introduce Graph of States (GoS), a general-purpose neuro-symbolic framework tailored for abductive tasks. GoS grounds multi-agent collaboration in a structured belief states, utilizing a causal graph to explicitly encode logical dependencies and a state machine to govern the valid transitions of the reasoning process. By dynamically aligning the reasoning focus with these symbolic constraints, our approach transforms aimless, unconstrained exploration into a convergent, directed search. Extensive evaluations on two real-world datasets demonstrate that GoS significantly outperforms all baselines, providing a robust solution for complex abductive tasks. Code repo and all prompts: https://github.com/gaorch85/Graph-of-States.