Multi-hop questions such as "Who directed the film whose lead actor was born in Lisbon?" require a system to find one fact, use it to form the next search, and keep going. Today the best trainable systems for this are search agents fine-tuned with reinforcement learning (RL), where the model learns by trial and error from a reward for the final answer. These agents are trained on whole multi-step episodes, and that makes them expensive: every training step must generate a full chain of searches and reasoning token by token. They are also trained on whatever question shapes appear in the training set, and nobody has checked whether they handle new shapes, such as a 4-hop chain or a "both A and B" question, when they have only seen 2-hop chains.
We propose to run RL only on single-hop sub-questions, which are short and cheap to roll out, and to obtain multi-hop behavior by composition at test time. Each sub-question gets a small learned score, which we call its value: how likely a candidate entity is to correctly answer that sub-question given the evidence retrieved so far. A question is parsed into a small program of sub-questions. Values are combined with the min/max rules of Boolean task algebra from compositional RL, and the combined value decides which bridging entity to commit to and when to backtrack. The bet has two parts. First, this setup should match full-trajectory RL on familiar question shapes at a fraction of the rollout compute. Second, it should beat full-trajectory RL on question shapes held out from training.
Core Claim
Multi-hop retrieval has the structure compositional RL needs. Benchmarks like MuSiQue are built bottom-up from single-hop question pairs and come with six reasoning-graph shapes. That gives us the sub-tasks for free, along with natural held-out compositions. Our claim is that a goal-conditioned value over (evidence, sub-question, candidate entity), trained only from single-hop RL episodes and combined with min/max composition, gives two things. It gives a multi-hop agent whose training cost scales with the number of distinct hops rather than the length of full trajectories. It also gives a per-hop failure signal that stops the cascading errors of linear iterative retrieval without running test-time tree search. The claim is falsified if monolithic RL given the same rollout budget matches us on held-out shapes, or if plain decompose-then-retrieve with no value guidance matches us everywhere.
Where This Sits
Three bodies of work motivate the proposal.
The first is compositional RL. Nangue Tasse et al. define AND, OR and NOT over goal-conditioned ("extended") value functions and solve composite tasks zero-shot in Four Rooms. CERLLA uses an LLM to parse instructions into Boolean expressions over pretrained value functions, reaching 92% success in MiniGrid against 80% for a non-compositional baseline after 21M steps. Both are confined to grid worlds with predefined primitives. We reuse their composition operators and parse-then-compose recipe in a text-retrieval setting where the primitives, single-hop sub-questions, come directly from how the benchmarks were built. The linearly solvable formulations of Saxe et al. and Jonsson et al. constrain the design. They need passive dynamics and KL control costs that have no natural analogue over a document corpus, so we use the min/max algebra rather than additive desirabilities.
The second is RL for multi-hop retrieval. FrugalRAG trains a 7B model with supervised exploration followed by Group Relative Policy Optimization (GRPO, a critic-free policy gradient that baselines each sample against other samples for the same prompt) to learn when to stop searching. EVO-RAG uses a seven-factor reward and preference optimization to shorten retrieval chains. Both optimize whole trajectories and never test held-out compositional shapes. GRAT handles intermediate errors with Monte Carlo tree search, which costs a great deal at test time. IRCoT interleaves reasoning and retrieval by prompting, and Wang et al. document how early retrieval mistakes cascade.
The third body of work supplies a method. L-RAG shows that middle-layer hidden states encode next-hop information and that a small MLP on them is enough for retrieval, at about 2.8s per query against over 20s for iterative generation. We put our value head in the same place.
On cost, ProRL used about 16,000 H100 hours for a 1.5B model, and RL4LMs explains why sequential generation in the loop is the main expense. Both motivate cutting rollout length rather than model count.
Research Program
The agent is a small language model (Qwen-family, 1.5B and 7B) with a fixed dense retriever (E5 or ColBERT, as in FrugalRAG). For each sub-question it issues a search, reads the results, and proposes candidate answer entities.
Stage one: primitive RL. We run GRPO on single-hop sub-questions extracted from MuSiQue's decompositions, 2WikiMultiHopQA's Wikidata triples, and HotpotQA bridge and intersection components. The reward is correctness of the sub-answer plus a small search-count penalty. Episodes are one or two searches long.
The value head. A two-layer MLP reads a middle-layer hidden state of the frozen-but-current policy and regresses onto the GRPO group's empirical success rate for that sub-question and candidate. The group mean is a free Monte Carlo value estimate, so we never host a separate critic model.
Stage two: test-time composition. The same model, prompted in-context as in CERLLA, writes each question as a short program. Chain steps substitute an earlier answer into a later sub-question. AND, OR and NOT combine sub-questions about the same entity, and comparison applies AND over two chains followed by a symbolic comparison. Writing $V(s, q, e)$ for the head's value of candidate entity $e$ for sub-question $q$ under evidence state $s$, we compose:
$$V_{\text{AND}}(s,e)=\min_i V(s,q_i,e),\qquad V_{\text{OR}}(s,e)=\max_i V(s,q_i,e),\qquad V_{\text{chain}}(s,e_1,e_2)=\min\big(V(s,q_1,e_1),\,V(s,q_2[e_1],e_2)\big)$$
Negation follows Nangue Tasse et al. using the head's upper and lower value bounds, and $q_2[e_1]$ is the second sub-question with the first answer substituted in. The agent keeps a beam of two or three bridging candidates. It scores them in one batched forward pass of the head, expands the best, and backtracks to the next candidate when the composed value along the current path falls below a threshold tuned on development data. This is a value-guided beam, not tree search with rollouts. It is cheap because the head reads states the model has already computed.
The theory behind min/max composition assumes deterministic goal-reaching tasks with shared terminal states. Retrieval only approximates that, so we measure composition fidelity directly. For a sample of composite questions we train a head on the composite itself and compare its scores with the min/max-composed scores.
Baselines
The naive reference point is one-shot retrieval with the same base model: embed the question, take the top-k passages, and answer. Any method has to clear it on every split.
The zero-training reference is IRCoT prompting with the same base model and retriever. It is the strongest method that needs no training compute, and it is the obvious answer to "why train at all." We run it with matched maximum hops and report latency alongside accuracy.
The strongest training-based competitor is FrugalRAG-style full-trajectory GRPO. FrugalRAG reports 68.47% model-based evaluation (an LLM judge of answer correctness) on HotpotQA with 2.05 searches at 7B, against 64.20% for ReAct (FrugalRAG). We reimplement it on our model, retriever and training questions in two budgets. One uses the same number of training questions. The other uses the same total generated rollout tokens as our method, which is the comparison the cost claim depends on. Hyperparameter search gets the same number of trials as ours. Beating it means statistically equal accuracy on in-distribution shapes at no more than a third of its rollout tokens, and higher accuracy on held-out shapes at equal tokens.
For accuracy ceilings we cite GRAT. It reports 75.2% accuracy on 2WikiMultiHopQA with Llama3-70B, and 66.8% with Llama3-8B after self-training on 11,000 search trajectories, up from 60.6% (GRAT). We rerun GRAT's tree search at 7B with test compute reported in model calls, so that its accuracy-per-call can be compared with our beam. EVO-RAG reports gains of up to 4.6 exact-match points with 15% shallower retrieval but gives no per-dataset scalar we can use. On MuSiQue the only number in our file is L-RAG's 0.352 accuracy (L-RAG). No reported result was found on Lacuna for FrugalRAG, GRAT or EVO-RAG on MuSiQue specifically, nor for any method on Bamboogle.
Three ablations isolate the key ingredient. In the first, we run the same primitive-trained policy through the parsed program with no value head, committing to each sub-question's top answer and never backtracking. This is decompose-then-retrieve. In the second, we replace min/max over learned values with hard intersection of top-k candidate sets. In the third, an oracle head is trained on composites directly, which bounds what composition can achieve.
Why not just…?
Why not just decompose the question and retrieve each piece, with no RL or values? This is the most serious threat, and it is exactly our first ablation. Decomposition pipelines fail silently. When a sub-question gets a wrong bridge entity, nothing signals it, and the error cascades as Wang et al. and the IRCoT analysis describe. Our claim is that the composed value recovers some of those cases. We will report the fraction of first-hop-error questions in which backtracking fires and the final answer becomes correct. If the ablation matches us on accuracy, the value algebra is unnecessary, and the contribution narrows to "primitive RL is a cheaper way to train the per-hop policy." We would report that outcome as such.
Why not just run full-trajectory RL with a curriculum from short to long chains? EVO-RAG's staged curriculum and FrugalRAG's training are the natural version of this. A curriculum still pays for long rollouts in its later stages, and it still sees only the shapes present in training. The equal-token comparison on held-out MuSiQue shapes settles whether a curriculum buys the same generalization. If monolithic GRPO trained on 2-hop chains transfers to 4-hop chains as well as we do, our generalization claim is false.
Why not just distill search trajectories with supervised fine-tuning? GRAT shows that distilling tree-search trajectories helps (60.6% to 66.8% at 8B), and supervised training avoids generation in the loop entirely. But producing those trajectories required tree search, and FrugalRAG reports RL on about 1,000 examples matching baselines trained on far more data. We include a supervised baseline trained on teacher-generated decomposed traces, using the same sub-questions as our RL stage. That isolates whether RL on primitives matters or whether the decomposition alone does the work.
Proposed Experiments
The central experiment uses compositional splits. On MuSiQue-Ans we train on 2-hop questions and their single-hop components, and test on 3-hop and 4-hop shapes withheld entirely. On 2WikiMultiHopQA we hold out bridge-comparison questions, which compose a bridge with a comparison. On HotpotQA we evaluate the intersection subset separately as a test of AND, and we use Bamboogle as an adversarial out-of-distribution check. We report exact match and F1, model-based evaluation for comparability with FrugalRAG, and supporting-fact recall.
Every result is paired with three costs: generated rollout tokens and GPU-hours during training, peak accelerator memory, and searches and wall-clock latency per test query. Runs at 1.5B also address FrugalRAG's untested small-model regime.
Three checks decide the proposal. First, at equal rollout tokens, does primitive RL with composition beat monolithic GRPO on the held-out 3–4 hop shapes, while staying within one point on in-distribution 2-hop questions? Second, do min/max-composed values rank candidates in agreement with the oracle composite head, measured by rank correlation and by accuracy gap? A poor fit would mean the algebra's assumptions break for retrieval. Third, does value-guided backtracking beat the decompose-then-retrieve ablation on first-hop-error questions, at fewer model calls than GRAT-style search at the same model size? A positive answer to all three would show that multi-hop retrieval agents can be trained one hop at a time. A negative answer on the first, with positive answers on the others, would still give a cheap, interpretable failure detector for decomposition pipelines.
References
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- Logical Composition in Lifelong Reinforcement Learning
- Compositional Instruction Following with Language Models and Reinforcement Learning
- Hierarchy Through Composition with Multitask LMDPs
- Hierarchical Linearly-Solvable Markov Decision Problems
- FrugalRAG: Less is More in RL Finetuning for Multi-hop Question Answering
- Curriculum Guided Reinforcement Learning for Efficient Multi Hop Retrieval Augmented Generation
- GRAT: Guiding Retrieval-Augmented Reasoning through Process Rewards Tree Search
- Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions
- Optimizing Multi-Hop Document Retrieval Through Intermediate Representations
- ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models
- Is Reinforcement Learning (Not) for Natural Language Processing: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization