ICML 2026 / NEURO-SYMBOLIC REASONING
Evidence shapes the search.
ICML 2026 Abductive Reasoning
1Nankai University 2Wenzhou Medical University 3Alibaba Cloud 4Lenovo 5Tsinghua University
ICML 2026
43rd International Conference on Machine Learning, Seoul, South Korea
* Corresponding author
01 THE PAPER
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.
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.
The paper identifies four recurring deficiencies in LLM reasoning frameworks: evidence fabrication, context drift, failed backtracking, and early stopping.
GoS keeps hypotheses, confidence, supporting evidence, and causal relations in an explicit graph, giving agents a shared state instead of an unstructured conversation history.
A state machine controls backtracking, drill-down, and report generation, so agents can revise shallow explanations and investigate more concrete root causes.
02 PROJECT FILM
See how Graph of States turns abductive reasoning into a structured, evidence-guided search.
03 THE FRAMEWORK
Select a hypothesis from the current belief state.
Expert agents investigate the focused explanation.
Connect observations and revise hypothesis confidence.
Backtrack, drill down, or report when the state allows it.
04 FOLLOW THE EVIDENCE
MICROSERVICE FAILURE DIAGNOSIS
Checkout requests start failing after an order-service release. Follow a diagnosis that tests several explanations, backs out of dead ends, and traces the failure to a missing connection release.
Loading the belief graph. The complete case is available in the transcript below.
Checkout starts returning 503s eight minutes after order-service v2.8 is deployed.
Record the symptom and time window. A nearby deployment is a lead to investigate, not enough evidence to blame the release.
Checkout starts returning 503s eight minutes after order-service v2.8 is deployed.
Record the symptom and time window. A nearby deployment is a lead to investigate, not enough evidence to blame the release.
Checkout depends on order-service, the database, and payment. Each could explain a slow or failed request.
Create competing hypotheses in one belief state. Start with database overload, but retain payment and order-service as alternatives.
An application trace shows a two-second wait to borrow a database connection.
Attach this observation to both plausible explanations. It may mean a busy database or a problem with the application's own pool; do not treat it as proof of either.
The leading hypothesis is still broad: what would make the database slow?
Refine it into slow SQL and lock contention. Ask for database-side measurements that can distinguish these explanations.
SQL latency is normal: 18 ms at p95. The long application wait happens before a query starts.
Connect the measurement to slow SQL with a refuting edge. Keep that branch in the graph and test lock contention next.
There are no blocked sessions, and database CPU is low throughout the failure window.
Lower belief in both lock contention and database overload. Neither refined explanation fits the evidence; continuing here would repeat a dead end.
Both children of database overload have been weakened by direct measurements.
Move from depth 2 back to depth 1 and select order-service. Preserve the rejected hypotheses and their evidence so later reasoning does not start the same investigation again.
Payment latency is normal. The trace places the delay inside order-service's connection-acquisition span.
Refute payment slowdown and strengthen the order-service branch. The focus now follows measured request timing, not the initial guess.
The fault is local to order-service, but that still does not explain what is failing.
Add pool exhaustion and CPU pressure as depth-2 hypotheses. Request pool counters and runtime measurements rather than choosing a cause by name.
All 80 connections are checked out. New requests queue, although many database sessions are idle.
Support pool exhaustion with the observed counters. Distinguish the bottleneck from its cause: a full pool does not yet explain why connections remain borrowed.
CPU usage is 32% and event-loop lag is 4 ms, both within the healthy range.
Mark CPU pressure as unsupported. Keep the pool as the current focus, with the alternative and its refuting evidence still visible.
Pool exhaustion could reflect too little capacity or connections that are never returned.
Refine the pool hypothesis into two depth-3 explanations. Test the simpler capacity explanation first, without discarding a possible leak.
Traffic and pool size are unchanged. Under the same load, the previous release peaked at 35 of 80 borrowed connections.
Lower belief in an undersized pool. Increasing capacity might delay the failure, but the comparison points to changed connection handling instead.
The capacity branch does not explain why the same workload worked before the release.
Return from depth 3 to the depth-2 pool hypothesis. Reconsider its remaining child, using the stored comparison rather than restarting the whole diagnosis.
A connection leak could explain an ever-full pool alongside mostly idle database sessions.
Select the existing leak hypothesis. Ask whether each successful borrow has a matching return, especially on failed or canceled requests.
Only v2.8 shows a growing borrow/return gap after canceled requests. The old release does not under the same test.
Attach this evidence to the leak hypothesis. It narrows the search to cancellation handling, but a matching code path and reproduction are still needed.
The new cancellation branch can return after borrowing a connection, before connection.release() runs.
Create a depth-4 hypothesis: cancellation skips cleanup. Link the code observation to it, then test that path before declaring a root cause.
In isolation, 20 requests canceled after acquisition leave exactly 20 connections checked out.
The controlled reproduction links this path to retained connections. This is stronger than the earlier correlation between deployment time and failures.
A finally block guarantees release. The same 20 cancellations now retain zero connections; a matched-load canary recovers.
Use the repair as another check of the explanation. The change removes the proposed mechanism and the observed bottleneck without enlarging the pool.
Canceled requests bypass cleanup in v2.8, leaking connections until the order-service pool is exhausted and checkout returns 503s.
Report the evidence-backed path and the verified fix: release the connection in finally. The graph retains the alternatives, two backtracks, and the observations behind the conclusion.
05 EVALUATION
Selected results from Tables 1 and 3. Match measures agreement with the reference diagnosis; the judge and task are shown separately.
Medical diagnosis
39.86%
Human-judged Match
Best baseline: 26.09% (Multi/FoT). GoS improves Match by 13.77 percentage points.
Table 1System failure diagnosis
70.67%
LLM-judged Match
Best baseline: 34.00% (Multi/CoT). GoS improves Match by 36.67 percentage points.
Table 3Reported cost
$0.12 / $0.10
Per medical / system case
Average costs reported in the paper's experiments, not current API price estimates.
Tables 1 and 3
06 WHERE IT APPLIES
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.
These domains share the same reasoning pattern: multiple plausible hypotheses, evidence-seeking interaction, controlled state transitions, and final convergence toward the most defensible explanation.
07 START FROM THE CODE
Start with the DiagnosisArena medical diagnosis setup. Prepare the data, API settings, and output paths before launching the script.
# From the configured repository directory
python main.py
The script writes predictions and reports to CSV, saves case logs, and exports the changing belief graph to HTML.
Repository entry point; local data and model setup are required.
08 FREQUENTLY ASKED
Graph of States is a neuro-symbolic framework that solves abductive tasks with large language models, published at ICML 2026. Instead of an unstructured conversation history, it keeps the reasoning state in a structured belief graph of symptoms, hypotheses, evidence, and causal links, and a state machine governs backtracking, drill-down, and reporting.
Abductive tasks — explaining observed symptoms by searching for hidden causes — expose four recurring failures in existing LLM reasoning frameworks: evidence fabrication, context drift, failed backtracking, and early stopping. GoS turns aimless exploration into a directed search: the current belief state selects the next reasoning focus, new evidence updates confidences and links, and explicit state transitions decide whether to refine an explanation or abandon it. Frameworks such as chain-of-thought or tree-of-thought search are designed for static deductive problems and lack this explicit state control.
GoS was evaluated on two real-world diagnosis datasets: medical diagnosis (Table 1) and distributed-system failure diagnosis (Table 3). It reaches 39.86% Human-judged Match on medical diagnosis versus 26.09% for the best baseline (Multi/FoT), and 70.67% LLM-judged Match on system failure diagnosis versus 34.00% (Multi/CoT). The two tasks use different judges, so the two numbers are not directly comparable.
The code and all prompts are open at github.com/gaorch85/Graph-of-States under an MIT license, with a Python 3.12 environment and configuration files for both evaluation domains. GoS targets diagnosis-style abductive reasoning; the medical evaluation is a research benchmark and is not evidence of clinical readiness.
09 CITE THIS WORK
@inproceedings{
luo2026graph,
title={Graph of States: Solving Abductive Tasks with Large Language Models},
author={Yu Luo and Rongchen Gao and Lu Teng and Xidao Wen and Jiamin Jiang and Qingliang Zhang and Yongqian Sun and Shenglin Zhang and Jiasong Feng and Tong Liu and Wenjie Zhang and Dan Pei},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=F6PoIbPAe2}
}