MIRAGE: Scaling Test-Time Inference with Parallel Graph-Retrieval-Augmented Reasoning Chains

Kaiwen Wei, Rui Shan, Dongsheng Zou, Jianzhong Yang, Bi Zhao, Junnan Zhu, Jiang ZhongarXiv 2025 · arXiv

TL;DR

MIRAGE introduces a parallel, multi-chain reasoning framework for medical question-answering that replaces fragile, linear reasoning paths with structured knowledge graph exploration. By decomposing complex clinical queries into entity-grounded sub-questions and verifying answers across parallel tracks, it significantly reduces error propagation and provides fully traceable medical explanations.

What Problem Does This Paper Address?

Large reasoning models (LRMs) like OpenAI's o1 or DeepSeek-R1 excel at complex problem-solving by allocating more computational budget at inference time—a paradigm known as test-time scaling. However, when applied to high-stakes, knowledge-intensive domains like medicine, current agentic Retrieval-Augmented Generation (RAG) methods face two major bottlenecks:

  1. Linear Fragility: They rely on a single, sequential reasoning chain. If an early step introduces an error or hallucinates a fact, that error cascades down the entire chain.
  2. Unstructured Noise: They typically ingest external knowledge as flat, unstructured text fragments from web searches, ignoring the rich, hierarchical relationships inherent in medical knowledge.

In clinical settings, where accuracy and auditability are non-negotiable, these limitations lead to unreliable answers and untraceable logic.

Figure 1: Comparison of medical QA strategies: (a) Static RAG retrieves documents or knowledge graph entries with- out explicit reasoning; (b) Agentic RAG methods like Search-o1 integrate retrieval with linear reasoning; (c) ToT explores multiple reasoning chains via sampling; (d) The proposed MIRAGE combines these approaches by perform- ing graph-based retrieval across parallel reasoning chains.

Methods

The authors propose MIRAGE (Multi-chain Inference with Retrieval-Augmented Graph Exploration), a framework that shifts test-time compute from linear depth to parallel breadth. Managed by a central Coordinator that tracks shared memory and execution states, MIRAGE operates in four distinct phases:

  • Question Decomposition: Instead of tackling a multi-symptom query all at once, MIRAGE breaks it down into distinct, self-contained sub-questions that are explicitly mapped to concrete medical entities.
  • Graph-Augmented Evidence Retrieval: For each sub-question, the model enters an iterative "think-while-search" loop over a structured medical knowledge graph (KG). It dynamically switches between two retrieval modes:
  • Anchor Mode: Retrieves the immediate local neighborhood of a single entity (e.g., symptoms or treatments associated with a disease).
  • Bridge Mode: Discovers multi-hop relational paths connecting two distinct entities (e.g., linking a specific symptom to a potential comorbidity).
  • Answer Synthesis & Cross-Path Verification: Each parallel chain produces a tentative answer. The framework then performs pairwise comparisons across all chains to detect contradictions or biological inconsistencies (e.g., a drug flagged as both a treatment and a cause for the same symptom). It applies a majority-based verification strategy to retain the most robustly supported claims.
  • Final Answer Generation: The verified knowledge graph paths, sub-questions, and answers are compiled into a final, patient-oriented prose response, accompanied by a machine-readable audit record for full traceability.
Figure 2: Overview of the proposed MIRAGE framework. Given a clinical query, the system decomposes it into sub-questions, each initiating a reasoning chain. For each chain, the system iteratively retrieves knowledge graph evidence using either Anchor mode or Bridge mode. Retrieved results are coordinated and aggregated to generate the final answer.

Datasets

MIRAGE was evaluated across three public medical QA benchmarks, each paired with a structured medical knowledge graph containing deduplicated entities and clearly defined relations:

  • GenMedGPT-5k (paired with the EMCKG knowledge graph)
  • CMCQA (paired with the CMCKG knowledge graph)
  • ExplainCPE (paired with the CMCKG knowledge graph)

These datasets cover diverse clinical scenarios, including open-ended questions, multi-turn dialogues, and multiple-choice examinations in both English and Chinese.

Key Insights and Ideas

  • Parallel Breadth > Linear Depth: Splitting a complex query into independent, parallel reasoning tracks allows the model to perform cross-chain verification. This isolates errors to individual branches rather than letting them corrupt the entire output.
  • Structure Trumps Raw Text: Relying on curated, structured knowledge graphs instead of raw web text drastically reduces noise. It allows the model to perform precise multi-hop reasoning by following explicit relational paths.
  • Demand-Driven Scaling: While over-decomposing questions can introduce noise, increasing the retrieval steps ($N_r$) yields stable, diminishing returns. This indicates that the graph-search process is naturally demand-driven, stopping early once sufficient grounding evidence is found.

Key Results

MIRAGE consistently outperformed strong baselines, including raw LLMs, Tree-of-Thought (ToT) variants, and sequential search agents like Search-o1:

  • Accuracy Boost: On the multi-answer ExplainCPE dataset, MIRAGE achieved 84.8% accuracy using a Qwen-QwQ-32B backbone, outperforming the base model (82.8%) and Search-o1 (80.7%).
  • Backbone Agnostic: The framework demonstrated excellent generalizability. When switched to a DeepSeek-R1-32B backbone, MIRAGE maintained its edge, achieving the highest GPT-4o ranking and an accuracy of 84.4%.
  • Human Alignment: In a blind study conducted by medical graduate students evaluating factual accuracy, reasoning clarity, and clinical fluency, MIRAGE was overwhelmingly preferred over all other baselines.
Figure 4: Human evaluation results on GenMedGPT-5k.

Limitations and Future Work

The authors note that MIRAGE is sensitive to the question decomposition threshold ($N_q$). If the framework splits a query too aggressively (over-decomposition), it can introduce longer, noisier reasoning chains or disrupt the natural contextual flow required for dialogue-style queries.

Future work will likely focus on developing adaptive decomposition mechanisms that dynamically calibrate the granularity of sub-questions based on the complexity of the patient's initial query.

Summary updated

Abstract

Large reasoning models (LRMs) have shown significant progress in test-time scaling through chain-of-thought prompting. Current approaches like search-o1 integrate retrieval augmented generation (RAG) into multi-step reasoning processes but rely on a single, linear reasoning chain while incorporating unstructured textual information in a flat, context-agnostic manner. As a result, these approaches can lead to error accumulation throughout the reasoning chain, which significantly limits its effectiveness in medical question-answering (QA) tasks where both accuracy and traceability are critical requirements. To address these challenges, we propose MIRAGE (Multi-chain Inference with Retrieval-Augmented Graph Exploration), a novel test-time scalable reasoning framework that performs dynamic multi-chain inference over structured medical knowledge graphs. Specifically, MIRAGE 1) decomposes complex queries into entity-grounded sub-questions, 2) executes parallel inference chains, 3) retrieves evidence adaptively via neighbor expansion and multi-hop traversal, and 4) integrates answers using cross-chain verification to resolve contradictions. Experiments on three medical QA benchmarks (GenMedGPT-5k, CMCQA, and ExplainCPE) show that MIRAGE consistently outperforms GPT-4o, Tree-of-Thought variants, and other retrieval-augmented baselines in both automatic and human evaluations. Additionally, MIRAGE improves interpretability by generating explicit reasoning chains that trace each factual claim to concrete chains within the knowledge graph, making it well-suited for complex medical reasoning scenarios. The code will be available for further research.
BibTeX
@misc{wei2025mirage,
  author = {Kaiwen Wei and Rui Shan and Dongsheng Zou and Jianzhong Yang and Bi Zhao and Junnan Zhu and Jiang Zhong},
  title = {{MIRAGE: Scaling Test-Time Inference with Parallel Graph-Retrieval-Augmented Reasoning Chains}},
  year = {2025},
  eprint = {2508.18260},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.18260},
}
Figure