Graph of States: Solving Abductive Tasks with Large Language Models

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.

Many real-world problems require working backward from incomplete clues to find the most likely cause, such as diagnosing a patient or locating the root cause of a system failure. While large language models are strong at tasks with fixed rules, they often struggle in these settings: they can invent missing evidence, lose track of what has already been checked, follow the wrong line of reasoning for too long, or stop at a surface-level explanation instead of the true root cause. We introduce Graph of States, a framework that gives language models a more structured way to investigate such problems. It records possible explanations and collected evidence in a graph, and uses a state machine to control when the system should dig deeper or backtrack. This turns open-ended trial and error into a more directed search. Across medical diagnosis and distributed-system failure diagnosis, our method produces more accurate and more fine-grained answers than existing baselines, while also using less computation than the strongest broad-search alternatives.