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

arXiv: https://arxiv.org/abs/2508.18260 · HTML: https://mlsanity.com/paper/2508.18260/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 25 Aug 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 12 of 12)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Multimodal Chain-of-Thought Reasoning in Language Models](https://mlsanity.com/paper/2302.00923/) (2023)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [WebThinker: Empowering Large Reasoning Models with Deep Research Capability](https://mlsanity.com/paper/2504.21776/) (2025)
- [Multi-Step Reasoning with Large Language Models, a Survey](https://mlsanity.com/paper/2407.11511/) (2024)
- [A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyond](https://mlsanity.com/paper/2503.21614/) (2025)
- [DeepRAG: Thinking to Retrieve Step by Step for Large Language Models](https://mlsanity.com/paper/2502.01142/) (2025)

## Built on by (most cited first, 7 of 7)

- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [GenProve: Learning to Generate Text with Fine-Grained Provenance](https://mlsanity.com/paper/2601.04932/) (2026)
- [MathAgent: Adversarial Evolution of Constraint Graphs for Mathematical Reasoning Data Synthesis](https://mlsanity.com/paper/2604.11188/) (2026)
- [BayesRAG: Probabilistic Mutual Evidence Corroboration for Multimodal Retrieval-Augmented Generation](https://mlsanity.com/paper/2601.07329/) (2026)
- [FocalOrder: Focal Preference Optimization for Reading Order Detection](https://mlsanity.com/paper/2601.07483/) (2026)
- [LLM Reasoning Is Latent, Not the Chain of Thought](https://mlsanity.com/paper/2604.15726/) (2026)
- [RH-RAG: Trustworthy Long-Form Generation for Privacy-Constrained Settings](https://mlsanity.com/paper/2608.01311/) (2026)

## Abstract (arXiv)

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.