PaperlayerView exact revision on arXiv

Source-linked AI summary

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, Jiasong Feng, Tong Liu, Wenjie Zhang, Dan Pei

arXiv:2603.21250v2cs.AI

TL;DR

Abductive reasoning from incomplete observations remains underexplored, and existing deductive frameworks lack explicit state representation and control for these tasks. GoS combines collaborative agents with a causal graph and state machine; on two real-world datasets, it significantly outperforms existing baselines.

  • Problem

    Abductive reasoning from incomplete observations remains underexplored, while deductive frameworks lack explicit state representation and control for dynamic abductive tasks.

    Source: §1 · p. 1

  • Method

    GoS combines role-based agent collaboration with a causal graph that structures beliefs and a state machine that governs reasoning transitions.

    Source: §1 · p. 2

  • Results

    GoS significantly outperforms existing baselines on two real-world datasets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GoS uses explicit belief states to direct investigation toward fine-grained root causes under incomplete information.

    Source: §5 · p. 9

    Evaluation is currently confined to medical diagnosis and failure diagnosis in distributed systems.

    Source: B. Limitations · pp. 12–13

Abstract

from arXiv · show

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.

1. Introduction

Abductive reasoning remains underexplored despite its relevance to real-world decisions, and deductive frameworks face structural challenges when applied to it. The paper introduces GoS, a general-purpose framework for abductive tasks, and reports that it outperforms existing baselines on two real-world datasets.

1. Introduction

  • Abduction infers probable hypotheses from incomplete observations and is important in settings such as medical diagnosis and failure investigation.The paper identifies abductive reasoning as underexplored and aims for a framework suited to its dynamic, non-monotonic nature.Source: §1 · p. 1
  • Deductive frameworks applied to abductive tasks exhibit evidence fabrication, context drift, failed backtracking, and early stopping.The authors attribute these problems to unstructured reasoning states and the absence of explicit state control.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • GoS combines role-based collaboration with a causal graph for belief-state memory and a state machine that governs backtracking and drill-down.The authors say these mechanisms target evidence fabrication, context drift, failed backtracking, and early stopping.Source: §1 · p. 2
  • GoS significantly outperforms existing baselines on two real-world datasets.The authors describe it as the first general-purpose multi-agent reasoning framework tailored for abductive tasks.Source: §1 · p. 2

2. Related Work

Prior general reasoning frameworks largely address deductive tasks, while symbolic methods typically handle fixed settings rather than interactive evidence gathering. Specialized abductive systems use domain-specific engineering, which the authors distinguish from generalized reasoning capability.

Reasoning frameworks for general deductive tasks

  • General deductive frameworks range from sequential Chain-of-Thought to tree, graph, and forest search structures.The cited overview describes CoT, ToT, GoT, and FoT as approaches developed primarily for deductive tasks.Source: §2 · p. 3

Neuro-symbolic reasoning with Large Language Models

  • Neuro-symbolic methods use formal logic or symbolic procedures to improve reasoning reliability, but mainly address fixed settings rather than interactive investigation.The latter requires iterative evidence acquisition, hypothesis revision, and progressive root-cause refinement.Source: §2 · p. 3

Large Language Models for specialized abductive tasks

  • Specialized abductive systems use multi-agent customization, retrieval, fine-tuning, and data preprocessing, with efficacy attributed mainly to domain-specific engineering.The overview contrasts these adaptations with generalized reasoning capabilities.Source: §2 · p. 3

3. Methodology

GoS frames abduction as finding a plausible root cause from incomplete observations. Its role-aligned agents work through a symbolic belief state and state machine that guide evidence gathering and changes in reasoning depth.

3.1. Dual-layer Framework

  • The task is to identify the most plausible root cause from incomplete observations, with deep evidence acquired on the fly rather than supplied comprehensively.GoS uses ReAct for dynamic retrieval of deep evidence.Source: §3.1 · pp. 3–4
  • GoS pairs role-aligned central and expert agents with a symbolic belief state comprising a causal graph and a state machine.The graph encodes symptoms, evidence, and hypotheses and their logical relations; the state machine tracks the level under investigation.Source: §3.1 · p. 4

3.2. Bi-Directional Neuro-Symbolic Interaction

  • Returned evidence updates graph confidences, nodes, and edges, while the current belief state and reasoning focus guide expert investigation.The central agent synthesizes observations and analysis to update the graph, and the symbolic layer turns the current focus into actionable guidance.Source: §3.2 · p. 5

3.3. State Conversions: Backtracking and Drill-Down

  • Contradicted ancestors trigger pruning and reset to their shallowest demoted level; drill-down requires a top-hypothesis confidence gap and minimum supporting evidence before deeper refinement.If the drill-down thresholds are unmet, the system keeps the current state for further evidence retrieval.Source: §3.3 · pp. 5–6

4. Experiments

GoS is evaluated on medical and distributed-systems diagnosis against standardized single- and multi-agent baselines. It leads the reported benchmark comparisons, while ablations and sensitivity analyses examine its state-management components and controls.

4. Experiments

  • The evaluation uses 150 medical cases and 150 production-system incidents, eight standardized baselines, Match and Relevant metrics, and human judging for medical diagnoses.The medical cases come from DiagnosisArena; the distributed-systems incidents come from a production microservice system. The common backbone is GPT-5.1-2025-11-13.Source: §4 · p. 6

4.1. Medical Diagnosis

  • Medical diagnosis begins with surface symptoms and requires auxiliary examinations; GoS assigns a Primary Physician as central agent and three clinical specialists as experts.The Multi-Agent baselines use the same clinical roles for consistency.Source: §4.1 · pp. 6–7

4.1. Medical Diagnosis; 4.2. Failure Diagnosis in Distributed Systems

  • Medical GoS scores 39.86% Human-as-a-Judge Match and 78.99% Relevant; distributed-systems GoS scores 70.67% Match and 88.00% Relevant.The paper reports GoS outperforming all baselines on medical diagnosis and establishing a new SOTA under the LLM-as-a-Judge setting for failure diagnosis.Source: Table 1 · p. 7, §4.1 · p. 7, Table 3 · p. 8
  • GoS costs $0.12/case versus Multi/FoT's $0.73 in medical diagnosis, and $0.10 versus $0.94 in failure diagnosis.The authors report the cost comparisons alongside GoS's superior accuracy.Source: §4.1 · p. 7, §4.2 · p. 8

4.1. Medical Diagnosis

  • Removing reasoning focus lowers Match from 31.88% to 19.57%; structured text without a causal graph scores 18.12% versus 12.32% without that structured state.The authors also report Match falling to 12.32% when the causal graph or state machine is removed, and attribute a cost spike to removing the state machine.Source: §4.1 · p. 7, Table 2 · p. 7
  • Higher iteration and retrieval budgets generally improve performance, while stricter drill-down thresholds trade higher Relevant for lower Match when set excessively high.Moderate thresholds improve correctness; the figure compares GoS with the best baseline, Multi/FoT.Source: §4.1 · pp. 7–8, Figure 5 · p. 8

4.2. Failure Diagnosis in Distributed Systems

  • Distributed-systems cases start with alerts while detailed evidence remains in raw observability data; GoS uses an ApplicationOperator with Linux, Network, and Database experts.The experts can query historical logs, retrieve system metrics, and execute restricted shell commands.Source: §4.2 · p. 8
  • In the illustrated production incident, investigation traces a read-only root filesystem to XFS metadata corruption as the root cause.The LinuxOperator inspects mount state and XFS-related kernel logs before GoS drills down to the finer-grained cause.Source: §4.2 · pp. 8–9, Figure 6 · p. 9

5. Conclusion

GoS is a general-purpose neuro-symbolic framework for abductive reasoning that grounds collaborative investigation in explicit belief states. The authors present its causal graph and state machine as directing search toward fine-grained root causes.

5. Conclusion

  • GoS grounds collaborative investigation in explicit belief states through a causal graph and state machine, directing search toward fine-grained root causes.The conclusion frames GoS as a potential reasoning backbone for complex, high-stakes domains when coupled with domain-specific adaptations.Source: §5 · p. 9

Impact Statement

The impact statement presents GoS as a general reasoning paradigm for abductive scenarios, compatible with domain-specific adaptations. Its algorithm alternates between agent investigation and symbolic state updates until a report is ready.

Impact Statement

  • GoS aims to address the lack of a general abductive reasoning framework and can integrate domain-specific adaptations such as RAG and input preprocessing.The impact statement names medical diagnosis, distributed-systems failure diagnosis, and criminal investigation as example scenarios.Source: Impact Statement · p. 9

A. Algorithm

  • The workflow initializes a graph and state, selects a focus, plans and runs expert investigation, updates the graph, converts state, and reports when ready.The appendix identifies Algorithm 1 as the overall workflow and Algorithm 2 as the state-conversion mechanism.Source: A. Algorithm · p. 12

B. Limitations

The evaluation is confined to medical diagnosis and failure diagnosis in distributed systems. Building high-quality abductive benchmarks in other high-stakes domains is constrained by limited access to detailed evidence under privacy and data-protection rules.

B. Limitations

  • Evaluation currently covers medical diagnosis and distributed-systems failure diagnosis; acquiring high-quality benchmarks in other domains is constrained by privacy and data-protection rules limiting access to detailed evidence.The authors describe their chosen datasets as high-quality, drawing on top-tier medical journals and real-world production environments.Source: B. Limitations · pp. 12–13

C.1. Dataset for Medical Diagnosis

The medical-diagnosis benchmark is reframed as an interactive evidence-gathering task, and its cases are manually checked to ensure diagnoses can be derived from the evidence. Evaluation also uses experienced human judges because repeated LLM judging can be inconsistent and favor longer answers.

C.1. Dataset for Medical Diagnosis

  • The task starts with only a chief complaint and basic examination; models must request auxiliary records before diagnosing.The original benchmark reveals all auxiliary records upfront, which the reformulation changes to on-demand retrieval.Source: §C.1 · p. 13, Figure 7 · p. 13
  • Experienced clinical researchers manually assessed outputs for more than 110 hours, prioritizing diagnostic correctness over response length.The paper reports inconsistent scores across repeated LLM assessments and unresolved ambiguity after majority voting.Source: §C.1 · p. 14
  • Twelve cases were excluded because information gaps or logical contradictions made their labeled diagnoses impossible to derive from the evidence.The paper provides examples of an incorrect label, a secondary diagnosis unrelated to the chief complaint, and insufficient clinical data.Source: §C.1 · pp. 14–15
  • One excluded case was labeled as tubal angiomyofibroblastoma, although its pathology supported uterine leiomyoma instead.The reported differences include immunohistochemical markers, morphology, and hormone-receptor associations.Source: §C.1 · p. 15

C.2. Dataset for Failure Diagnosis in Distributed Systems

The distributed-systems dataset is built from production incidents to represent diagnosis as interactive investigation under partial, evolving observability. It records heterogeneous evidence gathered during live response, while confidentiality requirements prevent release of raw data and traces.

C.2. Dataset for Failure Diagnosis in Distributed Systems

  • The dataset addresses evaluation gaps in synthetic or limited-scale settings, narrow root-cause targets, and offline diagnosis with evidence assumed to be pre-materialized.It is constructed from authentic production incidents to capture on-demand observations and intermediate shell snapshots along investigation trajectories.Source: §C.2 · pp. 15–16
  • Each of 150 incidents is represented as an investigation trajectory from the first alert to the postmortem-confirmed root cause.Records include time-series metrics, system logs, and shell snapshots; root-cause labels come from experienced on-call engineers’ post-incident analyses.Source: §C.2 · p. 16
  • Shell snapshots preserve intermediate probing actions and raw command outputs, so the root cause is not explicitly revealed unless evidence is correctly integrated over time.The dataset is drawn from a platform monitoring on the order of 2.5 × 10^4 infrastructure instances and processing roughly 12B log entries per day.Source: §C.2 · pp. 16–17
  • Company confidentiality, privacy, and compliance requirements prevent public release of the raw incident data and interaction traces.Published case examples are sanitized and anonymized and do not correspond to real asset identities.Source: §C.2 · p. 17

D. Error Analysis

The authors inspect low-scoring failures from GoS and baseline methods in medical diagnosis and distributed-systems diagnosis. Their taxonomy covers frequent operational and strategic errors, but is explicitly non-exhaustive.

D.1. Taxonomy of Error Types

  • The taxonomy reflects prevalent failure types rather than an exhaustive or mutually exclusive classification.A single failure case may contain multiple error types, and negligible outliers are omitted.Source: §D.1 · p. 17
  • Wrong Action Selection is using tools irrelevant to the current hypothesis, wasting resources without producing valid evidence.The example is querying memory metrics when investigating suspected CPU saturation.Source: §D.1 · p. 17
  • Evidence Fabrication asserts observational details absent from the context, corrupting the evidential basis for a hypothesis.The example claims a “Connection Refused” log entry even though the retrieved log is normal.Source: §D.1 · p. 17
  • Context Drift loses the historical reasoning trajectory, while Failed Backtracking persists with a hypothesis after contradictory evidence appears.These errors can lead to repeated tool use or ad-hoc auxiliary hypotheses instead of exploring alternatives.Source: §D.1 · p. 17
  • Early Stopping halts at a coarse symptom instead of identifying the fine-grained root cause needed for actionable mitigation.The example identifies a memory fault but not the memory exhaustion caused by a leak.Source: §D.1 · pp. 17–18

D.2. Quantitative Distribution Analysis

Across the analyzed failures, GoS has lower reported prevalence of evidence fabrication, context drift, and early stopping than the aggregated baselines. Its remaining failures reflect domain-knowledge needs and differ across medical and distributed-systems diagnosis.

D.2. Quantitative Distribution Analysis

  • 0% vs. 22.22% Evidence Fabrication, 9.70% vs. 41.32% Context Drift, and 18.75% vs. 63.89% Early Stopping are reported for GoS versus baselines.The authors attribute the differences to graph grounding, explicit memory, and state-machine enforcement of coarse-to-fine reasoning.Source: Table 4 · p. 18, §D.2 · p. 18
  • 55.90% vs. 47.22% Wrong Action Selection is reported for GoS versus baselines, but the authors call this a proportional artifact of GoS’s smaller failure set.They attribute persistent wrong actions primarily to domain-specific knowledge deficits, particularly in complex medical diagnosis.Source: §D.2 · p. 18
  • 30.90% of GoS backtracking errors are attributed to limited clinical expertise, which can prevent recognizing that retrieved evidence contradicts a hypothesis.The authors report that medical diagnosis contributes the largest portion of GoS failure cases.Source: §D.2 · p. 18
  • 35.76% Wrong Action Selection and 23.26% Failed Backtracking are reported for GoS in medical diagnosis.The authors link both patterns to the difficulty of selecting examinations and identifying alternatives without specialized clinical knowledge.Source: Table 5 · p. 19, §D.2 · p. 19
  • 12.85% Early Stopping and 20.14% Wrong Action Selection are reported for GoS in distributed-systems diagnosis.The authors say low-value queries can consume the predefined search budget, leaving insufficient resources for further investigation.Source: Table 5 · p. 19, §D.2 · p. 19
  • Domain-specific preprocessing and standard operating procedures are presented as complementary additions that may improve retrieval efficiency and support deeper investigation.The authors conclude that combining specialized adaptations with GoS’s general-purpose reasoning mechanism is a direction for deployment across domains.Source: §D.2 · p. 19

D.3. Qualitative Case Study

The case study contrasts a baseline that fabricates support for an initial diagnosis with GoS, which backtracks when evidence contradicts that diagnosis. GoS reaches a new investigative direction but can still stop with a coarse conclusion when domain knowledge is insufficient.

D.3. Qualitative Case Study

  • The curated case study focuses on decision pivots to illustrate how GoS suppresses fabrication and context drift while exposing wrong-action and backtracking challenges.It presents selected moments rather than exhaustive reasoning trajectories.Source: §D.3 · p. 19
  • The baseline hallucinates marrow edema to defend its osteomyelitis hypothesis despite a negative MRI, then issues a confident but incorrect diagnosis.The self-reinforcing loop prevents reassessment of earlier assumptions.Source: §D.3 · pp. 19, 21, Figure 10 · p. 20
  • GoS rejects the contradicted infection hypothesis and backtracks toward vasculitis, but poor test selection exhausts its reasoning budget and leaves only a coarse diagnostic category.The case illustrates successful backtracking alongside wrong action selection and early stopping.Source: Figure 10 · p. 20, §D.3 · p. 21

Related papers

Loading 2603.21250v2…