SPADER: Step-wise GRPO with Diversity-Aware Rewards Boosts Long-Tail Answer Discovery in Multi-Answer QA

Problem: Multi-Answer QA Requires Exhaustive Coverage

Large language models are shifting from single-turn Q&A to iterative search-answer loops. However, most existing work focuses on single-answer tasks. Real-world information needs often require multi-answer QA : the system must retrieve a complete set of valid entities. For example, the question "List all global launch sites with successful orbital launches in 2021" has a highly skewed answer distribution: head entities like Kennedy, Vandenberg, and Jiuquan are easily found, while tail entities such as PSCA and Spaceport hide in obscure corners of the knowledge space and demand persistent multi-round exploration.

Two Misalignments in Current RL Approaches

Issue 1: Coarse Credit Assignment on Long Trajectories

Long search trajectories make credit assignment difficult. Existing methods have limitations:

PPO (actor-critic) : Relies on a value network to estimate per-step long-term returns; estimation errors accumulate over long horizons, leading to unreliable credit assignment, expensive and unstable training.

GRPO (critic-free) : Removes the critic for better stability, but advantage remains at the trajectory level — a winning trajectory gives no signal about which intermediate search steps were effective.

Intermediate-step reward methods (R3-RAG, StepSearch) : Use PRM-style step scoring but depend on external evaluators or process annotations, and still optimize with trajectory-level GRPO advantage, providing no true step-level credit signal.

State-matching approaches (GiGPO, SALT) : Achieve step-level credit via strict state matching, but multi-answer QA observations are inherently noisy and diverse, making exact state matching impractical.

Issue 2: Reward Misalignment with Coverage Objective

F1-based rewards treat every entity equally, offering no extra incentive for hard-to-retrieve tail entities. Moreover, no signal tells the agent whether to continue searching or stop. Consequently, agents settle for easy head entities and terminate prematurely.

Method: SPADER Framework

SPADER (Step-wise Peer Advantage with Diversity-Aware Exploration Rewards) addresses both misalignments with two complementary components.

Component 1: SPA — Step-wise Peer Advantage

Built on GRPO's grouping mechanism: for each prompt, sample G parallel trajectories. SPA refines advantage from trajectory-level to step-level in four steps:

Decision-step alignment : Model search as an MDP where at state S_t the agent takes action a_t ∈ {Search, Answer}. At decision step t, the group of sampled trajectories forms a baseline conditioned on the same prompt and interaction round, without assuming semantic or state equivalence across trajectories. Trajectories that terminate early are padded to the group's maximum length L_max with future return 0, and a validity mask M_t (1 for t ≤ L_i, 0 otherwise) masks gradients after termination.

Future return estimation : Use Monte Carlo to estimate the discounted cumulative future return for trajectory i at step t, summing from step t to the trajectory's actual termination step.

Group baseline and step-level advantage : Compute the mean μ_t and standard deviation σ_t of future returns across the group at step t. The step-level relative advantage is A_t(i) = (R_t(i) - μ_t) / (σ_t + ε). Steps that beat the group expectation get positive advantage; those that fall short get negative advantage.

Training objective : Replace the trajectory-level advantage in the GRPO objective with A_t(i), perform importance sampling and clipping per decision step, and add KL regularization — yielding step-wise GRPO . No parametric value network or external evaluator is required.

Component 2: Dual-Axis Exploration Rewards

Good credit assignment alone is insufficient if the reward does not value tail entities. SPADER splits rewards into two phases: search-phase dual-axis exploration rewards and final answer-phase global evaluation reward.

For each newly discovered valid entity e at a search step, the reward combines two orthogonal dimensions:

Lateral information gain U_gain(e) : Base utility of retrieving a valid new entity, defined as constant 1.

Longitudinal novelty premium U_novelty(e) : A reward dilution mechanism. Let N(e, T) be the number of trajectories in the group that retrieved e. Then U_novelty(e) = 1 / N(e, T), inversely proportional to group-level retrieval frequency.

This design directly aligns with the coverage goal: head entities discovered by most trajectories (N ≈ G) suffer severe novelty dilution, leaving only the base gain α; unique tail discoveries (N = 1) receive the maximum reward α + β.

Each search step also incurs a fixed tool cost, normalized by the ground-truth answer set size |E_GT| to stabilize gradients. The tool cost makes "continue searching" non-free: when expected novelty reward no longer outweighs accumulated search cost, the agent naturally stops. Combined with a terminal answer reward (format violation = -1, otherwise final F1), the decision of when to continue and when to terminate emerges from the reward structure without hand-crafted search-round limits.

Experimental Results

Main Experiment: Consistent Gains Across Four Benchmarks and Two Base Models

Evaluated on Llama3.1-8B and Qwen3-8B against three baseline categories: prompting methods (RAG, ReAct), outcome-supervised RL (PPO, GRPO), and step-level supervision (R3-RAG, StepSearch). SPADER achieves the highest F1 on all four datasets with both base models. On QAMPARI, it improves up to 86.1% over PPO and GRPO, and consistently outperforms step-level baselines R3-RAG and StepSearch.

Ablation: Both Components Are Essential

Ablation on Qwen3-8B (retrained with one component removed) shows:

Removing SPA causes steady performance drop, confirming the value of step-level credit assignment.

Removing novelty premium leads to widespread degradation, proving it is critical to prevent early collapse to high-frequency entities.

Removing information gain biases the policy toward "rare but useless" entities, showing the two reward axes must be balanced.

Search Efficiency: No Excessive Exploration for Coverage

Average searches per valid entity retrieved (Qwen3-8B): SPADER remains competitive. Methods with fewer searches have lower recall (they stop after head entities); GRPO searches the most but achieves the worst recall, stuck in redundant searches. SPADER finds more valid entities with roughly the same search budget.

Temporal Dynamics: Exploration Persists Until Targets Are Exhausted

Tracking cumulative distinct valid entities per interaction round on QAMPARI: GRPO and ReAct converge prematurely after round 1; StepSearch extends search to later rounds; SPADER maintains the highest cumulative yield throughout the trajectory, plateauing only when no new entities remain. This demonstrates the agent learns when to continue and when to stop directly from the reward structure.

Conclusion

For multi-answer QA's "find all" objective, existing RL tool-augmented agents suffer from two misalignments: trajectory-level credit assignment and reward-coverage misalignment. SPADER responds with two components: SPA aligns parallel trajectories at each decision step, refining GRPO from trajectory-level to step-level using peer returns as baseline, achieving critic-free, evaluator-free step-level credit assignment; diversity-aware exploration rewards combine lateral information gain as a floor with longitudinal novelty premium that dilutes head entities, while tool costs and terminal settlement let the continue-vs-stop decision emerge naturally. Main experiments, ablations, efficiency analysis, and temporal dynamics consistently show that gains come from finer-grained training signals, not from more search steps.

Paper: https://arxiv.org/abs/2606.00593 Code: https://github.com/KhanCold/spader Model:

https://huggingface.co/KhanCold/qwen3-8b-spader