PRInTS: Reward Modeling for Long-Horizon Information Seeking

AI summary

Overview

Research area: AI agents, reward modeling, and long-horizon information-seeking (tool-using LLMs).

Technical level: Advanced. The paper assumes familiarity with reinforcement learning (GRPO), process reward models, LLM agents, and tool-use paradigms like ReAct.

Scope: The paper introduces PRInTS, a 4B-parameter generative process reward model that scores candidate agent steps via information-gain estimation and recursively summarizes long trajectories, improving information-seeking agents at test time without fine-tuning them.

What This Paper Is About

Long-horizon information-seeking agents — systems that use tools like web search and browsing across many steps — perform poorly compared to humans, and existing process reward models (PRMs) are ill-suited to guide them. Standard PRMs evaluate short reasoning snippets in isolation with coarse binary judgments, and they fail when agent context grows rapidly over many steps. PRInTS addresses both problems by jointly learning to (1) score full trajectory steps (reasoning + tool interaction) across multiple quality dimensions with dense scores, and (2) compress the accumulating trajectory into compact recursive summaries.

Key Contributions

1. Information gain as a step-quality signal. The authors formalize step evaluation as information gain — the change in expected accuracy of reaching the correct answer before and after a step — estimated via Monte Carlo rollouts, which yields dense, multi-faceted reward signals rather than binary judgments.

2. A dual-capability generative PRM (PRInTS). A single model is trained to both score candidate trajectory steps (generating chain-of-thought analyses plus a scalar score) and recursively summarize the trajectory to bound context length while preserving key information.

3. A joint SFT + GRPO training pipeline with complementary rewards. PRInTS is trained with a score reward (accuracy of predicting information gain) and a comparison reward (pairwise preference learning from automatically constructed step pairs), combined via an adaptive weight that downweights noisy annotations.

4. Strong, model-agnostic empirical gains. Test-time best-of-n sampling with PRInTS improves open-source LLMs, a specialized information-seeking agent, and a closed-source frontier model across FRAMES, GAIA, and WebWalkerQA — without modifying the base agents.

Main Findings

• Large, consistent gains on a large open-source model: On Qwen3-32B, PRInTS adds 9.3% absolute average accuracy across FRAMES, GAIA (Levels 1–3), and WebWalkerQA (easy–hard).

• Improvements for a specialized agent: On Tongyi DeepResearch-30B-A3B, PRInTS adds 3.9% absolute average accuracy, with particular strength on the hardest subsets (GAIA Level 3, WebWalkerQA Hard).

• Small reward model, frontier-level results: On GAIA, the 30B agent plus the 4B PRInTS reaches 64.4% average accuracy, surpassing DeepSeek-V3.1-671B (63.1%) — a model 20 times larger — and approaching OpenAI DeepResearch (67.4%).

• Generalization to frontier closed-source models: On Gemini-2.5-Flash, PRInTS delivers a 4.0% absolute average accuracy gain, with the largest improvement (+5.5%) on GAIA Level 3.

• Outperforms existing PRMs and heuristics: Baselines like Confidence, Relevance, Verbal-progress, GenPRM-7B, Web-Shepherd-8B, and StepWiser provide only marginal or inconsistent gains; even when StepWiser uses the same annotated data and backbone, it yields only 1.5% average gain versus PRInTS's 9.3% on Qwen3-32B.

• Summarization beats raw trajectories: Feeding full raw history (H_t) or truncated histories (H_{-1:}, H_{-2:}, H_{-4:}) underperforms PRInTS's recursive summaries, with the summary approach outperforming the full-history baseline by 7.7% absolute average accuracy — confirming that context noise, not just length, harms evaluation.

• Both rewards are necessary and adaptive weighting helps: Combining score and comparison rewards beats either alone by 2.0–3.1%, and adding the adaptive weight provides an additional 1.0% gain by mitigating annotation noise in low-margin preference pairs.

• Favorable test-time scaling, with a caveat: Performance improves up to n=8 candidates on GAIA Level 2 (up to 8.9% gain), but declines at n=16, likely because the model over-selects superficially informative exploratory steps over steps that commit to an answer.

Methodology in Plain English

The researchers start from the ReAct agent setup, where an LLM alternates between reasoning and calling tools like web search or code execution. Their central idea is to measure how much each step (a reasoning thought plus a tool call) helps the agent reach the correct answer. They estimate this "information gain" by running many simulated rollouts from each step and averaging final-answer accuracy — the change in that accuracy before and after the step becomes the step's score.

To train the reward model, they automatically build preference pairs: the step that led to a successful rollout is labeled the "winner," a randomly sampled alternative is the "loser," and both are re-scored via rollouts to confirm the ranking. PRInTS (initialized from Qwen3-4B) is then trained with GRPO using two rewards: one that rewards accurate prediction of the information gain score, and one that rewards correctly ranking winner steps above loser steps. The comparison signal is weighted by how large the score gap is, so noisy pairs count less.

In parallel, the same model is trained via supervised fine-tuning to act as a summarizer: given the query, the previous summary, the latest tool output, and the current step, it produces an updated compact summary. This keeps the input to the scorer short, avoiding the noise and length issues of processing the full trajectory. At test time, the agent generates several candidate next steps, PRInTS scores each one, and the highest-scoring step is chosen.

Why This Matters

Impact on research: PRInTS shows that test-time process guidance can be a powerful, model-agnostic complement to agent fine-tuning. It demonstrates that context compression is not just an efficiency trick but a prerequisite for accurate step-level evaluation in long-horizon tasks, and it challenges the assumption that PRMs designed for short math reasoning transfer directly to agentic workflows.

Real-world applications:

• Deep research assistants that synthesize answers from many web sources with fewer wasted search steps.
• Customer-facing or enterprise agents that need to decide when to search, browse, or stop and answer.
• Scientific literature review tools that must navigate large document spaces without drifting.
• Multimodal or code-using agents that need step-level guidance across tool calls.

Industry relevance: The results suggest a cost-effective path to frontier-level agent performance: rather than fine-tuning or deploying a 671B-parameter model, a 4B reward model can improve a 30B agent, reducing memory and compute requirements. This makes high-quality agentic information-seeking more accessible to smaller teams and deployment environments.

Future Directions

• Multilingual extension. The current data is English-only; extending to multilingual queries would broaden PRInTS's applicability.
• Dense reward for RL training. Using PRInTS as a reward signal to train information-seeking agents with reinforcement learning — rather than only guiding them at test time — is a natural next step, though computationally demanding.
• Fixing the n=16 scaling degradation. Understanding and mitigating the tendency to over-select exploratory steps at very large candidate pools would enable further test-time scaling.
• Better annotation efficiency. Reducing reliance on Monte Carlo rollouts for information gain annotation could make the pipeline cheaper and more scalable.

Target Audience

AI researchers and engineers working on LLM agents, tool use, and reward modeling — especially those studying test-time scaling, process reward models, or long-horizon reasoning. The paper is also relevant to practitioners seeking cost-effective ways to improve agentic information-seeking without fine-tuning large base models, and to students with a background in reinforcement learning and language model agents looking for a well-scoped applied research problem.

Authors’ abstract

Information-seeking is a core capability for AI agents, requiring them to gather and reason over tool-generated information across long trajectories. However, such multi-step information-seeking tasks remain challenging for agents backed by language models. While process reward models (PRMs) can guide agents by ranking candidate steps at test-time, existing PRMs - designed for short reasoning with binary judgment - cannot capture richer dimensions of information-seeking steps, such as tool interactions and reasoning over tool outputs, nor handle the rapidly growing context in long-horizon tasks. To address these limitations, we introduce PRInTS, a generative PRM trained with dual capabilities: (1) dense scoring based on the PRM's reasoning across multiple dimensions of step quality (e.g., interpretation of tool outputs, tool call informativeness) and (2) trajectory summarization that compresses the growing context while preserving essential information for step evaluation. Extensive evaluations across FRAMES, GAIA (levels 1-3), and WebWalkerQA (easy-hard) benchmarks on multiple models reveal that best-of-n sampling with PRInTS enhances information-seeking in open-source models as well as specialized agents, matching or surpassing frontier models with a much smaller backbone agent and outperforming other strong reward modeling baselines.