Elamur Research⌕
☰
home / papers / 2026 / GraphDx: A Cost-Aware Knowledge-Enhanced Multi-Agent Framework for Sequential Diagnosis

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

Paper · 2026 · Shaoting Tan, Ning Liu, Yuntao Du et al.

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):

    VariantSuccessCostHarmful-action rate
    Baseline65.7%$185712.5%
    Full GraphDx88.3%$10664.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 UniversitySingapore · Singapore156 works · 25,644 citations🎓East China Normal UniversityShanghai · China50 works · 2,174 citations🎓Shandong UniversityJinan · China17 works · 789 citations🎓Nankai UniversityTianjin · China24 works · 762 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksMedicine · 241 worksHealth Informatics · 184 worksHealth Professions · 69 worksHealth 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. DOI 10.18653/v1/2026.findings-acl.1092

@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}
}

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
  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
  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
  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
  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
  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. 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
  8. Harsha Nori, Nicholas King, Scott Mayer McKinney, Dean Carignan, and Eric Horvitz. 2023. Capabilities of gpt-4 on medical challenge problems. 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
  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
  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
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tan-2026-graphdx-cost-aware-knowledge-enhanced/