Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents

Changdae Oh; Wendi Li; Seongheon Park; Samuel Yeh; Tanwi Mallick; Sharon Li

Source-linked AI summary

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents

Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, Tanwi Mallick, Sharon Li

arXiv:2606.26080v1Jun 24, 2026cs.LGcs.AI

TL;DR

Step-level evaluation for LLM agents is difficult because long, stochastic trajectories make process reward modeling costly. This paper derives progress advantage from RL policy-reference log-probability ratios, finding it consistently outperforms confidence-based and trained reward-model baselines across applications and benchmarks.

Problem
Process reward models provide step-level feedback, but evaluating long-horizon agent trajectories remains difficult because interactions involve many actions and stochastic feedback.
Method
Progress advantage uses the log-probability ratio between an RL-trained policy and its reference policy to exactly recover optimal action advantages in stochastic MDPs.
Results
15.5% for Gemma4 and 11.3% for Qwen3.5 average margins show progress advantage outperforming training-based and confidence-based methods in test-time scaling.
Takeaways & Limitations
Progress advantage offers an annotation-free, domain-agnostic process-level signal available from existing RL post-training artifacts without task-specific retraining.
Takeaways & Limitations
The policy log-probability ratio alone cannot recover exact reward under stochastic transitions because inaccessible value-function residuals remain.

Abstract

from arXiv · show

Process reward models enable fine-grained, step-level evaluation of LLMs, yet building them for agentic settings remains prohibitively difficult: long-horizon interactions, irreversible actions, and stochastic environment feedback make both human annotation and Monte Carlo estimation infeasible at scale. In this work, we show that reinforcement learning (RL) post-training already provides the ingredients for effective step-level scoring, eliminating the need for dedicated reward model training altogether. Concretely, we derive an implicit advantage under a general stochastic Markov decision process, which we term progress advantage -- log-probability ratio between the RL-trained policy and its reference policy exactly recovers the optimal advantage function. This formulation makes the resulting signal annotation-free, domain-agnostic, and available as a byproduct of the standard RL post-training pipeline. We validate the effectiveness of the progress advantage across three different applications: test-time scaling, uncertainty quantification, and failure attribution on five benchmarks and four model families. Across all settings, it consistently outperforms confidence-based baselines and, despite requiring no task-specific training, surpasses dedicated trained reward models. We complement these results with deeper analyses on characteristics of progress advantage, offering practical guidance for adoption in real-world agentic systems.

1 Introduction

The paper addresses the difficulty of step-level evaluation for LLM agents by deriving progress advantage from standard RL post-training, without dedicated reward-model training. It validates this signal across test-time scaling, uncertainty quantification, and failure attribution, where it outperforms pre-trained reward models without task-specific training.

Motivation: Step-level reward evaluation is difficult for LLM agents because trajectories are long, environments are stateful, and some actions are irreversible.These conditions prevent the backtracking and repeated rollouts required by traditional Monte Carlo estimation, while step-level human annotation is prohibitively expensive.
Method: Progress advantage uses the log-probability ratio between an RL-trained policy and its reference policy as a theoretically grounded per-step progress signal.The signal is available from standard RL post-training and can score agent trajectories at both step and trajectory levels.
Properties: Progress advantage is annotation-free, domain-agnostic, and applicable to mainstream RL algorithms including GRPO and DAPO.It is computed from checkpoint pairs already produced by post-training and remains valid for algorithms with explicit KL penalties or clipping-based surrogates.
Evaluation: The method is evaluated across three inference-time applications, five agent benchmarks, and four model families.The applications are test-time scaling, uncertainty quantification, and failure attribution; the benchmarks include BFCLv4-MT, WebShop, AgentDojo, τ 2-bench, and Who & When.
Results: Progress advantage outperforms confidence-based baselines and pre-trained reward models across the reported inference-time applications without task-specific training.The introduction also states that it surpasses task-specific process reward models in test-time scaling.

2 Preliminary

This section formulates multi-turn LLM agents as token-level stochastic MDPs and reviews KL-regularized RL post-training. It motivates extending deterministic implicit-reward analyses to stochastic agent settings, where external feedback causes non-deterministic transitions.

Problem setup and notation: Agents operate in a token-level MDP whose states contain the full interaction history, while actions are generated tokens and transitions depend on environment dynamics.The initial state is sampled from the prompt distribution; EOS can trigger stochastic transitions, whereas non-EOS actions concatenate tokens to the state.
RL fine-tuning of LLMs: PPO and GRPO share a KL-regularized reward-maximization abstraction despite differing in advantage estimation and surrogate objectives.The regularization coefficient satisfies β > 0, and πref is typically initialized from a pretrained or supervised-fine-tuned checkpoint.
Reward reparameterization in deterministic MDP: The KL-regularized objective admits a maximum-entropy RL formulation with a fixed-point policy expressed through optimal action values and value functions.Q∗ measures expected cumulative future reward from a state-action pair, while V∗ is its expectation under π∗; the Bellman equation includes expected next-state values for nonterminal transitions.
Reward reparameterization in deterministic MDP: Deterministic implicit-reward analyses do not directly apply to multi-turn stochastic agents because user responses, tool outputs, and environment feedback create non-deterministic transitions.Prior deterministic formulations reduce the expected next-state value to V∗(s_t+1), but that simplification fails when external observations affect transitions.

3 Implicit Process Reward Modeling for LLM Agents

This section derives progress advantage as a step-level signal from the log-probability ratio between an RL-trained policy and its reference, avoiding dedicated process-reward modeling. Unlike exact reward recovery, the advantage remains valid in stochastic MDPs and across KL-regularized or clipping-based RL objectives.

Motivation: Building agentic process reward models is difficult because long-horizon stateful environments make annotation expensive, Monte Carlo estimation infeasible, and task-specific models poorly generalizable.These limitations motivate deriving a process-level signal directly from post-training policy pairs.
Stochastic MDPs: In stochastic MDPs, the policy log-probability ratio does not recover exact reward because residual value-function terms fail to cancel.The residual δ_t captures the difference between the current state value and expected next-state value, vanishing through telescoping only under deterministic transitions.
Progress advantage: Progress advantage instead extracts the exact advantage Q*(s, a)−V*(s), measuring an action’s relative merit without requiring direct access to the optimal value function.It is derived from the optimal behavior policy and reference policy pair and provides a fine-grained signal for scoring agent trajectories.
Generality: The formulation applies to RL policies trained with either explicit KL regularization or clipping-based surrogate objectives.The clipping-based result establishes a conservative KL-constrained solution governed by the clipping threshold ϵ.

4 Empirical Validation

Empirical validation evaluates progress advantage for best-of-8 test-time scaling, trajectory uncertainty quantification, and failure attribution across agentic benchmarks and LLM families. It consistently outperforms confidence-based and trained reward-model baselines, while supporting cross-policy trajectory monitoring and revealing task-dependent aggregation effects.

Test-time scaling: 15.5% for Gemma4 and 11.3% for Qwen3.5 are the average margins over training-based and confidence-based methods in best-of-8 scaling.The method shows stable performance across datasets and models.
Uncertainty quantification: Progress advantage remarkably outperforms confidence-based methods and pre-trained reward models for trajectory-level success prediction measured by AUROC.The evaluation covers τ 2-bench Airline and Retail domains across four model backbones.
Uncertainty quantification: Using Gemma4-4B, progress advantage scores Qwen3.5-9B and Qwen3-14B trajectories, acting as an external scorer for arbitrary behavior policies.This cross-policy evaluation on τ 2-Airline indicates potential as an off-the-shelf reward model.
Signal analysis: Contrasting the trained and reference policies provides more reliable uncertainty signals than using either policy alone.Average AUROC ranks on τ 2-Airline confirm that contrasting distributions sharpens the signal.
Signal analysis: Aggregation performance is task- and model-dependent: (MEAN, MIN) performs strongly for best-of-N selection, whereas (MAX, MEAN) wins for uncertainty quantification.Progress advantage is aggregated at both token and step levels.

5 Related Work

Prior process reward models supervise intermediate reasoning steps through classification or ranking, while agent-focused PRMs often depend on Monte Carlo step annotations that become unreliable or infeasible for complex, long-horizon tasks.

Process Reward Modeling for Reasoning Models: Early process reward models label each intermediate reasoning step as correct or incorrect using binary classification.Recent approaches instead formulate PRM learning as a ranking problem based on Q-value theory or probabilistic step formulations.
Process Reward Modeling for Reasoning Models: Recent reasoning-model PRMs move beyond step-wise classification by framing process supervision as ranking.These methods draw on Q-value theory or probabilistic formulations of step q.
Process Reward Modeling for LLM Agents: Agent-focused PRMs typically use per-step Monte Carlo estimation, but this approach is unreliable and infeasible for complex, long-horizon tasks.Prior work generally restricts evaluation to relatively simple tasks with only a few conversational turns.

6 Conclusion · Appendix

The paper frames intermediate-progress measurement in stochastic, multi-turn agentic environments as valuable but constrained by the expense of process-annotated PRM training. It establishes progress advantage as a theoretical foundation for implicit rewards and proposes building PRMs from RL-fine-tuned LLM checkpoint pairs.

6 Conclusion: Agentic harnesses place LLMs in multi-turn, interactive environments with stochasticity.These settings motivate methods that can assess progress during goal-oriented trajectories.
6 Conclusion: Measuring intermediate progress over goal-oriented trajectories offers substantial opportunities for agentic systems.
6 Conclusion: Expensive training of process reward models with process annotations is identified as the central bottleneck.
6 Conclusion: Progress advantage provides a theoretical foundation for implicit reward technology in stochastic MDPs.
6 Conclusion: The work offers a novel angle for constructing process reward models without relying solely on conventional process-annotation training.
6 Conclusion: The proposed recipe builds process reward models from pairs of LLM checkpoints produced through RL fine-tuning.

A Implementation of Progress Advantage … B Details on Experiment Setup

Progress advantage uses the RL-trained behavior policy and its reference policy, evaluated across five representative open-source model families. Its default implementation scores realized tokens directly, while a top-k-smoothed variant addresses known instability concerns and is compared with the vanilla version.

A.1 Policy Pairs in Progress Advantage: Progress advantage is constructed from the RL-trained behavior policy and its reference policy, which serves as the regularization pivot during RL training.These two policies form the required policy pair for the method.
A.1 Policy Pairs in Progress Advantage: Five representative open-source model families are used to evaluate progress advantage because publicly available policy pairs are limited.The selected families provide the base or intermediate checkpoint of the final post-trained model.
A.1 Policy Pairs in Progress Advantage: Industry practice commonly releases only the final post-trained model while retaining base and intermediate checkpoints privately.This limits the publicly available policy pairs needed to construct progress advantage.
A.2 Progress k-Advantage: The default implementation computes progress advantage from the token probabilities assigned by ˜π∗ and πref to each realized token in a trajectory.The score uses the realized token at every position rather than a separately trained evaluator.
A.2 Progress k-Advantage: Naive token-probability-based regularized RL can introduce gradient-estimation instability, motivating alternatives to the vanilla implementation.Recent work reports this nuance instability in some regularized RL training settings.
A.2 Progress k-Advantage: Confidence-based self-evaluation methods such as Self-Certainty and DeepConf typically smooth probabilities across multiple tokens.Progress k-advantage compares a top-k-smoothed log-probability version with the vanilla version in Appendix C.

B.1 Baseline Methods … B.3 Inference Setup and Configuration

The paper compares training-free confidence scores, general and task-specific reward models, and scenario-specific baselines across test-time scaling, uncertainty quantification, and failure attribution. Experiments use defined agent benchmarks and standardized inference configurations, with stochastic best-of-N generation for TTS and single-pass scoring of greedy trajectories for UQ and FA.

B.1 Baseline Methods: Self-Certainty scores trajectories using the behavior policy’s token distribution, while DeepConf uses local top-k confidence over non-overlapping agent action steps.DeepConf is instantiated as Tail, which uses the termination-phase group confidence, and B10, which averages the lowest 10% of group confidences.
B.1 Baseline Methods: Behavior-policy-only confidence methods can reward fluent or locally likely continuations without reliably reflecting goal-directed progress in agentic settings.The setup uses a top-20 truncated distribution for practicality, but this can score correct low-frequency tool-call strings poorly.
B.2.1 Test-time scaling (TTS): TTS evaluates reward models by scoring parallel candidate trajectories and selecting the highest-scoring response across BFCLv4, WebShop, AgentDojo, and τ 2-bench Airline.The benchmark setup samples N = 8 rollouts per task and reports greedy decoding, mean-of-N, and pass@N as scenario-specific references.
B.2.2 Uncertainty quantification (UQ): UQ scores whether a realized trajectory will succeed, reporting AUROC on the τ 2-bench Airline and Retail domains.Telecom is excluded because modern agents’ performance is saturated there, and Claude-Sonnet-4.6 serves as the LLM-as-a-Judge baseline.
B.2.3 Failure attribution (FA): Failure attribution identifies the decisive error step in a failed multi-agent trajectory, using Who&When tasks sourced from GAIA and AssistantBench.AgenTracer is the task-specific training-based baseline, predicting an error step with a reasoning trace after GRPO training on annotated failure trajectories.
B.3 Inference Setup and Configuration: Across TTS, UQ, and FA, models run in bfloat16 on a single GPU with model-family-tailored tokenizers and chat templates.The common configuration includes family-specific processing choices such as qwen3_coder with the qwen3 reasoning parser, gemma4, and olmo3.
B.3 Inference Setup and Configuration: TTS uses vLLM with max_model_len=32768, while UQ and FA re-tokenize complete conversation logs and score greedy trajectories in one HuggingFace forward pass with max_length=16384.Stochastic TTS generation uses top_p=0.95 and max_new_tokens=1024, with temperature 0.7 on τ 2-bench and WebShop and 0.4 on BFCL and AgentDojo.

C Additional Results

Additional analyses show that progress advantage generally outperforms its smoothed variant and constituent signals, while aggregation choices and task-specific settings affect performance. The results also indicate that progress advantage can outperform task-trained and general reward-model baselines without downstream-task training.

Probability smoothing: Progress advantage and progress k-advantage consistently achieve the best or second-best results in test-time scaling and uncertainty quantification, with default progress advantage generally superior.The k-smoothed variant can nevertheless outperform the default on some failure-attribution setups with the Gemma4-4B backbone.
Signal ingredients: Progress advantage consistently outperforms the individual behavior-policy and reference-policy log-probability ingredients across eight uncertainty-quantification scenarios.The comparison averages ranking and AUROC over 25 token-and-step aggregation combinations per method.
Aggregation strategies: Aggregation winners vary across best-of-N datasets and models, with (MEAN, LAST) uniquely winning BFCLv4 for Qwen3.5-9B.WebShop and AgentDojo are relatively robust across aggregation methods, while other datasets are more sensitive.
Aggregation strategies: In uncertainty quantification, (MAX, MEAN) wins for Airline and (MIN, LAST) wins for Retail, indicating that extreme token scores and domain-specific step aggregation are informative.The analysis sweeps 25 token-wise and step-wise aggregation combinations.
Task-specific reward models: On WebShop, progress advantage outperforms AgentPRM despite AgentPRM outperforming comparable-size general reward models and confidence-based baselines.AgentPRM is trained directly on a downstream task, whereas progress advantage is not trained on the specific WebShop dataset.

D Derivation of Implicit Rewards Under Stochastic MDP · E Missing Proof

The derivation formulates KL-constrained reward maximization as an equivalent maximum-entropy RL problem with a reference policy and regularization coefficient. Under stochastic dynamics, telescoping fails to recover rewards solely from policy terms, motivating progress advantage.

D Derivation of Implicit Rewards Under Stochastic MDP: The KL-constrained reward maximization problem uses β > 0 as a regularization coefficient and πref as the reference policy.The reference policy is commonly initialized from pre-trained or SFT checkpoints.
D Derivation of Implicit Rewards Under Stochastic MDP: The objective can be equivalently written in maximum entropy RL form with entropy H(·).This reformulation connects the KL-constrained objective to a standard entropy-regularized RL formulation.
D Derivation of Implicit Rewards Under Stochastic MDP: The optimization has a known optimal policy π∗(at|st) = exp.The supplied derivation introduces this policy as the solution to the reformulated optimization problem.
D Derivation of Implicit Rewards Under Stochastic MDP: The derivation also obtains the corresponding optimal action-value function from the Bellman optimality equation.The action-value expression incorporates the reward, reference-policy term, and expected next-state value when applicable.
D Derivation of Implicit Rewards Under Stochastic MDP: Re-expressing Eq. 14 in reward-centric form and summing across the trajectory up to T −1 yields the next derivation step.The trajectory-level summation is used to investigate whether rewards can be recovered from policy quantities.
D Derivation of Implicit Rewards Under Stochastic MDP: Under stochastic MDPs, intermediate value terms do not cancel through telescoping, so exact rewards cannot be represented solely with known policy terms.This limitation motivates the alternative progress-advantage derivation in Proposition 1.

E.1 Derivation of Progress Advantage

Under a KL-regularized RL objective, the optimal advantage function is exactly recovered from the policy’s log-probability ratio to a reference policy. This implicit process reward incorporates stochastic state transitions without requiring them to be modeled explicitly.

Core derivation: Proposition 3 shows that the optimal advantage function is exactly recovered by a log-probability ratio under the KL-regularized RL objective.The result assumes β > 0 and a reference policy with positive probability for every action-state pair.
Core derivation: The derivation proceeds from the optimal policy through the optimal state and action value functions to the optimal advantage as an implicit process reward.It uses the KL-regularized objective, state-value formulation, soft Bellman equation, policy improvement, and constrained optimization.
Core derivation: The optimal policy for the local step-level objective is equivalent to the global trajectory-level objective by the Policy Improvement Theorem.The local constrained optimization is solved using Lagrangian multipliers.
Stochasticity handling: State-transition stochasticity is embedded in the optimal action and state values, so the log-probability pseudo-reward bypasses explicit stochasticity modeling.This applies to the general non-deterministic MDP described in the derivation.

E.2 Proof: Clipping Surrogate RL as an Implicit KL Constraint

The proof shows that PPO-Clip-style per-sample ratio clipping implicitly constrains both forward and reverse KL divergence. Specifically, the feasible policies lie within a KL trust region of radius ε^2/2 when ε is small.

Trust-region bound: PPO-Clip-style optimization enforces |δ(s, a)| ≤ ε, where δ(s, a) = R(s, a) − 1, establishing the starting point for the trust-region proof.Here, R(s, a) is the importance-sampling ratio between target and reference policies.
Trust-region bound: Any feasible PPO-Clip-style policy lies within a forward and reverse KL trust region of radius ε^2/2, regardless of the KL-penalty direction.The result is stated for small ε and policies sharing the same support.
Trust-region bound: The shared support and normalization of πref and πθ imply Eπref[δ] = 0, exactly removing the linear Taylor term from both KL expansions.This reduces both divergences locally to scaled Pearson χ2-divergence terms.
Trust-region bound: The per-sample bound |δ(s, a)| ≤ ε yields Eπref[δ^2] ≤ ε^2, which bounds the quadratic terms governing both KL directions.The argument applies to the forward KL DKL(πθ ∥ πref) and reverse KL DKL(πref ∥ πθ).

F Limitation and Future Work … J Prompt Template for Baseline Methods

The discussion positions progress advantage as an annotation-free implicit reward signal for stochastic agent interactions, while noting model-access limitations and practical deployment, compute, and baseline-prompt considerations.

F Limitation and Future Work: Institutional checkpoint restrictions limited the model candidates, while the assumption that public post-trained models approximate the RL optimum is difficult to falsify.The authors call for a fully open model-development cycle to enable broader uses of progress advantage.
G.1 Outcome Reward Modeling: Outcome reward models provide scalable final-response supervision for reranking, search, and reinforcement learning, but their supervision is coarse and outcome-focused.The passage contrasts easy-to-collect outcome annotations with the lack of process-level evaluation.
G.2 Implicit Reward Modeling: Implicit reward methods avoid explicit reward modeling, but applying them to LLM agents is difficult because trajectories combine model completions with stochastic environmental observations.The paper addresses this gap by establishing implicit reward under a stochastic MDP tied to realistic LLM-agent settings.
G.3 Distribution Contrasting and Sharpening: Progress advantage contrasts the behavior-policy and reference-policy likelihoods, connecting its probabilistic form to likelihood-ratio testing and noise-contrastive estimation.The passage presents these as related interpretations of the contrastive quantity.
G.4 Self-improving Intelligent Systems: Progress advantage extracts a self-contained progress signal from the log-ratio between an RL-trained future-self policy and a past-self reference policy without external supervision.This parallels self-improvement methods that sharpen an LLM by concentrating probability mass on high-quality generations.
G.5 Open-source AI and Sustainable Machine Learning: Sharing model-development artifacts such as checkpoints supports reusable, sustainable machine learning and has renewed interest in ensembles and model merging.The passage places progress advantage within this broader open-source and sustainable-AI direction.
H Broader Impacts: Progress advantage scores agent trajectories without a cost-heavy reward-model development phase, potentially reducing deployment GPU hours while supporting safety monitoring and response quality.Its reward signals are based on the log-probability ratio of trained LLM policies.