RELOOP: Recursive Retrieval with Multi-Hop Reasoner and Planners for Heterogeneous QA

1. Problem Statement

Retrieval-Augmented Generation (RAG) systems currently face three critical challenges when handling complex, multi-step questions across heterogeneous data sources (text, tables, and Knowledge Graphs):

• C1: Coverage in Single-Pass Retrievers: Traditional "retrieve-then-generate" pipelines struggle to trace complete evidence chains. Dense retrievers often lack path coverage for multi-hop reasoning, while chunking heuristics can fragment discourse. Long-context prompting shifts token budgets toward irrelevant information without providing explicit signals for evidence sufficiency.
• C2: Uncontrolled Iteration and Latency: Agentic RAG systems that use multi-agent collaboration often suffer from "branchy" plans, repeated tool calls, and verbose reasoning chains. This leads to unpredictable token costs, high latency, and premature termination or wasted loops because the stopping criteria are often heuristic rather than evidence-based.
• C3: Heterogeneity Across Formats: Existing systems typically require distinct indices, retrievers, and prompt styles for text, tables, and Knowledge Graphs (KGs). This prevents policy reuse, complicates training, and often involves lossy serialization that obscures data provenance.

2. Methodology: The RELOOP Framework

RELOOP addresses these issues by introducing a Hierarchical Sequence (HSEQ) representation and a Guided, Budget-Aware Iteration mechanism. The framework consists of three core modules:

A. HSEQ-Adapter (HSEQ-A): Unified Reversible Parsing

The system first linearizes heterogeneous sources (text documents, relational tables, and KGs) into a single, reversible Hierarchical Sequence ($S_h$).

• Structure: Each data item is converted into a set of typed segments $s = (id, \ell, p, c, \mu)$, where:
  • $\ell$: Level tag (e.g., paragraph, table row, triplet).
  • $p$: Parent pointer (establishing hierarchy/containment).
  • $c$: Human-readable content snippet.
  • $\mu$: Metadata (source ID, offsets/coordinates, schema, time).
• Reversibility: This structure preserves provenance and allows for exact reconstruction of the original data, ensuring auditability.
• Unification: By standardizing formats into a sequence of segments with explicit locality and alignment, a single retrieval policy can operate across all modalities.

B. RELOOP-Iterator (RELOOP-I): Guided Budget-Aware Selection

Instead of a single pass or uncontrolled expansion, RELOOP employs a learned iteration policy ($\pi_\theta$) that operates on a sliding window of the HSEQ.

• Guidance Prior ($g$): A lightweight planner (Head Agent) or heuristic template generates a short guidance plan specifying initial targets, expansion rules (e.g., parent/child hops, row/column neighbors), and stopping conditions.
• Iterative Process:
  1. Selection: At each step $t$, the policy selects up to $k$ promising segments from a candidate window $C_t$.
  2. Expansion: It can expand the search via structure-aware operators (e.g., fetching all rows in a table if a cell is promising).
  3. Sufficiency Prediction: The policy predicts a binary signal $s_t \in \{0, 1\}$ indicating if the accumulated evidence $M_t$ is sufficient to answer the question.
  4. Termination: The loop stops when $s_t=1$ (sufficiency detected) or the budget (tokens/steps) is exhausted.
• Efficiency: This approach concentrates computation only on inspected evidence, avoiding the "explosion" of search space common in agentic systems.

C. RELOOP-Head (RELOOP-H): Synthesis and Refinement

• Answer Synthesis: Once iteration terminates, a canonicalizer ($\kappa$) packages the selected segments into a compact, provenance-preserving format. The Head module generates the final answer based only on this evidence.
• Refinement Loop: An optional verifier checks for contradictions. If detected, a brief refinement loop is triggered with tightened guidance and a reduced budget.

3. Key Contributions

1. Unified, Reversible Structured Parsing: The introduction of HSEQ, a format-agnostic representation that standardizes text, tables, and KGs into a single hierarchical sequence with lightweight structural tags. This enables a single learned policy to navigate diverse modalities without per-dataset specialization.
2. Guided, Budget-Aware Iteration: A learned selection policy with an explicit sufficiency signal. This allows the system to concentrate computation on necessary evidence, providing predictable latency and reducing unnecessary tool calls compared to unconstrained agentic loops.
3. Canonicalized Evidence for Reliable QA: A mechanism to package evidence that preserves provenance (IDs, offsets, source). This improves answer consistency, auditability, and enables optional contradiction-driven refinement.

4. Experimental Results

The framework was evaluated on four benchmarks covering different modalities:

• Text: HotpotQA (Multi-hop).
• Table+Text: TAT-QA (Financial), HybridQA.
• Knowledge Graph: MetaQA (2-hop and 3-hop).

Performance Highlights:

• Accuracy: RELOOP consistently outperformed strong baselines (including LLM-only, single-pass RAG, and specialized agentic RAG like Graph-constrained Reasoning and Think-on-Graph).
  • On MetaQA-3hop, RELOOP achieved 93.4% Accuracy and 88.3% F1, surpassing the next best baseline (AdaptiveRAG) by a significant margin.
  • On HotpotQA, it achieved 56.3% Accuracy, outperforming Graph-constrained Reasoning (39.2%) and Think-on-Graph (43.1%).
• Efficiency: RELOOP demonstrated a superior trade-off between accuracy and latency.
  • While "LLM-only" was fastest (1 step), it had poor accuracy.
  • "Think-on-Graph" required 11–17 steps and high latency (e.g., ~24k ms on MetaQA-3hop).
  • RELOOP achieved high accuracy with only 3–5 steps on average, reducing latency by more than 50% compared to graph-centric baselines while maintaining multi-hop capabilities.
• Ablation Studies: Removing the fine-tuned iteration policy (SFT) or the guidance mechanism caused significant performance drops, confirming the necessity of both the learned policy and the structured guidance.

5. Significance

RELOOP represents a paradigm shift in RAG architecture by moving away from "retrieve-all" or "uncontrolled-agentic" approaches toward structured, iterative, and budget-conscious reasoning.

• Scalability: By unifying modalities, it simplifies the deployment of QA systems across diverse data types.
• Reliability: The explicit sufficiency signal and provenance preservation make the system more robust against hallucinations and easier to audit.
• Efficiency: It proves that high-quality multi-hop reasoning does not require exhaustive search or massive token consumption; rather, it benefits from guided, small-step exploration.

The code and models are available to facilitate further research in heterogeneous retrieval and multi-hop reasoning.