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

Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, [0.2em] Tanwi Mallick, Sharon Li, [0.2em] University of Wisconsin–Madison · 2026

Read Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents by Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, [0.2em] Tanwi Mallick, Sharon Li, [0.2em] University of Wisconsin–Madison (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26080.txt.

Introduction

Changdae Oh and colleagues find a free reward signal hiding inside standard agent training. Process reward models grade each step an agent takes. Building them for long, irreversible tasks is brutally hard. Human labels and Monte Carlo estimates both fail at scale. Their insight starts from reinforcement learning post-training itself. A trained policy already differs from its reference policy in informative ways.

Progress advantage names the recovered signal. The log-probability ratio between the trained and reference policies equals the optimal advantage function. That equality holds under a general stochastic decision model. No annotation is needed, and the signal works across domains. Three applications test it: test-time scaling, uncertainty checks, and failure attribution. Five benchmarks and four model families supply the evidence. The byproduct signal beats confidence-based baselines everywhere. It even beats dedicated trained reward models, despite needing no task-specific training at all.

Catalog record

CREATORChangdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, [0.2em] Tanwi Mallick, Sharon Li, [0.2em] University of Wisconsin–Madison
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26080

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh, [0.2em] Tanwi Mallick, Sharon Li, [0.2em] University of Wisconsin–Madison Abstract 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. URLs: , 1 Introduction Reinforcement learning (RL) has become the dominant paradigm for post-training large language models (LLMs), producing agents that can operate autonomously across complex, multi-turn tasks involving tool use, web navigation, and code execution 100 ; 83 ; 30 ; 2 . A central challenge in deploying these agents is evaluating the quality of their behavior, so-called reward , at the level of individual steps rather than only at the end of a trajectory. Outcome reward models assign a single scalar to a generated output 16 ; 129 ; 109 ; 98 ; 31 , but this coarse signal provides little guidance for credit assignment over trajectories that may span hundreds of actions. Process reward models (PRMs) address this by providing step-level supervision 66 ; 112 ; 101 ; 70 ; 64 , enabling finer-grained trajectory evaluation that benefits test-time scaling, runtime monitoring, and failure diagnosis. However, PRMs have been explored mostly in mathematical reasoning, and they remain largely underexplored for LLM agents. Unfortunately, building PRMs for LLM agents is notoriously difficult: agentic trajectories span long horizons and pass through stateful environments where actions such as sending an email or deleting a file are irreversible, preventing the backtracking and repeated rollouts that traditional Monte Carlo estimation relies on 112 ; 70 . Collecting step-level human annotations in this setup is prohibitively expensive, and even when domain-specific (process) reward models can be trained, they often fail to generalize across tasks or environments 28 ; 75 ; 97 ; 143 . The result is a conspicuous gap: the agents that most need process-level evaluation are precisely the ones for which building process reward models is least feasible. Figure 1: Framework overview . (a) We derive an optimal advantage function from an RL-trained policy and its reference policy, which can (b) score the LLM agent trajectories at both the step and trajectory levels without dedicated reward model training. In this paper, we take a fundamentally different approach. Rather than collecting process annotations or training dedicated reward models 66 ; 112 ; 15 ; 119 ; 132 ; 67 , we show that RL post-training already freely encodes a process-level signal that can be directly used for inference-time scoring. Concretely, the log-probability ratio between the trained policy and its reference policy—readily available from standard RL post-training—constitutes a theoretically grounded measure of per-step progress, which we term progress advantage . We prove that progress advantage exactly recovers the optimal advantage function under the general stochastic MDP (Proposition 1 ). While prior implicit PRM approaches 93 ; 92 exploit similar likelihood-based signals in deterministic reasoning settings, agentic environments involve stochastic transitions and external interactions, where such interpretations no longer directly apply (Remark 1 ). We show that progress advantage naturally corresponds to an advantage function for assessing an agent’s sequence of actions in this setting, providing a principled and practical signal for process-level evaluation. Notably, progress advantage has several appealing properties. It is annotation-free and computed from checkpoint pairs that already exist as artifacts of post-training. It is general and valid for most of mainstream RL algorithms, including those with explicit KL penalties such as GRPO 98 and those with only clipping-based surrogates such as DAPO 131 (Proposition 2 ). It is domain-agnostic because it emerges from the general post-training phase rather than the task-specific adaptation stage, transferring across tasks without needs for retraining. See Figure 1 for an illustrative overview. We extensively validate progress advantage across three inference-time applications on multiple agent benchmarks (BFCLv4-MT 87 , WebShop 126 , AgentDojo 18 , \tau^{2} -bench 7 , and Who & When 139 ) and four model families (Gemma4 29 , Qwen3.5 91 , Qwen3 122 , and Olmo3 82 ). In test-time scaling, progress advantage scores best-of- N trajectory candidates to boost task success rates, outperforming confidence-based baselines, pre-trained reward models, and even task-specific PRMs (Sec. 4.2 ). In uncertainty quantification, it predicts trajectory-level success or failure with substantially higher AUROC than all baselines, including pre-trained PRMs or a powerful proprietary LLM-as-a-Judge baseline (Sec. 4.3 ). In failure attribution, it localizes the error step in multi-agent systems, approaching the step-level prediction accuracy of a method specifically trained for this task (Sec. 4.4 ). These results hold consistently across model families and benchmarks, suggesting that the signal captured by progress advantage is robust and broadly useful. Contribution: (1) We establish the foundation of implicit reward formulation in stochastic environment and derive progress advantage for LLM agents trained by a broad class of RL algorithms; (2) We demonstrate its effectiveness across three practical inference-time applications (test-time scaling, uncertainty quantification, and failure attribution), where it outperforms pre-trained reward models without any task-specific training; (3) We provide analyses characterizing how progress advantage works, offering practical guidance and insights for real-world adoption. 2 Preliminary Problem setup and notation. We model the stochastic agents operating in the multi-turn interaction settings as a general token-level Markov Decision Process (MDP), specified by a tuple (\mathcal{S},\mathcal{A},f,r,\rho) . The state space \mathcal{S} contains states s_{t} representing the full sequence of tokens generated and observed up to time t , i.e. , s_{t}=(s_{0},a_{0},...,s_{t-1},a_{t-1}) . The initial state s_{0}\sim\rho corresponds to the input prompt, such as a task specification or a user’s initial query to the agent, sampled from the prompt distribution \rho . The action a_{t}\in\mathcal{A} denotes the token generated at step t by the agent policy a_{t}\sim\pi(\cdot|s_{t}) . The state transition dynamics is shaped by function f:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S} which is a stochastic transition, s_{t+1}\sim f(\cdot|s_{t},a_{t}) with a valid probability distribution ( \sum f(s_{t+1}|s_{t},a_{t})=1 ) if a_{t} is the end of sequence token ( EOS ) for each step. Otherwise, it is a concatenation s_{t+1}=f(s_{t},a_{t})=[s_{t};a_{t}] . The stochastic transition brings external observations, such as user messages or tool-calling outputs, into the agent’s context. Finally, a reward function r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} produces a scalar reward per token. The objective is to find a policy that maximizes the expected cumulative rewards. RL fine-tuning of LLMs. Beyond imitation

Read the complete text