Reinforcement Learning with Verifiable Rewards for Small Search Agents

• At sub-1B scale, prior evidence described in the introduction found pure RL too unstable to bootstrap search from a cold start, recovering the behavior only with teacher distillation.Source: §1 · p. 2
• Whether reason-over-search transfers to a sub-1B model trained from its own initialization, and which reward shape best supports accuracy and stability, remains open.Source: §1 · p. 2
• The research questions address feasibility and generalization, held-out exact-match accuracy across reward shapes, and stability across seeds and training horizon.Source: §1 · p. 2
• The study trains Qwen3.5-0.8B with GRPO on MuSiQue and evaluates checkpoints on a held-out seven-benchmark question-answering suite.Source: §1 · p. 3
• The Search-R1-faithful exact-match-only reward was worst at every seed at the matched horizon, even on exact match, while dense token-F1 carried the gains.Source: §1 · p. 3

2.1 RL for LLM reasoning

• RLVR uses verifiable answer scoring in place of a learned reward model, while GRPO removes PPO’s value critic; this work moves the setting to open-domain QA and a sub-1B policy.Source: §2.1 · p. 3

2.2 Retrieval-augmented reasoning with tool use

• Prior reason-over-search methods interleave reasoning and retrieval; Search-R1 uses final-answer exact match, ReSearch uses token-F1 with a format floor, and other work adds per-step credit.Source: §2.2 · p. 4
• The controlled comparison addresses two gaps: sub-1B reason-over-search had been tested only with distillation, and prior recipes did not make reward shape their controlled variable.Source: §2.2 · p. 4

2.3 Reward shaping, and whether tricks help

• Earlier reward-shape evidence is mixed: token-F1 loses to exact match when answer avoidance occurs, while this paper’s floorless F1-only arm does not show that collapse at 0.8B.Source: §2.3 · pp. 4–5

2.4 Efficiency in agentic RL, and small-model post-training

• The paper varies only reward shape against a minimal plain-GRPO recipe, while prior efficiency work studies interventions or response length and small agentic-search evidence relied on distillation.Source: §2.3 · p. 5, §2.4 · p. 5

3.1 Problem setting

• A rollout alternates model generation with retrieval when a search query is completed, then ends with an answer, a limit, or end-of-sequence; one answer-based scalar reward is assigned per rollout.Source: §3.1 · p. 5
• Retrieved passages are tool inputs rather than model outputs, so they are excluded from the training loss, and no intermediate step receives a score.Source: §3.1 · p. 5

3.2 Group Relative Policy Optimization

• GRPO replaces PPO’s learned value critic with a baseline from the mean and standard deviation of rewards across the same question’s rollout group.Source: §3.2 · pp. 5–6
• When most rollouts in a group receive the same score, their advantages approach zero, reducing that group’s contribution to the gradient even if many answers are wrong.Source: §3.2 · p. 6

4 Method

• The training pipeline uses a critic-free GRPO loop whose reward node branches into three ablated reward shapes.Source: §4 · p. 6, Figure 1 · p. 7

4.1 Rollout construction and loss masking

• The rollout interface uses Qwen3.5-native tool tags, masks retrieved tokens from the loss, and shares prompt and scoring code between training and evaluation.Source: §4.1 · p. 6

4.2 The three reward shapes

• The three rewards span sparse-to-dense feedback, with EM-only and F1+format anchored to published recipes and F1-only isolating the floor’s contribution.Source: §4.2 · pp. 7–8
• The ablation compares sparse exact match, token-F1 alone, and token-F1 with a 0.1 format floor; the floor replaces F1 when F1 is zero rather than adding a bonus.Source: §4.2 · pp. 7–8

5 Experimental Setup

• Nine runs vary only reward shape across three seeds, holding the model, training data, prompt, retriever, and optimizer settings identical.This makes the comparison paired within seed and isolates reward shape from the other shared recipe components.Source: §5 · p. 8

5.1 Model, data, and retrieval

• Training uses Qwen3.5-0.8B on MuSiQue; evaluation covers seven benchmarks, six strictly out-of-distribution, with 51,713 rows per checkpoint.MuSiQue is a 2-to-4-hop dataset; the held-out suite includes single-hop, 2-hop, and 2-to-4-hop benchmarks.Source: §5.1 · p. 8
• Retrieval uses Wikipedia-2018 with E5-base-v2 through FlashRAG and a quantized IVF4096-SQ8 index; the study uses top-5 retrieval.The authors report observed recall@10 at 96 to 99% of the flat index during bringup, explicitly an engineering observation rather than a logged experiment.Source: §5.1 · p. 8

5.2 Training configuration

• Training uses five rollouts per question, and generation is capped at 10 turns and 8192 tokens.The token cap often binds early and is discussed as central to the later analysis; full-epoch runs cost roughly $120 to $140 of rented compute each.Source: §5.2 · p. 9

5.3 Horizon, seeds, and evaluation protocol

• Each seed is capped at 180, 230, or 312 steps, and cross-seed comparisons use the common horizon of step ≤180.Runs were length-bounded by the compute grant rather than stopped for performance; the authors also report best checkpoints within each seed’s own horizon separately.Source: §5.3 · p. 9
• Every checkpoint is evaluated with greedy decoding; reported metrics are unweighted macro-averages over seven benchmarks, selected on the same suite without a separate validation split.The primary metrics are EM and token-F1, with substring-cover accuracy as a more lenient check.Source: §5.3 · p. 9

6.1 Feasibility below one billion parameters (C1)

• 0.352 average EM versus the 0.092 untrained floor is the best run’s result, a 3.8-fold gain on a held-out suite after MuSiQue-only training.The best run was still improving at the budget horizon, so the authors describe 0.352 as a conservative lower bound rather than a converged ceiling.Source: §6 · p. 9, Table 1 · p. 10, §6.1 · p. 10

6.2 The reward-shape ablation (C2)

• At the matched horizon, EM-only ranks last at all three seeds and has the widest seed range, 0.052.The authors report an exact one-sided ranking probability of 1/27 under the stated exchangeability null, but also give conservative alternatives because the direction was not pre-registered.Source: §6.2 · pp. 10–11
• EM-only is lowest on all three matched-horizon metrics: EM 0.271, F1 0.340, and ACC 0.300.The comparison uses the same predictions at each run’s best-EM checkpoint; the authors note that the metric orderings are not independent evidence.Source: §6.2 · p. 11
• F1+format wins seeds 42 and 43, while F1-only wins seed 44; F1+format has the tightest seed range and F1-only the highest endpoint, 0.352.The practical choice is described as a trade-off, with the stability advice qualified by only three seeds and the ceiling coming from one full-epoch seed.Source: §6.2 · p. 11

6.3 A proposed mechanism for the exact-match deficit

• A proposed explanation is that sparse exact-match rewards leave most group rollouts equally scored at zero, whereas token-F1 separates wrong answers by partial overlap.Per-group reward variance was not logged, so the proposed mechanism is not directly tested; EM-only also has the lowest gradient norm at every seed, without evidence of divergence.Source: §6.3 · p. 12
• On multi-hop benchmarks, completed rollouts peak at two searches, and EM-only is strongest at that peak, but its abort rate is 22.8% versus 12.7% for F1-only and 5.0% for F1+format.Because aborted rollouts score zero, the authors read the deficit as more consistent with failure to terminate than uniformly worse completed answers, while treating the curves as descriptive.Source: §6.3 · p. 13

6.4 Emergent compression, and its reward dependence

• Both F1 shapes reduce the length-clip ratio to about 1% by each leg’s end, while EM-only ends at 9.7%, 14.1%, and 35.6% across seeds 42, 43, and 44.The authors hypothesize that the 8192-token cap acts as an implicit length penalty; the evidence is correlational, and they lacked a base-model control to separate model prior from cap effects.Source: §6.4 · pp. 13–14

6.5 A higher training reward is not more exact matches

• At seed 44, F1+format reaches the highest training reward, 0.358, but the lowest training-time exact-match rate, 20.5%.The authors therefore rank on held-out EM rather than comparing training reward scalars across shapes; they also report bridge-entity resolution as a residual failure mode no shape fixes.Source: §6.5 · p. 14

7 Limitations and Future Work

• Results cover one model family and size, with no cross-architecture or cross-scale validation; one training dataset also leaves reward effects entangled with the training distribution.The authors note they did not ablate data diversity.Source: §7 · p. 14
• The matched horizon is 180 steps, about 0.58 of an epoch, and several runs were still improving, leaving a sparse-reward slow-start explanation open.Seed-44 EM-only’s late recovery to 0.318 fits that alternative reading.Source: §7 · p. 14
• Three seeds do not provide tight variance estimates, leaving the seed-44 inversion between the two F1 shapes unresolved.The authors report that three seeds suffice for an exact test of the headline last-place ranking, but not tight variance estimates.Source: §7 · p. 14
• Checkpoint selection on the reported suite inflates cell scores potentially unevenly; the authors say an independent selection rule would most strengthen the result.Each cell is the best of roughly 18 to 31 evaluations, with no held-out validation split.Source: §7 · p. 15
• Untested confounds include group size rather than reward density; there is no supervised control, and reasoning-chain quality has no human or judge-based evaluation.The group size is G = 5.Source: §7 · p. 15
• Follow-ups include a same-generation control, a run at 2B parameters or above, semantic-similarity rewards, and retrieval-side changes to the ceiling.These tests target model generation versus parameter count, reward-shape behavior across scale, and retrieval-side limits.Source: §7 · p. 15

8 Conclusion

• 0.271 to 0.307 average held-out EM at the matched horizon, versus a 0.092 untrained floor, rises to 0.352 in the best run without distillation.The evaluation covers seven benchmarks, six never trained on.Source: §8 · p. 15
• At the matched horizon, exact-match-only ranks worst at every seed, including on EM, while F1+format favors seed robustness and F1-only the ceiling.The ordering between the two partial-credit shapes is seed-dependent.Source: §8 · p. 15

A Per-seed Held-out Trajectories

• Seed 42’s held-out EM trajectories show F1+format leading, with all three reward shapes clearing the 0.092 floor early.Source: Figure 2 · p. 20
• Seed 43’s held-out EM trajectories show F1+format as most stable and F1-only collapsing over steps 130 to 190.Source: Figure 3 · p. 20
• Seed 44’s full-epoch trajectory shows F1-only reaching 0.352 at step 310, while EM-only rises late.Source: Figure 4 · p. 21

Training dynamics

• Figures 6–8 show per-seed training dynamics, with the seed-42 and seed-43 runs capped at steps 180 and 230.The plots overlay reward, tool calls, response length, total tokens, and length-clip ratio, using moving averages over raw per-step series.Source: B Training Dynamics · p. 21, Figure 6 · p. 22, Figure 7 · p. 22
• At the matched horizon, F1 shapes reduce tool calls and response length as reward climbs, whereas EM-only remains highest on tool calls.Reward levels are not comparable across shapes; the reported interpretation rests on within-shape trends.Source: Figure 5 · p. 21, B Training Dynamics · p. 21
• In seed 44, reward climbs while tool calls, response length, total tokens, and clip ratio fall for the F1 shapes, while EM-only stays high.The full-epoch leg is shown through its last full cadence at step 310.Source: Figure 8 · p. 23

C Emergent-compression Detail

• Reward anti-correlates with the length-clip ratio across F1 runs, but the predicted weakening for EM-only is clear only at seed 44.At seed 42, EM-only sits inside the F1 range; reading its full 211 steps instead of its 180-step cap gives −0.33, outside that range.Source: C Emergent-compression Detail · p. 24
• In seed 44, the F1 shapes compress on every Table 2 axis, while EM-only leans mid-horizon and then re-enters over-search.Per-rollout response length is not shown because it does not move in one direction across shapes.Source: Table 2 · p. 24

D Held-out Bars and Metric Robustness

• EM-only is lowest on held-out EM, token-F1, and substring accuracy, and has the shortest EM bar at every seed under the same step ≤180 cap.The two F1 shapes are close and higher across all three metrics.Source: Figure 10 · p. 25, Figure 9 · p. 25

E Cross-generation Context

• The Qwen2.5-3B reproduction moves from a 0.199 untrained floor to 0.341 trained, versus 0.092 to 0.352 for this model, but the 1.1-point endpoint gap is within reproduction error.The settings differ in model, generation, corpus, reward, and recipe, so this comparison does not isolate an effect of parameter count.Source: E Cross-generation Context · p. 26

F Training-health Diagnostics

• For seed 42, gradient norm stays bounded; approximate token-level entropy declines for the F1 shapes while EM-only remains pinned high.The plotted diagnostics also include loss, KL divergence, aborted ratio, and natural-termination rate.Source: F Training-health Diagnostics · p. 26, Figure 11 · p. 27

G Worked Rollout and Loss Masking

• The schematic two-hop rollout interleaves reasoning with native tool calls and retrieved passages, while the GRPO loss is computed only on model-generated tokens.The transcript is illustrative, not a verbatim MuSiQue trace.Source: G Worked Rollout and Loss Masking · p. 27, Figure 12 · p. 28

H Held-out Search-count Profile and the Termination Gap

• At each shape’s held-out peak of two searches, completed-rollout EM is 0.378 for F1-only, 0.341 for F1+format, and 0.386 for EM-only, while EM-only aborts more often.Abort rates are 22.8% for EM-only, 12.7% for F1-only, and 5.0% for F1+format; the search-count profile is descriptive, not causal.Source: H Held-out Search-count Profile and… · p. 29, Figure 13 · p. 29

I Training Configuration

• All nine runs use Qwen3.5-0.8B with GRPO on MuSiQue, with reward shape and seed as the only varied axes.The setup uses 19,968 training prompts, Wikipedia-2018 retrieval, and checkpoints saved every 10 steps.Source: I Training Configuration · p. 30
• Three legs are truncated to their seed caps; restoring the seed-43 F1+format step-250 score of 0.317 would widen its margin over the reported 0.313.The two truncated EM-only legs do not affect their reported cells because their best checkpoints fall inside the caps.Source: I Training Configuration · p. 30

J Supporting Tables

• Tables 4 and 5 report token-F1 and substring-cover accuracy, respectively, under different checkpoint-selection rules and horizons.The table captions state that EM-only is worst on substring-cover accuracy as well.Source: J Supporting Tables · p. 30, Table 4 · p. 31, Table 5 · p. 31
• Table 3 reports per-benchmark EM, with MuSiQue the sole in-distribution set and the other six out-of-distribution.TriviaQA is highest everywhere at about 0.48 to 0.53, while MuSiQue is lowest at about 0.07 to 0.16.Source: Table 3 · p. 30, J Supporting Tables · p. 30