Outcome-based Exploration for LLM Reasoning
Yuda Song, Julia Kempe, Remi Munos · 2025
Read Outcome-based Exploration for LLM Reasoning by Yuda Song, Julia Kempe, Remi Munos (2025) 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-2509-06941.txt.
Introduction
Reinforcement learning that rewards only correct final answers makes language models less varied, and Yuda Song and two co-authors propose a fix in a 2025 machine learning paper. Outcome-based training raises accuracy but collapses generation diversity, which hurts test-time scaling, where many attempts are sampled. The authors analyze training as a sampling process.
Two findings stand out: diversity loss on solved problems spreads to unsolved ones, and a reasoning task allows only a small, enumerable set of distinct answers, so outcomes can be explored directly. Their outcome-based exploration adds bonuses based on final answers. One algorithm rewards rarely observed answers, in the style of upper confidence bounds; the other penalizes repetition inside a batch. On competition math with Llama and Qwen models, both improved accuracy while limiting diversity collapse, backed by a new bandit model.
Catalog record
| CREATOR | Yuda Song, Julia Kempe, Remi Munos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06941
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Outcome-based Exploration for LLM Reasoning Yuda Song, Julia Kempe, Remi Munos Abstract 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 𝚄𝙲𝙱 \mathtt{UCB} -style bonuses, and batch exploration , which penalizes within-batch repetition to promote test-time diversity. Experiments on standard competition math with 𝙻𝚕𝚊𝚖𝚊 \mathtt{Llama} and 𝚀𝚠𝚎𝚗 \mathtt{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. † † affiliation: FAIR at Meta † † affiliation: CMU † † affiliation: NYU † † date: August 10, 2026 † † correspondence: Yuda Song at [email protected] Figure 1: Test performance comparison (averaged across \mathtt{MATH\text{-}500} , \mathtt{AIME2024/2025} , \mathtt{AMC23} ) between our exploration methods ( \mathtt{UCB\text{-}Con} and \mathtt{Batch} ) and the \mathtt{GRPO} baseline, with \mathtt{Llama\text{-}3.1\text{-}8B\text{-}Instruct} on the easy dataset (left) and \mathtt{Qwen\text{-}2.5\text{-}7B\text{-}Base} on the medium dataset (right). We report pass@ k for k\in\{1,2,4,8,16,32\} on an early checkpoint (at timestep 100) and the final checkpoint (at timestep 700). We repeat each experiment with 3 different random seeds and plot the mean performance. The exploration methods outperform the baseline on nearly all metrics across the training process (except \mathtt{Qwen\text{-}2.5\text{-}7B\text{-}Base} with \mathtt{UCB\text{-}Con} on pass@1 on the early checkpoint due to exploration, but it has much higher pass@32 rate), and better exploitation-exploration trade-off and mitigation of overoptimization (note that the last checkpoint of Llama 3.1 8B with Vanilla RL has overall worse performance than its early checkpoint due to overoptimization). 1 Introduction Large language models (LLMs) are commonly post-trained with reinforcement learning (RL), both in preference alignment ( Ouyang et al. 2022 ; Bai et al. 2022 ) and in reasoning ( Shao et al. 2024 ; Guo et al. 2025 ) . A longstanding difficulty in RL is the design of reward signals: while one might hope to shape intermediate reasoning steps, recent works have shown that the seemingly crude strategy of rewarding only the final correctness (e.g., whether a math answer is correct) can be remarkably effective ( Shao et al. 2024 ; Guo et al. 2025 ) . However, a growing body of evidence points to an important drawback of RL post-training: a systematic loss of diversity in model generations ( Song et al. 2024b ; Dang et al. 2025 ; Yue et al. 2025 ; Zhao et al. 2025 ; Wu et al. 2025 ) . This phenomenon is most cleanly captured by the pass@ k metric: when k is large (say k=512 ), post-trained models exhibit a lower pass@ k than the base model. This raises a practical concern: in real-world deployments, diversity is often valuable and can amplify performance through test-time scaling ( Wu et al. 2024 ; Snell et al. 2024 ) , with different sampling processes such as directly sampling from the model or tree search. Indeed, we find that diversity degradation already manifests during training, as models collapse to a reduced set of candidate answers on unsolved problems due to a transfer effect of the diversity degradation induced by concentrating on correct answers, which we detail in \pref sec:motivation. Exploration is the canonical RL tool for combating such collapse ( Bellemare et al. 2016 ; Azar et al. 2017 ; Burda et al. 2018 ) . However, directly importing classical techniques such as Upper Confidence Bound ( \mathtt{UCB} ) exploration ( Auer et al. 2002 ) to token-level language modeling is intractable, as it would require searching over exponentially many sequences. Motivated by the success of outcome-based rewards, we therefore study outcome-based exploration , where exploration bonuses depend only on final outcomes. This perspective allows us to adapt \mathtt{UCB} -style methods to LLM training, which we further refine by incorporating both positive and negative outcome signals. A subtlety arises, however: in language models, one must distinguish between historical exploration (visiting a more diverse set of states and actions during training) and batch exploration (producing diverse outputs at test time). The latter improves pass@k but does not necessarily increase diversity during training whereas the former improves pass@1 but does not guarantee test-time diversity of the trained model. We introduce and study a batch version of outcome-based exploration, which demonstrates improved tradeoff between accuracy and diversity during test time. Our contributions 1. We study RL post-training dynamics by framing RL as a sampling process ( \pref sec:motivation). This perspective reveals that diversity loss is not limited to test-time behavior, but already occurs on the training set: as RL concentrates probability mass on previously solved questions, the resulting collapse propagates and reduces diversity even on unsolved ones. We term this effect the transfer of diversity degradation. 2. We propose outcome-based exploration ( \pref sec:method), which adapts classical exploration bonuses (e.g. \mathtt{UCB} ) to the outcome space of LLM tasks. We show that naively adapting \mathtt{UCB} does not lead to improved testing performance. We thus propose more refined algorithms ( \mathtt{UCB\text{-}Mean} , \mathtt{UCB\text{-}Con} ) which incorporate both positive and negative signals, and show that they improve both training exploration and test generalization, on standard reasoning dataset such as \mathtt{DAPO} and models such as \mathtt{Llama\text{-}3.1\text{-}8B\text{-}Instruct} . We further provide a theoretical analysis on the benefit of outcome-based exploration in a new bandit setting (outcome-based bandits), inspired by the practical considerations ( \pref sec:theoretical-results-summary). 3. We introduce a batch version of the outcome-based exploration algorithm ( \mathtt{Batch} ) ( \pref sec:batch). By penalizing repetitive answers within the latest samples, the algorithm explicitly encourages diverse generations on the batch level, yielding a better accuracy–diversity tradeoff at test time. 4. We analyze the interaction between historical and batch exploration, showing that they are not mutually exclusive ( \pref sec:his_vs_batch). In summary, our proposed methods can be easily incorporated into standard RL for LLMs reasoning training, agnostic to the training algorithm, and consistently improve both accuracy and diversity. 2 Diversity Degradation: RL as Sampling 2.1 Preliminaries We consider LLM reasoning training with RL in a verifiable reward setting. Denote the set of questions as \mathcal{X} , the training question set \mathcal{X}_{\mathsf{train}}\subseteq\mathcal{X} and the test question set \mathcal{X}_{\mathsf{test}}\subseteq\mathcal{X} . Further, define the space of intermediate text as \mathcal{Y} , and the answer space as \mathcal{A} ; we consider an LLM to be a