GraphWalker: Patient Analogy Meets Information Gain for Clinical Reasoning with Large Language Models
Organizations: School of Computer Science, Peking University, Beijing, China · National Engineering Research Center for Software Engineering, Peking University, Beijing, China
Abstract
Clinical reasoning over electronic health records (EHRs) is a fundamental yet challenging task in modern healthcare. While large language models (LLMs) offer a promising paradigm via in-context demonstrations that requires no task-specific parameter updates, existing methods for reasoning by patient analogy in EHR settings suffer from three core limitations: (1) Perspective Limitation, where data-driven similarity misaligns with LLM reasoning needs while model-driven signals are constrained by limited clinical competence; (2) Cohort Awareness, as demonstrations are selected independently without modeling population-level structure; and (3) Information Aggregation, where redundancy and interaction effects among demonstrations are ignored. We propose GraphWalker, a training-free framework that lets frozen LLMs reason by analogy over retrieved patient cases. GraphWalker (i) jointly leverages data-driven and model-driven perspectives, (ii) discovers patient cohorts to ground retrieval in population-level structure, and (iii) employs a lazy greedy search with frontier expansion to compose demonstrations with high marginal information gain. Extensive experiments on multiple real-world EHR benchmarks show that GraphWalker consistently outperforms state-of-the-art demonstration selection baselines, and remains substantially more robust under cross-dataset distribution shift, without task-specific parameter updates. GraphWalker further generalizes to black-box LLMs and composes naturally with agentic reasoning frameworks, positioning it as a pluggable patient-analogy skill in LLM-based clinical workflows. Our code is available at https://github.com/PuppyKnightUniversity/GraphWalker.
Figures & tables
| Method | MIMIC-III Mortality | MIMIC-III LOS | MIMIC-IV Readmission | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Paradigm | Approach | AUROC | AUPRC | F1 | ma-ROC | mi-ROC | AUROC | AUPRC | F1 |
| Qwen3-14B | |||||||||
| Vanilla | Zero-shot | 64.09 5.26 | 17.58 3.98 | 31.62 5.44 | 65.22 3.00 | 37.49 2.48 | 41.11 4.77 | 27.11 4.51 | 41.66 3.80 |
| Random | 66.33 5.12 | 31.04 6.89 | 43.00 5.88 | 58.12 1.98 | 61.28 3.35 | 49.98 4.47 | 24.81 3.63 | 40.77 4.05 | |
| Data Perspective | Semantic-emb | 64.43 6.71 | 21.78 6.09 | 33.60 6.16 | 57.06 3.77 | 66.60 2.60 | 45.12 4.13 | 26.91 4.99 | 42.01 3.94 |
| EHR-emb | 75.24 5.86 | 29.52 8.20 | 42.49 8.88 | 62.03 3.13 | 66.98 2.53 | 57.79 4.37 | 32.73 5.01 | 44.87 4.01 | |
| Method | MIMIC-III Mortality | MIMIC-III LOS | MIMIC-IV Readmission | |||||
|---|---|---|---|---|---|---|---|---|
| AUROC | AUPRC | F1 | ma-ROC | mi-ROC | AUROC | AUPRC | F1 | |
| GraphWalker | 84.19 3.35 | 59.46 7.64 | 58.24 5.89 | 69.51 3.16 | 84.64 2.14 | 75.91 4.11 | 60.61 6.19 | 58.01 5.33 |
| w/o EHR-emb | 61.09 5.32 | 31.13 6.81 | 37.50 5.73 | 62.03 3.40 | 72.63 2.46 | 45.30 4.55 | 26.69 4.20 | 41.74 3.79 |
| w/o Cohort | 81.19 3.78 | 48.27 8.01 | 55.06 6.18 | 65.85 3.75 | 81.16 2.27 | 75.65 4.04 | 59.61 6.09 | 56.87 5.19 |
| w/o Greedy & Frontier Expansion | 69.43 5.80 | 46.72 8.24 | 55.34 7.22 | 60.93 3.30 | 53.33 2.52 | 62.43 4.72 | 43.69 6.25 | 47.24 4.90 |
| w/o Early Stop | 81.34 3.74 | 48.66 7.91 | 55.99 6.18 | 66.31 3.23 | 82.77 2.14 | 75.53 4.09 | 59.13 6.12 | 57.38 5.22 |
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | MIMIC-III Mortality | MIMIC-III LOS | MIMIC-IV Readmission | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Paradigm | Approach | AUROC | AUPRC | F1 | ma-ROC | mi-ROC | AUROC | AUPRC | F1 |
| Qwen3-32B | |||||||||
| Vanilla | Zero-shot | 65.67 5.75 | 30.54 7.56 | 38.43 6.99 | 55.79 3.33 | 23.53 2.46 | 44.19 4.57 | 25.06 3.88 | 42.57 3.83 |
| Random | 59.90 5.06 | 24.63 5.29 | 36.22 4.94 | 59.50 3.51 | 80.44 2.00 | 48.25 4.65 | 28.13 4.51 | 42.22 3.77 | |
| Data Perspective | Semantic-emb | 60.62 5.80 | 19.87 4.61 | 32.08 5.59 | 57.65 3.65 | 74.16 2.38 | 47.86 4.71 | 26.07 3.89 | 42.47 3.85 |
| EHR-emb | 85.02 3.21 | 58.56 8.02 | 58.84 6.01 | 63.02 3.33 | 67.00 2.71 | 61.32 4.45 | 44.25 5.92 | 46.24 4.06 | |
| Method | MIMIC-III Mortality | MIMIC-IV Readmission | ||||
|---|---|---|---|---|---|---|
| AUROC | AUPRC | F1 | AUROC | AUPRC | F1 | |
| SMART (fine-tuned predictor) | 80.64 | 45.40 | 47.18 | 74.41 | 54.62 | 57.38 |
| GraphWalker (with SMART encoder) | 84.19 | 59.46 | 58.24 | 75.91 | 60.61 | 58.01 |
| +3.55 | +14.06 | +11.06 | +1.50 | +5.99 | +0.63 | |
| ConCare (fine-tuned predictor) | 69.19 | 36.01 | 40.65 | 70.30 | 41.87 | 50.26 |
| GraphWalker (with ConCare encoder) | 70.46 | 36.93 | 45.90 | 77.01 | 59.49 | 59.44 |
| Method | AUROC | AUPRC | F1 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| In-Dom. | OOD | Drop | In-Dom. | OOD | Drop | In-Dom. | OOD | Drop | |
| SFT | 68.34 6.29 | 51.04 5.47 | 25.3% | 17.48 4.88 | 11.34 4.11 | 35.1% | 30.43 6.35 | 17.38 5.12 | 42.9% |
| RAM-EHR Xu et al. (2024a) | 80.58 3.48 | 59.26 3.35 | 26.5% | 53.02 3.87 | 39.23 4.47 | 26.0% | 51.26 3.44 | 37.26 3.67 | 27.3% |
| GraphCare Jiang et al. (2024) | 80.21 3.55 | 62.34 5.57 | 22.3% | 54.77 3.19 | 39.35 3.67 | 28.2% | 52.22 3.75 | 36.04 4.36 | 31.0% |
| DearLLM Xu et al. (2025) | 82.77 3.63 | 69.99 5.21 | 15.4% | 58.02 3.24 | 42.85 6.39 | 26.1% | 56.79 3.75 | 43.32 6.06 | 23.7% |
| GraphWalker | 84.19 3.35 | 81.29 3.91 | 3.4% | 59.46 7.64 | 52.98 6.01 | 10.9% | 58.24 5.89 | 54.08 5.84 | 7.1% |
| Method | Direct Answer (Few-shot) | + ReAct | ||||
|---|---|---|---|---|---|---|
| AUROC | AUPRC | F1 | AUROC | AUPRC | F1 | |
| Zero-shot | 70.81 4.86 | 33.69 6.88 | 41.42 6.20 | 71.11 5.47 | 32.86 4.97 | 43.61 6.33 |
| Random | 70.41 4.69 | 31.32 6.94 | 39.12 5.61 | 68.46 3.26 | 29.08 5.53 | 39.08 4.96 |
| Semantic-emb | 69.91 5.23 | 25.78 6.32 | 36.30 6.09 | 70.91 4.11 | 26.01 5.37 | 36.92 5.58 |
| EHR-emb | 81.59 4.87 | 48.45 6.96 | 46.07 5.78 | 82.09 7.81 | 47.98 5.96 | 48.51 6.45 |
| GraphWalker | 87.64 5.14 | 62.31 8.96 | 64.79 7.74 | 88.72 3.18 | 64.69 2.43 | 67.11 2.45 |
| Split | MedQA | CMB | CMB-Clin |
|---|---|---|---|
| Train | 10,178 | 15,465 | 83 |
| Val | 1,272 | 1,940 | 42 |
| Test | 1,273 | 1,935 | 83 |
| Total | 12,723 | 19,340 | 208 |
| Method | CMB | MedQA | CMB-clin | ||
| EM | EM | BLEU-4 | BLEU-1 | ROUGE-L | |
| Zero-shot | 80.21 0.92 | 56.56 3.59 | 21.06 1.37 | 59.85 2.30 | 44.97 1.73 |
| Random | 81.50 2.78 | 52.96 3.53 | 26.85 1.44 | 66.05 2.08 | 38.63 1.77 |
| Semantic-emb | 80.52 2.70 | 59.58 3.52 | 26.86 1.47 | 64.90 2.01 | 41.26 2.07 |
| Time-series | 78.05 2.90 | 52.11 3.55 | 29.05 10.65 | 66.56 2.24 | 40.12 1.57 |
| SPELL | 81.98 2.73 | 54.10 3.49 | 28.41 1.46 | 66.75 2.10 | 36.82 1.64 |
| Component | Content |
|---|---|
| Prompt | You will be provided with longitudinal electronic health record (EHR) data for a single patient. Each clinical feature is represented as a time-ordered list of measurements corresponding to the same hospital stay. Missing values are denoted as NaN . Patient Information: • Number of measurements: 19 • Measurement times (hours since admission): [4.68, 5.18, 6.18, 7.18, 8.18, …] Task Description: You are tasked with predicting in-hospital mortality based on patient EHR data. Instructions & Output Format: Provide only a floating-point number between 0 and 1 representing the predicted probability of mortality. Do not provide any reasoning or additional text. Output only the numerical value (e.g., 0.XX ). |
| Target Patient | Clinical Features Over Time: • Heart Rate (bpm): [117.0, 110.0, 111.0, 107.0, 102.0, …, 119.0, 122.0, 118.0] • Systolic BP (mmHg): [99.0, 96.0, 92.0, 109.0, 87.0, …, 127.0, 118.0, 120.0] • Diastolic BP (mmHg): [39.0, 56.0, 44.0, 54.0, 47.0, …, 87.0, 75.0, 67.0] • Mean BP (mmHg): [59.0, 69.3, 60.0, 72.3, 60.3, …, 100.3, 89.3, 84.7] • SpO 2 (%): [97.0, 94.0, 95.0, 95.0, 94.0, …, 96.0, 95.0, 95.0] • GCS (Total): [NaN, 15.0, 15.0, 15.0, 15.0, …, 15.0, 15.0, 15.0] |
| Ground Truth | 0 (Survival). |
| Zero-shot Output | Prediction: 0.72 Incorrect |
| GraphWalker Examples | Example 1 Label: 0 ; • Heart Rate: [78.0, 104.0, 81.0, 98.0, 74.0, …, 73.0, NaN, 74.0, 72.0] • Systolic BP: [119.0, 134.0, 111.0, 165.0, 149.0, …, 107.0, 96.0, 112.0, 118.0] • Diastolic BP: [62.0, 70.0, 79.0, 73.0, 66.0, …, 43.0, 56.0, 62.0] • SpO 2 : [98.0, 94.0, 95.0, 98.0, 96.0, …, 98.0, NaN, 97.0, 96.0] • GCS (Total): [NaN, 14.0, NaN, 14.0, NaN, …, 15.0, …] Example 2 Label: 0 ; • Heart Rate: [87.0, 92.0, 92.0, 97.0, 90.0, …, 88.0, 77.0, 75.0, 74.0] • Systolic BP: [138.0, 155.0, 143.0, 152.0, 131.0, …, 136.0, 116.0, 133.0, 136.0] • Diastolic BP: [62.0, 78.0, 69.0, 79.0, 57.0, …, 59.0, 66.0, 61.0] • SpO 2 : [93.0, 93.0, 93.0, 95.0, 91.0, …, 93.0, 97.0, 98.0, 98.0] • GCS (Total): [NaN, 15.0, NaN, …, 15.0, …] Example 3 Label: 0 ; • Heart Rate: [102.0, 105.0, 95.0, 91.0, 96.0, …, 77.0, 79.0, 80.0, 81.0] • Systolic BP: [122.0, 118.0, 115.0, 118.0, 106.0, …, 132.0, 118.0, 129.0, 130.0] • Diastolic BP: [62.0, 52.0, 65.0, 74.0, 63.0, …, 84.0, 76.0, 79.0, 85.0] • SpO 2 : [83.0, 95.0, 94.0, 95.0, 93.0, …, 93.0, 93.0, 92.0, 91.0] • GCS (Total): [NaN, NaN, 15.0, …, 15.0, …] |
| GraphWalker Output | Prediction: 0.0689 Correct |
| Symbol | Description |
|---|---|
| EHR record of patient | |
| Pretrained EHR encoder | |
| Patient embedding of patient | |
| Number of patients in the EHR base | |
| Population-level patient graph | |
| Set of patient nodes in the graph |