When a language model is trained with reinforcement learning to write programs, its reward usually comes from a test suite: the program passes every test or it does not. Recent pipelines build these suites by having a model write small generator programs, scripts that produce test inputs on demand, including huge stress cases and adversarial inputs aimed at slow or subtly wrong solutions. Stronger suites remove false positives, meaning wrong programs that slip through. But on hard problems they also make the reward flat. Every one of the model's sampled attempts fails, all get reward zero, and the learning signal disappears. Planning researchers call this situation a heuristic plateau: a region where the guiding score is identical everywhere, so the search cannot tell which direction is better.
The standard fix in planning is a principled tie-breaker, a secondary signal consulted only when the primary score is tied. We propose the same move for code RL. The generator programs already encode a natural ordering of difficulty: small random inputs, then boundary cases, then full-scale random inputs, then stratified inputs, then adversarial time-limit attacks. We use the highest consecutive tier a program passes as a tie-breaker. It is consulted only inside groups of samples whose strict pass/fail reward is identical. A wrong program can then never outrank a correct one, yet a flat group still yields a gradient. In two sentences: strict generated tests create zero-signal plateaus on hard problems, and lenient tests invite reward hacking. Gating a difficulty-ordered partial credit so it only breaks ties gives signal on the plateau without letting the lenient tests define what "correct" means.
Core Claim
Group-relative policy optimization (GRPO) is the RL method used by most code and math reasoning work. It scores each sampled program relative to the other samples drawn for the same problem. When all samples in a group receive the same reward, every advantage is zero and the problem contributes nothing. We claim three things. First, the fraction of such flat groups is a direct, measurable plateau width, and it grows with verifier strictness. Second, the abrupt growth of flat groups as training reaches hard problems is a cause of the instability that RL-for-code papers attribute to verifier quality. Third, a tier-ordered tie-breaker shrinks plateau width and stabilizes training, and it does so without the reward hacking produced by the obvious alternative of rewarding the fraction of tests passed.
The prior work splits along exactly this tension. HARDTESTGEN builds four kinds of generator (direct boundary inputs, range-based random scripts, stratified scripts that balance output classes, and "hack" generators targeting time limits). It shows that weak verifiers degrade GRPO training while its strict tests give stable validation curves, and that existing verifiers can have precision as low as 17% on the hardest problems. Themis names the failure modes of lenient suites as false positives and slow positives that RL learns to exploit. Both papers motivate strictness. Neither studies what strictness does to the shape of the reward signal on problems the policy cannot yet solve, which is the plateau side of the trade-off.
How the Directions Fit Together
The planning literature supplies the mechanism. Learning and Exploiting Progress States in Greedy Best-First Search learns classifiers that recognize "progress states" and uses them purely as tie-breakers on plateaus. Under the FF heuristic, this reduces expansions in 215 tasks against 43 for the baseline. Improving Greedy Best-First Search by Removing Unintended Search Bias shows that how ties are broken matters a great deal: arbitrary tie-breaking wastes effort on wide irrelevant regions, and a better rule raises solved tasks from 77 to 92.1.
We borrow the design principle: the secondary signal never overrides the primary one. We do not borrow the learned logical features, since those are planning-specific and costly to evaluate. Our tie-breaker is nearly free, because the tiers are just generator scripts run at different settings.
Training instability is the outcome we measure and try to prevent. Cliff Diving shows that RL reward surfaces have sharp cliffs. CAPO and ExGRPO stabilize LLM RL from the optimizer side:
- CAPO masks tokens whose updates cause curvature spikes.
- ExGRPO replays past successful attempts.
Both treat the reward as given. ExGRPO in particular has nothing to replay for a problem never solved, which is exactly the plateau case.
Exposure bias enters as a constraint and an evaluation lens rather than as a mechanism. Exposure bias is the mismatch between the conditions a model is trained under and the conditions it is used under; On Exposure Bias, Hallucination and Domain Shift in Neural Machine Translation shows this mismatch causes failures that compound. Training against a lenient verifier and evaluating against a strict one is the RL analogue. The policy learns behaviors that are rewarded during training and exposed at test time. Our gating rule is designed so the lenient tiers never become the training target. We measure this mismatch directly as the gap between training reward and held-out strict pass rate.
Research Program
We build tiered verifiers on top of the HARDTESTGEN generators for its 26.6k problems. Each problem's generators are run to produce up to $K=5$ ordered tiers:
- Small-size random inputs (the range-based generator with its size bound reduced).
- Boundary inputs.
- Full-scale random inputs.
- Stratified inputs.
- Time-limit attack inputs.
Expected outputs come from the existing oracle consensus, so correctness labels are no weaker than the original suite.
For a sampled program $y$, let $s(y)\in\{0,1\}$ be the strict reward (all tiers pass). Let $k(y)\in\{0,\dots,K\}$ be the number of consecutive tiers passed starting from tier 1. The reward within a group $G$ is
$$r(y) = s(y) + \lambda \cdot \mathbb{1}[\text{all } s \text{ equal in } G] \cdot \frac{k(y)}{K},$$
where $\lambda\in(0,1)$ sets the tie-breaker's weight. The indicator switches the tie-breaker on only when the strict rewards in the group are identical. In any group containing a strict pass, the tie-breaker is off, so ordering is purely by correctness. Requiring consecutive tiers, rather than a count, prevents credit for passing large random cases while failing small ones. That pattern usually signals output-format luck rather than progress.
The analysis has three parts. First, we measure plateau width (the fraction of flat groups per training step) as a function of verifier strictness across the HARDTESTGEN difficulty levels. We relate it to instability markers: gradient-norm spikes, entropy blow-up, and reward collapse. Second, we train with the gated tie-breaker and its competitors under matched compute. Third, we audit reward hacking. For every policy we measure the false-positive rate of its programs on lower tiers relative to the strict suite, and the train-to-test reward gap.
Baselines
The naive reference is GRPO with the binary strict reward alone, on the same tiered tests collapsed to pass/fail. This is the setting in which HARDTESTGEN reports stable, monotonic validation curves, but the file gives no numeric RL result for it. We also use the published rejection-sampling figure as a calibration point: HARDTESTS filtering raised LiveCodeBench pass@10 from 56.19% to 60.00%. For the RL setting, no reported result was found on Lacuna for GRPO on HARDTESTS. Beating this baseline means higher strict pass@1 on held-out LiveCodeBench problems at equal rollout count, especially on the hardest bucket.
The strongest reward-side competitor is pass-fraction reward: the fraction of all tier tests passed, always on. It is the most obvious dense signal and directly attacks the same plateau. It is run on identical tests, with the same rollout budget and an equal hyperparameter sweep over its scale. Beating it requires matching or exceeding its strict pass@1 while showing a lower false-positive rate. If pass-fraction ties on accuracy with no extra hacking, our gating is unnecessary, and we will say so.
A third baseline is dynamic filtering, a common GRPO practice: drop flat groups and resample until the batch is informative. It addresses the zero-advantage problem by spending more samples rather than adding signal. We give it the same total rollout budget, counting discarded samples.
The strongest optimizer-side competitors are CAPO and ExGRPO. CAPO reports up to 30× fewer training completions than conservative GRPO for equal MATH accuracy, with under 3% overhead. ExGRPO reports a +3.5-point average math gain on Qwen2.5-Math-7B, and it rescues Llama-3.1-8B Base from complete collapse. Both are run with binary strict reward and their published settings, tuned with the same sweep budget. We also run both combined with our tie-breaker, since the methods are complementary in principle.
We include two ablations of the key ingredient. Shuffled tiers keeps the gating but randomizes tier order per problem, which tests whether difficulty ordering carries progress information. Ungated tiers applies $k(y)/K$ in every group, which tests whether gating is what prevents hacking. A lenient-to-strict global curriculum, which switches tiers on over training, isolates per-group gating from simple scheduling.
Why not just…?
Why not just reward the fraction of tests passed? This is the real threat. On problems where partial correctness is meaningful, it may work as well as our method. What argues against it is Themis's finding that rewarding lenient suites produces false and slow positives that RL exploits. An always-on fraction keeps paying for those even after the policy can solve the problem. The pass-fraction baseline, the ungated ablation, and the false-positive audit settle this directly. If pass-fraction matches on strict accuracy and false-positive rate, we drop the gating claim and report the plateau-width analysis alone.
Why not just discard flat groups and sample more? Resampling does not create information on a problem the policy cannot solve. It only finds the rare lucky success, so its cost grows sharply as success probability falls. This mirrors the planning finding that blind tie-breaking wastes effort in wide plateaus (Asai and Fukunaga). The matched-budget comparison, stratified by difficulty, shows where this breaks. We expect parity on easy problems and a gap on the hardest bucket.
Why not just stabilize the optimizer with CAPO or replay? These address unstable updates, not missing signal. A flat group produces zero gradient whatever the optimizer does, and replay needs a prior success. Neither CAPO nor ExGRPO reports results on code RL in the file. Running them with and without the tie-breaker shows whether the gains are additive, which is what the plateau account predicts, or redundant.
Why not just raise temperature? Cliff Diving and selective noise injection show that unguided noise near sharp reward surfaces tends to push policies off cliffs rather than out of plateaus. We include a temperature sweep on the binary baseline as a cheap check.
Proposed Experiments
Training uses HARDTESTS problems dated before the evaluation window. Evaluation is pass@1 on LiveCodeBench, whose release-date cutoffs guard against contamination, scored with strict tests. Secondary evaluation uses held-out CodeContests+ problems with their roughly 101 tests per problem. We report results by difficulty bucket. We use two backbones: a 7B code model, and Llama-3.1-8B Base, chosen because ExGRPO documents its collapse under on-policy GRPO and so it stresses stability.
Tracked measures are:
- Plateau width per step.
- Gradient-norm spikes and entropy over training.
- Number of collapse events across three seeds.
- False-positive rate of generated programs on lower tiers relative to the strict suite.
- The gap between training reward and held-out strict pass rate.
The decisive checks are three. First, plateau width should predict instability in the binary baseline: flat-group fraction should rise before gradient spikes and reward drops. Second, the gated tie-breaker should beat pass-fraction on strict pass@1 in the hardest bucket, or tie it with a clearly lower false-positive rate. Third, the shuffled-tier ablation should lose most of the gain. If it does not, tier ordering carries no progress information, and the method reduces to generic partial credit.
A negative result on the second check would still be informative. It would mean that, for code, strictness-induced plateaus are better handled by spending samples or by optimizer-side fixes than by reshaping reward.
References
- HARDTESTGEN: A High-Quality RL Verifier Generation Pipeline for LLM Algorithimic Coding
- Themis: Automated Constraint-Aware Test Synthesis Framework for Code Reinforcement Learning
- Learning and Exploiting Progress States in Greedy Best-First Search
- Improving Greedy Best-First Search by Removing Unintended Search Bias (Extended Abstract)
- Cliff Diving: Exploring Reward Surfaces in Reinforcement Learning Environments
- Stabilizing Policy Gradients for Sample-Efficient Reinforcement Learning in LLM Reasoning
- ExGRPO: Learning to Reason from Experience
- On Exposure Bias, Hallucination and Domain Shift in Neural Machine Translation
- Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck
- LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code
- CodeContests+: High-Quality Test Case Generation for Competitive Programming