GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis

Shaoting Tan; Ning Liu; Yuntao Du; Shuyue Wei; Wu Shuai; Qian Li; Yanyu Xu; Wei Zhang

cs.AIApr 8, 2026

GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis

Authors: Shaoting Tan, Ning Liu, Yuntao Du, Shuyue Wei, Wu Shuai, Qian Li, Yanyu Xu, Wei Zhang,

Organizations: Shandong University · Nankai University · East China Normal University · National Technological University

Abstract

Sequential diagnosis requires balancing diagnostic accuracy against resource costs through iterative information gathering. Existing Large Language Model (LLM) approaches exhibit a critical knowledge-reasoning gap: despite encoding extensive medical knowledge, they struggle to reason systematically under cost constraints, often resorting to excessive testing. We propose GraphDx, a knowledge-enhanced framework with two core innovations. First, we design an automated pipeline that leverages LLMs to construct Medical Diagnosis Knowledge Graphs (MDKGs) with quantized typicality, action-centric topology, and dual-objective attributes for both diagnostic relevance and cost-sensitivity. Second, we introduce three collaborative agents (Perception, Reasoning, and Decision) where the Perception and Decision Agents handle language understanding and generation, while the Reasoning Agent performs deterministic evidence scoring and cost-aware planning on the MDKG. Experiments on MedQA and MIMIC-IV across three LLM backbones (DeepSeek-V3, Kimi-k2, Llama-3.3) show that GraphDx improves diagnostic success rates from 50--68% to 79--93% while reducing test costs by 20--54%, providing a robust, economical, and interpretable solution for automated clinical diagnosis.

Figures & tables

Method	Explicit KG	Auto Construction	Sequential Diagnosis	Cost- Sensitive
End-to-End LLM Singhal et al. (2023)	✗	–	$\triangle$	✗
Multi-Agent LLM Nori et al. (2025)	✗	–	✓	$\triangle$
KG-Enhanced LLM Gao et al. (2025)	✓	✗	$\triangle$	✗
AutoKG Chen and Bertozzi (2023)	✓	✓	✗	✗
GraphDx (Ours)	✓	✓	✓	✓

Table 1: Comparison of Recent Works and Ours. ✓=Yes, ✗=No,

\triangle

=Weak/partial, —=Not applicable.

Figure 1: Overview of the GraphDx framework. Left: Automated MDKG Construction Pipeline (Algorithm 1), utilizing parallel extraction and hybrid alignment to build the graph. Right: Graph-Augmented Diagnostic Agent (Algorithm 2), employing a knowledge-enhanced loop of observation extraction, graph grounding, evidence scoring, and utility-based action planning.

Base Model	Method	Score (0-10) $\uparrow$	Cost ( $)$ \downarrow$	Turns	Success Rate $\uparrow$	Harmful Rate $\downarrow$
DeepSeek-V3	Standard LLM	7.25 $\pm$ 1.34	1062.69 $\pm$ 655.20	4.66 $\pm$ 0.77	67.8%	22.5%
	MAI-DxO	8.05 $\pm$ 0.98	2460.20 $\pm$ 1114.69	9.51 $\pm$ 2.74	75.0%	13.2%
	GraphDx (Ours)	9.05 $\pm$ 0.47	537.13 $\pm$ 221.24	4.76 $\pm$ 0.94	88.7%	7.7%
Kimi-k2	Standard LLM	7.66 $\pm$ 1.24	1456.88 $\pm$ 575.35	3.62 $\pm$ 0.51	66.8%	12.2%
	MAI-DxO	6.92 $\pm$ 1.61	2220.57 $\pm$ 1026.20	11.99 $\pm$ 3.54	64.0%	24.5%
	GraphDx (Ours)	9.50 $\pm$ 0.29	1156.02 $\pm$ 407.83	4.17 $\pm$ 0.73	93.2%	1.3%

Table 2: Diagnostic Performance Comparison on MedQA Dataset

Figure 2: Joint distribution of Cost vs. Diagnostic Score for DeepSeek-V3 model.

Base Model	Method	Score (0-10) $\uparrow$	Cost ( $)$ \downarrow$	Turns	Success Rate $\uparrow$	Harmful Rate $\downarrow$
DeepSeek-V3	Standard LLM	6.60 $\pm$ 0.93	737.43 $\pm$ 267.38	5.41 $\pm$ 0.87	56.8%	18.8%
	MAI-DxO	5.57 $\pm$ 1.43	1497.13 $\pm$ 844.00	11.28 $\pm$ 3.53	45.0%	30.5%
	GraphDx (Ours)	8.27 $\pm$ 0.51	340.98 $\pm$ 129.84	5.19 $\pm$ 0.93	83.0%	5.7%
Kimi-k2	Standard LLM	6.24 $\pm$ 1.08	1040.60 $\pm$ 539.29	4.02 $\pm$ 0.57	54.2%	23.2%
	MAI-DxO	5.19 $\pm$ 1.45	956.93 $\pm$ 559.68	11.97 $\pm$ 3.71	45.0%	36.5%
	GraphDx (Ours)	8.06 $\pm$ 0.65	658.48 $\pm$ 246.00	5.30 $\pm$ 1.26	79.3%	7.5%

Table 3: Diagnostic Performance Comparison on MIMIC-IV Dataset

Figure 3: Evolution of GT Disease Rank and Top-k Hit Rate. The blue line (left) shows the decline in average rank, while bars (right) show the increasing probability of GT entering the Top-1/3/5 list.

Method	Score $\uparrow$	Cost ( $)$ \downarrow$	Success Rate $\uparrow$	Harmful Rate $\downarrow$
Baseline	7.51 $\pm$ 1.30	1857 $\pm$ 773	65.7%	12.5%
w/o Graph	8.00 $\pm$ 1.21	1710 $\pm$ 739	71.5%	10.5%
w/o Inference	8.39 $\pm$ 1.08	1286 $\pm$ 642	77.5%	11.2%
GraphDx (Full)	9.24 $\pm$ 0.57	1066 $\pm$ 469	88.3%	4.3%

Table 4: Detailed Ablation Study Results on Llama-3.3

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Typicality Label	Symbol	Weight Value
Strongly Positive	++	4.0
Positive	+	1.5
Negative	-	-1.5
Strongly Negative	–	-4.0

Appendix

Table 5: Typicality Weights used in Evidence Scoring

Cost Label	Score	Invasiveness	Multiplier
Very Low	1.0	Low	1.0
Low	2.0	Moderate	1.5
Moderate	3.0	High	2.0
High	4.0
Very High	5.0

Appendix

Table 6: Cost Scores and Invasiveness Multipliers

Panel of Figure 4 — Figure 4: Statistical distribution of key attributes in MDKG.

Figure 5: Sensitivity of Top-1 Accuracy to variations in Strong Evidence Weight ( $w_{++}$ ) and Absence Penalty ( $\lambda$ ). The system exhibits a stable performance plateau, demonstrating robustness.

Figure 6: Typical Case Analysis (Scenario 50: Primary Amenorrhea). The Baseline agent (left) misdiagnosed Turner Syndrome by focusing on amenorrhea while ignoring the contradictory evidence of tall stature and fractures . In contrast, GraphDx (right) successfully linked these cues to Aromatase Deficiency via the structured graph, demonstrating the navigational role of structured knowledge.

Clinical Decision-Making

Clinical decision-making studies how evidence, patient preferences, risks, and resource constraints can guide diagnosis, treatment, and care.

See all 130 papers

MedExAgent: Training LLM Agents to Ask, Examine, and Diagnose in Noisy Clinical Environments
May 8, 2026Yicheng Gao, Xiaolin Zhou, Yahan Li +2Healthcare Medical Diagnosis
University of Southern California · Arizona State University
Timely Clinical Diagnosis through Active Test Selection
Oct 21, 2025Silas Ruhrberg Estévez, Nicolás Astorga, Mihaela van der SchaarClinical Decision Support Clinical Decision-Making
University of Cambridge Cambridge, UK
ClinicalAgents: Multi-Agent Orchestration for Clinical Decision Making with Dual-Memory
Mar 27, 2026Zhuohan Ge, Haoyang Li, Yubo Wang +3Clinical Decision-Making Multi-Agent LLM Systems
The Hong Kong Polytechnic University, Hong Kong SAR, China · The Hong Kong University of Science and Technology, Hong Kong SAR, China

May 8, 2026J/K move · Enter open · S save

MedExAgent: Training LLM Agents to Ask, Examine, and Diagnose in Noisy Clinical Environments

Yicheng Gao, Xiaolin Zhou, Yahan Li, Yue Zhao+1

University of Southern California · Arizona State University

Healthcare Medical Diagnosis LLM Agent Training RL for LLM Agents LLM Agent Reliability Medical AI Agents

Open paper AskPDF arXiv

Real-world clinical diagnosis is a complex process in which the doctor is required to obtain information from both interaction with the patient and conducting medical exams. Additionally, the doctor needs to adapt to different patient personas, as well as noisy and incomplete information that can happen at any time during the process. However, existing benchmarks for medical LLMs and methods for automatic diagnosis largely simplify this process by reducing it to single-turn question answering, noise-free conversations, or sequential exam making, etc., ignoring the interactive and uncertain nature of clinical diagnosis. In this paper, we aim to address this gap by formalizing clinical diagnosis as a Partially Observable Markov Decision Process (POMDP) with three action types: questioning the patient, ordering medical exams as tool calls, and issuing a diagnosis. We also introduce a systematic noise model comprising seven patient noise types and three exam noise types. Using our proposed environment, we train an effective diagnosis agent, MedExAgent, through a two-stage pipeline that first performs supervised finetuning on synthetic conversations structured after the Calgary-Cambridge model for clinical interviews, and then applies DAPO to optimize a composite reward capturing diagnostic accuracy, tool call quality, and exam cost including financial cost and patient discomfort. Through extensive experiments and ablation studies, we demonstrate that MedExAgent achieves diagnostic performance comparable to larger models while maintaining cost-efficient examination strategies.

Abstract

Clinical Decision-Making

Explore similar work

MedExAgent: Training LLM Agents to Ask, Examine, and Diagnose in Noisy Clinical Environments

Timely Clinical Diagnosis through Active Test Selection

ClinicalAgents: Multi-Agent Orchestration for Clinical Decision Making with Dual-Memory