PaperlayerView exact revision on arXiv

Source-linked AI summary

TIPS: Turn-Level Information-Potential Reward Shaping for Search-Augmented LLMs

Yutao Xie, Nathaniel Thomas, Nicklas Hansen, Yang Fu, Li Erran Li, Xiaolong Wang

arXiv:2603.22293v1cs.CLcs.AIcs.LG

TL;DR

Multi-turn search-augmented RL for QA suffers from sparse terminal rewards and difficult credit assignment across reasoning and tool calls. TIPS assigns turn-level information-potential rewards based on changes in answer likelihood and integrates them with potential-based shaping. It consistently improves QA performance and training stability over PPO and GRPO, while retaining a scope boundary around PPO-based training and introducing modest computational overhead.

  • Problem

    Sparse terminal rewards make it difficult to identify which intermediate reasoning and tool-use turns improved the final answer, producing unstable credit assignment in multi-turn QA.

  • Method

    TIPS models trajectories as segment-level MDPs and rewards each turn according to its change in teacher-policy likelihood for an acceptable answer, using potential-based reward shaping.

  • Results

    Across eight QA benchmarks, TIPS consistently outperforms PPO and GRPO with more stable training; on Qwen-2.5-7B Instruct, average EM and F1 improve by over 10% relative to PPO.

  • Takeaways & Limitations

    Turn-level information shaping is an effective, lightweight alternative to token-level process supervision for training tool-using agents under sparse terminal rewards.

  • Takeaways & Limitations

    TIPS has modest computational overhead and is currently tied to PPO; its policy-invariance analysis also assumes episodic returns with γ = 1 and shaping confined to segment boundaries.

Abstract

from arXiv · show

Search-augmented large language models (LLMs) trained with reinforcement learning (RL) have achieved strong results on open-domain question answering (QA), but training still remains a significant challenge. The optimization is often unstable due to sparse rewards and difficult credit assignments across reasoning and tool calls. To address this, we introduce Turn-Level Information Potential Reward Shaping (TIPS), a simple framework that assigns dense, turn-level rewards to each reasoning + tool-call segment based on the increased likelihood of the correct answer under a teacher model. By leveraging the potential-based reward shaping, TIPS offers fine-grained and policy-invariant guidance that overcomes the limitations of outcome-only optimization. Evaluated on seven QA benchmarks, TIPS consistently outperforms GRPO/PPO baselines and substantially improves training stability. For instance, with a Qwen-2.5 7B Instruct model, TIPS improves the average Exact Match score by 11.8% and F1 by 13.6% relative to PPO. Our results demonstrate that turn-level information-potential reward shaping provides an effective and general solution to sparse-reward credit assignment for multi-turn LLM reasoning.

1 INTRODUCTION

TIPS addresses unstable, sparse-reward training for multi-turn search agents by assigning information-based credit at turn boundaries and integrating it with policy-invariant reward shaping. Across QA benchmarks, it improves performance and training stability over PPO and GRPO baselines.

  • Motivation: Outcome-only rewards create severe credit-assignment problems because intermediate reasoning and tool decisions receive feedback only after the final answer.Tool calls change the information state, and many distinct trajectories can produce the same terminal outcome.
  • Motivation: Prior densification methods often require intermediate labels or additional reward-model training, while tool-use interactions are naturally organized around reasoning–action–observation turns.The paper identifies a need for feedback that is discriminative, lightweight, and compatible with standard RL fine-tuning.
  • TIPS: TIPS measures each turn’s incremental increase in the likelihood of the gold answer, assigning positive credit to helpful turns and small or negative credit to unhelpful ones.This converts outcome-only supervision into dense feedback targeting information acquisition during tool use.
  • TIPS: TIPS represents interactions as a segment-level MDP and uses potential differences for turn-level reward shaping, preserving optimal policies under standard conditions.The information credit is interpreted as potential-based reward shaping rather than a replacement objective.
  • Results: Across eight QA benchmarks, TIPS consistently improves over PPO and GRPO while reducing training variance and collapse or drift failures.On Qwen-2.5-7B Instruct, average EM and F1 improve by over 10% relative to PPO, with larger margins over GRPO.

2 PRELIMINARIES

The paper formulates search-augmented QA as an LLM interaction with iterative reasoning, retrieval, and answer extraction, then describes token-level on-policy RL baselines. PPO uses clipped importance ratios and a learned value baseline, while GRPO normalizes sequence-level rewards without a critic.

  • Problem formulation: The search agent receives a question and iteratively reasons, issues natural-language retrieval queries, and uses returned passages to produce a tagged final answer.Evaluation extracts the answer inside <answer> tags and compares it with a small gold answer set using EM or F1.
  • Token-level MDP: The token-level MDP treats the generated prefix as the state and the next sampled token as the action, appending retrieval observations when triggered.The episode ends at EOS, with correctness determining the final reward and all other tokens receiving zero reward.
  • On-policy RL: PPO trains the policy against a snapshot of the old policy using clipped importance ratios and a learned value baseline.The supplied passage introduces PPO as an on-policy RL baseline for LLMs.
  • On-policy RL: GRPO removes the critic by normalizing terminal rewards across groups of rollouts, while a binary response mask excludes non-trainable tokens.The normalization uses the group mean and standard deviation of sequence-level rewards.

3 METHOD

TIPS addresses high-variance credit assignment in multi-turn tool use by rewarding turns according to how much they increase the teacher’s likelihood of a correct answer. It frames these rewards as potential-based shaping at turn boundaries, densifying feedback while preserving policy preferences under the terminal reward.

  • Motivation: Turn-level credit assignment is difficult because sparse terminal rewards do not reveal which intermediate tool calls improved the information state.Different turn sequences can produce the same outcome, while a single early mistake may determine failure.
  • Turn-level information rewards: TIPS scores each reasoning–tool-call–observation turn by the change in a frozen policy snapshot’s log-probability of generating a correct answer.Relevant evidence raises the teacher’s confidence, whereas redundant or off-topic queries may leave it unchanged or shift probability toward incorrect answers.
  • Turn-level information rewards: Each turn’s reward ∆k is the change in answer potential between successive dialogue contexts, with positive values indicating movement toward valid answers.The potential summarizes the teacher’s likelihood that the current context will yield any correct answer.
  • Turn-level information rewards: The information reward can be interpreted as a scaled pointwise mutual-information signal between new evidence and answer correctness under the teacher.This interpretation reflects the intended role of each tool call as incremental evidence for QA.
  • Potential-based reward shaping: TIPS treats each whole turn as one action in a segment-level MDP and injects potential differences at segment boundaries.The construction matches standard potential-based reward shaping.
  • Potential-based reward shaping: Under episodic returns with γ = 1 and boundary-confined shaping, shaped returns differ from outcome-only returns by a state-dependent constant independent of within-turn actions.Therefore, actions that are relatively better under the original outcome reward remain relatively better after shaping.
  • Potential-based reward shaping: Because every token in a turn receives the same pre-turn-state offset, TIPS densifies learning signals while preserving the optimal policy under the terminal reward.The framework refreshes the teacher periodically; with approximate critics, this can cause small shifts in raw returns.

4 EXPERIMENTS

Across in-domain and out-of-domain QA experiments, TIPS consistently outperforms PPO and GRPO while producing more stable training. Its gains are strongest for larger models and multi-hop tasks, with modest teacher-scoring overhead.

  • 4.1 MAIN RESULTS: TIPS consistently outperforms PPO and GRPO across in-domain and out-of-domain QA settings.The largest absolute improvements occur on multi-hop out-of-domain tasks, while 3B gains are more modest than 7B gains.
  • 4.2 ANALYSIS: TIPS climbs steadily to an EM plateau of approximately 0.55-0.60 with low variance, whereas GRPO collapses around steps 320–350 and PPO stagnates after 400 steps.
  • 4.1 MAIN RESULTS: Across five models and multiple scales, TIPS improves relative EM by +7.3% to +34.0% and F1 by +6.1% to +29.3% over outcome-only PPO.Teacher scoring adds approximately 11.7% per-step FLOPs across the evaluated architectures.
  • 4.2 ANALYSIS: TIPS rises smoothly and stabilizes across benchmarks, while PPO shows drift, especially on multi-hop QA, with mid-training degradation and only partial recovery.
  • 4.2 ANALYSIS: TIPS produces concentrated positive advantages in a clean bimodal distribution, whereas PPO exhibits fat-tailed positives and dense near-zero mass associated with instability and drift.This distribution provides a mechanistic explanation for TIPS suppressing late-stage drift and collapse.
  • 4.2 ANALYSIS: TIPS adds about 12% relative FLOPs to PPO, compared with roughly 3.5× PPO FLOPs for GRPO.Measured wall-clock overheads are 18% for Qwen2.5-3B and 16% for Qwen2.5-7B.
  • 4.3 ABLATIONS: For PPO, turn-level information gain consistently outperforms outcome-only supervision, while history-max gating weakens results.Rule-based and rubric-based dense rewards provide only minor gains or little improvement in the compared settings.
  • 4.3 ABLATIONS: A broad teacher-refresh optimum appears around N=200; fixed refresh at N=500 performs worse, although all N ∈[100, 500] settings outperform outcome-only PPO.

5 RELATED WORK

Prior work addresses credit assignment in LLM reasoning, tool use, and verification, but TIPS focuses on attributing reward across multiple tool segments using verifiable answer-likelihood changes.

  • Outcome-only rewards provide little guidance about which intermediate segments caused success or failure during long-horizon LLM reasoning.
  • Tool-use QA introduces turn-level interventions whose retrieval, search, or execution results can change the agent’s information state.
  • TIPS generalizes turn-level credit assignment across multiple tool segments by allocating reward according to each segment’s marginal contribution to gold-answer likelihood.
  • Unlike judge-based feedback, TIPS uses a frozen reference language model to provide verifiable, likelihood-based increments toward the gold answer.

6 CONCLUSIONS

TIPS addresses brittle search-augmented RL by applying turn-level information shaping within a segment-level MDP. Across the reported benchmarks and model sizes, it improves QA metrics over PPO and GRPO while training more stably, although it adds computational overhead and is currently tied to PPO.

  • TIPS uses a segment-level MDP and turn-level information shaping to address brittle optimization in search-augmented QA reinforcement learning.
  • TIPS improves EM and F1 over PPO and GRPO across seven benchmarks and two model sizes while training more stably.
  • The method’s reported limitations are modest computational overhead and current integration only with PPO.

A DATASETS

The evaluation spans standard and challenging open-domain QA datasets covering retrieval, factual knowledge, explainable multi-hop reasoning, compositional reasoning, and search-agent performance. BrowseComp-Plus provides a fixed-corpus setting for controlled comparison, where TIPS consistently outperforms PPO/GRPO and a 4B TIPS agent surpasses a 32B SEARCH-R1 baseline.

  • Natural Questions: Natural Questions contains real anonymized Google queries paired with Wikipedia pages and long-answer, short-answer, or yes/no annotations.Its public release includes 307,000 training, 8,000 development, and 8,000 test examples.
  • TriviaQA: TriviaQA evaluates open-domain question answering using diverse trivia questions, multiple evidence documents, and answer-extraction targets.The dataset contains over 95,000 question–answer pairs and more than 650,000 question–answer–evidence triples.
  • PopQA: PopQA tests popular and long-tail factual knowledge with entity-centric questions generated from Wikidata triples and popularity metadata.Its approximately 14,000 English QA pairs support controlled analysis of retrieval bias and factual memorization versus retrieval.
  • Multi-hop QA: HotpotQA, 2WikiMultiHopQA, and MuSiQue evaluate multi-hop reasoning through supporting facts, structured reasoning paths, or decomposed single-hop steps.These datasets cover comparison, inference, compositional, bridge, and 2–4-hop reasoning settings.
  • Bamboogle: Bamboogle is a compact 125-question benchmark of hand-crafted two-hop questions designed to stress-test compositional reasoning without exploitable artifacts.
  • BrowseComp-Plus: TIPS consistently improves over PPO and GRPO on BrowseComp-Plus, and a 4B TIPS agent surpasses the 32B SEARCH-R1 baseline.
  • BrowseComp-Plus: BrowseComp-Plus replaces dynamic live web search with a fixed curated corpus, shared retriever, human-verified supporting documents, and mined hard negatives.

C ANALYSIS OF TEACHER SELECTION

TIPS evaluates teacher models through answer log-likelihoods, with the main experiments using a periodically refreshed frozen policy copy. The ablation indicates that behavioral alignment with the current policy matters more than raw teacher strength.

  • TIPS defines its potential from teacher-model log-likelihoods over valid answers and periodically refreshes a frozen copy of the policy.
  • Across Qwen2.5-7B and Qwen3-4B, the frozen policy teacher is clearly strong compared with alternative teacher choices.
  • Teachers that differ behaviorally from the policy can make answer-likelihood increases noisy or adversarial signals for the current policy.

D ANALYSIS OF α SELECTION

The shaping scale α controls the balance between turn-level information rewards and terminal outcomes. Fixed and dynamic procedures favor a medium regime that keeps information rewards substantially below the terminal reward.

  • Fixed α: α controls the relative weight between information rewards and terminal outcome rewards.Changing α rescales returns and advantage variance without changing within-turn action preferences.
  • Fixed α: If α is too small, TIPS approaches outcome-only PPO; if too large, teacher-derived shaping can dominate and increase gradient variance.The paper recommends keeping the information reward clearly below the terminal reward of 1.0.
  • Fixed α: A fixed-α pilot chooses α so the average absolute information reward is approximately 0.2 per turn.The procedure estimates typical |∆k| under the current teacher before selecting α.
  • Dynamic α: Dynamic α adjusts online to keep the running mean of |α∆k| within a selected target band.The explored bands are small [0.001, 0.05], medium [0.05, 0.3], and large [0.3, 1.0].
  • Selection outcome: Across configurations, both fixed and dynamic schemes identify a broad medium regime in which TIPS remains robust without delicate α tuning.This regime keeps the information reward around 0.2 per turn and substantially below the terminal reward.

E IMPLEMENTATION DETAILS

The implementation defines evaluation, segment-level rewards, token mappings, and multi-turn credit mechanisms for tool-using agents. It also formalizes turn boundaries and the potential-based shaping used by TIPS and related MT-GRPO variants.

  • Evaluation: Exact Match is binary, while F1 is maximized over acceptable answers when multiple references exist.Exact Match equals 1 only for an exact acceptable answer; otherwise it is 0.
  • Segment rewards: Rule-based segment rewards score tool execution and answer presence, with at most one presence credit per segment.Segments beginning with “Error:” are excluded, and acceptable answers are matched against ground truth.
  • Token mapping: Segment rewards are mapped to tokens using tool-response boundaries, with unsupported or inactive segments receiving no reward.The default implementation places rewards on the last token of each segment.
  • MT-GRPO: MT-GRPO combines normalized turn-level and outcome rewards into token-level advantages, extending to multiple tool segments with segment-specific credit.Final-answer tokens receive only outcome reward, while the shared outcome signal remains available across tool segments.
  • TIPS shaping: TIPS uses potential differences at turn boundaries, and its history-max variant rewards only turns that raise the maximum teacher belief seen so far.The history-max design avoids penalizing nonimproving but potentially useful steps.
  • Turn formalization: A turn is a token sequence ending at a retrieval boundary, so each interaction is partitioned into K reasoning-and-tool-use units for reward assignment.The segment state is the state at the boundary after the tool observation.

F.5 TURN-CONSTANT SHIFT OF RETURNS (KEY LEMMA)

The key lemma shows that potential-based shaping adds a constant shift to returns within each turn. Because this shift is independent of within-turn actions, it preserves action comparisons and the set of optimal policies.

  • Key lemma: Within a turn, the shaping adjustment is constant with respect to the token sequence τk.The constant depends on the preceding segment state rather than the actions taken inside the current turn.
  • Policy invariance: The induced Q-value shift is action-independent, so the argmax over actions remains unchanged.This leaves greedy, advantage-based, and policy-gradient action comparisons unaffected.
  • Policy invariance: Under the stated shaping construction, the set of optimal policies is preserved.The result relies on the additive shift not depending on the within-turn action sequence.
  • Implementation consequence: Monte Carlo estimation can subtract or ignore the turn-constant shift without changing within-turn comparisons.Thus relative Q-values and advantage-based learning decisions are unchanged.
  • Rollout analysis: The rollout visualizations compare PPO and TIPS using z-score-normalized token advantages, with blue denoting negative and red positive values.The examples include successful and failed rollouts from both methods.

H OVERHEAD ANALYSIS

TIPS adds teacher-scoring computation to PPO, with prefix caching reducing repeated work. The reported overhead is moderate in FLOPs and wall time, while response length explains much of the raw timing difference between TIPS and PPO.

  • FLOP overhead: Teacher scoring increases computation by approximately 11% over vanilla PPO for both Qwen 2.5 3B and 7B models.The comparison is based on PPO step FLOPs plus teacher-scoring FLOPs.
  • FLOP overhead: Prefix caching reuses shared prefixes across teacher-scoring passes, yielding FLOP savings at scale.The scoring cost is decomposed into prefix-processing and answer-scoring components.
  • Wall-time overhead: Teacher reward computation adds 16–18% to per-step training time.The overhead is calculated from training time with reward computation relative to time without it.
  • Length adjustment: Raw per-step timing is strongly affected by the average decoded response length, so the analysis regresses time on response length.The fitted comparison uses ordinary least squares and evaluates both methods at common response lengths.
  • Length adjustment: Response length explains 92.6% of the 3B timing gap and 70.6% of the 7B gap after adjustment.At PPO mean length, TIPS is −2.1% from PPO for 3B and +7.7% for 7B.
Loading 2603.22293v1…