--- title: "GraphDx — paper by Tan et al. (2026) — summary and ideas" description: "An LLM-driven pipeline automatically builds a Medical Diagnosis Knowledge Graph (MDKG) that links diseases, features and… 12 references." authors: ["Shaoting Tan", "Ning Liu", "Yuntao Du", "Shuyue Wei", "Wu Shuai", "Qian Li", "Yanyu Xu", "Wei Zhang", "Lizhen Cui", "Haitao Yuan"] year: 2026 venue: "Findings of the Association for Computational Linguistics: ACL 2026" source: "https://aclanthology.org/2026.findings-acl.1092/" doi: "10.18653/v1/2026.findings-acl.1092" licence: "CC BY 4.0 (ACL Anthology)" licence_url: "https://creativecommons.org/licenses/by/4.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/tan-2026-graphdx-cost-aware-knowledge-enhanced/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/tan-2026-graphdx-cost-aware-knowledge-enhanced/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/31/) / GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis # 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](https://md.research.elamur.ai/free/en/authors/qian-li/), Yanyu Xu, [Wei Zhang](https://md.research.elamur.ai/free/en/authors/wei-zhang/), Lizhen Cui and Haitao Yuan · **Year:** 2026 · **Venue:** [Findings of the Association for Computational Linguistics: ACL 2026](https://md.research.elamur.ai/free/en/venues/findings/) ([Findings of the Association for Computational Linguistics 2026](https://md.research.elamur.ai/free/en/venues/findings/2026/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/) **Links:** [Publisher's page](https://aclanthology.org/2026.findings-acl.1092/) · [PDF](https://aclanthology.org/2026.findings-acl.1092.pdf) · [DOI 10.18653/v1/2026.findings-acl.1092](https://doi.org/10.18653/v1/2026.findings-acl.1092) · [OpenAlex](https://openalex.org/W7166842103) **Citations:** 0 citations (OpenAlex, 2026-10-14) ## Summary In sequential diagnosis, a clinician asks about symptoms and orders tests over several turns, trying to get the diagnosis right without spending too much. The authors argue that LLMs know a great deal of medicine but reason poorly when cost matters, so they tend to over-order tests. They call this the knowledge-reasoning gap. GraphDx addresses it in two parts: - **Graph construction.** An LLM-driven pipeline automatically builds a Medical Diagnosis Knowledge Graph (MDKG) that links diseases, features and tests. It stores discrete typicality weights for features and cost and invasiveness attributes for tests. - **Three agents.** A Perception agent maps patient answers onto graph nodes. A Decision agent writes the replies. Between them, a Reasoning agent scores the evidence deterministically and picks the next action on the graph by weighing utility against cost. The framework was tested on MedQA-Extended and MIMIC-IV with three backbones. Diagnostic success rose and test spending fell, and the gains held even with weaker models where prompt-heavy multi-agent baselines fail. Moving the reasoning onto an explicit graph makes diagnosis cheaper and easier to interpret. ## Key points - **Headline results:** across DeepSeek-V3, Kimi-k2 and Llama-3.3, success rates went from 50–68% to 79–93%, and test costs dropped by 20–54%. - **Graph-building techniques:** - Feature typicality is bucketed into four levels: Hallmark, Common, Rare and Impossible. - Edges run from features to the tests that can verify them. - Synonyms are merged using Overlap Coefficient plus embedding retrieval, with an LLM making the final call. - A "dynamic node upgrade" can promote a feature to a disease, such as Heart Failure. - **Ablation (Llama-3.3, MedQA-Extended):** | Variant | Success | Cost | Harmful-action rate | |---|---|---|---| | Baseline | 65.7% | $1857 | 12.5% | | Full GraphDx | 88.3% | $1066 | 4.3% | Removing either the real graph or the inference engine hurt results. - **Limitations:** - Graph quality depends on the LLM that builds it (DeepSeek-V3). - The system handles text only. - Each decision step is slower than a plain LLM. - The simulated patients and judge are LLM-based. - **Released resources:** the code, the graph-construction pipeline and the ClinicSim environment are open-sourced on GitHub (ossiver-GEL/GraphDx). *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [Nanyang Technological University](https://md.research.elamur.ai/free/en/universities/nanyang-technological-university/) — University, Singapore, Singapore · 156 works · 25,644 citations - [East China Normal University](https://md.research.elamur.ai/free/en/universities/east-china-normal-university/) — University, Shanghai, China · 50 works · 2,174 citations - [Shandong University](https://md.research.elamur.ai/free/en/universities/shandong-university/) — University, Jinan, China · 17 works · 789 citations - [Nankai University](https://md.research.elamur.ai/free/en/universities/nankai-university/) — University, Tianjin, China · 24 works · 762 citations 📚 Shelves (6): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🩺 Medicine](https://md.research.elamur.ai/free/en/shelves/medicine/) · 241 works · [🩺 Health Informatics](https://md.research.elamur.ai/free/en/shelves/medicine/health-informatics/) · 184 works · [🏥 Health Professions](https://md.research.elamur.ai/free/en/shelves/health-professions/) · 69 works · [🏥 Health Information Management](https://md.research.elamur.ai/free/en/shelves/health-professions/health-information-management/) · 50 works ## Cite Cite as: Shaoting Tan, Ning Liu, Yuntao Du, Shuyue Wei, Wu Shuai, Qian Li, Yanyu Xu, Wei Zhang, Lizhen Cui and Haitao Yuan. 2026. GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis. Findings of the Association for Computational Linguistics: ACL 2026. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{tan2026graphdx, title = {{GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis}}, author = {Shaoting Tan, Ning Liu, Yuntao Du, Shuyue Wei, Wu Shuai, Qian Li, Yanyu Xu, Wei Zhang, Lizhen Cui and Haitao Yuan}, booktitle = {Findings of the Association for Computational Linguistics: ACL 2026}, year = {2026}, doi = {10.18653/v1/2026.findings-acl.1092}, url = {https://doi.org/10.18653/v1/2026.findings-acl.1092} } ``` - [← previous Graph-Based Phonetic Error Correction of Noisy ASR](https://md.research.elamur.ai/free/en/papers/singh-2026-graph-based-phonetic-error-correction/) - [next → GraphLoRA: Structure-Aware Low-Rank Adaptation for Large Language Model Recommendation](https://md.research.elamur.ai/free/en/papers/mu-2026-graphlora-structure-aware-low-rank/) - [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/31/) ## References 12 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Sydney Anuyah, Mehedi Mahmud Kaushik, Sri Rama Krishna Reddy Dwarampudi, Rakesh Shiradkar, Arjan Durresi, and Sunandan Chakraborty. 2025. Automated knowledge graph construction using large language models and sentence complexity modelling. In Proceedings of the 2025 Conference on Empirical Methods i… [find](https://scholar.google.com/scholar?q=Sydney+Anuyah%2C+Mehedi+Mahmud+Kaushik%2C+Sri+Rama+Krishna+Reddy+Dwarampudi%2C+Rakesh+Shiradkar%2C+Arjan+Durresi%2C+and+Sunandan+Chakraborty%2E+2025%2E+Automated+knowledge+graph+construction+using+large+language+mo) 2. Bohan Chen and Andrea L. Bertozzi. 2023. Autokg: Efficient automated knowledge graph generation for language models. Preprint, arXiv:2311.14740. — [arXiv:2311.14740](https://arxiv.org/abs/2311.14740) [find](https://scholar.google.com/scholar?q=Bohan+Chen+and+Andrea+L%2E+Bertozzi%2E+2023%2E+Autokg%3A+Efficient+automated+knowledge+graph+generation+for+language+models%2E+Preprint%2C+arXiv%3A2311%2E14740%2E+%E2%80%94+%5BarXiv%3A2311%2E14740%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2311%2E14740%29) 3. Silas Ruhrberg Estévez, Nicolás Astorga, and Mihaela van der Schaar. 2025. Timely clinical diagnosis through active test selection. Preprint, arXiv:2510.18988. — [arXiv:2510.18988](https://arxiv.org/abs/2510.18988) [find](https://scholar.google.com/scholar?q=Silas+Ruhrberg+Est%C3%A9vez%2C+Nicol%C3%A1s+Astorga%2C+and+Mihaela+van+der+Schaar%2E+2025%2E+Timely+clinical+diagnosis+through+active+test+selection%2E+Preprint%2C+arXiv%3A2510%2E18988%2E+%E2%80%94+%5BarXiv%3A2510%2E18988%5D%28https%3A%2F%2Farxiv%2Eorg%2Fa) 4. 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 AI, 4:e58670. [find](https://scholar.google.com/scholar?q=Y%2E+Gao%2C+R%2E+Li%2C+E%2E+Croxford%2C+J%2E+Caskey%2C+B%2E+Patterson%2C+M%2E+Churpek%2C+T%2E+Miller%2C+D%2E+Dligach%2C+and+M%2E+Afshar%2E+2025%2E+Leveraging+medical+knowledge+graphs+into+large+language+models+for+diagnosis+prediction%3A+De) 5. Zhihao Jia, Mingyi Jia, Junwen Duan, and Jianxin Wang. 2025. Ddo: Dual-decision optimization for llm-based medical consultation via multi-agent collaboration. Preprint, arXiv:2505.18630. [find](https://scholar.google.com/scholar?q=Zhihao+Jia%2C+Mingyi+Jia%2C+Junwen+Duan%2C+and+Jianxin+Wang%2E+2025%2E+Ddo%3A+Dual%2Ddecision+optimization+for+llm%2Dbased+medical+consultation+via+multi%2Dagent+collaboration%2E+Preprint%2C+arXiv%3A2505%2E18630%2E) 6. Alistair E. W. Johnson, Lucas Bulgarelli, Lu Shen, Alvin Gayles, Ayad Shammout, Steven Horng, Tom J. Pollard, Sicheng Hao, Benjamin Moody, Brian Gow, Liwei H. Lehman, Leo A. Celi, and Roger G. Mark. 2023. [MIMIC-IV, a freely accessible electronic health record dataset](https://md.research.elamur.ai/free/en/papers/johnson-2023-mimic-iv-freely-accessible-electronic/). Scientific Data, 10(1):1. 7. Harsha Nori, Mayank Daswani, Christopher Kelly, Scott Lundberg, Marco Tulio Ribeiro, Marc Wilson, Xiaoxuan Liu, Viknesh Sounderajah, Jonathan Carlson, Matthew P Lungren, Bay Gross, Peter Hames, Mustafa Suleyman, Dominic King, and Eric Horvitz. 2025. Sequential diagnosis with language models. Preprin… — [arXiv:2506.22405](https://arxiv.org/abs/2506.22405) [find](https://scholar.google.com/scholar?q=Harsha+Nori%2C+Mayank+Daswani%2C+Christopher+Kelly%2C+Scott+Lundberg%2C+Marco+Tulio+Ribeiro%2C+Marc+Wilson%2C+Xiaoxuan+Liu%2C+Viknesh+Sounderajah%2C+Jonathan+Carlson%2C+Matthew+P+Lungren%2C+Bay+Gross%2C+Peter+Hames%2C+Mustaf) 8. Harsha Nori, Nicholas King, Scott Mayer McKinney, Dean Carignan, and Eric Horvitz. 2023. [Capabilities of gpt-4 on medical challenge problems](https://md.research.elamur.ai/free/en/papers/nori-2023-capabilities-gpt-4-medical-challenge/). Preprint, arXiv:2303.13375. 9. Pengcheng Qiu, Chaoyi Wu, Junwei Liu, Qiaoyu Zheng, Yusheng Liao, Haowen Wang, Yun Yue, Qianrui Fan, Shuai Zhen, Jian Wang, Jinjie Gu, Yanfeng Wang, Ya Zhang, and Weidi Xie. 2025. Evolving diagnostic agents in a virtual clinical environment. Preprint, arXiv:2510.24654. — [arXiv:2510.24654](https://arxiv.org/abs/2510.24654) [find](https://scholar.google.com/scholar?q=Pengcheng+Qiu%2C+Chaoyi+Wu%2C+Junwei+Liu%2C+Qiaoyu+Zheng%2C+Yusheng+Liao%2C+Haowen+Wang%2C+Yun+Yue%2C+Qianrui+Fan%2C+Shuai+Zhen%2C+Jian+Wang%2C+Jinjie+Gu%2C+Yanfeng+Wang%2C+Ya+Zhang%2C+and+Weidi+Xie%2E+2025%2E+Evolving+diagnostic+) 10. Ali Sarabadani, Maryam Abdollahi Shamami, Hamidreza Sadeghsalehi, Borhan Asadi, and Saba Hesaraki. 2025. Dkg-llm : A framework for medical diagnosis and personalized treatment recommendations via dynamic knowledge graph and large language model integration. Preprint, arXiv:2508.06186. — [arXiv:2508.06186](https://arxiv.org/abs/2508.06186) [find](https://scholar.google.com/scholar?q=Ali+Sarabadani%2C+Maryam+Abdollahi+Shamami%2C+Hamidreza+Sadeghsalehi%2C+Borhan+Asadi%2C+and+Saba+Hesaraki%2E+2025%2E+Dkg%2Dllm+%3A+A+framework+for+medical+diagnosis+and+personalized+treatment+recommendations+via+dyna) 11. Samuel Schmidgall, Rojin Ziaei, Carl Harris, Eduardo Reis, Jeffrey Jopling, and Michael Moor. 2025. Agentclinic: a multimodal agent benchmark to evaluate ai in simulated clinical environments. Preprint, arXiv:2405.07960. — [arXiv:2405.07960](https://arxiv.org/abs/2405.07960) [find](https://scholar.google.com/scholar?q=Samuel+Schmidgall%2C+Rojin+Ziaei%2C+Carl+Harris%2C+Eduardo+Reis%2C+Jeffrey+Jopling%2C+and+Michael+Moor%2E+2025%2E+Agentclinic%3A+a+multimodal+agent+benchmark+to+evaluate+ai+in+simulated+clinical+environments%2E+Preprin) 12. Karan Singhal, Shekoofeh Azizi, Tao Tu, S. Sara Mahdavi, Jason Wei, Hyung Won Chung, Nathan Scales, Ajay Tanwani, Heather Cole-Lewis, Stephen Pfohl, Perry Payne, Martin Seneviratne, Paul Gamble, Chris Kelly, Abubakr Babiker, Nathanael Schärli, Aakanksha Chowdhery, Philip Mansfield, Dina Demner-Fushm… — [Large Language Models Encode Clinical Knowledge](https://md.research.elamur.ai/free/en/papers/singhal-2022-large-language-models-encode-clinical/) *Updated 1 November 2026*