# Outcome-based Exploration for LLM Reasoning

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

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 54 of its 71 references that are in the map.
- First posted on arXiv 8 Sep 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Understanding the Effects of RLHF on LLM Generalisation and Diversity](https://mlsanity.com/paper/2310.06452/) (2023)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Reasoning with Exploration: An Entropy Perspective](https://mlsanity.com/paper/2506.14758/) (2025)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)

## Built on by (most cited first, 30 of 83)

- [Reasoning with Sampling: Your Base Model is Smarter Than You Think](https://mlsanity.com/paper/2510.14901/) (2025)
- [AgentEvolver: Towards Efficient Self-Evolving Agent System](https://mlsanity.com/paper/2511.10395/) (2025)
- [Rethinking Entropy Interventions in RLVR: An Entropy Change Perspective](https://mlsanity.com/paper/2510.10150/) (2025)
- [POPE: Learning to Reason on Hard Problems via Privileged On-Policy Exploration](https://mlsanity.com/paper/2601.18779/) (2026)
- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Soft Tokens, Hard Truths](https://mlsanity.com/paper/2509.19170/) (2025)
- [RL Squeezes, SFT Expands: A Comparative Study of Reasoning LLMs](https://mlsanity.com/paper/2509.21128/) (2025)
- [KL-Regularized Reinforcement Learning is Designed to Mode Collapse](https://mlsanity.com/paper/2510.20817/) (2025)
- [Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening](https://mlsanity.com/paper/2601.21590/) (2026)
- [Diversity-Incentivized Exploration for Versatile Reasoning](https://mlsanity.com/paper/2509.26209/) (2025)
- [Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Reward](https://mlsanity.com/paper/2512.16912/) (2025)
- [Differential Smoothing Mitigates Sharpening and Improves LLM Reasoning](https://mlsanity.com/paper/2511.19942/) (2025)
- [Compute as Teacher: Turning Inference Compute Into Reference-Free Supervision](https://mlsanity.com/paper/2509.14234/) (2025)
- [Beyond the Sampled Token: Preserving Candidate Support in RLVR](https://mlsanity.com/paper/2510.14807/) (2025)
- [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025)
- [Reuse your FLOPs: Scaling RL on Hard Problems by Conditioning on Very Off-Policy Prefixes](https://mlsanity.com/paper/2601.18795/) (2026)
- [Rebellious Student: Reversing Teacher Signals for Reasoning Exploration with Self-Distilled RLVR](https://mlsanity.com/paper/2605.10781/) (2026)
- [Teaching Models to Teach Themselves: Reasoning at the Edge of Learnability](https://mlsanity.com/paper/2601.18778/) (2026)
- [Clip-Low Increases Entropy and Clip-High Decreases Entropy in Reinforcement Learning of Large Language Models](https://mlsanity.com/paper/2509.26114/) (2025)
- [Quantile Advantage Estimation: Stabilizing RLVR for LLM Reasoning](https://mlsanity.com/paper/2509.22611/) (2025)
- [Revisiting Entropy Regularization: Adaptive Coefficient Unlocks Its Potential for LLM Reinforcement Learning](https://mlsanity.com/paper/2510.10959/) (2025)
- [Save the Good Prefix: Precise Error Penalization via Process-Supervised RL to Enhance LLM Reasoning](https://mlsanity.com/paper/2601.18984/) (2026)
- [Random Policy Valuation is Enough for LLM Reasoning with Verifiable Rewards](https://mlsanity.com/paper/2509.24981/) (2025)
- [MATH-Beyond: A Benchmark for RL to Expand Beyond the Base Model](https://mlsanity.com/paper/2510.11653/) (2025)
- [Can LLMs Guide Their Own Exploration? Gradient-Guided Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2512.15687/) (2025)
- [h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning](https://mlsanity.com/paper/2510.07312/) (2025)
- [MindGPT-4ov: An Enhanced MLLM via a Multi-Stage Post-Training Paradigm](https://mlsanity.com/paper/2512.02895/) (2025)
- [Expanding LLM Agent Boundaries with Strategy-Guided Exploration](https://mlsanity.com/paper/2603.02045/) (2026)
- [Uniform-Correct Policy Optimization: Breaking RLVR's Indifference to Diversity](https://mlsanity.com/paper/2605.00365/) (2026)
- [Exploring Multi-Temperature Strategies for Token- and Rollout-Level Control in RLVR](https://mlsanity.com/paper/2510.08892/) (2025)

## Abstract (arXiv)

Reinforcement learning (RL) has emerged as a powerful method for improving the reasoning abilities of large language models (LLMs). Outcome-based RL, which rewards policies solely for the correctness of the final answer, yields substantial accuracy gains but also induces a systematic loss in generation diversity. This collapse undermines real-world performance, where diversity is critical for test-time scaling. We analyze this phenomenon by viewing RL post-training as a sampling process and show that, strikingly, RL can reduce effective diversity even on the training set relative to the base model. Our study highlights two central findings: (i) a transfer of diversity degradation, where reduced diversity on solved problems propagates to unsolved ones, and (ii) the tractability of the outcome space, since reasoning tasks admit only a limited set of distinct answers. Motivated by these insights, we propose outcome-based exploration, which assigns exploration bonuses according to final outcomes. We introduce two complementary algorithms: historical exploration, which encourages rarely observed answers via UCB-style bonuses, and batch exploration, which penalizes within-batch repetition to promote test-time diversity. Experiments on standard competition math with Llama and Qwen models demonstrate that both methods improve accuracy while mitigating diversity collapse. On the theoretical side, we formalize the benefit of outcome-based exploration through a new model of outcome-based bandits. Together, these contributions chart a practical path toward RL methods that enhance reasoning without sacrificing the diversity essential for scalable deployment.