💬 NLP

Can David Beat Goliath? On Multi-Hop Reasoning with Resource-Constrained Agents

The paper introduces David-GRPO, a reinforcement learning framework that enhances multi-hop reasoning in resource-constrained agents by combining off-policy expert bootstrapping with evidence-guided on-policy exploration to overcome the scarcity of useful training paths and achieve superior performance on multi-hop QA benchmarks.

Original authors: Hojae Han, Heeyun Jung, Jongyoon Kim, Seung-won Hwang

Published 2026-05-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hojae Han, Heeyun Jung, Jongyoon Kim, Seung-won Hwang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex mystery, like figuring out if two famous landmarks are in the same neighborhood. You have a small, smart assistant (a "small language model") who wants to help, but this assistant has a very tight budget. It can only ask a few questions to a librarian (the "retrieval tool") before it has to give an answer.

The problem is that most training methods for these assistants are like training a chess grandmaster by letting them play thousands of games against a supercomputer. That works great if you have a supercomputer, but our small assistant only has a few coins to spend on games. If you try to train it with so few games, it usually gives up, guesses randomly, or stops asking questions too early.

The authors of this paper, titled "Can David Beat Goliath?", propose a new training method called DAVID-GRPO. They call it "David" because it's designed for small, resource-constrained agents, while "Goliath" represents the massive, expensive training setups used by big tech companies.

Here is how DAVID-GRPO works, using simple analogies:

1. The Problem: The "Empty Room" of Learning

Usually, to teach an AI to solve multi-step puzzles, you let it try many times (rollouts) and reward it when it gets the right answer. But with a tiny budget, the AI tries a few times, fails to find the right clues, and gets no rewards. It's like a student trying to solve a math problem in a room with no books; they just guess, get it wrong, and stop trying. The AI gets stuck in a loop of failure.

2. The Solution: Two Special Tricks

DAVID-GRPO fixes this by using two clever strategies to make every single attempt count:

Trick A: The "Expert Cheat Sheet" (Expert Bootstrapping)
Instead of letting the AI start from zero, the researchers give it a tiny "cheat sheet." They take just four perfect examples of how an expert (a much smarter AI or a human) solved the problem.

The Analogy: Imagine you are learning to bake a cake but only have one recipe card. Instead of trying to invent a cake from scratch, you look at that one perfect recipe to get a head start.
How it helps: Even though the AI only sees these four examples, it uses them to jumpstart its learning. It doesn't just copy them; it uses them as a guide to understand what a "good" path looks like, preventing it from giving up immediately.

Trick B: The "Partial Success" Rescue (Evidence-Guided Exploration)
Sometimes, the AI gets part of the way there. It finds some clues but misses the final piece. In old methods, this attempt would be thrown away as a failure.

The Analogy: Imagine you are looking for a specific key in a messy house. You find the drawer where it might be, but you don't find the key itself. An old teacher would say, "You failed, start over." DAVID-GRPO says, "Great job finding the drawer! Let's stop right there and try looking in that specific drawer again with fresh eyes."
How it helps: The system checks how many clues (evidence) the AI found. If it found some but not all, it cuts the attempt short at the point where it was still doing well, and asks the AI to continue from there. This turns a "failure" into a "new attempt," saving precious time and money.

3. The Result: Small Budget, Big Wins

The researchers tested this on small AI models (about 1.5 billion parameters) using just four standard graphics cards (RTX 3090s).

The Comparison: They compared their method against other AI trainers that use massive budgets (thousands of GPUs and millions of attempts).
The Outcome: DAVID-GRPO managed to solve complex, multi-step questions (like "Who is the cousin of the person who wrote X?") almost as well as the expensive giants, but it used only 4.7% of the computing budget.
The Behavior Change: Without this method, small AIs often skip looking for clues entirely or stop after one quick search. With DAVID-GRPO, the small AI learns to dig deeper, gathering more evidence before answering, just like a real detective would.

Summary

In short, DAVID-GRPO is a training technique that allows small, cheap AI agents to learn complex reasoning tasks by:

Learning from a few expert examples to avoid starting from scratch.
Recycling partial successes instead of discarding them, ensuring every bit of effort counts.

It proves that you don't need a "Goliath" budget to train a "David" to solve hard problems; you just need a smarter way to use the resources you have.

Technical Summary: Can David Goliath? On Multi-Hop Reasoning with Resource-Constrained Agents

Problem Statement

The paper addresses the challenge of training small language model (SLM) agents to perform multi-hop reasoning (e.g., multi-hop Question Answering) under strict resource constraints. While Reinforcement Learning (RL) has successfully trained agents for complex tasks, existing approaches typically rely on high-cost settings involving large batch sizes and extensive on-policy rollouts (e.g., thousands of trajectories per update). These settings are inaccessible to researchers using commodity hardware (e.g., 4×RTX 3090 GPUs).

Under low-budget constraints (small batches, few rollouts), standard RL methods like Group Relative Policy Optimization (GRPO) face a critical bottleneck: each update contains too few useful trajectories from the current policy to form meaningful advantage estimates. Specifically, in multi-hop retrieval, an agent must accumulate multiple supporting documents (bridge evidence and answer evidence). With sparse rollouts, agents often fail to retrieve any useful evidence, leading to "policy collapse" where the agent receives zero rewards and cannot learn. Existing solutions fail in this regime:

SFT-based initialization overfits when annotated trajectories are scarce.
Retrieval-level rewards often assign credit to individual documents without optimizing the coverage of the full evidence set.
Rollout expansion (e.g., Tree-GRPO) wastes compute when expanding from prefixes that lack evidence-progress signals.

Methodology: DAVID-GRPO

The authors propose DAVID-GRPO, a budget-efficient RL framework designed to make small trajectory batches more informative by leveraging information from both outside and inside the current policy. The method consists of two core components:

1. Expert Bootstrapping (Off-Policy Injection)

To prevent early policy collapse when the agent's own exploration yields no rewards, DAVID-GRPO injects a small number of off-policy expert trajectories into the RL update group.

Mechanism: Instead of relying on thousands of annotated trajectories for Supervised Fine-Tuning (SFT), the method uses a "few-shot" expert trajectory pool ( $X_{inj}$ ) containing only $k$ examples (where $k \ll |X_{train}|$ ).
Integration: For a given input, the training group is constructed with one off-policy expert trajectory ( $\tau^*$ ) and $G-1$ on-policy trajectories sampled from the current policy ( $\pi_\theta$ ).
Objective: The loss function is modified to include a mixed objective where the expert trajectory is assigned a specific advantage to encourage imitation, while on-policy trajectories are updated via standard group-relative advantages. This provides a gradient signal even when the agent's exploration fails.

2. Evidence-Guided Exploration (On-Policy Reuse)

To address the issue of suboptimal batches where no trajectory achieves a perfect reward, the method introduces a denser reward signal and a mechanism to reuse partial successes.

Evidence-Coverage Reward ( $r_g$ ): Instead of relying solely on the final answer correctness ( $r_o$ ), the method calculates a reward based on the recall of the full support set $D$ within the cumulative set of retrieved documents $\hat{D}_{union}$ across the entire trajectory.
$r_g(\tau) = \frac{|\hat{D}_{union} \cap D|}{|D|}$
The total reward is a weighted sum: $R(\tau) = \lambda r_g(\tau) + (1-\lambda)r_o(\tau)$ . This encourages the agent to retrieve all necessary bridge and answer documents, not just the final answer.
Prefix Continuation: If the best trajectory in a batch is still suboptimal (i.e., incomplete evidence coverage), the method identifies the last step $t'$ where evidence coverage increased. It truncates the trajectory at $t'$ and resamples the continuation from the current policy. If the new continuation improves the reward, it replaces the worst trajectory in the batch. This effectively "recycles" promising prefixes to generate higher-quality examples without requiring additional full rollouts.

Key Contributions

DAVID-GRPO Framework: A novel RL framework that combines expert bootstrapping and evidence-guided exploration to enable multi-hop reasoning training on small models with limited compute.
Efficiency Gains: Demonstrates that small agents (up to 1.5B parameters) can learn complex multi-hop retrieval strategies using only 4.7% of the rollout budget required by high-cost baselines like Tree-GRPO.
Behavioral Shift: Shows that DAVID-GRPO learns to perform multiple retrieval actions and accumulate full evidence sets, whereas prior low-budget baselines often skip retrieval or stop after shallow searches.
Robustness: The method remains stable across different model sizes (0.5B to 1.5B) and generalizes to tool-use chains beyond Wikipedia-style QA (e.g., BFCL tool-use benchmarks).

Experimental Results

The authors evaluated DAVID-GRPO on six multi-hop QA benchmarks (HotpotQA, 2WikiMultiHopQA, MuSiQue, Bamboogle, BamTwoogle, and AntiLeakBench) using Qwen2.5 and Llama-3.2 models (0.5B and 1.5B parameters) trained on 4×RTX 3090 GPUs.

Performance vs. High-Budget Baselines: Despite using only 4.7% of the rollout budget of the high-cost Tree-GRPO baseline, DAVID-GRPO achieved higher Exact Match (EM) scores on 2WikiMultiHopQA, MuSiQue, and Bamboogle.
Performance vs. Low-Budget Baselines: Under the same low-budget constraints, DAVID-GRPO significantly outperformed other low-budget methods (Tree-GRPO, StepSearch, Search-R1-v0.3). For instance, on the 1.5B scale AntiLeakBench, it exceeded the second-best baseline by 19.6 percentage points in EM.
Retrieval Behavior: Analysis revealed that DAVID-GRPO agents performed 2–3 retrieval actions on average, successfully covering both bridge and answer documents. In contrast, baselines like Tree-GRPO often performed zero retrieval actions, relying on parametric knowledge.
Ablation Studies: Removing either expert bootstrapping or evidence-guided exploration components led to performance degradation, confirming the necessity of both mechanisms. The method also showed robustness when trained on "silver evidence" (generated questions paired with fixed answer-support pairs).

Significance and Claims

The paper claims that the primary bottleneck for small agents in multi-hop reasoning is not model size alone, but the lack of dense, evidence-level training signals under resource constraints. By introducing DAVID-GRPO, the authors demonstrate that:

Small agents can learn effective multi-hop retrieval strategies without dense rollout budgets.
Combining a few off-policy expert trajectories with on-policy evidence-guided reuse can stabilize training and improve sample efficiency.
This approach lowers the compute barrier for agent research, making it feasible for academic labs with commodity hardware to reproduce and extend agent capabilities previously limited to well-resourced organizations.

The authors conclude that their work provides a pathway to training capable retrieval agents on commodity hardware, though they note future work could further reduce dependence on retriever quality and corpus coverage.