PaperlayerView exact revision on arXiv

Source-linked AI summary

Retrieval is Cheap, Show Me the Code: Executable Multi-Hop Reasoning for Retrieval-Augmented Generation

Jiashuo Sun, Jimeng Shi, Yixuan Xie, Saizhuo Wang, Jash Rajesh Parekh, Pengcheng Jiang, Zhiyi Shi, Jiajun Fan, Qinglong Zheng, Peiran Li, Shaowen Wang, Ge Liu, Jiawei Han

arXiv:2605.12975v1cs.AI

TL;DR

Existing RAG systems are brittle on multi-hop questions because natural-language reasoning leaves intermediate state implicit, permits entity drift, and relies on ungrounded self-reflection. PyRAG casts multi-hop RAG as executable Python program synthesis over retrieval and QA tools, enabling deterministic execution feedback, inspectable state, self-repair, and adaptive retrieval. Across five benchmarks, it consistently outperforms strong baselines, with the largest gains on compositional multi-hop datasets.

  • Problem

    Existing multi-hop RAG methods use free-form reasoning with implicit state, query drift, and self-generated error signals, limiting control over chained retrieval and reasoning.

  • Method

    PyRAG synthesizes and executes Python programs over retrieval and QA APIs, storing intermediate answers as variables reused by downstream steps.

  • Results

    PyRAG consistently outperforms strong baselines across five QA benchmarks in training-free and RL-trained settings, with especially large gains on compositional multi-hop datasets.

  • Takeaways & Limitations

    Executable reasoning exposes intermediate state and deterministic feedback while enabling self-repair and adaptive retrieval directly through program execution.

  • Takeaways & Limitations

    Retrieval missing accounts for roughly half of incorrect predictions, and adaptive retrieval cannot recover silently plausible but incorrect documents.

Abstract

from arXiv · show

Retrieval-Augmented Generation (RAG) has become a standard approach for knowledge-intensive question answering, but existing systems remain brittle on multi-hop questions, where solving the task requires chaining multiple retrieval and reasoning steps. Key challenges are that current methods represent reasoning through free-form natural language, where intermediate states are implicit, retrieval queries can drift from intended entities, and errors are detected by the same model that produces them making self-reflection an unreliable, ungrounded signal. We observe that multi-hop question answering is a typical form of step-by-step computation, and that this structured process aligns closely with how code-specialized language models are trained to operate. Motivated by this, we introduce \pyrag, a framework that reformulates multi-hop RAG as program synthesis and execution. Instead of free-form reasoning trajectories, \pyrag represents the reasoning process as an executable Python program over retrieval and QA tools, exposing intermediate states as variables, producing deterministic feedback through execution, and yielding an inspectable trace of the entire reasoning process. This formulation further enables compiler-grounded self-repair and execution-driven adaptive retrieval without any additional training. Experiments on five QA benchmarks (PopQA, HotpotQA, 2WikiMultihopQA, MuSiQue, and Bamboogle) show that \pyrag consistently outperforms strong baselines under both training-free and RL-trained settings, with especially large gains on compositional multi-hop datasets. Our code, data and models are publicly available at https://github.com/GasolSun36/PyRAG.

1 Introduction

Multi-hop RAG requires chaining evidence and maintaining intermediate results, but natural-language reasoning leaves state implicit and can suffer entity drift and ungrounded self-reflection. PyRAG instead represents this computation as executable programs, enabling inspectable state, deterministic feedback, adaptive refinement, and strong benchmark gains.

  • Motivation: Multi-hop questions require chaining evidence across sources, while vanilla RAG is designed for single-hop retrieval.The motivating example requires retrieving and comparing two birth dates.
  • Limitations: Existing approaches encode intermediate results in free-form text, allowing query drift and unreliable self-reflection to accumulate errors.Search trajectories may retrieve “Henry II of England” instead of “John William Henry II.”
  • PyRAG: PyRAG reformulates multi-hop reasoning as executable program synthesis over retrieval and answering APIs, with intermediate results stored as reusable variables.Its Decompose, Plan, and Answer Agents convert atomic sub-queries into executable retrieval-and-answer steps.
  • PyRAG: Execution provides explicit state, deterministic compiler feedback, and inspectable traces, while supporting self-repair and adaptive retrieval without additional training.Runtime exceptions guide program revision, and insufficient-evidence signals can increase retrieval scope.
  • Implication: The paper argues that code-specialized models’ advantage emerges under program-synthesis interfaces, making model capability and reasoning interface co-design important.This follows the proposed alignment between step-by-step QA computation and program construction and execution.
  • Results: +11.8 average EM over Vanilla RAG and +25.5 on Bamboogle are reported for training-free 7B PyRAG.PyRAG-RL also achieves the highest average EM among 7B-scale RL-trained methods and generalizes across Qwen3-4B and LLaMA-3.1-8B.

2 Method

PyRAG reformulates multi-hop RAG as executable program synthesis, making intermediate reasoning states explicit and verifiable. Its execution interface supports deterministic self-repair and targeted adaptive retrieval without additional training.

  • Overview: PyRAG decomposes each multi-hop question into atomic sub-queries, plans an executable Python program, and executes it step-by-step.The pipeline uses decomposition, planning, and execution stages.
  • Executable Planning: The planning agent composes retrieve(query, topk) and answer(query, docs) through variable assignments and explicit data dependencies.Intermediate answers are stored as variables and reused in later steps.
  • Execution: Execution records intermediate queries, retrieved documents, and answers in an inspectable trace for debugging and analysis.The trace exposes the reasoning process rather than leaving intermediate states implicit in narrative text.
  • Execution-Guided Refinement: Compiler-grounded self-repair uses structured runtime errors to revise and re-execute invalid programs.The planning agent responds to execution feedback such as invalid operations or inconsistent variable usage.
  • Execution-Guided Refinement: Adaptive retrieval selectively increases the retrieval scope when an intermediate answer indicates insufficient evidence.This corrects under-evidenced steps without modifying the entire reasoning plan, and both refinements require no additional training.

3 Experiments

PyRAG is evaluated across open-domain QA benchmarks under training-free and RL-trained settings, with Exact Match as the primary metric. It consistently improves over strong baselines, especially on compositional multi-hop tasks, while execution contributes substantially to gains and retrieval remains the main failure bottleneck.

  • Experimental Setup: PyRAG is evaluated on PopQA, HotpotQA, 2WikiMultihopQA, MuSiQue, and Bamboogle, using Exact Match as the primary metric.HotpotQA is the in-domain training set for RL-trained variants; the other datasets are out-of-domain.
  • Main Results: 30.8 average EM: training-free PyRAG with Qwen2.5-7B-Instruct surpasses ITER-RETGEN by +4.6 and Vanilla RAG by +11.8.It also gains +14.5 on 2WikiMQA and +25.5 on Bamboogle relative to Vanilla RAG.
  • Main Results: 39.2 average EM: PyRAG-RL with Qwen2.5-7B is on par with ReSearch (38.9) and outperforms Search-R1 by +6.8 and StepSearch by +4.7.PyRAG-RL achieves the highest 7B scores on 2WikiMQA (49.4) and Bamboogle (46.1).
  • Ablation Study: 21.3 to 36.3 average EM: progressively adding decomposition, planning, and execution yields monotonic gains, with execution contributing the largest jump.The ablation compares Vanilla RAG, Decompose-only, PyRAG without execution, and full PyRAG.
  • Ablation Study: +1.8 on HotpotQA, +6.9 on 2WikiMQA, and +2.0 on Bamboogle: code-specialized models outperform instruction-tuned counterparts under PyRAG, but not under Vanilla RAG.The results indicate that code-model benefits emerge when reasoning is formulated as program synthesis.
  • Efficiency Analysis: 3.7 average LLM calls: PyRAG matches Search-R1’s EM, while PyRAG-RL reaches the highest EM with 3.1 calls.Compiler-grounded self-repair triggers on ∼5% of queries and adaptive retrieval on ∼20% in the reported analysis.
  • Failure Analysis: Retrieval missing accounts for roughly half of sampled failures, while program errors contribute only ∼5%.The failure analysis identifies upstream retrieval recall as the dominant bottleneck; the answer agent accounts for ∼95% of failures in the program-error characterization.

4 Related Work

Prior multi-hop RAG methods use implicit retrieval–reasoning trajectories and rely on model self-judgment, while program-guided reasoning typically assumes evidence is already available. PyRAG addresses open-domain QA where intermediate answers are unknown and later queries depend on earlier results.

  • Multi-Hop Retrieval-Augmented Generation: Multi-hop RAG prior work includes iterative retrieve-and-reason prompting, graph-based reasoning, and reinforcement-learned search policies.These approaches retain implicit retrieval–reasoning interactions and use LLM self-judgment for error detection.
  • Program-Guided Reasoning: Program-guided reasoning has been effective for symbolic structures but generally assumes that the evidence is available a priori.This assumption differs from open-domain multi-hop QA, where evidence must be retrieved during reasoning.
  • Program-Guided Reasoning: PyRAG targets open-domain multi-hop QA by synthesizing and executing programs whose later queries depend on earlier intermediate answers.It contributes a concrete program-execution interface for this setting.

5 Conclusion

PyRAG reformulates multi-hop RAG as program synthesis and execution, exposing intermediate states, deterministic compiler feedback, and inspectable traces. Across five QA benchmarks and both training-free and RL-trained settings, it consistently improves over strong baselines, especially on compositional multi-hop datasets.

  • Conclusion: PyRAG encodes retrieval–reasoning as executable Python, enabling explicit intermediate variables, deterministic compiler feedback, and an inspectable reasoning trace.The executable formulation also supports training-free self-repair and adaptive retrieval.
  • Conclusion: Across five QA benchmarks and training-free and RL-trained settings, PyRAG delivers consistent gains over strong baselines.The largest improvements occur on compositional multi-hop datasets.

A Limitations

PyRAG’s gains are bounded by failures in retrieval, answer grounding, adaptive-retrieval signaling, and planner decomposition. The executable interface localizes these errors but does not eliminate the underlying difficulties.

  • Retrieval recall: Retrieval missing accounts for roughly half of incorrect predictions, making upstream retrieval recall the single largest failure source.Adaptive retrieval helps when answer agents explicitly signal insufficient evidence, but not when plausible incorrect documents are returned silently.
  • Answer grounding: A substantial fraction of remaining failures arises because answer agents cannot faithfully ground responses in retrieved passages and compose them across hops.RL fine-tuning improves the Answer Agent over the training-free variant, but current objectives do not eliminate this difficulty.
  • Adaptive retrieval: Sentinel-based adaptive retrieval can silently propagate errors when values such as “unknown” are interpolated into downstream queries as content.The passage proposes structured return types or calibrated confidence signals as more robust alternatives.
  • Planner decomposition: The dominant program-error mode is under-decomposition: syntactically valid code issues one retrieve() call for questions requiring multiple hops.Because no exception is raised, compiler-grounded self-repair cannot detect this failure.
  • Interpretability: The inspectable execution trace lowers the barrier to auditing silent reasoning errors and fabricated intermediate facts, but the interface does not itself resolve retrieval or grounding failures.The trace localizes failures to specific stages while the underlying retrieval and answer-agent limitations remain.

C Extended Related Work

Prior multi-hop RAG work combines retrieval with iterative prompting, reasoning-action loops, decomposed sub-questions, or graph-based structures. These approaches represent alternative strategies for chaining evidence across passages.

  • Iterative and graph-based methods: Multi-hop QA methods interleave retrieval with chain-of-thought reasoning, reasoning-action loops, or decomposed sub-questions.They address questions requiring evidence to be chained across multiple passages.
  • Iterative and graph-based methods: A parallel line of work constructs graph-based reasoning structures over retrieved content.This provides another representation for organizing multi-hop evidence and reasoning.

C.1 Program-Guided Reasoning

Program-guided reasoning uses executable symbolic structures to separate language-model planning from deterministic execution. PyRAG extends this idea to settings where evidence must be retrieved during reasoning rather than supplied beforehand.

  • Executable reasoning: Executable-code methods offload numerical, table, logical, or verification reasoning to interpreters and symbolic solvers.Examples include PAL, Program-of-Thoughts, Binder, Faithful-CoT, Logic-LM, and ProgramFC.
  • Scope distinction: These approaches generally assume that the evidence required for reasoning is available a priori in self-contained inputs or closed evidence corpora.Their setting differs from retrieval-centered multi-hop QA, where evidence must be acquired during the reasoning process.
  • Pipeline-level approaches: DSPy treats language-model pipelines as compilable programs and optimizes prompts and demonstrations, whereas PyRAG targets a specific retrieval-and-reasoning process.The cited HotPotQA case study for DSPy uses a hand-designed two-hop module with fixed structure.

E.1 Implement Details

The implementation decomposes questions, synthesizes executable programs, and executes them with retrieval, answer, repair, and trace mechanisms. Training uses staged specialization of three agents, while experiments follow specified retrieval and dataset setups.

  • Pipeline: PyRAG’s pipeline uses Decompose, Plan, and Answer agents to convert questions into executable retrieval-and-answer programs.The Plan Agent uses retrieve() and answer(), while the Answer Agent conditions on retrieved passages in structured tags.
  • Execution: The execution procedure maintains a Python environment and trace, runs retrieval and answer statements, and returns the final answer or an exception.Native Python operations are also evaluated, and each executed statement with its environment value is appended to the trace.
  • Adaptive retrieval: Adaptive retrieval re-runs an answer operation with an increased retrieval scope when an intermediate answer signals insufficient evidence.The default and boosted top-k values are represented as k0 and k1, with k1 greater than k0.
  • Repair: Runtime errors trigger Plan-Agent self-repair with failed code and a Python traceback for up to three attempts, while syntax errors receive up to three inline retries.This repair process is grounded in execution feedback rather than free-form self-reflection.
  • Training: All three agents are fine-tuned with GRPO using a curriculum-style schedule that sequentially specializes one shared backbone into Answer, Plan, and Decompose roles.The other two agents remain frozen at each stage, and the Answer Agent is trained first because it is the terminal step bounding end-to-end reward.

E.2 Datasets

The evaluation combines training on NQ and HotpotQA with benchmarks spanning domain shift and hop count, while the appendix specifies the agents’ prompts and repair procedures.

  • Training data: RL training uses 87,925 examples from Natural Questions and HotpotQA, combining single-hop and multi-hop reasoning.The mixture contains 79,168 NQ examples and 8,757 HotpotQA examples.
  • Evaluation data: Evaluation covers seven datasets organized by in-domain versus out-of-domain status and single-hop versus multi-hop complexity.The listed sets include NQ, HotpotQA, PopQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle; the passage’s count and enumeration are internally inconsistent.
  • Agent prompts: The Decompose Agent converts each question into atomic, independently answerable subqueries using a strict JSON-list format.Parsing failures receive up to three retries before the original question is used as a single-element list.
  • Agent prompts: The Plan Agent synthesizes executable Python over retrieve(query) and answer(query, docs), enforcing variable reuse and a two-part final synthesis format.The contract includes a no-docs aggregation mode and prevents intermediate answers from leaking into the final question template.
  • Agent prompts: Compiler-grounded repair addresses both syntax failures and runtime exceptions by returning parser locations or tracebacks to the generation call.Both repair mechanisms allow up to three retries.
  • Agent prompts: The Answer Agent uses evidence mode for document-grounded subanswers and aggregation mode to compose final answers from supplied facts without documents.Evidence mode requires inline document citations, while aggregation mode uses the Given/Answer template.

G Case Study

The case study shows how executable traces expose both successful data flow and localized failures, while Python operations and guarded retrieval repair address specific multi-hop errors.

  • Successful execution: Variables produced at one step can be explicitly consumed by later retrieval and answer calls through string interpolation.This makes intermediate data flow visible in the executable program.
  • Adaptive retrieval: When a sub-step returns unknown, execution-guided refinement broadens retrieval while preserving the original plan structure.The repair targets the under-evidenced sub-step rather than modifying the overall plan.
  • Programmatic operations: Boolean conjunction is implemented as a Cartesian grid of yes/no probes whose result is decided by Python’s all expression.This moves the conjunction operation out of free-form answer-agent reasoning.
  • Programmatic operations: Arithmetic over retrieved years is performed deterministically by converting strings with int(...) and subtracting the resulting integers.The final answer is absent from individual documents and must be computed from two retrieved values.
  • Failure localization: Executable traces localize entity drift to the planning stage when a literal iTunes replaces the intended program variable in a later query.The trace distinguishes this planning error from surrounding reasoning text.
  • Failure localization: Treating unknown as ordinary content propagates retrieval failure, motivating guarded fallback branches for hops with no evidence.The failure is localized to a single data-dependency edge.
  • Failure localization: A final answer can fail even when retrieved variables are correct, because the aggregation agent misreads its own bindings.The case motivates more structured aggregation prompts such as typed slots.
  • Failure localization: The case study also exposes answer-agent errors in conjunction, type handling, and final aggregation despite otherwise available evidence.Examples include returning No when both flags are yes and iterating through characters of a comma-joined string.
Loading 2605.12975v1…