# Replay Failures as Successes: Sample-Efficient Reinforcement Learning for Instruction Following

arXiv: https://arxiv.org/abs/2512.23457 · HTML: https://mlsanity.com/paper/2512.23457/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 49 of its 60 references that are in the map.
- First posted on arXiv 29 Dec 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 49)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [PaLM-E: An Embodied Multimodal Language Model](https://mlsanity.com/paper/2303.03378/) (2023)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Large Language Models: A Survey](https://mlsanity.com/paper/2402.06196/) (2024)
- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judge](https://mlsanity.com/paper/2411.16594/) (2024)
- [Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning](https://mlsanity.com/paper/2502.14768/) (2025)
- [WebSailor: Navigating Super-human Reasoning for Web Agent](https://mlsanity.com/paper/2507.02592/) (2025)
- [Foundation Models in Robotics: Applications, Challenges, and the Future](https://mlsanity.com/paper/2312.07843/) (2023)
- [Generalizing Verifiable Instruction Following](https://mlsanity.com/paper/2507.02833/) (2025)
- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [Benchmarking Complex Instruction-Following with Multiple Constraints Composition](https://mlsanity.com/paper/2407.03978/) (2024)
- [InFoBench: Evaluating Instruction Following Ability in Large Language Models](https://mlsanity.com/paper/2401.03601/) (2024)
- [Self-play with Execution Feedback: Improving Instruction-following Capabilities of Large Language Models](https://mlsanity.com/paper/2406.13542/) (2024)
- [WebResearcher: Unleashing unbounded reasoning capability in Long-Horizon Agents](https://mlsanity.com/paper/2509.13309/) (2025)
- [CFBench: A Comprehensive Constraints-Following Benchmark for LLMs](https://mlsanity.com/paper/2408.01122/) (2024)
- [AGENTIF: Benchmarking Instruction Following of Large Language Models in Agentic Scenarios](https://mlsanity.com/paper/2505.16944/) (2025)
- [VerIF: Verification Engineering for Reinforcement Learning in Instruction Following](https://mlsanity.com/paper/2506.09942/) (2025)

## Built on by (most cited first, 8 of 8)

- [From Storage to Experience: A Survey on the Evolution of LLM Agent Memory Mechanisms](https://mlsanity.com/paper/2605.06716/) (2026)
- [Rubrics to Tokens: Bridging Response-level Rubrics and Token-level Rewards in Instruction Following Tasks](https://mlsanity.com/paper/2604.02795/) (2026)
- [FMBench: Adaptive Large Language Model Output Formatting](https://mlsanity.com/paper/2602.06384/) (2026)
- [Learning from Failures: Correction-Oriented Policy Optimization with Verifiable Rewards](https://mlsanity.com/paper/2605.14539/) (2026)
- [Counterfactual Constraint-Conditioned On-Policy Distillation for Multi-Constraint Instruction Following](https://mlsanity.com/paper/2609.27421/) (2026)
- [MOPD-Router: Rethinking Teacher Routing in Multi-Teacher On-Policy Distillation](https://mlsanity.com/paper/2609.30837/) (2026)
- [ScopeIF: Improving Scope-Aware Precise Instruction-Following in Large Language Models via Graded Reward Modeling](https://mlsanity.com/paper/2609.32189/) (2026)
- [Rubrics from the Task, Verdicts from Evidence: Pointwise Rubric Rewards with Tool-Augmented Judges](https://mlsanity.com/paper/2610.18766/) (2026)

## Abstract (arXiv)

Reinforcement Learning (RL) has shown promise for aligning Large Language Models (LLMs) to follow instructions with various constraints. Despite the encouraging results, RL improvement inevitably relies on sampling successful, high-quality responses; however, the initial model often struggles to generate responses that satisfy all constraints due to its limited capabilities, yielding sparse or indistinguishable rewards that impede learning. In this work, we propose Hindsight instruction Replay (HiR), a novel sample-efficient RL framework for complex instruction following tasks, which employs a select-then-rewrite strategy to replay failed attempts as successes based on the constraints that have been satisfied in hindsight. We perform RL on these replayed samples as well as the original ones, theoretically framing the objective as dual-preference learning at both the instruction- and response-level to enable efficient optimization using only a binary reward signal. Extensive experiments demonstrate that the proposed HiR yields promising results across different instruction following tasks, while requiring less computational budget. Our code and dataset is available at https://github.com/sastpg/HIR.