🤖 AI

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

GraphDx is a cost-aware, knowledge-enhanced multi-agent framework that leverages automated Medical Diagnosis Knowledge Graphs and collaborative agents to significantly improve diagnostic accuracy while reducing testing costs compared to existing LLM approaches.

Original authors: Shaoting Tan, Ning Liu, Yuntao Du, Shuyue Wei, Wu Shuai, Qian Li, Yanyu Xu, Wei Zhang, Lizhen Cui, Haitao Yuan

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Shaoting Tan, Ning Liu, Yuntao Du, Shuyue Wei, Wu Shuai, Qian Li, Yanyu Xu, Wei Zhang, Lizhen Cui, Haitao Yuan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complicated mystery, like figuring out why a car won't start. You have a super-smart detective who has read every single manual ever written about cars. This detective knows the names of every part, the sound of every engine, and the history of every model. But here's the catch: this detective is a bit scatterbrained when it comes to the actual process of solving the mystery. If you ask them to fix the car, they might say, "I know everything about cars! Let's just take the engine out, replace the transmission, swap the tires, and paint the whole thing red just to be safe!" They have all the knowledge, but they lack a plan. They don't know how to save time or money, and they often jump to expensive conclusions without checking the simple clues first.

This is exactly the problem scientists are facing with Artificial Intelligence (AI) in medicine. We have created "Large Language Models" (LLMs), which are like that super-smart detective. They have read millions of medical textbooks and know a huge amount about diseases. But when doctors use them to diagnose patients, the AI often acts like that scatterbrained detective. It might suggest ordering every single test in the hospital just to be sure, ignoring the fact that some tests are expensive, painful, or unnecessary. This is called the "knowledge-reasoning gap." The AI knows the facts, but it struggles to use them logically to make a smart, cost-effective decision. This paper, GraphDx, tries to fix that by giving the detective a map and a strict set of rules to follow, turning a chaotic brainstorming session into a precise, step-by-step investigation.

The Paper's Big Idea: Giving the AI a Map

The authors of this paper, a team from several universities, realized that just feeding an AI more medical books wasn't enough. The AI needed a way to organize that information so it could reason through a patient's symptoms step-by-step, balancing the need for an accurate diagnosis with the cost of medical tests. They built a new system called GraphDx.

Think of the current AI approach as trying to find a needle in a haystack by guessing. You ask the AI, "What could this be?" and it might guess "Hay fever," "A broken leg," or "The flu," and then suggest buying a ticket to the moon just in case. GraphDx changes the game by building a Medical Diagnosis Knowledge Graph (MDKG).

Imagine this graph as a giant, interactive subway map of the human body.

The Stations are diseases (like "Flu" or "Broken Bone").
The Lines connect diseases to their symptoms (like "Fever" or "Swelling").
The Tickets are the medical tests (like "Blood Test" or "X-Ray").

But this isn't just a normal map. The authors gave this map special superpowers that existing maps don't have:

Typicality Labels: The map knows which symptoms are "Hallmark" (super common for a disease, like a fever for the flu) and which are "Rare" (very unlikely).
Cost Tags: Every test on the map has a price tag and a "pain level." The map knows that a quick blood test is cheap and easy, while a full-body CT scan is expensive and invasive.
Action-Centric Paths: The map doesn't just say "Fever happens with Flu." It says, "If you see a Fever, here is the specific test to confirm it, and here is the cost."

How GraphDx Works: The Three-Headed Detective Team

To use this map, the authors created a team of three AI agents who work together. They don't just talk; they have specific jobs.

The Perception Agent (The Listener): This agent listens to the patient. If a patient says, "My tummy hurts and I feel dizzy," this agent translates that into the language of the map. It finds the "Stomach Pain" and "Dizziness" stations on the subway map and marks them as "Present."
The Reasoning Agent (The Navigator): This is the brain of the operation. It looks at the marked stations on the map and starts calculating. It asks, "If the patient has stomach pain and dizziness, which diseases are most likely?" It uses the map's "Typicality" labels to score the diseases. Then, it looks at the "Cost Tags" to figure out the next best move. Instead of ordering a million tests, it asks, "Which single test will give us the most information for the least money?" It might say, "Let's check the blood sugar first because it's cheap and will rule out diabetes."
The Decision Agent (The Speaker): This agent takes the Navigator's plan and talks to the patient. It asks the right question or orders the right test in a natural, friendly way.

The Results: Smarter, Cheaper, and Safer

The authors tested this new system in two different worlds: a set of medical exam questions (MedQA) and a collection of real-world patient records (MIMIC-IV). They compared GraphDx against standard AI (the scatterbrained detective) and other advanced AI teams.

The results were impressive. In the simulations:

Accuracy: The standard AI got the diagnosis right about 50% to 68% of the time. GraphDx jumped that up to 79% to 93%.
Cost: The standard AI was very wasteful, often ordering expensive tests. GraphDx reduced the cost of tests by 20% to 54%. For example, on one dataset, the average cost dropped from $1,062 to $537 per case.
Efficiency: GraphDx didn't just save money; it saved time. It avoided the "defensive medicine" trap where AI orders every test just to be safe.

The paper also showed that GraphDx works even when the AI encounters a disease it hasn't seen before. Because the map is built on general rules (like "Chest Pain usually leads to an ECG"), the system could still navigate effectively even if the specific disease wasn't on the map.

What This Means (and What It Doesn't)

The authors are very clear about what they have achieved and what they haven't. They demonstrated through rigorous simulations and LLM-based evaluation that adding a structured map and a cost-aware planner helps AI make better medical decisions than just using a raw language model. They showed that GraphDx significantly outperforms existing baselines, suggesting that the structure of the reasoning process is a critical factor in improving performance, rather than relying solely on the raw intelligence or text volume of the base model.

However, they also point out some limits. This system is currently a simulation. It works in a computer environment where the "patients" are also AI acting out roles. The authors note that real patients might be vaguer, more confused, or harder to read than the simulation allows. They also admit that the map itself is built by an AI, so if the AI making the map makes a mistake, the map might be wrong.

Most importantly, the authors state that this is not a tool for doctors to use on real patients right now. It is a research tool to show how AI could work in the future. They emphasize that human doctors must always be in the loop.

In short, GraphDx suggests that if we want AI to be a good doctor, we can't just give it a library of books. We have to give it a map, a budget, and a plan. By doing so, the AI stops guessing and starts solving, saving both money and lives in the process.

Technical Summary: GraphDx

Problem Statement

Sequential diagnosis in clinical settings requires balancing diagnostic accuracy against resource costs (monetary expense, patient discomfort, time) through iterative information gathering. While Large Language Models (LLMs) have demonstrated remarkable success in static medical examinations by encoding extensive medical knowledge, they exhibit a critical knowledge-reasoning gap when applied to sequential diagnosis. Specifically, LLMs struggle to reason systematically under cost constraints. Despite possessing medical knowledge, they often resort to "defensive medicine," ordering excessive tests to compensate for reasoning uncertainty rather than leveraging discriminative features for efficient differential diagnosis. This behavior stems from the implicit, unstructured nature of LLM reasoning, which lacks explicit domain models for systematic hypothesis testing.

The paper identifies two primary challenges underlying this gap:

Diagnosis-Ready Knowledge Graph Construction: Existing knowledge graphs (e.g., UMLS) lack quantitative attributes essential for diagnosis, such as symptom typicality and test utilities. Furthermore, medical concepts often exhibit context-dependent semantics (e.g., a disease acting as a symptom in another context), requiring dynamic role modeling that static ontologies cannot provide.
Effective Multi-Agent Collaboration: Bridging neural language understanding with symbolic graph reasoning requires orchestrating observation extraction, graph grounding, evidence scoring, and response generation. Existing multi-agent approaches often rely on complex prompt-based coordination that demands strong instruction-following capabilities from base models, leading to performance degradation on less capable LLMs.

Methodology

The authors propose GraphDx, a knowledge-enhanced framework comprising two integrated components: an automated Medical Diagnosis Knowledge Graph (MDKG) construction pipeline and a collaborative multi-agent diagnostic system.

1. Automated MDKG Construction

The framework constructs a directed graph $G = (V, E, W, A)$ where nodes represent diseases, features (symptoms/signs), and tests. The construction pipeline operates in three stages without manual annotation:

Parallel Knowledge Extraction: Specialized agents extract tuples of features, their typicality, and verifying tests for each disease. To mitigate noise from LLM probability estimates, a Quantized Typicality strategy maps linguistic descriptions to discrete weight buckets (e.g., "Hallmark," "Common," "Rare," "Impossible"). The pipeline enforces an Action-Centric Topology, explicitly modeling edges between features and the tests that can confirm or rule them out, transforming the graph into a navigation structure for diagnostic actions.
Hybrid Entity Alignment & Dynamic Upgrade: To handle semantic ambiguity and role shifts (e.g., a disease becoming a symptom), the system employs a hybrid retrieval strategy (lexical overlap + semantic embedding) followed by an LLM-based discriminator for alignment. A Dynamic Node Upgrade mechanism allows nodes to transition roles (e.g., from feature to disease) automatically, enabling complex causal chains to emerge without manual ontology restructuring.
Attribute Enrichment: A metadata module infers quantitative attributes for test nodes, specifically cost (monetary level) and invasiveness, ensuring the graph supports cost-sensitive planning.

2. Graph-Augmented Diagnostic Agent

The agent operates through a "Think-then-Act" loop involving three specialized roles:

Perception Agent: Extracts structured observations from unstructured patient inputs (verbal descriptions or test reports) and grounds them to canonical graph nodes using the alignment mechanism.
Reasoning Agent: Performs deterministic Evidence Scoring and Cost-Sensitive Action Planning.
- Evidence Scoring: Computes a confidence score for each disease based on the alignment between graph knowledge and observed states, explicitly handling positive and negative evidence with penalty factors.
- Action Planning: Uses a heuristic utility function to select the next action (inquiry or test). It prioritizes features that maximize discriminative power among top candidate diseases and selects tests that maximize the information-to-cost ratio, penalizing expensive or invasive options.
Decision Agent: Generates the final natural language response and action, conditioned on a structured reasoning summary (ranked diseases, top features, and suggested tests) derived from the symbolic engine. This constrains the LLM's generation space to medically valid paths.

Key Contributions

Automated MDKG Construction: A novel pipeline that constructs knowledge graphs enriched with quantitative diagnostic attributes (typicality, cost, invasiveness) and dynamic role modeling, addressing the lack of diagnosis-ready attributes in existing graphs.
Explicit Reasoning Engine: A hybrid architecture that offloads complex, deterministic reasoning (state tracking, hypothesis scoring, utility calculation) to a symbolic engine, reducing dependence on the base LLM's implicit reasoning capabilities.
Cost-Aware Multi-Agent Framework: A collaborative agent design that effectively balances diagnostic accuracy with resource constraints, mitigating "defensive medicine" behaviors observed in baseline LLMs.

Experimental Results

The framework was evaluated on MedQA (200 cases) and MIMIC-IV (200 real-world cases) across three LLM backbones: DeepSeek-V3, Kimi-k2, and Llama-3.3.

Diagnostic Accuracy: GraphDx significantly improved diagnostic success rates (Score $\ge$ 8) from a baseline range of 50–68% to 79–93%. For instance, on MedQA with DeepSeek-V3, the success rate jumped from 67.8% to 88.7%.
Cost Efficiency: The framework reduced test costs by 20–54%. On MedQA with DeepSeek-V3, average costs dropped from \ $1,062 to \$ 537.
Robustness: In the noisy MIMIC-IV dataset, GraphDx maintained high performance (83.0% success rate with DeepSeek-V3) while baseline multi-agent frameworks (MAI-DxO) suffered performance collapse or incurred extremely high costs due to uncontrolled exploration.
Open-Set Evaluation: Even when the ground truth disease was excluded from the constructed graph, GraphDx outperformed standard LLMs, demonstrating the utility of the general feature-test structure in guiding the agent.
Ablation Studies: Results confirmed that both the structured knowledge (MDKG) and the explicit inference engine are critical; removing either component led to significant performance drops and increased costs.

Significance and Claims

The paper claims that GraphDx provides a robust, economical, and interpretable solution for automated clinical diagnosis. Its primary significance lies in bridging the knowledge-reasoning gap by combining the perceptual capabilities of LLMs with the logical capabilities of symbolic systems. By explicitly modeling test costs and evidence, the framework offers a path toward interpretable medical AI, where every diagnostic conclusion traces back to explicit evidence scores.

The authors emphasize that GraphDx is intended for research and educational simulation purposes and is not a direct clinical decision-making tool without human oversight. They acknowledge limitations, including dependence on the base LLM's knowledge for graph construction, lack of end-to-end multi-modal processing (e.g., direct image analysis), and the potential for simulation gaps between synthetic and real patient interactions. Future work is proposed to extend the framework to multi-modal data fusion and larger-scale clinical validation.