While scaling laws guide compute allocation for LLM pre-training, analogous prescriptions for reinforcement learning (RL) post-training of large language models (LLMs) remain poorly understood. We study the compute-optimal allocation of sampling compute for on-policy RL methods in LLMs, framing scaling as a compute-constrained optimization over three resources: parallel rollouts per problem, number of problems per batch, and number of update steps. We find that the compute-optimal number of parallel rollouts per problem increases predictably with compute budget and then saturates. This trend holds across both easy and hard problems, though driven by different mechanisms: solution sharpening on easy problems and coverage expansion on hard problems. We further show that increasing the number of parallel rollouts mitigates interference across problems, while the number of problems per batch primarily affects training stability and can be chosen within a broad range. Validated across base models and data distributions, our results recast RL scaling laws as prescriptive allocation rules and provide practical guidance for compute-efficient LLM RL post-training.
Figures & tables
Figure 1: Compute-optimal sampling for LLM RL. We study allocation of sampling compute along three axes: parallel rollouts per problem ( n ), problems per batch ( Bp ), and sequential iterations ( M ), where the total compute is C=Bp⋅n⋅M . We find that: (1) optimal number of rollouts n increases with the compute budget C ; (2) easy and hard problem sets exhibit similar scaling trends but arise from different underlying mechanisms; (3) under a constraint on B=Bp⋅n , the optimal strategy prioritizes larger Bp (smaller n ) at low compute budgets, and shifts toward larger n (smaller Bp ) at high compute budgets to maximize performance; and (4) Bp has only a marginal effect on performance when kept within a moderate range.
Figure 2: Difficulty distribution of Easy vs. Hard problems. We split problems into Easy and Hard sets according to pass@16 (average pass rate over 16 generations per problem).
Figure 3: Regularization ablations on Easy and Hard. On the Easy set, standard KL+Entropy regularization achieves the best reward. On the Hard set, these regularizers destabilize training even with zero-variance filtering; disabling them yields significantly more stable optimization and higher reward.
Figure 4: LR scaling strategy. Square-root scaling ( B ) outperforms linear and constant scaling at large batch sizes ( B=8192 ).
Figure 5: Illustration of record-breaking points. Gray dots show validation reward points from multiple training runs, while orange dots mark record-breaking points, defined as the earliest (smallest compute) points that enter a higher discretized reward bin than all previous points. The dashed curve shows the monotonic fit over the retained points on the performance frontier.
Figure 6: Validation reward vs. compute (Bp=32) . The frontier shifts to larger n as compute increases. For easy problems (left) , large n dominates at high compute where small n plateaus. Hard problems (right) show the same trend but saturate earlier with a smaller n .
Figure 7: Compute-optimal scaling of parallel rollouts n ( Bp=32 ). The optimal value of rollouts n shifts systematically higher as the total sampling compute increases. Points show a running-average estimate of the frontier-attaining n∗(C) at each compute budget (colored by reward), and the red curves fit a sigmoid parameterizing logn as a function of logC .
Figure 8: Different mechanisms of how n values optimize best@4 vs. worst@4 on easy and hard problems. Bars show the n maximizing reward for a given Bp . On the Easy set (left) , the optimal n for best@4 is smaller than for worst@4, indicating that improving robustness requires more parallel rollouts than for coverage. Conversely, on the Hard set (right) , a larger n is needed to improve best@4, while worst@4 saturates at smaller n .
Figure 9: Compute-optimal allocation shifts from Bp to n under a fixed total batch size constraint on easy set.
Figure 10: Sensitivity of validation reward to Bp vs. n . Easy (left) : The impact of varying n (9.2% range) shows a clear positive correlation and is significantly larger than varying Bp (1.9%). Hard (right) : Sensitivity to Bp (2.2%) is comparable to n (3.1%). The fluctuating trend in the top-right plot suggests that Bp selection introduces optimization instability on hard tasks, explaining the less predictable trends when fixing B .
Figure 11: Training reward distributions on Easy and Hard sets at a matched compute level ( n=8 vs. n=128 ). (1) Interference exists: On the Easy set (initial pass rate 0.3-0.6), optimization sacrifices some problems, leaving a non-zero fraction unsolved after training. (2) Easy set: Larger n results in a more uniform distribution of pass rates, avoiding polarized outcomes seen in smaller n . (3) Hard set: Larger n improves coverage (reducing zero fraction), while smaller n sharpens performance on a subset.
Figure 12: Generalizing n scaling trends to other models. We observe increasing n boosts returns at high compute across all settings, while optimal n saturates differently.
Figure 13: Impact of data size ( D ). With more data ( D=6k ; left ), performance scales up to n=512 . With small data ( D=500 ; right ), the frontier saturates at smaller n=256 , and scaling further to n=512 leads to overfitting and degradation.
Figure 14: Results across difficulty levels for small ( n=8 ) and large ( n=64 ) rollout budgets under different training data distributions (5K total samples) using Qwen2.5-7B-Instruct. We consider Hard ( pass@128=0 ), Easy ( pass@128∈[0.3,0.6] ), and Very Easy ( pass@128∈[0.6,0.9] ) problems. Rows correspond to Hard Only, Heterogeneous-Dual Mix (50% Hard, 50% Easy), and Heterogeneous-Tri Mix (50% Hard, 25% Easy, 25% Very Easy; the J-shaped distribution from Polaris). Across distributions, larger n consistently performs better at higher compute in in-domain evaluations , except on the Very Easy evaluation set, where the task is likely too easy for additional compute to matter. Training only on Hard data causes substantial catastrophic forgetting on Easy and Very Easy problems , while mixing Easy data largely mitigates this effect with only a small drop on Hard performance. In contrast, adding Very Easy data does not help and can hurt both Easy and Hard performance.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 15: Demonstrations of frontier point detection for each n . (Left) Validation reward trajectories plotted against compute (rollouts) for varying population sizes ( n=32 in blue, n=64 in red). Scatter points show raw data; dashed curves show smoothed trends. Arrows illustrate the “record-breaking” extraction process, identifying the earliest compute step where reward crosses a discretized threshold (e.g., 0.5 or 0.6 ). In practice, we employ finer reward bins (e.g., 0.005 ) tailored to task difficulty. (Right) Extracted frontier points in the n vs. Compute space. Each circle represents the compute budget C required for a specific n to reach a higher performance bin. The dashed curve shows the fitted scaling law, indicating the optimal n scaling as compute increases.
Figure 16: Compute-optimal frontiers maximizing over n varying problems per batch ( Bp ) on the Easy set.
Figure 17: Compute-optimal frontiers maximizing over n varying problems per batch ( Bp ) on the Hard set.
Figure 18: Compute-optimal frontiers on the Easy set under fixed total batch size B∈{4096,8192,16384} . Each subplot fixes the total batch size B and sweeps the number of parallel rollouts per problem plotting validation reward versus compute (measured in millions of rollouts).
Figure 19: Compute-optimal frontiers on the Hard set under fixed total batch size B∈{4096,8192,16384} . Compared to the Easy set, the trends are noisier in the Hard regime. Nevertheless, the qualitative trend remains consistent: as compute increases, the compute-optimal allocation increasingly favors larger parallel rollouts per problem, i.e., larger n .
Figure 20: Compute-optimal frontiers on the in-domain Extremely Hard subset (pass@128 =0 ), evaluated with best@4 (left) and worst@4 (right). Larger n improves best@4 at higher compute, whereas worst@4 is maximized by a moderate n=64 , highlighting a strong coverage-sharpening trade-off in the extremely hard regime.
Figure 21: Compute-optimal parallel rollouts n∗(C) under joint optimization of (Bp,n,M) . For each total rollout compute budget C , we sweep (Bp,n,M) and select the globally best configuration. The optimal n increases monotonically with compute and is well-fit by a sigmoid trend on both the Easy (left) and Hard (right) splits.
Figure 22: Compute-optimal frontiers from sweeping (Bp,n,M) on Easy and Hard problems. Points on the frontier are annotated by the pre-training sampling configuration (Bp,n) , with M determined by the remaining compute. Consistent with earlier sections, the frontier shifts to systematically larger n as compute increases. In contrast, the frontier-attaining Bp varies across budgets but has only a marginal effect on performance within a moderate range (cf. Section 4.2 ).
Figure 23: AIME 24 scores trained with varying parallel rollouts ( n ) under a fixed problem batch size ( Bp=32 ).
Figure 24: n∗ scaling is consistent under token-based vs. rollout-based compute. We fit sigmoid curves for log2(n∗) as a function of compute C , using either total generated tokens ( left ) or total rollouts ( right ). Both choices produce the same qualitative scaling curve—rapid growth followed by saturation—indicating that the compute-optimal n∗ trend is robust to the compute definition.
Figure 25: Generalization to other RL algorithms (PPO and CISPO). Validation reward versus compute (million rollouts) for varying parallel rollouts per problem n . Left: Easy set with PPO. Middle: Hard set with PPO. Right: Easy set with CISPO. The qualitative trend matches the main text: as compute increases, larger n becomes increasingly favorable, with a stronger separation on the Hard split.
Figure 26: Effects of baseline estimation variance. Validation reward vs. compute (million rollouts) under a fixed problem batch size Bp=128 , comparing three GRPO settings: (i) large group size ntrain/nest=256/256 , (ii) small group size 64/64 , and (iii) decoupled baseline estimation 64/256 (estimate baseline from 256 rollouts but sample 64 from them for the policy-gradient update). We observe consistent ordering (1) > (3) ≈ (2) , showing that lower-variance baseline estimation yields negligible gains, while the full n=256 run remains best, indicating the dominant gains from scaling n come from broader exploration.
Figure 27: Dynamics of pass@1 distributions (sanity-checking the interference analysis in Fig. 11 ). We visualize the evolution of pass@1 histograms across training for the same four cases (Easy/Hard ⋅n=8/128 ) at matched compute. The temporal trajectories corroborate the main-text interpretation: on Easy , small n progressively polarizes into a mass near 1 with a persistent non-zero fraction near 0 (optimization-induced interference ), whereas large n maintains a more dispersed, uniform distribution. On Hard , large n increases coverage by steadily reducing the zero-mass, while small n concentrates gains on a subset of solvable problems, yielding sharper but less comprehensive improvements.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
We demonstrate that training LLMs with RL does not improve performance equally across a dataset. RL shows large improvements on easy problems that an LLM is already good at solving, but small improvements on hard problems. We call this the Matthew Effect in RL for LLMs, after the phenomenon of cumulative advantage from economics and network science summarized as "the rich get richer". The naive explanation is that hard problems require more compute to find a solution. We argue that modern RL methods are exacerbating the issue by wasting too much compute on easy problems and instead should dynamically reallocate how they use compute. We introduce Never Give Up (NGU), a simple adaptive sampling method that keeps generating samples for a problem until one is correct. By leveraging asynchronous RL, this naturally uses fewer samples to filter out easy problems and allocates more compute to solving harder problems. We investigate the design choices that affect NGU, such as off-policy robustness, and develop a set of best practices. On the math benchmark Deepscaler, NGU improves performance per compute, especially on harder problems. On a recent coding task, Manufactoria, standard GRPO with a per-test reward fails to fully solve problems that have a range of easy and difficult tests. NGU iteratively improves, solving harder and harder tests, until it learns to fully solve coding problems.
Michael Noukhovitch, Hamish Ivison, Nathan Lambert +1
Mila, Université de Montréal · Allen Institute for AI · University of Washington +1
Reinforcement Learning with Verifiable Rewards (RLVR) and other RL-style post-training paradigms have been used for aligning large language models (LLMs) with reasoning standards. The resulting recent Reasoning Language Models (RLMs) such as DeepSeek-R1, o3, and Kimi k1.5 show that such RL-style post-training ("RL-for-LLMs") can substantially improve chain-of-thought reasoning, long-horizon planning, and self-correction. However, the computational footprint of these systems is massive: state-of-the-art RLM training requires millions of GPU-hours and tightly coupled multi-model pipelines that stress modern hardware far beyond classical supervised LLM training. This makes RLM training as much a parallel and distributed systems problem as an algorithmic one. In this work, to facilitate developing RLMs that are simultaneously high-performance, scalable, and cost-effective, we first systematize the RL-for-LLM paradigm and provide a compute-centric analysis of prominent post-training algorithmic frameworks: Proximal Policy Optimization (PPO), Group Relative Policy Optimization (GRPO), as well as their variants. Second, we develop a taxonomy of intra- and inter-model parallelism strategies for RL-for-LLMs, covering both traditional techniques (data, tensor, pipeline, sequence, context, and expert parallelism) as well as novel forms of parallelism and optimization techniques for multi-model RLM training, for example disaggregated placement, stage fusion, hybrid parallelism, and asynchronous execution. We harness the work-depth model of parallel computing to make our taxonomy and its insights rigorous and portable. Finally, we analyze existing RLM frameworks and we distill practical guidelines and outline open research directions for building scalable, fast, and cost-effective RLMs.
Recent studies on reinforcement learning (RL) report seemingly conflicting evidence about large language model (LLM) reasoning. Training on mathematics can improve performance in other domains, yet gains in Pass@1 can coincide with lower Pass@N than the base model. This raises a fundamental question: does RL expand an LLM's reasoning boundary, or merely reweight its existing reasoning space? We revisit these phenomena across Qwen and Gemma model families, showing both cross-domain gains and forgetting, while coverage at large sampling budgets increases on some tasks and decreases on others. Detailed analysis of solution traces before and after RL indicates a shift in the reasoning strategies the model employs, motivating a two-stage autoregressive policy model that separates strategy selection from problem-specific execution. Within this framework, we prove how RL's implicit bias reshapes strategy preferences, allowing gains on some tasks while suppressing strategies required by others. This mechanism can also broaden or narrow coverage at a given sampling budget even without expanding strategy support. We further provide theoretical justifications for log-sigmoid and log-linear scaling laws in RL compute, and evaluate their predictive power. Together, these results connect changes in strategy selection to cross-domain transfer, reasoning coverage, and compute scaling.