Graph of States: Solving Abductive Tasks with Large Language Models

Yu Luo; Rongchen Gao; Lu Teng; Xidao Wen; Jiamin Jiang; Qingliang Zhang; Yongqian Sun; Shenglin Zhang

cs.AIMar 22, 2026

Graph of States: Solving Abductive Tasks with Large Language Models

Authors: Yu Luo, Rongchen Gao, Lu Teng, Xidao Wen, Jiamin Jiang, Qingliang Zhang, Yongqian Sun, Shenglin Zhang, +4 more

Organizations: Nankai University · Wenzhou Medical University · Alibaba Cloud · Lenovo · Tsinghua University

Abstract

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.

Figures & tables

Figure 1: Illustration of reasoning frameworks applied to Deductive tasks (Left) versus Abductive tasks (Right). While deductive frameworks succeed in static logic ( e.g. , Game of 24), applying them to abductive tasks exposes four deficiencies: (1) Evidence Fabrication , (2) Context Drift , (3) Failed Backtracking , and (4) Early Stopping .

Figure 2: Overview of GoS . Left: Schematic of the dual-layer architecture. Right: The iterative inference workflow.

Figure 3: Bi-Directional Neuro-Symbolic Interaction.

Figure 4: State Conversions: Backtracking & Drill-Down.

Methods	LLM-as-a-Judge		Human-as-a-Judge		$/case
Methods	Match	Relevant	Match	Relevant	$/case
GoS	31.88	74.64	39.86	78.99	0.12
Single/CoT	21.01	47.83	24.64	48.55	0.03
Single/ToT	18.84	47.10	19.57	45.65	0.08
Single/GoT	21.01	50.00	22.46	52.90	0.07
Single/FoT	21.74	58.70	21.01	61.59	0.32

Table 1: Performance of Medical Diagnosis (%)

Methods	LLM-as-a-Judge		$/case
Methods	Match	Relevant	$/case
GoS	31.88	74.64	0.12
w/o reasoning focus	19.57	67.39	0.14
w/ structured state management	18.12	59.42	0.15
w/o causal graph	12.32	48.55	0.12
w/o state machine	12.32	50.00	0.17

Table 2: Ablation Study of Medical Diagnosis (%)

Figure 5: Sensitivity Analysis. Solid line stands for GoS , dashed line stands for best baseline (Multi/FoT). (1) upper-left : maximum number of neuro-symbolic interaction iterations; (2) upper-right : maximum number of retrieval actions of expert agent; (3) lower-left : minimum support evidence for drill-down transition; (4) lower-right : confidence gap for drill-down transition.

Methods	LLM-as-a-Judge		$/case
Methods	Match	Relevant	$/case
GoS	70.67	88.00	0.10
Single/CoT	26.67	81.33	0.03
Single/ToT	25.33	78.00	0.14
Single/GoT	27.33	80.00	0.11
Single/FoT	28.67	84.00	0.45

Table 3: Performance of Failure Diagnosis in Distributed Systems (%)

Figure 6: An example of failure diagnosis in distributed systems

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Reformulating DiagnosisArena as an interactive diagnostic task. In the original setting, all auxiliary examination records are revealed upfront. In contrast, our reformulation restricts the initial input to the chief complaint and basic physical examination, and requires the model to explicitly request auxiliary examinations from an external repository before making the final diagnosis.

Figure 8: Scoring consistency of LLM-as-a-Judge across five repetitions for ten medical diagnostic cases (green: 6 consistent; red: 4 inconsistent).

Figure 9: An example of an interactive failure diagnosis process in distributed systems. Given an initial alarm summary, the agent iteratively investigates the incident by querying heterogeneous signals, including time-series metrics, system logs, and shell-level snapshots. Through progressive evidence collection and interpretation, the system converges to the final root cause.

Methods	Error Types
Methods	Wrong Action Selection	Evidence Fabrication	Context Drift	Failed Backtracking	Early Stopping
Baselines (Pooled)	47.22	22.22	41.32	52.78	63.89
GoS	55.90	0	9.70	30.90	18.75

Appendix

Table 4: Error Distribution Comparison across Methods (%).

Domains	Error Types
Domains	Wrong Action Selection	Evidence Fabrication	Context Drift	Failed Backtracking	Early Stopping
Medical	35.76	0	7.29	23.26	5.90
Distributed Systems	20.14	0	2.41	7.64	12.85

Appendix

Table 5: Error Distribution Comparison across Domains (%).

Figure 10: Case Study of Error Types. Visualizing the divergence in reasoning trajectories under contradictory evidence. Left (SingleAgentCoT): The baseline ignores negative findings, succumbing to Evidence Fabrication and Failed Backtracking , which leads to a confident misdiagnosis. Right ( GoS ): Our method enforces Successful Backtracking via causal graph but subsequently encounters Wrong Action Selection due to domain knowledge deficits, resulting in Early Stopping after reasoning budget exhaustion.

Explore similar work

Wiring the 'Why': A Unified Taxonomy and Survey of Abductive Reasoning in LLMs
Apr 9, 2026Moein Salimi, Shaygan Adim, Danial Parnian +3Abductive Reasoning
Department of Computer Engineering, Sharif University of Technology · Department of Mathematical Sciences, Sharif University of Technology
Abductive Reasoning with Probabilistic Commonsense
May 8, 2026Joseph Cotnareanu, Chiara Roverato, Han Zhou +3Abductive Reasoning Neuro-Symbolic Reasoning
McGill University · International Laboratory on Learning Systems · Mila - Quebec Artificial Intelligence Institute +1
CEDAR-GRPO: Process-Aware Reinforcement Learning for General Abductive Reasoning in LLMs
Aug 14, 2026Moein Salimi, Danial Parnian, Shaygan Adim +6Abductive Reasoning RL for Language Model Reasoning
Sharif University of Technology · University of Tehran

Apr 9, 2026J/K move · Enter open · S save

Wiring the 'Why': A Unified Taxonomy and Survey of Abductive Reasoning in LLMs

Moein Salimi, Shaygan Adim, Danial Parnian, Nima Alighardashi+2

Department of Computer Engineering, Sharif University of Technology · Department of Mathematical Sciences, Sharif University of Technology

Abductive Reasoning

Open paper AskPDF arXiv

Regardless of its foundational role in human discovery and sense-making, abductive reasoning--the inference of the most plausible explanation for an observation--has been relatively underexplored in Large Language Models (LLMs). Despite the rapid advancement of LLMs, the exploration of abductive reasoning and its diverse facets has thus far been disjointed rather than cohesive. This paper presents the first survey of abductive reasoning in LLMs, tracing its trajectory from philosophical foundations to contemporary AI implementations. To address the widespread conceptual confusion and disjointed task definitions prevalent in the field, we establish a unified two-stage definition that formally categorizes prior work. This definition disentangles abduction into Hypothesis Generation, where models bridge epistemic gaps to produce candidate explanations, and Hypothesis Selection, where the generated candidates are evaluated and the most plausible explanation is chosen. Building upon this foundation, we present a comprehensive taxonomy of the literature, categorizing prior work based on their abductive tasks, datasets, underlying methodologies, and evaluation strategies. In order to ground our framework empirically, we conduct a compact benchmark study of current LLMs on abductive tasks, together with targeted comparative analyses across model sizes, model families, evaluation styles, and the distinct generation-versus-selection task typologies. Moreover, by synthesizing recent empirical results, we examine how LLM performance on abductive reasoning relates to deductive and inductive tasks, providing insights into their broader reasoning capabilities. Our analysis reveals critical gaps in current approaches--from static benchmark design and narrow domain coverage to narrow training frameworks and limited mechanistic understanding of abductive processes...

Abstract

Explore similar work

Wiring the 'Why': A Unified Taxonomy and Survey of Abductive Reasoning in LLMs

Abductive Reasoning with Probabilistic Commonsense

CEDAR-GRPO: Process-Aware Reinforcement Learning for General Abductive Reasoning in LLMs