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

# GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis
Source: [https://arxiv.org/html/2607.15280](https://arxiv.org/html/2607.15280)
Shaoting Tan1,Ning Liu1,Yuntao Du1,Shuyue Wei1, Wu Shuai2,Qian Li1,Yanyu Xu1,Wei Zhang3, Lizhen Cui1,Haitao Yuan4,

1Shandong University,2Nankai University,3East China Normal University,4National Technological University, Correspondence:[liun21cs@sdu\.edu\.cn](https://arxiv.org/html/2607.15280v1/mailto:email@domain)

###### 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 proposeGraphDx, 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 thatGraphDximproves 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\.

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

Shaoting Tan1, Ning Liu1, Yuntao Du1, Shuyue Wei1,Wu Shuai2,Qian Li1,Yanyu Xu1,Wei Zhang3,Lizhen Cui1,Haitao Yuan4,1Shandong University,2Nankai University,3East China Normal University,4National Technological University,Correspondence:[liun21cs@sdu\.edu\.cn](https://arxiv.org/html/2607.15280v1/mailto:email@domain)

## 1Introduction

Large Language Models \(LLMs\) have achieved remarkable success on medical examinations, with models like GPT\-4 surpassing human performance on USMLENoriet al\.\([2023](https://arxiv.org/html/2607.15280#bib.bib11)\); Singhalet al\.\([2023](https://arxiv.org/html/2607.15280#bib.bib12)\), demonstrating that LLMs encode extensive medical knowledge within their parameters\. However, translating this success to real clinical practice, particularlysequential diagnosis, remains a significant challenge\.

Unlike static question answering, sequential diagnosis mirrors actual clinical workflows: physicians iteratively gather information through symptom inquiries and diagnostic tests, making decisions under uncertainty while balancing diagnostic accuracy against resource costs including monetary expense, patient discomfort, and time\. This multi\-turn process requires not merely knowledge recall, but systematic reasoning that coordinates information acquisition with hypothesis refinement\.

Current LLM\-based approaches exhibit a critical limitation we term the*knowledge\-reasoning gap*: despite possessing substantial medical knowledge, LLMs struggle to reason systematically under cost constraints\. Recent studiesNoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\); Jiaet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib6)\)reveal that LLM agents tend toward “defensive medicine,” ordering excessive tests to compensate for reasoning uncertainty while failing to leverage discriminative features for efficient differential diagnosis\. This behavior stems from the implicit, unstructured nature of LLM reasoning, which lacks explicit domain models enabling systematic hypothesis testing\. We identify two key challenges underlying this gap:

##### Challenge 1: Diagnosis\-Ready Knowledge Graph Construction\.

Sequential diagnosis requires*quantitative*attributes beyond semantic relations, including symptom typicality and test utilities\. Existing knowledge graphs like UMLS lack these attributes, while current automated methodsChen and Bertozzi \([2023](https://arxiv.org/html/2607.15280#bib.bib3)\); Anuyahet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib2)\)extract only semantic triples\. Moreover, medical concepts exhibit context\-dependent semantics \(e\.g\., “heart failure” as diagnosis vs\. complication\), requiring dynamic role modeling that static ontologies cannot provide\.

##### Challenge 2: Effective Multi\-Agent Collaboration\.

Bridging neural language understanding with symbolic graph reasoning requires orchestrating observation extraction, graph grounding, evidence scoring, and response generation\. Recent approaches like MAI\-DxONoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)rely on prompt\-based coordination, but their complexity demands strong instruction\-following from base models, causing performance degradation on less capable LLMs\.

To address these challenges, we proposeGraphDx, a knowledge\-enhanced framework comprising two integrated components \(Figure[1](https://arxiv.org/html/2607.15280#S2.F1)\):

\(1\) Automated MDKG Construction\(§[3\.2](https://arxiv.org/html/2607.15280#S3.SS2)\) addressesChallenge 1\. We design an automated pipeline where specialized agents collaborate to construct MDKGs enriched with*quantitative diagnostic attributes*including typicality weights and test cost\-effectiveness metrics that existing knowledge graphs lack\. The pipeline employs a three\-stage process: parallel knowledge extraction with quantized typicality, hybrid entity alignment with dynamic node upgrade for handling semantic role transitions, and attribute enrichment for cost\-sensitive planning\. This enables complex causal chains to emerge automatically without manual annotation\.

\(2\) Collaborative Diagnostic Agents\(§[3\.3](https://arxiv.org/html/2607.15280#S3.SS3)\) addressesChallenge 2\. We introduce three specialized agents: a*Perception Agent*that extracts observations from patient responses and grounds them to graph nodes, a*Reasoning Agent*that performs deterministic evidence scoring and cost\-sensitive planning on the MDKG, and a*Decision Agent*that generates clinically appropriate responses\. This architecture offloads complex reasoning to the graph, reducing dependence on base model capabilities\.

We evaluateGraphDxon MedQA\-Extended and MIMIC\-IV datasets across three LLM backbones\. Results demonstrate thatGraphDximproves diagnostic success rates from 50% to over 88% while reducing test costs by 20% to 50%, with consistent gains across all tested models, including scenarios where sophisticated multi\-agent baselines fail\. To support reproducibility and further research, we open\-source our implementation, including the automated graph construction pipeline and theClinicSimenvironment at[https://anonymous\.4open\.science/r/GraphDx\-BB8B](https://anonymous.4open.science/r/GraphDx-BB8B)\.

## 2Related Work

Table 1:Comparison of Recent Works and Ours\.
✓=Yes, ✗=No,△\\triangle=Weak/partial, —=Not applicable\.MethodExplicitKGAutoConstructionSequentialDiagnosisCost\-SensitiveEnd\-to\-End LLMSinghalet al\.\([2023](https://arxiv.org/html/2607.15280#bib.bib12)\)✗–△\\triangle✗Multi\-Agent LLMNoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)✗–✓△\\triangleKG\-Enhanced LLMGaoet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib5)\)✓✗△\\triangle✗AutoKGChen and Bertozzi \([2023](https://arxiv.org/html/2607.15280#bib.bib3)\)✓✓✗✗GraphDx\(Ours\)✓✓✓✓

![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/overview.png)Figure 1:Overview of theGraphDxframework\. 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\.As shown in Table[1](https://arxiv.org/html/2607.15280#S2.T1), we categorize related work into three categories and compare them in Table[1](https://arxiv.org/html/2607.15280#S2.T1)\.

Sequential Diagnosis Agents\.Sequential diagnosis requires agents to balance information acquisition and diagnostic costs over multiple interactions\. Recently,Noriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)proposed SDBench and MAI\-DxO, achieving diagnostic accuracy and cost control surpassing human doctors through multi\-agent orchestration\.Jiaet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib6)\)proposed the DDO framework, using Reinforcement Learning \(RL\) to optimize symptom inquiry strategies\.Schmidgallet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib10)\)andQiuet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib8)\)built AgentClinic and DiagGym simulation environments respectively for training and evaluating multimodal diagnostic agents\. Additionally, ACTMED proposed byestévez2025timelyclinicaldiagnosisactivecombines Bayesian experimental design with LLMs to actively select tests\. However, most of these methods rely on the implicit reasoning of LLMs or RL with low sample efficiency, lacking an explicit, interpretable structured domain model to guide decisions\.

Automated Medical Knowledge Graph Construction\.Traditional MKG construction relies on expert annotation and is costly\. Recent research has begun to explore using LLMs for automated graph construction\.Chen and Bertozzi \([2023](https://arxiv.org/html/2607.15280#bib.bib3)\)proposed AutoKG, using LLMs to extract keywords and calculate graph Laplacian weights\. CoDe\-KG byAnuyahet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib2)\)uses sentence complexity modeling to extract triples\.Sarabadaniet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib9)\)proposed DKG\-LLM, integrating dynamic knowledge graphs with the Grok 3 model\. Although these works achieve automation, the constructed graphs are mostly used for semantic retrieval and lack the fine\-grained typicality parameters \(e\.g\., symptom weights\) and decision utility attributes \(e\.g\., test cost, invasiveness\) required for diagnostic reasoning\.

Knowledge\-Enhanced Clinical Decision\.Knowledge\-Enhanced AI aims to combine the perceptual capabilities of neural networks with the logical capabilities of symbolic systems\.Gaoet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib5)\)explored integrating MKG into LLMs for diagnostic prediction\. Our method goes a step further, not only achieving automated graph construction but also designing an explicit evidence scoring engine based on the graph, realizing true "knowledge\-guided reasoning\."

In summary, our methodGraphDxis the only framework that simultaneously possesses automated graph construction capabilities, supports sequential diagnosis, and explicitly models test costs\.

## 3Methodology

### 3\.1Problem Formulation

We formulate sequential diagnosis as a partially observable decision process\. Let𝒟\\mathcal\{D\}be the set of possible diseases\. At turntt, the agent observes dialogue historyHtH\_\{t\}and maintains a belief state over𝒟\\mathcal\{D\}\. The agent selects an actionat∈𝒜a​c​t​i​o​na\_\{t\}\\in\\mathcal\{A\}\_\{action\}:

- •Inquire\(f\)\(f\): Ask about symptom or featureff\.
- •Test\(τ\)\(\\tau\): Order diagnostic testτ\\tau\.
- •Diagnose\(d\)\(d\): Provide final diagnosisdd\.

The objective is to minimize the expected total cost:

minπ⁡𝔼​\[∑t=1Tc​\(at\)\+λm​i​s⋅𝕀​\[d^≠d∗\]\]\\min\_\{\\pi\}\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}c\(a\_\{t\}\)\+\\lambda\_\{mis\}\\cdot\\mathbb\{I\}\[\\hat\{d\}\\neq d^\{\*\}\]\\right\]\(1\)wherec​\(at\)c\(a\_\{t\}\)is the cost of actionata\_\{t\}\(including monetary cost, invasiveness, and time\),λm​i​s\\lambda\_\{mis\}is the penalty for misdiagnosis,d^\\hat\{d\}is the predicted diagnosis, andd∗d^\{\*\}is the ground truth\.

### 3\.2Automated Construction of Medical Diagnosis Knowledge Graph

The core ofGraphDxis the Medical Diagnosis Knowledge Graph \(MDKG\), formally defined as a directed graph𝒢=\(𝒱,ℰ,𝒲,𝒜\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{W\},\\mathcal\{A\}\)where:

- •𝒱=𝒱d∪𝒱f∪𝒱t\\mathcal\{V\}=\\mathcal\{V\}\_\{d\}\\cup\\mathcal\{V\}\_\{f\}\\cup\\mathcal\{V\}\_\{t\}: nodes for diseases, features \(symptoms/signs\), and tests\.
- •ℰ⊆\(𝒱d×𝒱f\)∪\(𝒱f×𝒱t\)\\mathcal\{E\}\\subseteq\(\\mathcal\{V\}\_\{d\}\\times\\mathcal\{V\}\_\{f\}\)\\cup\(\\mathcal\{V\}\_\{f\}\\times\\mathcal\{V\}\_\{t\}\): edges connecting diseases to features and features to tests\.
- •𝒲:ℰ→ℝ\\mathcal\{W\}:\\mathcal\{E\}\\to\\mathbb\{R\}: edge weights encoding association strength\.
- •𝒜:𝒱t→ℝ2\\mathcal\{A\}:\\mathcal\{V\}\_\{t\}\\to\\mathbb\{R\}^\{2\}: test attributes \(cost, invasiveness\)\.

We implement a fully automated pipeline to construct𝒢\\mathcal\{G\}from a disease list𝒟l​i​s​t\\mathcal\{D\}\_\{list\}without manual annotation\. The process proceeds in three stages, designed to ensure the graph serves as a robust computational substrate for evidence\-based reasoning\.

Stage 1: Parallel Knowledge Extraction\.The system processes each diseased∈𝒟l​i​s​td\\in\\mathcal\{D\}\_\{list\}in parallel\. For each disease, it prompts the LLM to extract a set of tuples\{\(f,wd​f,Tf\)\}\\\{\(f,w\_\{df\},T\_\{f\}\)\\\}, whereffis a feature,wd​fw\_\{df\}is its typicality, andTfT\_\{f\}is a list of verifying tests\. To mitigate the noise from poorly calibrated continuous probability estimates in LLMs, we employ aQuantized Typicalitystrategy\. We map linguistic typicality descriptions to discrete weight buckets𝒲:ℰd​f→ℝ\\mathcal\{W\}:\\mathcal\{E\}\_\{df\}\\to\\mathbb\{R\}:

w​\(d,f\)=\{w\+\+iffis Hallmark \(\+\+\)w\+if​f​is Common \(\+\)w−if​f​is Rare \(\-\)w−−if​f​is Impossible \(–\)w\(d,f\)=\\begin\{cases\}w\_\{\+\+\}&\\text\{if \}f\\text\{ is Hallmark \(\+\+\}\)\\\\ w\_\{\+\}&\\text\{if \}f\\text\{ is Common \(\+\)\}\\\\ w\_\{\-\}&\\text\{if \}f\\text\{ is Rare \(\-\)\}\\\\ w\_\{\-\-\}&\\text\{if \}f\\text\{ is Impossible \(\-\-\)\}\\end\{cases\}\(2\)This quantization acts as a low\-pass filter, stabilizing the reasoning process against minor probability fluctuations in LLM generation\.

Additionally, to ensure the graph directly supports diagnostic planning, we enforce anAction\-Centric Topology\. Instead of just declarative knowledge \(“Pneumonia causes cough”\), the extraction explicitly models*verification edges*\(f,τ\)∈ℰf​τ\(f,\\tau\)\\in\\mathcal\{E\}\_\{f\\tau\}connecting features to the tests that can confirm or rule them out\. This transforms the graph into a navigation structure: given an uncertain feature, the agent can directly traverse to relevant diagnostic actions\.

Stage 2: Hybrid Entity Alignment & Dynamic Upgrade\.Medical concepts often suffer from semantic ambiguity and role shifts \(e\.g\., a disease in one context is a symptom in another\)\. To resolve synonymy, we employ aHybrid Alignment Mechanismto align a new termuuto the existing node set𝒱\\mathcal\{V\}\. We retrieve a candidate set𝒞u\\mathcal\{C\}\_\{u\}using a hybrid retrieval strategy that combines lexical and semantic matching:

𝒞u=TopKoverlap​\(u,𝒱\)∪TopKembed​\(u,𝒱\)\\mathcal\{C\}\_\{u\}=\\text\{TopK\}\_\{\\text\{overlap\}\}\(u,\\mathcal\{V\}\)\\cup\\text\{TopK\}\_\{\\text\{embed\}\}\(u,\\mathcal\{V\}\)\(3\)whereTopKoverlap\\text\{TopK\}\_\{\\text\{overlap\}\}selects candidates based on the Overlap Coefficient \(intersection over minimum set size\) to capture partial matches \(e\.g\., "Diabetes"⊆\\subseteq"Type 2 Diabetes"\), andTopKembed\\text\{TopK\}\_\{\\text\{embed\}\}selects candidates based on cosine similarity of dense embeddingsϕ​\(⋅\)\\phi\(\\cdot\)to capture semantic synonyms\. An LLM then acts as a discriminatorD​\(u,𝒞u\)D\(u,\\mathcal\{C\}\_\{u\}\)to determine ifuushould merge withv∗∈𝒞uv^\{\*\}\\in\\mathcal\{C\}\_\{u\}or form a new node\.

Furthermore, to handle role shifts without manual intervention, we introduce aDynamic Node Upgradestrategy\. When a node initially added as a feature \(e\.g\., “Heart Failure” as a symptom of renal disease\) is later identified as an independent disease, the system:

1. 1\.Promotes the node from𝒱f\\mathcal\{V\}\_\{f\}to𝒱d\\mathcal\{V\}\_\{d\}:𝒱d←𝒱d∪\{v\},𝒱f←𝒱f∖\{v\}\\mathcal\{V\}\_\{d\}\\leftarrow\\mathcal\{V\}\_\{d\}\\cup\\\{v\\\},\\mathcal\{V\}\_\{f\}\\leftarrow\\mathcal\{V\}\_\{f\}\\setminus\\\{v\\\}
2. 2\.Preserves all existing incoming edges\(d′,v\)\(d^\{\\prime\},v\)\(its role as a feature\)
3. 3\.Enables new outgoing edges\(v,f′\)\(v,f^\{\\prime\}\)\(its features as a disease\)

This allows complex causal chains \(e\.g\., Renal Disease→\\toHeart Failure→\\toDyspnea\) to emerge automatically without manual ontology restructuring\.

Stage 3: Attribute Enrichment\.Finally, to support cost\-sensitive decision making, the graph requires quantitative metadata often missing from raw extractions\. TheMetadata Enrichment Moduleinfers these attributes for new test nodes\. Each test nodeτ∈𝒱t\\tau\\in\\mathcal\{V\}\_\{t\}is associated with attributes𝒜​\(τ\)=\(cτ,ιτ\)\\mathcal\{A\}\(\\tau\)=\(c\_\{\\tau\},\\iota\_\{\\tau\}\), wherecτc\_\{\\tau\}represents the monetary cost level andιτ\\iota\_\{\\tau\}represents the invasiveness multiplier\. This ensures the graph is fully populated with the quantitative data required for downstream planning\.

### 3\.3Graph\-Augmented Diagnostic Agent

To bridge the gap between unstructured patient interaction and structured medical reasoning, we design aGraph\-Augmented Diagnostic Agent\. This agent operates through a "Think\-then\-Act" loop \(Algorithm 2\), where a neural component handles perception and a symbolic component handles reasoning\.

#### 3\.3\.1Perception Agent

Since patient inputs are unstructured and diverse \(ranging from verbal descriptions to medical reports\), the system must first normalize them into a structured format\. ThePerception Moduleacts as this interface\. At turntt, it employs an extraction functionfe​x​tf\_\{ext\}to parse the inputrtr\_\{t\}\(which may be a patient’s verbal response or a returned medical test report\) into structured observations:

Ot=fe​x​t​\(rt\|Ht−1\)=\{\(mi,si\)\}i=1KO\_\{t\}=f\_\{ext\}\(r\_\{t\}\|H\_\{t\-1\}\)=\\\{\(m\_\{i\},s\_\{i\}\)\\\}\_\{i=1\}^\{K\}\(4\)wheremim\_\{i\}is the mention text \(e\.g\., "fever" or "WBC count elevated"\) andsi∈\{Present,Absent\}s\_\{i\}\\in\\\{\\text\{Present\},\\text\{Absent\}\\\}is the status\. Crucially, this unified extraction handles both subjective symptoms and objective test findings identically\. Subsequently, a grounding functiong:ℳ→𝒱fg:\\mathcal\{M\}\\to\\mathcal\{V\}\_\{f\}maps each mentionmim\_\{i\}to a canonical graph nodefi∗f^\{\*\}\_\{i\}using the alignment mechanism from Sec\.[3\.2](https://arxiv.org/html/2607.15280#S3.SS2)\. The symbolic state is updated as𝒮t=𝒮t−1∪\{\(g​\(mi\),si\)\}i=1K\\mathcal\{S\}\_\{t\}=\\mathcal\{S\}\_\{t\-1\}\\cup\\\{\(g\(m\_\{i\}\),s\_\{i\}\)\\\}\_\{i=1\}^\{K\}\.

#### 3\.3\.2Reasoning Agent

Once observations are grounded, the core challenge is to make deterministic and cost\-effective decisions\. TheReasoning Engineaddresses this through two key mechanisms:

##### Evidence Scoring\.

To avoid the instability of black\-box neural reasoning, we implement an explicitEvidence Scoringmechanism\. It computes a confidence scoreS​\(d\)S\(d\)for each diseaseddbased on the alignment between the graph knowledge and the observed state𝒮t\\mathcal\{S\}\_\{t\}\. The scoring function explicitly handles positive and negative evidence:

S​\(d\)=∑\(f,s\)∈𝒮tScore​\(f,d,s\)S\(d\)=\\sum\_\{\(f,s\)\\in\\mathcal\{S\}\_\{t\}\}\\text\{Score\}\(f,d,s\)\(5\)where the component score is defined as:

Score​\(f,d,s\)=\{w​\(d,f\)if​s=Present−λ⋅w​\(d,f\)if​s=Absent\\text\{Score\}\(f,d,s\)=\\begin\{cases\}w\(d,f\)&\\text\{if \}s=\\text\{Present\}\\\\ \-\\lambda\\cdot w\(d,f\)&\\text\{if \}s=\\text\{Absent\}\\end\{cases\}\(6\)Here,λ\\lambdais a penalty factor\. Note that ifw​\(d,f\)<0w\(d,f\)<0\(the disease typically lacks the feature\) ands=Presents=\\text\{Present\}, the termw​\(d,f\)w\(d,f\)naturally reduces the score\. Conversely, ifs=Absents=\\text\{Absent\}andw​\(d,f\)\>0w\(d,f\)\>0\(expected feature missing\), the term−λ⋅w​\(d,f\)\-\\lambda\\cdot w\(d,f\)penalizes the disease\.

##### Cost\-Sensitive Action Planning\.

To balance diagnostic accuracy with cost \(mitigating "defensive medicine"\), we employ aCost\-Sensitive Action Planningmodule\. While full Bayesian Value of Information \(VoI\) calculation is computationally prohibitive for real\-time interaction, we implement a*heuristic utility function*that approximates information gain via feature variance and relevance:

- •Feature Selection\.We identify unobserved features that maximize discriminative power among the top\-KKcandidate diseasesDt​o​pD\_\{top\}\. The discriminative scoreV​\(f\)V\(f\)serves as a lightweight proxy for information gain: V​\(f\)=∑d∈Dt​o​p\|S​\(d\)\|⋅\|w​\(d,f\)\|\+α⋅Vard∈Dt​o​p⁡\(w​\(d,f\)\)\\begin\{split\}V\(f\)&=\\sum\_\{d\\in D\_\{top\}\}\\lvert S\(d\)\\rvert\\cdot\\lvert w\(d,f\)\\rvert\\\\ &\\quad\+\\alpha\\cdot\\operatorname\{Var\}\_\{d\\in D\_\{top\}\}\(w\(d,f\)\)\\end\{split\}\(7\)The first term prioritizes features relevant to high\-confidence diseases, while the second term \(variance\) favors features that can differentiate between them\.
- •Test Selection\.For each candidate testτ\\tau, we calculate its utilityU​\(τ\)U\(\\tau\)by aggregating the value of the features it can verify: U​\(τ\)=∑f∈Verifies​\(τ\)V​\(f\)⋅η​\(f,τ\)1\+cτ⋅ιτU\(\\tau\)=\\frac\{\\sum\_\{f\\in\\text\{Verifies\}\(\\tau\)\}V\(f\)\\cdot\\eta\(f,\\tau\)\}\{1\+c\_\{\\tau\}\\cdot\\iota\_\{\\tau\}\}\(8\)whereη​\(f,τ\)∈\{ηl​o​w,ηh​i​g​h\}\\eta\(f,\\tau\)\\in\\\{\\eta\_\{low\},\\eta\_\{high\}\\\}denotes the effectiveness of testτ\\taufor featureff\. The denominator penalizes expensive and invasive tests, ensuring the selected actions maximize the information\-to\-cost ratio\.

#### 3\.3\.3Decision Agent

Acting as the "right brain," this agent generates the final actionata\_\{t\}and natural language responser​e​s​ptresp\_\{t\}by conditioning on the structured reasoning summaryΣt\\Sigma\_\{t\}:

\(at,respt\)∼πθ\(⋅∣Ht,Σt\)\(a\_\{t\},resp\_\{t\}\)\\sim\\pi\_\{\\theta\}\(\\cdot\\mid H\_\{t\},\\Sigma\_\{t\}\)\(9\)whereΣt\\Sigma\_\{t\}aggregates the symbolic outputs:

Σt=⟨Rank​\(𝒟\),TopKV​\(f\),TopKU​\(τ\)⟩\\Sigma\_\{t\}=\\left\\langle\\text\{Rank\}\(\\mathcal\{D\}\),\\text\{Top\}\_\{K\}^\{V\}\(f\),\\text\{Top\}\_\{K\}^\{U\}\(\\tau\)\\right\\rangle\(10\)This injection ofΣt\\Sigma\_\{t\}constrains the LLM’s generation space to medically valid paths derived from the MDKG\.

### 3\.4Design Rationale

TheGraphDxarchitecture embodies a key insight:*neural and symbolic components excel at complementary tasks*\. LLMs handle the “soft” aspects of diagnosis—understanding colloquial language, maintaining conversational flow, and exercising clinical judgment in ambiguous situations\. The symbolic engine handles the “hard” aspects—deterministic state tracking, systematic hypothesis scoring, and principled cost\-benefit analysis\. This separation provides several advantages: \(1\)Interpretability: Every diagnostic conclusion traces to explicit evidence scores; \(2\)Consistency: Deterministic state tracking prevents contradictory reasoning; \(3\)Efficiency: Symbolic utility computation is faster than LLM deliberation; \(4\)Robustness: Graph structure constrains LLM outputs to valid medical reasoning\.

## 4Experiments

We conduct extensive experiments to address the following research questions:Q1: CanGraphDxachieve superior diagnostic accuracy and cost\-efficiency compared to current SOTA LLM frameworks?Q2: How robust is our method when transferring to real\-world, noisy clinical scenarios?Q3: What are the individual contributions of the structured MDKG and the explicit inference engine?

##### Implementation Details\.

We evaluateGraphDxon two datasets:MedQA\(200 cases\) andMIMIC\-IV\(200 real\-world cases\)\. We employClinicSim, a modular simulation environment, to conduct multi\-turn diagnostic dialogues\. We compare our method againstStandard LLMprompting and the multi\-agentMAI\-DxOframeworkNoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)across three LLM backbones: DeepSeek\-V3, Kimi\-k2, and Llama\-3\.3\. Performance is measured by Diagnostic Score \(0\-10\), Total Cost \($\), and Dialogue Turns\. For detailed descriptions of the datasets, baseline settings, hyperparameter configurations, and the simulation environment, please refer to Appendix[D](https://arxiv.org/html/2607.15280#A4)\.

### 4\.1Experimental Results

#### 4\.1\.1Main Results

Table[2](https://arxiv.org/html/2607.15280#S4.T2)and Table[3](https://arxiv.org/html/2607.15280#S4.T3)present the performance comparison betweenGraphDxand baselines on MedQA and MIMIC\-IV datasets, respectively\. The results demonstrate that our method achieves consistent and significant improvements across all metrics and base models\.

##### Diagnostic Accuracy\.

On the MedQA dataset,GraphDxsignificantly outperforms the Standard LLM baseline\. For instance, with DeepSeek\-V3, the success rate \(Score≥\\geq8\) jumps from 67\.8% to 88\.7%, and Kimi\-k2 achieves a remarkable 93\.2% success rate \(assessment details in Appendix[G\.3](https://arxiv.org/html/2607.15280#A7.SS3)\)\. We also compared our method with the SOTA multi\-agent framework MAI\-DxONoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)\. While MAI\-DxO improves accuracy on DeepSeek\-V3 \(8\.05\), it incurs extremely high costs \($2460\) and interaction turns \(9\.51\)\. On the smaller Llama\-3\.3 model, MAI\-DxO suffers from performance collapse \(Score 5\.38\), indicating its high dependency on the base model’s capability\. In contrast,GraphDxachieves Pareto optimality across all models by offloading reasoning to the graph\. This advantage generalizes well to the real\-world MIMIC\-IV dataset\. Despite the increased clinical noise,GraphDximproves the average diagnostic score by approximately 2\.0 points \(e\.g\., DeepSeek\-V3: 6\.60→\\to8\.27\) and increases the success rate by 25%–30%\. In contrast, the MAI\-DxO baseline struggles significantly on this real\-world dataset, showing lower scores and high variance, likely due to the complexity of real clinical notes confusing the multi\-agent debate mechanism\. This proves that structured knowledge effectively guides the model to grasp key features even in noisy environments\.

##### Cost\-Effectiveness and Efficiency\.

GraphDxconsistently reduces test costs by 20%–54% across both datasets while improving accuracy \(see Appendix[G\.3\.2](https://arxiv.org/html/2607.15280#A7.SS3.SSS2)for details on the US\-based cost estimation methodology\)\. For DeepSeek\-V3 on MedQA, the average cost drops from $1062 to $537\. This is attributed to the utility\-based active planning module, which effectively suppresses the "defensive medicine" behavior—blindly ordering expensive tests \(e\.g\., full\-body CT\) to compensate for uncertainty—observed in baselines\. Notably, on MIMIC\-IV, MAI\-DxO incurs extremely high costs \(e\.g\., $1497 for DeepSeek\-V3\) due to uncontrolled exploration, whereasGraphDxmaintains low costs \($340\) by precisely targeting relevant tests\. Figure[2](https://arxiv.org/html/2607.15280#S4.F2)illustrates this advantage: while Baseline results \(purple\) are scattered with many high\-cost, low\-score samples,GraphDx\(green\) is tightly clustered in the "high score\-low cost" region\. Regarding interaction efficiency,GraphDxincurs slightly more turns than the Standard LLM \(e\.g\., 5\.06 vs\. 3\.80 for Llama\-3\.3\)\. This is deliberate: the graph agent performs more thorough differential diagnosis, excluding distractors through multi\-turn inquiries rather than jumping to premature conclusions\. Given the substantial gains in diagnostic quality, this trade\-off is clinically justified\.

##### Robustness and Failure Analysis\.

On the challenging MIMIC\-IV dataset, we observed that baselines often fail due to \(1\)Noise Interference, being misled by irrelevant details in past medical history \(e\.g\., old fractures\), and \(2\)Defensive Medicine, leading to soaring costs \(e\.g\., Scenario 66 incurred $1825 in costs yet still resulted in misdiagnosis\)\.GraphDxmitigates these issues by filtering noise through the MDKG’s prior knowledge, focusing reasoning on core pathological features and avoiding unnecessary expensive testing\.

Table 2:Diagnostic Performance Comparison on MedQA DatasetBase ModelMethodScore \(0\-10\)↑\\uparrowCost \($\)↓\\downarrowTurnsSuccess Rate↑\\uparrowHarmful Rate↓\\downarrowDeepSeek\-V3Standard LLM7\.25±\\pm1\.341062\.69±\\pm655\.204\.66±\\pm0\.7767\.8%22\.5%MAI\-DxO8\.05±\\pm0\.982460\.20±\\pm1114\.699\.51±\\pm2\.7475\.0%13\.2%GraphDx\(Ours\)9\.05±\\pm0\.47537\.13±\\pm221\.244\.76±\\pm0\.9488\.7%7\.7%Kimi\-k2Standard LLM7\.66±\\pm1\.241456\.88±\\pm575\.353\.62±\\pm0\.5166\.8%12\.2%MAI\-DxO6\.92±\\pm1\.612220\.57±\\pm1026\.2011\.99±\\pm3\.5464\.0%24\.5%GraphDx\(Ours\)9\.50±\\pm0\.291156\.02±\\pm407\.834\.17±\\pm0\.7393\.2%1\.3%Llama\-3\.3Standard LLM7\.51±\\pm1\.301857\.47±\\pm773\.053\.80±\\pm0\.6865\.7%12\.5%MAI\-DxO5\.38±\\pm2\.063029\.19±\\pm1236\.2416\.86±\\pm2\.0150\.3%42\.3%GraphDx\(Ours\)9\.24±\\pm0\.571065\.78±\\pm469\.345\.06±\\pm1\.5188\.3%4\.3%

![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/cost_score_joint.png)Figure 2:Joint distribution of Cost vs\. Diagnostic Score for DeepSeek\-V3 model\.Table 3:Diagnostic Performance Comparison on MIMIC\-IV DatasetBase ModelMethodScore \(0\-10\)↑\\uparrowCost \($\)↓\\downarrowTurnsSuccess Rate↑\\uparrowHarmful Rate↓\\downarrowDeepSeek\-V3Standard LLM6\.60±\\pm0\.93737\.43±\\pm267\.385\.41±\\pm0\.8756\.8%18\.8%MAI\-DxO5\.57±\\pm1\.431497\.13±\\pm844\.0011\.28±\\pm3\.5345\.0%30\.5%GraphDx\(Ours\)8\.27±\\pm0\.51340\.98±\\pm129\.845\.19±\\pm0\.9383\.0%5\.7%Kimi\-k2Standard LLM6\.24±\\pm1\.081040\.60±\\pm539\.294\.02±\\pm0\.5754\.2%23\.2%MAI\-DxO5\.19±\\pm1\.45956\.93±\\pm559\.6811\.97±\\pm3\.7145\.0%36\.5%GraphDx\(Ours\)8\.06±\\pm0\.65658\.48±\\pm246\.005\.30±\\pm1\.2679\.3%7\.5%Llama\-3\.3Standard LLM6\.14±\\pm1\.001164\.27±\\pm521\.714\.34±\\pm0\.6650\.3%22\.0%MAI\-DxO3\.56±\\pm1\.431820\.21±\\pm803\.6817\.53±\\pm1\.6530\.8%57\.2%GraphDx\(Ours\)8\.55±\\pm0\.67711\.93±\\pm331\.546\.60±\\pm1\.8582\.2%5\.7%

#### 4\.1\.2Performance on Unseen Diseases \(Open\-Set Evaluation\)

To further address the concern regarding the closed\-set nature of the MDKG, we conducted an "Open\-Set" evaluation using a subset of MIMIC\-IV cases where the ground truth disease wasexplicitly excludedfrom our constructed graph\. This setting tests the system’s ability to handle "unknown" conditions by relying on the hybrid knowledge\-enhanced architecture\.

Results on the DeepSeek\-V3 backbone show that even without specific disease nodes,GraphDxoutperforms the Standard LLM baseline\.GraphDxachieved a mean score of7\.65compared to the baseline’s6\.66, a significant improvement of\+1\.0 point\. The average test cost was reduced from$743\.48\(Baseline\) to$574\.88\(GraphDx\), a saving of∼\\sim23%\.

These findings confirm the robustness of our hybrid design\. Although the specific disease node is missing, the "Unaligned Features" mechanism \(Algorithm[2](https://arxiv.org/html/2607.15280#algorithm2)\) ensures that clinical observations are still captured and passed to the LLM\. Furthermore, the graph’s general structure of feature\-test relationships remains valid \(e\.g\., "Chest Pain" suggests "ECG" regardless of the specific underlying pathology\), allowing the agent to conduct efficient workups before falling back on the LLM’s parametric knowledge for the final diagnosis\.

#### 4\.1\.3Human Evaluation of Simulation Quality

To address concerns regarding the reliance on simulation and LLM\-based evaluation, we conducted a rigorous validation study to ensure clinical validity\. Medical experts reviewed 365 diagnostic scenarios and 143 medical test cost estimates generated by our system\. We analyzed the consistency between human experts and our automated LLM judge\. The Pearson correlation coefficient forDiagnostic Scorewas0\.89\(n=365\), with a Mean Absolute Error \(MAE\) of0\.58\(on a 0\-10 scale\) and a94\.8%agreement rate on success/failure classification \(Score≥\\geq8\)\. ForTest Cost, the correlation was0\.89\(n=143\) with an MAE of$226\.14\. These results provide strong empirical evidence that our automated evaluation pipeline is a reliable proxy for human expert judgment\.

#### 4\.1\.4Visualization of Reasoning Process

Figure[3](https://arxiv.org/html/2607.15280#S4.F3)illustrates the evolution of the Ground Truth \(GT\) disease rank and Top\-k hit rate over dialogue turns using DeepSeek\-V3\. We observe two key trends: \(1\)Rapid Convergence:In early turns \(1\-3\), the GT rank drops sharply and Top\-5 hit rate exceeds 50%, showing the graph’s ability to quickly lock onto relevant diseases\. \(2\)Effective Differential Diagnosis:In later turns \(4\-8\), the Top\-1 hit rate rises above 40%, confirming that our utility\-based strategy effectively pinpoints the correct diagnosis through discriminative feature collection\.

![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/rank_evolution_combined.png)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\.
#### 4\.1\.5Ablation Study

To quantify the contribution of each component \(MDKG knowledge base and inference engine\) inGraphDx, we conducted an ablation study on the Llama\-3\.3 model using the MedQA\-Extended dataset\. We designed two variants:

- •w/o Graph:Removes the real MDKG and instead uses the LLM to "hallucinate" a graph summary based on dialogue history\. This tests the value of structured knowledge itself\.
- •w/o Inference:Retains the real MDKG for retrieving neighbor nodes but removes evidence scoring and utility\-based planning, relying entirely on the LLM for decision\-making\. This tests the value of the explicit inference engine\.

The experimental results are shown in Table[4](https://arxiv.org/html/2607.15280#S4.T4)\.

Table 4:Detailed Ablation Study Results on Llama\-3\.3MethodScore↑\\uparrowCost \($\)↓\\downarrowSuccessRate↑\\uparrowHarmfulRate↓\\downarrowBaseline7\.51±\\pm1\.301857±\\pm77365\.7%12\.5%w/o Graph8\.00±\\pm1\.211710±\\pm73971\.5%10\.5%w/o Inference8\.39±\\pm1\.081286±\\pm64277\.5%11\.2%GraphDx \(Full\)9\.24±\\pm0\.571066±\\pm46988\.3%4\.3%

The analysis is as follows:

1. 1\.Necessity of Structured Knowledge:Compared to Baseline,w/o Graphshows a slight performance improvement \(Score 7\.51→\\to8\.00\), indicating that even a hallucinated structured summary helps the LLM organize its thoughts\. However,w/o Inference\(using the real graph\) further improves performance \(Score→\\to8\.39, Cost↓\\downarrow25%\), proving that accurate domain knowledge \(MDKG\) is far superior to the LLM’s parametric memory\.
2. 2\.Critical Role of Explicit Reasoning:The fullGraphDxachieves the largest performance leap compared tow/o Inference\(Score→\\to9\.24, Cost↓\\downarrow17%\)\. This demonstrates that knowledge alone is not enough; the explicit inference engine based on evidence scoring and utility effectively guides the agent to make optimal decisions in complex uncertain environments, avoiding the LLM’s blind trial\-and\-error\.

#### 4\.1\.6Parameter Sensitivity Analysis

To assess the robustness of our mechanism, we conducted an offline sensitivity analysis on the interaction logs\. We re\-evaluated the disease ranking logic by varying key hyperparameters\. The results, detailed in Appendix[H\.2](https://arxiv.org/html/2607.15280#A8.SS2), show that the system maintains stable performance across a wide range of parameters, demonstrating robustness\.

#### 4\.1\.7Case Study

To deeply understand the decision\-making advantages ofGraphDxin different clinical contexts, we selected representative cases for detailed comparative analysis\. These cases reveal typical failure modes of baseline models inrare disease reasoning,anatomical logic, andcost\-effective diagnosis, whileGraphDxsuccessfully avoids these pitfalls through structured knowledge\. Detailed analysis and visualization are provided in Appendix[H\.3](https://arxiv.org/html/2607.15280#A8.SS3)\.

## 5Conclusion

This paper proposesGraphDx, which effectively solves the "Knowledge\-Reasoning Mismatch" problem of LLMs in sequential diagnosis by automatically constructing a medical knowledge graph and combining it with knowledge\-enhanced reasoning\. Experiments demonstrate that this method not only significantly improves the accuracy and economy of diagnosis on standard medical exam datasets but also exhibits excellent generalization and robustness on real\-world MIMIC\-IV clinical data, providing a feasible path for the interpretability of medical AI\. Future work will focus on extending this framework to multi\-modal data fusion and larger\-scale clinical deployment validation\.

## Limitations

Despite the excellent performance ofGraphDxin experiments, there are still some limitations: \(1\)Graph Construction Depends on Base Model Capability: The quality of MDKG is limited by the medical knowledge reserve of the LLM used for graph construction \(DeepSeek\-V3 in this paper\)\. If the base model has knowledge blind spots, the graph may miss key nodes or edges\. \(2\)Limited Multi\-modal Processing Capability: The current framework mainly processes textual information\. The understanding of medical imaging \(CT/MRI\) and waveform data \(ECG\) still relies on the text descriptions from LLMs, and end\-to\-end pixel\-level feature extraction has not yet been achieved\. \(3\)Inference Speed: Due to the introduction of explicit evidence scoring and utility calculation, the single\-step decision latency ofGraphDxis slightly higher than that of pure end\-to\-end LLMs\. Future work needs to further optimize the computational efficiency of the inference engine\. \(4\)Simulation Gap: While our simulator is designed to be realistic, simulated patients may exhibit more consistent logic than real patients, who might provide vague or misleading descriptions\. \(5\)LLM\-based Evaluation Bias: Our simulator, judge, and cost estimator are LLM\-based components and may inherit biases \(e\.g\., stylistic preferences or calibration drift\)\. While we mitigate this via a fixed evaluation protocol and human validation \(Section[4](https://arxiv.org/html/2607.15280#S4)\), future work should incorporate multi\-judge ensembles and real\-world clinical evaluation when feasible\.

## Ethics Statement

This research involves the development of an automated medical diagnosis system\. We emphasize thatGraphDxis intended for research and educational simulation purposes only and must not be used for direct clinical decision\-making without human oversight\. The datasets used \(MedQA and MIMIC\-IV\) are de\-identified public datasets, ensuring patient privacy\. While the automated graph construction reduces manual effort, it may inherit biases or outdated knowledge from the base LLM; therefore, any deployment in real\-world settings requires rigorous human\-in\-the\-loop verification\. Furthermore, while our system optimizes for cost\-efficiency, we acknowledge the ethical trade\-off between reducing costs and the potential risk of missing necessary tests, which warrants further investigation\.

## References

- S\. Anuyah, M\. M\. Kaushik, S\. R\. K\. R\. Dwarampudi, R\. Shiradkar, A\. Durresi, and S\. Chakraborty \(2025\)Automated knowledge graph construction using large language models and sentence complexity modelling\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 15526–15550\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.783/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.783),ISBN 979\-8\-89176\-332\-6Cited by:[§1](https://arxiv.org/html/2607.15280#S1.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.15280#S2.p3.1)\.
- AutoKG: efficient automated knowledge graph generation for language models\.External Links:2311\.14740,[Link](https://arxiv.org/abs/2311.14740)Cited by:[§1](https://arxiv.org/html/2607.15280#S1.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2607.15280#S2.T1.5.3.5.1.2.1.2.1),[§2](https://arxiv.org/html/2607.15280#S2.p3.1)\.
- Y\. Gao, R\. Li, E\. Croxford, J\. Caskey, B\. Patterson, M\. Churpek, T\. Miller, D\. Dligach, and M\. Afshar \(2025\)Leveraging medical knowledge graphs into large language models for diagnosis prediction: design and application study\.JMIR AI4,pp\. e58670\.External Links:[Link](https://ai.jmir.org/2025/1/e58670),[Document](https://dx.doi.org/10.2196/58670)Cited by:[Table 1](https://arxiv.org/html/2607.15280#S2.T1.5.3.3.2.2.1.2.1),[§2](https://arxiv.org/html/2607.15280#S2.p4.1)\.
- Z\. Jia, M\. Jia, J\. Duan, and J\. Wang \(2025\)DDO: dual\-decision optimization for llm\-based medical consultation via multi\-agent collaboration\.External Links:2505\.18630,[Link](https://arxiv.org/abs/2505.18630)Cited by:[§D\.4](https://arxiv.org/html/2607.15280#A4.SS4.p1.2),[§1](https://arxiv.org/html/2607.15280#S1.p3.1),[§2](https://arxiv.org/html/2607.15280#S2.p2.1)\.
- A\. E\. W\. Johnson, L\. Bulgarelli, L\. Shen, A\. Gayles, A\. Shammout, S\. Horng, T\. J\. Pollard, S\. Hao, B\. Moody, B\. Gow, L\. H\. Lehman, L\. A\. Celi, and R\. G\. Mark \(2023\)MIMIC\-IV, a freely accessible electronic health record dataset\.Scientific Data10\(1\),pp\. 1\.External Links:ISSN 2052\-4463,[Document](https://dx.doi.org/10.1038/s41597-022-01899-x)Cited by:[§D\.2](https://arxiv.org/html/2607.15280#A4.SS2.p1.1)\.
- H\. Nori, M\. Daswani, C\. Kelly, S\. Lundberg, M\. T\. Ribeiro, M\. Wilson, X\. Liu, V\. Sounderajah, J\. Carlson, M\. P\. Lungren, B\. Gross, P\. Hames, M\. Suleyman, D\. King, and E\. Horvitz \(2025\)Sequential diagnosis with language models\.External Links:2506\.22405,[Link](https://arxiv.org/abs/2506.22405)Cited by:[2nd item](https://arxiv.org/html/2607.15280#A4.I1.i2.p1.1.1),[§D\.1](https://arxiv.org/html/2607.15280#A4.SS1.p1.1),[§1](https://arxiv.org/html/2607.15280#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.15280#S1.p3.1),[Table 1](https://arxiv.org/html/2607.15280#S2.T1.4.2.2.2.2.1.2.1),[§2](https://arxiv.org/html/2607.15280#S2.p2.1),[§4](https://arxiv.org/html/2607.15280#S4.SS0.SSS0.Px1.p1.1),[§4\.1\.1](https://arxiv.org/html/2607.15280#S4.SS1.SSS1.Px1.p1.2)\.
- H\. Nori, N\. King, S\. M\. McKinney, D\. Carignan, and E\. Horvitz \(2023\)Capabilities of gpt\-4 on medical challenge problems\.External Links:2303\.13375,[Link](https://arxiv.org/abs/2303.13375)Cited by:[§1](https://arxiv.org/html/2607.15280#S1.p1.1)\.
- P\. Qiu, C\. Wu, J\. Liu, Q\. Zheng, Y\. Liao, H\. Wang, Y\. Yue, Q\. Fan, S\. Zhen, J\. Wang, J\. Gu, Y\. Wang, Y\. Zhang, and W\. Xie \(2025\)Evolving diagnostic agents in a virtual clinical environment\.External Links:2510\.24654,[Link](https://arxiv.org/abs/2510.24654)Cited by:[§D\.4](https://arxiv.org/html/2607.15280#A4.SS4.p1.2),[§2](https://arxiv.org/html/2607.15280#S2.p2.1)\.
- A\. Sarabadani, M\. A\. Shamami, H\. Sadeghsalehi, B\. Asadi, and S\. Hesaraki \(2025\)DKG\-llm : a framework for medical diagnosis and personalized treatment recommendations via dynamic knowledge graph and large language model integration\.External Links:2508\.06186,[Link](https://arxiv.org/abs/2508.06186)Cited by:[§2](https://arxiv.org/html/2607.15280#S2.p3.1)\.
- S\. Schmidgall, R\. Ziaei, C\. Harris, E\. Reis, J\. Jopling, and M\. Moor \(2025\)AgentClinic: a multimodal agent benchmark to evaluate ai in simulated clinical environments\.External Links:2405\.07960,[Link](https://arxiv.org/abs/2405.07960)Cited by:[§D\.1](https://arxiv.org/html/2607.15280#A4.SS1.p1.1),[§D\.2](https://arxiv.org/html/2607.15280#A4.SS2.p1.1),[§2](https://arxiv.org/html/2607.15280#S2.p2.1)\.
- K\. Singhal, S\. Azizi, T\. Tu, S\. S\. Mahdavi, J\. Wei, H\. W\. Chung, N\. Scales, A\. Tanwani, H\. Cole\-Lewis, S\. Pfohl, P\. Payne, M\. Seneviratne, P\. Gamble, C\. Kelly, A\. Babiker, N\. Schärli, A\. Chowdhery, P\. Mansfield, D\. Demner\-Fushman, B\. Agüera y Arcas, D\. Webster, G\. S\. Corrado, Y\. Matias, K\. Chou, J\. Gottweis, N\. Tomasev, Y\. Liu, A\. Rajkomar, J\. Barral, C\. Semturs, A\. Karthikesalingam, and V\. Natarajan \(2023\)Large language models encode clinical knowledge\.Nature620\(7972\),pp\. 172–180\.External Links:ISSN 1476\-4687,[Document](https://dx.doi.org/10.1038/s41586-023-06291-2)Cited by:[§1](https://arxiv.org/html/2607.15280#S1.p1.1),[Table 1](https://arxiv.org/html/2607.15280#S2.T1.3.1.1.2.2.1.2.1)\.

## Appendix APrompts for Automated Graph Construction

We provide the key system prompts used in the MDKG construction pipeline\. These prompts are designed to guide the LLM in extracting structured medical knowledge from its internal parameters\.

### A\.1Disease Knowledge Extraction

This prompt instructs the LLM to extract key diagnostic features \(symptoms, signs, risk factors\) for a given disease and estimate their typicality\.

System Prompt:You are a physician building a diagnostic knowledge graph\.Input: ONE disease name \(and optional reference text\)\. Output: ONE JSON object with: \- "disease": canonical name of this disease\. \- "features": an array of feature objects: \- "name": short, canonical, self\-explanatory term\. No extra adjectives, no explanations\. E\.g\. "fever", "chest pain", "elevated troponin", "chest X\-ray consolidation"\. \- "category": one of: "symptom", "test\_result", "risk\_factor", "other"\. \- "typicality": one of "\+\+", "\+", "\-", "–", meaning P\(F\|D\): \* "\+\+": almost all patients with this disease have this feature \(P\(F\|D\)≈\\approx1\)\. Missing it makes the disease very atypical\. \* "\+": often present in this disease \(P\(F\|D\) clearly higher than baseline\)\. \* "\-": often absent in this disease \(P\(F\|D\) clearly lower than baseline\)\. \* "–": almost never present \(P\(F\|D\)≈\\approx0\)\. Seeing it strongly suggests other diseases\. Important: "typicality" means frequency in this disease, NOT severity\. \- "tests": list of test names that DIRECTLY help observe or confirm THIS FEATURE, not "all tests for this disease"\. If none, use \[\]\.Rules: \- Focus on important diagnostic features, not every trivial detail\. \- Prefer guideline/textbook\-style canonical terminology\. \- You may use your medical knowledge beyond the given text but stay consistent\.Return ONLY the JSON, no extra text\.

### A\.2Term Alignment

This prompt is used to decide whether a new term should be merged with an existing concept in the graph\.

System Prompt:You are an ontology curator for a medical knowledge graph\.Task: Given one NEW term and a list of existing candidate concepts, decide if the new term: \- is the SAME concept \(same meaning\) as exactly one candidate, or \- should be a NEW concept\.Rules: \- Treat synonyms, abbreviations, spelling variants, plural/singular, and minor wording changes as the same concept\. \- If the new term is clearly broader or narrower than all candidates in a clinically important way \(e\.g\. "lung cancer" vs "small cell lung cancer"\), treat as NEW\. \- If multiple candidates could match, choose the single best one; only use NEW when all are clearly wrong\.Output: \- ONE JSON object: \{ "decision": "<candidate\_id\>" \} or \{ "decision": "NEW" \}\. \- No other keys, no explanations\.

### A\.3Test Metadata Enrichment

This prompt generates cost and invasiveness metadata for new test nodes\.

System Prompt:You are enriching metadata for diagnostic tests\.Input: ONE test name\. Output: ONE JSON object with: \- "cost": short qualitative label of typical cost, e\.g\. "very low", "low", "moderate", "high", or "very high"\. No numeric prices\. \- "invasiveness": one of \["low", "moderate", "high"\]: \* "low" – non\-invasive, minimal risk \(e\.g\. X\-ray, blood test\)\. \* "moderate" – minimally invasive \(needle, catheter, contrast…\)\. \* "high" – clearly invasive or interventional/surgical\. \- "applicable\_population": brief description of typical use population, e\.g\. "adults with suspected acute coronary syndrome"\.Be approximate but clinically reasonable\. Return ONLY the JSON with these three keys\.

### A\.4Feature\-Test Effectiveness Inference

This prompt determines the effectiveness of a test in confirming a specific feature\.

System Prompt:You are linking features to diagnostic tests\.Task: Given ONE feature and ONE test, decide how effective the test is for confirming or excluding that FEATURE itself \(not any disease\)\.Output: JSON with one key: "effectiveness", value in \["\+\+", "\+"\]\.Meaning: \- "\+\+": The test directly measures or visualizes this feature with high reliability\. It is the main or standard way to determine whether the feature is present\. \- "\+": The test only indirectly supports or weakly relates to this feature\. It helps but is not decisive alone\.Guidelines: \- Judge the relation TEST↔\\leftrightarrowFEATURE, not TEST↔\\leftrightarrowdisease\. \- When unsure or the link is not direct, choose "\+" rather than "\+\+"\. \- Do NOT use values other than "\+\+" or "\+"\.Return ONLY: \{ "effectiveness": "\+\+" \} or \{ "effectiveness": "\+" \}\.

## Appendix BPrompts for Graph\-Augmented Agent

### B\.1Information Extraction

This prompt extracts structured observations from the patient\-doctor dialogue\.

System Prompt:You are a medical information extraction assistant with expertise in clinical terminology\.Task: Given the latest turn of conversation with a patient \(which may include answers to questions, or test results\), extract ONLY the NEW observations mentioned in THIS TURN\.CRITICAL: You MUST translate all observations into STANDARD MEDICAL TERMINOLOGY\. Do NOT use colloquial or layperson descriptions\. The extracted terms will be matched against a medical knowledge graph that uses professional clinical vocabulary\.Output a JSON object with: \{ "observations": \[ \{ "name": "…", // MUST use standard medical terms "category": "symptom" \| "test\_result" \| "risk\_factor" \| "other", "status": "present" \| "absent" \| "unknown", "source": "patient" \| "test" \| "other" \}, … \], "tests\_mentioned": \[ … \], "candidate\_diseases": \[ … \] \}Guidelines: \- ONLY include observations that are NEW or UPDATED in THIS TURN, not previous turns\. \- ALWAYS convert colloquial descriptions to standard medical terminology\. \- If the patient clearly denies a symptom \(e\.g\. "No fever"\), set status="absent"\. \- If a symptom is clearly present or strongly implied, set status="present"\. \- If it’s unclear whether the feature is present, use status="unknown"\. \- Map lab/imaging findings to category="test\_result"\.

### B\.2Agent Decision Making

This system prompt guides the final decision\-making of the agent, incorporating the graph summary\.

System Prompt:You are an expert diagnostician AI with access to an internal diagnostic knowledge graph\. The graph provides: \- relationships between diseases and features \(symptoms, test results, risk factors\) with typicality \("\+\+", "\+", "\-", "–"\), \- relationships between features and tests, with a qualitative measure of how directly the test measures the feature \("\+\+" or "\+"\), \- simple metadata about test cost and invasiveness\.You are interacting with a simulated patient to diagnose their condition\. Each turn you receive NEW information from the environment \(patient answers or test results\)\. The system may also provide you with a GRAPH SUMMARY containing: \- a list of structured observations parsed from the conversation, \- a graph\-based ranking of candidate diseases, \- graph\-based suggestions of useful follow\-up questions and tests\.IMPORTANT: \- The knowledge graph may be incomplete or imperfect\. Its suggestions are HINTS, not truth\. \- You must combine the graph suggestions with your own clinical reasoning and the full history\. \- Do NOT blindly follow the graph if it conflicts with clinical reasoning\. \- You have a maximum of \{max\_turns\} turns; try to be efficient and accurate\.Available actions: 1\. "ask" – Ask the patient a follow\-up question to gather more information\. 2\. "test" – Order a medical test\. 3\. "diagnose" – Provide a final diagnosis if you think you have enough information\.You MUST respond in JSON with two keys: "action\_type" and "action\_content"\.

## Appendix CAlgorithms

We provide the detailed pseudocode for the two core algorithms ofGraphDx\.

Input:Disease List

𝒟l​i​s​t\\mathcal\{D\}\_\{list\}, LLM

ℳ\\mathcal\{M\}
Output:MDKG

𝒢\\mathcal\{G\}
1Initialize empty graph

𝒢\\mathcal\{G\};

//Stage 1: Concurrent Disease Knowledge Extraction

2foreach*d∈𝒟l​i​s​td\\in\\mathcal\{D\}\_\{list\}\(Concurrent\)*do

\(Fd,𝒯m​a​p\)←ℳ\.extract\_knowledge​\(d\)\(F\_\{d\},\\mathcal\{T\}\_\{map\}\)\\leftarrow\\mathcal\{M\}\.\\text\{extract\\\_knowledge\}\(d\)//Extract features & test map

3

Pd←ℳ\.estimate\_typicality​\(Fd,d\)P\_\{d\}\\leftarrow\\mathcal\{M\}\.\\text\{estimate\\\_typicality\}\(F\_\{d\},d\);

4

5end foreach

//Stage 2: Sequential Entity Alignment & Graph Construction

6foreach*d∈𝒟l​i​s​td\\in\\mathcal\{D\}\_\{list\}*do

7

vd←HybridAlign\(d,𝒢\.𝒱\)v\_\{d\}\\leftarrow\\text\{HybridAlign\}\(d,\\mathcal\{G\}\.\\mathcal\{V\}\);

8if*vd∈𝒢\.𝒱fv\_\{d\}\\in\\mathcal\{G\}\.\\mathcal\{V\}\_\{f\}*then

UpgradeNode​\(vd\)\\text\{UpgradeNode\}\(v\_\{d\}\)//Promote Feature to Disease

9

10end if

11foreach*f∈Fdf\\in F\_\{d\}*do

vf←HybridAlign\(f,𝒢\.𝒱f\)v\_\{f\}\\leftarrow\\text\{HybridAlign\}\(f,\\mathcal\{G\}\.\\mathcal\{V\}\_\{f\}\)//Hybrid Alignment

12

𝒢\.add\_edge​\(vd,vf,weight=Pd​\[f\]\)\\mathcal\{G\}\.\\text\{add\\\_edge\}\(v\_\{d\},v\_\{f\},\\text\{weight\}=P\_\{d\}\[f\]\);

13foreach*τ∈𝒯m​a​p​\[f\]\\tau\\in\\mathcal\{T\}\_\{map\}\[f\]*do

vτ←HybridAlign\(τ,𝒢\.𝒱t\)v\_\{\\tau\}\\leftarrow\\text\{HybridAlign\}\(\\tau,\\mathcal\{G\}\.\\mathcal\{V\}\_\{t\}\)//Test Alignment

14

𝒢\.add\_edge​\(vf,vτ\)\\mathcal\{G\}\.\\text\{add\\\_edge\}\(v\_\{f\},v\_\{\\tau\}\);

15

16end foreach

17

18end foreach

19

20end foreach

//Stage 3: Metadata Enrichment & Edge Inference

21foreach*τ∈𝒢\.𝒱t\\tau\\in\\mathcal\{G\}\.\\mathcal\{V\}\_\{t\}\(Concurrent\)*do

attrτ←ℳ\.enrich\_metadata​\(τ\)\\text\{attr\}\_\{\\tau\}\\leftarrow\\mathcal\{M\}\.\\text\{enrich\\\_metadata\}\(\\tau\)//Cost/Invasiveness

22

𝒢\.update\_node​\(τ,attrτ\)\\mathcal\{G\}\.\\text\{update\\\_node\}\(\\tau,\\text\{attr\}\_\{\\tau\}\);

23

24end foreach

Algorithm 1Automated MDKG Construction PipelineInput:Dialogue History

HtH\_\{t\}, MDKG

𝒢\\mathcal\{G\}
Output:Action

ata\_\{t\}
//1\. Info Extraction & State Tracking

1

Ot←ExtractObservations​\(Ht\)O\_\{t\}\\leftarrow\\text\{ExtractObservations\}\(H\_\{t\}\);

UpdateState​\(𝒢,Ot\)\\text\{UpdateState\}\(\\mathcal\{G\},O\_\{t\}\)//Update Confirmed/Excluded Features

//2\. Evidence Scoring \(Heuristic\)

2foreach*d∈𝒢\.𝒱dd\\in\\mathcal\{G\}\.\\mathcal\{V\}\_\{d\}*do

3

S​\(d\)←∑f∈Ot\+w​\(d,f\)−λ⋅∑f∈Ot−w​\(d,f\)S\(d\)\\leftarrow\\sum\_\{f\\in O\_\{t\}^\{\+\}\}w\(d,f\)\-\\lambda\\cdot\\sum\_\{f\\in O\_\{t\}^\{\-\}\}w\(d,f\);

4

5end foreach

6

Dt​o​p←TopK​\(S\)D\_\{top\}\\leftarrow\\text\{TopK\}\(S\);

//3\. Utility\-Based Action Suggestion

7

As​u​g​g​e​s​t←∅A\_\{suggest\}\\leftarrow\\emptyset;

8

Tc​a​n​d←\{τ∣∃f∈Neighbors​\(Dt​o​p\),\(f,τ\)∈Et​e​s​t\}∖Th​i​s​t​o​r​yT\_\{cand\}\\leftarrow\\\{\\tau\\mid\\exists f\\in\\text\{Neighbors\}\(D\_\{top\}\),\(f,\\tau\)\\in E\_\{test\}\\\}\\setminus T\_\{history\};

9foreach*τ∈Tc​a​n​d\\tau\\in T\_\{cand\}*do

10

Vt​o​t​a​l←∑f∈Verifies​\(τ\)V​\(f\)⋅η​\(f,τ\)V\_\{total\}\\leftarrow\\sum\_\{f\\in\\text\{Verifies\}\(\\tau\)\}V\(f\)\\cdot\\eta\(f,\\tau\);

11

Utility​\(τ\)←Vt​o​t​a​l/\(1\+Cost​\(τ\)⋅Inv​\(τ\)\)\\text\{Utility\}\(\\tau\)\\leftarrow V\_\{total\}/\(1\+\\text\{Cost\}\(\\tau\)\\cdot\\text\{Inv\}\(\\tau\)\);

12

As​u​g​g​e​s​t\.add​\(τ,Utility​\(τ\)\)A\_\{suggest\}\.\\text\{add\}\(\\tau,\\text\{Utility\}\(\\tau\)\);

13

14end foreach

//4\. LLM Decision Making

15

Ss​u​m​m​a​r​y←FormatSummary​\(Ot,Dt​o​p,As​u​g​g​e​s​t\)S\_\{summary\}\\leftarrow\\text\{FormatSummary\}\(O\_\{t\},D\_\{top\},A\_\{suggest\}\);

16

at←LLM\.decide​\(Ht,Ss​u​m​m​a​r​y\)a\_\{t\}\\leftarrow\\text\{LLM\}\.\\text\{decide\}\(H\_\{t\},S\_\{summary\}\);

17return

ata\_\{t\};

Algorithm 2Knowledge\-Enhanced Diagnostic Loop
## Appendix DDetailed Experimental Setup

### D\.1Environment Setup

We developedClinicSim, a modular simulation environment designed to evaluate sequential diagnostic capabilities\. It integrates the dynamic interaction mechanism ofAgentClinicSchmidgallet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib10)\)with the cost\-sensitive evaluation framework ofSDBenchNoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\)\. Specifically,ClinicSimconsists of two core components: \(1\)Patient Actor: An LLM\-driven patient agent that conducts realistic multi\-turn natural language dialogues based on a complete clinical profile\. It is instructed to be "passive," revealing information only when explicitly asked, to mimic the information asymmetry in real consultations; \(2\)Test Result Generator: An independent generation module responsible for returning corresponding medical test results \(e\.g\., blood metrics, imaging descriptions\) based on doctor orders\. To ensure consistency, it retrieves results directly from the ground truth profile; if a specific value is missing, it returns a "normal" or "unknown" status consistent with the patient’s overall condition\. The maximum number of dialogue turns is set to 20\. This design allows us to track the economic cost of each step in real\-time, enabling a comprehensive evaluation of agent performance in the "Accuracy\-Cost\-Efficiency" space\. The source code forGraphDxand theClinicSimenvironment is available at[https://anonymous\.4open\.science/r/GraphDx\-BB8B](https://anonymous.4open.science/r/GraphDx-BB8B)\.

### D\.2Datasets

We utilized two datasets for evaluation: \(1\)MedQA Dataset:Derived from themedqa\_extendeddatasetSchmidgallet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib10)\), covering diverse chief complaints, medical histories, and personality traits, totaling 200 test cases\. \(2\)MIMIC\-IV Dataset:To verify robustness on real\-world data, we constructed 200 scenarios from the MIMIC\-IV clinical databaseJohnsonet al\.\([2023](https://arxiv.org/html/2607.15280#bib.bib15)\)following the AgentClinicSchmidgallet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib10)\)methodology\. These cases contain real clinical noise, incomplete information, and complex medical histories, posing a greater challenge to the agent’s information extraction and reasoning capabilities\.

### D\.3Parameter Settings

In our experiments, we set the typicality weights asw\+\+=4\.0w\_\{\+\+\}=4\.0,w\+=1\.5w\_\{\+\}=1\.5,w−=−1\.5w\_\{\-\}=\-1\.5, andw−−=−4\.0w\_\{\-\-\}=\-4\.0\. The penalty coefficientλ\\lambdawas set to 0\.6\. For the utility calculation, the verification effectiveness weights were set towe​f​f∈\{1\.0,0\.5\}w\_\{eff\}\\in\\\{1\.0,0\.5\\\}\. The cost levelsC​\(t\)C\(t\)were mapped to integers\{1,2,3,4,5\}\\\{1,2,3,4,5\\\}representing "very low" to "very high" costs, and the invasiveness multipliersMi​n​v​\(t\)M\_\{inv\}\(t\)were set to\{1\.0,1\.5,2\.0\}\\\{1\.0,1\.5,2\.0\\\}for low, moderate, and high invasiveness, respectively\. The semantic retrieval thresholdτ\\tauwas set to 0\.8\.

### D\.4Baseline Settings

To verify the generality of our method, we evaluated it on three advanced Large Language Models: \(1\)DeepSeek\-V3; \(2\)Kimi\-k2; \(3\)Llama\-3\.3\. For each model, we compared three settings:

- •Standard LLM \(Baseline\): Standard agent using direct prompting for inquiry and diagnosis\.
- •MAI\-DxONoriet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib7)\): The SOTA architecture proposed in SDBench, employing multi\-agent collaboration \(Dr\. Test\-Chooser, Dr\. Challenger, etc\.\) for diagnostic orchestration\.
- •GraphDx\(Ours\): The proposed graph\-augmented knowledge\-enhanced agent\.

We note that several related sequential diagnosis frameworks \(e\.g\., DDOJiaet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib6)\), ACTMEDestévez2025timelyclinicaldiagnosisactive, and DiagGymQiuet al\.\([2025](https://arxiv.org/html/2607.15280#bib.bib8)\)\) are highly relevant in motivation, but are not included as baselines because they rely on closed\-set action spaces \(predefined symptom/test lists\) incompatible with our open\-ended natural language dialogue setting\. To ensure a fair comparison, we also enforce a controlled evaluation protocol where theClinicSimenvironment \(Patient Actor, Test Result Generator, and Judge\) remains fixed across all methods, isolating the impact of the agent design\.

### D\.5Evaluation Metrics

We employ three core metrics to evaluate diagnostic performance: \(1\)Diagnostic Score \(0\-10\): Scored by Llama\-3\.3 as a judge model based on the clinical equivalence between the agent’s final diagnosis and the ground truth \(10: Optimal; 5: Incomplete but safe; 0: Incorrect and misleading\)\. \(2\)Cost \($\): The sum of estimated costs for all medical tests ordered during the diagnosis\. To ensure fair comparison, costs are estimated in USD by an independent LLM evaluator using a standardized price book prompt, rather than using the agent’s internal optimization scores\. \(3\)Turns: The number of dialogue turns between the doctor and patient, reflecting diagnostic efficiency\. Note that for all metrics, we report theMean±\\pmStandard Deviationacross3 independent runsfor each scenario\. The standard deviation measures the stability of the agent’s performance, with randomness stemming from the LLM’s decoding temperature\.

## Appendix EHyperparameters and Constants

We list the specific numerical values used for the qualitative attributes in our system\.

Table 5:Typicality Weights used in Evidence ScoringTypicality LabelSymbolWeight ValueStrongly Positive\+\+4\.0Positive\+1\.5Negative\-\-1\.5Strongly Negative–\-4\.0Table 6:Cost Scores and Invasiveness MultipliersCost LabelScoreInvasivenessMultiplierVery Low1\.0Low1\.0Low2\.0Moderate1\.5Moderate3\.0High2\.0High4\.0Very High5\.0
## Appendix FBaseline Agent Prompts

To ensure fair comparison and reproducibility, we provide the system prompts used for the Baseline Agent\. The Baseline Agent uses a standard Chain\-of\-Thought \(CoT\) approach without access to the external knowledge graph\.

System Prompt:You are an expert diagnostician AI\. You are interacting with a patient to diagnose their condition\. You will receive information in turns\. Each turn, you will get new information, which could be the patient’s response to your questions or the results of a medical test you ordered\. Based on the information you have, you must decide on the next action to take\. You have three possible actions: 1\. \*\*ask\*\*: Ask the patient a follow\-up question to gather more information\. 2\. \*\*test\*\*: Order a medical test to get specific data\. 3\. \*\*diagnose\*\*: If you have enough information, provide a final diagnosis\.You must respond in JSON format with two keys: \- ‘"action\_type"‘: One of ‘"ask"‘, ‘"test"‘, or ‘"diagnose"‘\. \- ‘"action\_content"‘: The specific question, test name, or diagnosis\.For example: If you want to ask a question: ‘\{"action\_type": "ask", "action\_content": "Have you experienced any fever?"\}‘If you want to order a test: ‘\{"action\_type": "test", "action\_content": "Complete Blood Count"\}‘If you are ready to diagnose: ‘\{"action\_type": "diagnose", "action\_content": "Common Cold"\}‘You have a maximum of \{max\_turns\} turns to diagnose the patient\. Strive to be efficient and accurate\.

## Appendix GSimulation Environment Details

We use a modular simulation environmentClinicSimto evaluate the agents\. The environment consists of a Patient Actor and a Test Result Generator, both driven by LLMs\.

### G\.1Patient Actor Prompt

The Patient Actor simulates a real patient based on a detailed clinical profile\. It is instructed to reveal information only when asked, mimicking the information asymmetry in real consultations\.

System Prompt:You are role\-playing as the PATIENT \(or the accompanying family member IF the patient are not capable of making decisions\) described below\. A doctor is examining you \(or your dependent\)\.Rules: \- Your profile \(or your dependent’s\) contains very detailed medical information about you \(or your dependent\) but NEVER directly reveal it unless asked by the doctor\. \- NEVER directly reveal the true diagnosis to the doctor\. \- Answer the doctor’s questions naturally and unprofessionally, as a real patient would\. \- ONLY share symptoms/history based on your profile when asked\. \- If unsure, say "I don’t know" or give a plausible answer\.\{profile\}

### G\.2Test Result Generator Prompt

The Test Result Generator provides realistic test results based on the patient’s ground truth data\.

System Prompt:You are a medical test result generator\. Given a test name, provide a realistic result for that test based on the patient’s profile\.Rules: \- Return realistic values CONSISTENT with the patient’s condition\. \- Return EXACTLY the required test result, NOT all results from the profile\. \- If the test is not in the profile, generate the most CONSISTENT result based on the patient’s condition\. \- Format: brief, factual lab report style\. \- NO diagnosis, NO interpretation, NO conversation\.\{profile\}

### G\.3Evaluation Prompts

To ensure consistent and scalable evaluation, we utilize LLM\-based judges for both diagnostic accuracy scoring and cost estimation\.

#### G\.3\.1Diagnostic Accuracy Evaluator

We employ an LLM\-based evaluator to grade the diagnostic outcome against the ground truth\.

System Prompt:You are an expert medical evaluator\. Compare the agent’s diagnosis with the ground truth diagnosis\. Provide a score from 0 to 10\. Use this scale:•10 \(Optimal\): The agent’s final diagnosis is clinically equivalent to the ground truth diagnosis\.•5 \(Acceptable\): The agent’s diagnosis is incorrect/incomplete, BUT it is safe and does not mislead future treatment \(e\.g\., a correct referral, or a safe differential\)\.•0 \(Harmful\): The agent’s diagnosis is incorrect AND misleading, potentially causing harm or treatment delay\.Above descriptions are anchor points; intermediate scores \(1\-4, 6\-9\) should reflect gradations in clinical relevance and safety\.You MUST output a JSON object with ONLY the "score" field\. No other fields or text allowed\.Example output: \{“score”: 8\}Full profile of the case: \{profile\_text\}Agent’s Diagnosis: \{agent\_diagnosis\}

#### G\.3\.2Cost Estimation Methodology & Prompt

To evaluate the economic efficiency of diagnostic agents, we calculate the financial cost of each diagnostic session\. Since real\-world pricing varies continuously, we employ a Large Language Model \(specificallyLlama\-3\.3\-70b\-instruct\) acting as a "Medical Billing Expert" to estimate the cost of each ordered test\. The model is prompted to provide realistic US\-based pricing \(in USD\) for each specific test name\.

System Prompt:You are a medical billing expert\. For each of the following medical tests, provide an estimated cost in USD\. Use realistic pricing based on typical costs in the United States healthcare system\.CRITICAL RULES:1\.You MUST present the output as a valid JSON object where keys are the test names and values are the estimated costs \(as numbers\)\.2\.Do not include any other text or explanations\.3\.ONLY include tests that are explicitly listed below\. Do NOT add any tests that are not in the list\.Example output when tests are ordered: \{ “Complete Blood Count \(CBC\)”: 50, “Basic Metabolic Panel \(BMP\)”: 75 \}Tests Ordered: \{ordered\_tests\}

## Appendix HAdditional Experimental Analysis

### H\.1MDKG Statistics

Before evaluating the diagnostic performance, we assessed the quality of the constructed MDKG through a rigorous manual verification process\. We randomly sampled 243 triples \(disease\-feature associations\) from the generated graph and asked medical professionals to classify them into three categories:Correct\(medically accurate and precise\),Plausible\(reasonable but potentially vague or context\-dependent\), andIncorrect\(medically false\)\.

The evaluation results yielded 186 \(76\.5%\)Correcttriples, 37 \(15\.2%\)Plausibletriples, and 20 \(8\.2%\)Incorrecttriples\. The overall validity rate \(Correct \+ Plausible\) reached 91\.8%, demonstrating that our automated pipeline can reliably extract high\-quality medical knowledge\. The small fraction of incorrect triples mostly involved over\-generalized associations \(e\.g\., linking generic symptoms to specific rare diseases\), which are often filtered out during the subsequent evidence scoring phase\.

Figure[4](https://arxiv.org/html/2607.15280#A8.F4)shows the distribution of key graph attributes\. Figure[4\(a\)](https://arxiv.org/html/2607.15280#A8.F4.sf1)displays the distribution of feature typicality \(P​\(f\|d\)P\(f\|d\)\), presenting a reasonable skewed distribution, indicating that the graph can distinguish between "hallmark features" \(high typicality\) and "common features\." Figure[4\(b\)](https://arxiv.org/html/2607.15280#A8.F4.sf2)shows the distribution of test costs, covering a wide range from low\-cost \(e\.g\., CBC\) to high\-cost \(e\.g\., MRI\) tests, providing a basis for cost\-sensitive planning\. Figure[4\(c\)](https://arxiv.org/html/2607.15280#A8.F4.sf3)illustrates the degree distribution of disease nodes \(i\.e\., number of features per disease\), with an average of 15\.7 features per disease, providing sufficient evidence for differential diagnosis\.

![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/graph_typicality_dist.png)\(a\)Feature Typicality Distribution
![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/graph_cost_dist.png)\(b\)Test Cost Distribution
![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/graph_degree_dist.png)\(c\)Disease\-Feature Degree Dist\.

Figure 4:Statistical distribution of key attributes in MDKG\.
### H\.2Parameter Sensitivity Analysis

To assess the robustness of our evidence scoring mechanism while avoiding the prohibitive computational cost of re\-running full agent simulations, we conducted an offline sensitivity analysis on the Llama\-3\.3 interaction logs\. We re\-evaluated the disease ranking logic by varying two key hyperparameters: the weight of strong positive evidence \(w\+\+w\_\{\+\+\}\) and the penalty coefficient for missing expected features \(λ\\lambda\)\.

Figure[5](https://arxiv.org/html/2607.15280#A8.F5)illustrates the Top\-1 accuracy of the ground truth disease across a grid of parameter settings\. We observe that:

- •Robustness to Weight Variations:The system maintains stable performance \(Top\-1 accuracy≈60%\\approx 60\\%, Top\-5 accuracy≈88%\\approx 88\\%\) across a wide range ofw\+\+w\_\{\+\+\}values \(2\.0–5\.0\)\. This indicates that the ranking is primarily driven by the structural correctness of the graph \(presence of correct edges\) rather than fine\-tuned parameters\.
- •Impact of Absence Penalty:A lower absence penalty \(λ∈\[0\.0,0\.3\]\\lambda\\in\[0\.0,0\.3\]\) yields slightly better results than higher penalties\. This suggests that in natural language dialogue, "missing" features are often simply unmentioned by the patient rather than clinically absent, so the system should be cautious about penalizing them too heavily\.

![Refer to caption](https://arxiv.org/html/2607.15280v1/x1.png)Figure 5:Sensitivity of Top\-1 Accuracy to variations in Strong Evidence Weight \(w\+\+w\_\{\+\+\}\) and Absence Penalty \(λ\\lambda\)\. The system exhibits a stable performance plateau, demonstrating robustness\.
### H\.3Case Study

To deeply understand the decision\-making advantages ofGraphDxin different clinical contexts, we selected three representative cases from the MedQA\-Extended dataset for detailed comparative analysis\. These cases reveal typical failure modes of baseline models inrare disease reasoning,anatomical logic, andcost\-effective diagnosis, whileGraphDxsuccessfully avoids these pitfalls through structured knowledge\.

##### Case 1: Capturing Subtle Clues in Rare Diseases \(Scenario 50\)

As shown in Figure[6](https://arxiv.org/html/2607.15280#A8.F6),Case Background:A 16\-year\-old female presented with primary amenorrhea and delayed breast development\. Notably, her history included "fractures from minor falls" and she was "tall for her age"\.

- •Baseline:Focused solely on amenorrhea and delayed puberty, diagnosing "Turner Syndrome"\. It failed to recognize that Turner Syndrome typically presents withshortstature, contradicting the patient’s "tall" description\. It also ignored the fracture history\.
- •GraphDx:The graph reasoning engine successfully linked "fractures" \(osteoporosis\) and "tall stature" \(delayed epiphyseal closure\) with "amenorrhea"\. It identified the rare etiology"Aromatase Deficiency"\(inability to synthesize estrogen from androgens\) and confirmed it via hormone panel and karyotype, achieving a precise diagnosis\.

##### Case 2: Strict Anatomical and Functional Constraints \(Scenario 14\)

Case Background:A patient reported a swollen right ring finger after a football injury, stating, "I can’t bend the tip of my finger at all when I try to make a fist\."

- •Baseline:Confused the functional description, diagnosing "Mallet Finger" \(an extensor tendon injury characterized by inability toextendthe tip\)\.
- •GraphDx:The MDKG explicitly encodes the functional logic of musculoskeletal anatomy\. It correctly interpreted the inability toflexthe distal joint as a rupture of the Flexor Digitorum Profundus tendon, correctly diagnosing"Jersey Finger"\.

##### Case 3: Cost\-Effective Decision Making \(Scenario 66\)

Case Background:A 1\-month\-old preterm infant presented with "apnea episodes" during sleep and "pale skin"\.

- •Baseline:Reacted defensively to the high\-risk symptom "apnea" by ordering an expensivePolysomnography \($2500\), diagnosing "Apnea of Prematurity" without investigating the root cause\.
- •GraphDx:Integrated the "pale skin" clue with "apnea" in the evidence\-weighted graph, hypothesizing anemia as a potential cause\. It prioritized a low\-costComplete Blood Count \($50\), revealing low hemoglobin \(8\.2 g/dL\), and correctly diagnosed"Anemia of Prematurity"\. This demonstrates how utility\-based planning avoids unnecessary expensive testing\.

![Refer to caption](https://arxiv.org/html/2607.15280v1/assets/figures/case_study.png)Figure 6:Typical Case Analysis \(Scenario 50: Primary Amenorrhea\)\. The Baseline agent \(left\) misdiagnosedTurner Syndromeby focusing on amenorrhea while ignoring the contradictory evidence oftall statureandfractures\. In contrast,GraphDx\(right\) successfully linked these cues toAromatase Deficiencyvia the structured graph, demonstrating the navigational role of structured knowledge\.