Freshness-Aware Prioritized Experience Replay for LLM/VLM Reinforcement Learning
Weiyu Ma, Yongcheng Zeng, Yan Song, Xinyu Cui, Jian Zhao, Xuhui Liu, Mohamed Elhoseiny · 2026
Read Freshness-Aware Prioritized Experience Replay for LLM/VLM Reinforcement Learning by Weiyu Ma, Yongcheng Zeng, Yan Song, Xinyu Cui, Jian Zhao, Xuhui Liu, Mohamed Elhoseiny (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-2604-16918.txt.
Introduction
Ma and six colleagues fix a staleness flaw in experience replay for language-model training. Old high-priority examples keep dominating sampling long after they stop teaching anything. Their freshness-aware variant decays priority exponentially with age, lifting scores by 46 percent on NQ Search, 367 percent on Sokoban, and 133 percent on VLM FrozenLake over on-policy baselines.
Catalog record
| CREATOR | Weiyu Ma, Yongcheng Zeng, Yan Song, Xinyu Cui, Jian Zhao, Xuhui Liu, Mohamed Elhoseiny |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49253 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16918
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Freshness-Aware Prioritized Experience Replay for LLM/VLM Reinforcement Learning Weiyu Ma, Yongcheng Zeng, Yan Song, Xinyu Cui, Jian Zhao, Xuhui Liu, Mohamed Elhoseiny Abstract Reinforcement Learning (RL) has achieved impressive success in post-training Large Language Models (LLMs) and Vision-Language Models (VLMs), with on-policy algorithms such as PPO, GRPO, and REINFORCE++ serving as the dominant paradigm. However, these methods discard all collected trajectories after a single gradient update, resulting in poor sample efficiency, particularly wasteful for agentic tasks where multi-turn environment interactions are expensive. While Experience Replay drives sample efficiency in classic RL by allowing agents to reuse past trajectories and prioritize informative ones, directly applying Prioritized Experience Replay (PER) to LLMs fails. The rapid policy evolution of billion-parameter models renders stored priorities stale, causing old high-priority trajectories to dominate sampling long after they have become uninformative. We propose FreshPER, which addresses this priority staleness problem by augmenting any PER-based priority with a multiplicative exponential age decay grounded in effective sample size analysis. To the best of our knowledge, FreshPER is the first work to successfully apply PER to LLM/VLM reinforcement learning. We evaluate on eight multi-step agentic, reasoning, and math competition tasks with 0.5B, 3B, and 7B models. FreshPER significantly outperforms on-policy baselines, achieving +46% on NQ Search, +367% on Sokoban, and +133% on VLM FrozenLake, while standard PER without age decay consistently degrades performance. Our code is publicly available at https://github.com/Vision-CAIR/Freshness-Aware-PER . 1 Introduction Figure 1: Overview of the FreshPER training pipeline. Top : On-policy loop—the behavior policy \pi_{\mu} (vLLM inference) interacts with agentic environments, and the current policy \pi_{\theta} (DeepSpeed training) is updated via policy gradient on fresh data. Bottom : Off-policy loop—trajectories with their behavior log-probs and rewards are stored in the replay buffer on the CPU controller. An asynchronous thread refreshes priorities via p_{i}\leftarrow p_{i}^{\text{base}}\cdot\exp(-\Delta_{i}/\tau) , and prioritized batches are sampled for additional off-policy training. Reinforcement learning (RL) has become a transformative technique for large language models (LLMs). RLHF ( 24 ) played a central role in producing ChatGPT, demonstrating that RL-based post-training can dramatically improve the usability and safety of LLMs. More recently, OpenAI o1 ( 23 ) and DeepSeek-R1 ( 2 ) showed that RL can unlock advanced reasoning capabilities, achieving expert-level performance on mathematics and coding benchmarks. These successes have been powered by on-policy policy gradient algorithms—PPO ( 31 ) , GRPO ( 33 ) , and REINFORCE++ ( 10 ) —which remain the dominant training paradigm. A particularly exciting frontier is agentic RL , where LLMs and vision-language models (VLMs) interact with external environments over multiple turns: searching the web ( 13 ) , executing code ( 40 ) , calling tools ( 30 ) , and navigating visual environments ( 4 ) . Unlike single-turn preference alignment, agentic RL requires the model to take sequential actions and receive feedback from a live environment, bringing LLM training much closer to the classical RL paradigm. This shift also introduces a critical new challenge: environment interactions are very expensive . Consider training a search agent with REINFORCE++ on a retrieval-augmented QA task ( 13 ) . Each prompt generates multiple rollout trajectories (e.g., 8 per prompt), and each trajectory involves up to 5 search turns. For a batch of 128 prompts, this yields over 5,000 retrieval calls per iteration, each requiring embedding computation and vector index lookup on dedicated hardware. The rollout stage alone dominates training time, often exceeding 70% of the total wall-clock cost ( 43 ) . Yet on-policy algorithms use these expensive trajectories for a single gradient update and then discard them entirely ( fig. 2 ). Figure 2: On-policy LLM RL algorithms (PPO, REINFORCE++, GRPO) use each trajectory for a single gradient update and then discard it ( \otimes ), regardless of its learning potential. In classical RL, experience replay ( 15 ; 21 ) and its prioritized variant PER ( 29 ) are the standard solutions to this problem, enabling agents to reuse past experiences and prioritize the most informative ones. However, directly applying PER to LLM RL fails. The core issue is priority staleness : LLM policies evolve rapidly due to large gradient updates on long token sequences, causing old high-priority trajectories to dominate sampling long after they have become uninformative or even detrimental. Standard PER has no mechanism to account for this temporal degradation. We present FreshPER, which addresses priority staleness by augmenting any PER base priority with a multiplicative exponential age decay, directly motivated by the exponential decay of effective sample size (ESS) as the policy diverges from the behavior policy. This simple mechanism ensures that even the highest-priority old trajectory is eventually deprioritized below a fresh trajectory of moderate priority, while preserving the informativeness-driven sampling of standard PER. The main contributions of this work are summarized as follows: • To the best of our knowledge, we are the first to successfully apply PER to LLM/VLM RL. We identify priority staleness as a key failure mode and propose freshness-aware age decay grounded in importance sampling theory. • We implement a complete off-policy training pipeline with trajectory-level replay, integrated into the ROLL framework ( 38 ) . • We demonstrate consistent improvements across eight environments with 0.5B, 3B, and 7B models, achieving +46% on NQ Search, +367% on Sokoban, and +133% on VLM FrozenLake, while standard PER without age decay consistently degrades. 2 Related Work Reinforcement learning has become a central technique for post-training LLMs and VLMs, spanning preference alignment ( 24 ) , reasoning ( 2 ; 33 ) , agentic tasks ( 42 ; 13 ; 39 ) , and visual reasoning ( 12 ; 34 ) . Distributed training frameworks such as ROLL ( 38 ) , veRL ( 35 ) , and OpenRLHF ( 11 ) provide the infrastructure to scale these methods. Below we review three threads most relevant to our work. Online and Offline RL for LLMs. Online (on-policy) methods dominate LLM RL. PPO ( 31 ) remains the workhorse of RLHF ( 24 ) ; GRPO ( 33 ) simplifies it by removing the critic; DAPO ( 44 ) , REINFORCE++ ( 10 ) , and Dr. GRPO ( 16 ) further refine the policy gradient estimator. On the offline side, DPO ( 27 ) and its iterative variants ( 3 ) optimize from preference data without environment interaction. A common limitation across online methods is that trajectories are discarded after a single gradient update, while offline methods forgo interaction entirely. Off-Policy RL for LLMs. A middle ground is off-policy training, which reuses historical trajectories. Asynchronous RLHF ( 22 ) and AReaL ( 8 ) decouple generation from training with uniform replay. This introduces data staleness, prompting work on off-policy stability through importance-weight control ( 28 ; 46 ; 41 ; 18 ) . On the data reuse side, RLEP ( 45 ) replays correct trajectories, DOTS ( 36 ) combines difficulty-targeted selection with replay, and LoRR ( 17 ) enables high replay ratios via parameter resets. Most recently, Fatemi ( 6 ) proposes problem-level prioritized scheduling for RL post-training, but explicitly argues that transition-level PER is “ill-suited for sequence models” and instead uses success-rate-based curriculum scheduling. In contrast, we demonstrate that trajectory-level PER can succeed in LLM RL when augmented