ICML 2026 Abductive Reasoning

Graph of States: Solving Abductive Tasks with Large Language Models

Yu Luo¹, Rongchen Gao¹, Lu Teng², Xidao Wen³, Jiamin Jiang¹, Qingliang Zhang¹, Yongqian Sun^1,*, Shenglin Zhang¹, Jiasong Feng⁴, Tong Liu⁴, Wenjie Zhang⁴, Dan Pei⁵

¹Nankai University ²Wenzhou Medical University ³Alibaba Cloud ⁴Lenovo ⁵Tsinghua University

ICML 2026

43rd International Conference on Machine Learning, Seoul, South Korea

* Corresponding author

Paper Code 机器之心 Slide Story

Reasoning deficiencies in abductive tasks — Deductive reasoning frameworks can solve static logic problems, but abductive tasks expose evidence fabrication, context drift, failed backtracking, and early stopping.

01 THE PAPER

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 structured belief states, utilizing a causal graph to explicitly encode logical dependencies and a state machine to govern valid reasoning transitions. 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: gaorch85/Graph-of-States.

Project Overview

Abductive Reasoning

GoS focuses on diagnosis-style tasks where agents must explain observed symptoms by searching for hidden causes, rather than simply deriving answers from complete premises.

Failure Modes

The paper identifies four recurring deficiencies in LLM reasoning frameworks: evidence fabrication, context drift, failed backtracking, and early stopping.

Structured Belief State

GoS keeps hypotheses, confidence, supporting evidence, and causal relations in an explicit graph, giving agents a shared state instead of an unstructured conversation history.

State-Guided Search

A state machine controls backtracking, drill-down, and report generation, so agents can revise shallow explanations and investigate more concrete root causes.

02 THE FRAMEWORK

Method

03 EVALUATION

Experimental Results

Table 1: Performance of medical diagnosis

Medical Diagnosis Results: GoS achieves the best Match and Relevant scores under both LLM-as-a-Judge and Human-as-a-Judge evaluation.

Table 2: Ablation study of medical diagnosis

Ablation Study: Removing reasoning focus, structured state management, the causal graph, or the state machine weakens GoS on medical diagnosis.

Sensitivity Analysis: GoS remains consistently stronger than the best baseline across interaction, retrieval, evidence, and confidence settings.

Table 3: Performance of failure diagnosis in distributed systems

Distributed-System Diagnosis: GoS substantially improves Match and Relevant scores for failure diagnosis in distributed systems.

Figure 6: Example of failure diagnosis in distributed systems

Case Study: A failure diagnosis example shows how GoS updates hypotheses, drills down through evidence, and reports a concrete root cause.

04 WHERE IT APPLIES

Possible Deployable Areas

GoS is designed for long-horizon reasoning tasks where the goal is not to produce a one-shot answer, but to make multiple hypotheses converge through iterative interaction with the environment and accumulating evidence.

Medical diagnosis: A diagnostic agent can maintain competing disease hypotheses, request new tests or observations, and gradually refine the belief state until the evidence supports a reliable diagnosis.
Failure diagnosis: In complex software or distributed systems, GoS can organize possible root-cause hypotheses, drill down into logs, metrics, and traces, and backtrack when a shallow explanation is contradicted.
Criminal investigation: Investigators often reason over incomplete clues, suspects, timelines, and motives. GoS provides a structured way to update hypotheses as new evidence appears and to avoid premature closure.
Scientific discovery: Scientific reasoning repeatedly proposes hypotheses, designs observations or experiments, and revises explanations. GoS can support this process by keeping hypotheses, evidence, and causal relations explicit.

These domains share the same reasoning pattern: multiple plausible hypotheses, evidence-seeking interaction, controlled state transitions, and final convergence toward the most defensible explanation.

05 CITE THIS WORK

BibTeX

@article{luo2026graph,
  title={Graph of States: Solving Abductive Tasks with Large Language Models},
  author={Luo, Yu and Gao, Rongchen and Teng, Lu and Wen, Xidao and Jiang, Jiamin and Zhang, Qingliang and Sun, Yongqian and Zhang, Shenglin and Feng, Jiasong and Liu, Tong and others},
  journal={arXiv preprint arXiv:2603.21250},
  year={2026}
}