RL without Ground-Truth Solutions: RiVER Improves LLMs on Score-Based Tasks

Paper: 2606.27369 Authors: Yingyu Lin, Qiyue Gao, Nikki Lijing Kuang, Xunpeng Huang, Kun Zhou, Tongtong Liang, Zhewei Yao, Yi-An Ma, Yuxiong He Categories: cs.LG

The Gap

Existing RLVR (reinforcement learning with verifiable rewards) assumes a ground-truth answer exists for each task — you compare the model’s output to the answer and assign +1 or 0. This works for math, code correctness, etc. But many real-world tasks (heuristic search, optimization, creative design) have no unique correct answer. Prior work either avoided RL or used hand-crafted reward models. Neither scales.

The paper identifies two specific failure modes when naively applying group-relative RL to continuous execution scores: scale dominance (instances with large score ranges dominate the gradient) and frequency dominance (mediocre solutions repeatedly sampled drown out rare strong ones). RiVER tackles both with instance-wise rank calibration.

Problem: RL for LLM needs verifiable ground-truth
   |
   v
Gap: Many tasks (score-based) have no G.T. answer
   |
   v
Assumption: Raw execution scores + calibration can replace G.T.
   |
   v
Method: RiVER (group-relative RL + rank-calibrated reward shaping)
   |
   v
Evidence: +8.9% ALE rating on Qwen-3, +9.4% on GLM, +2.4%/+3.5% on exact-solution benchmarks
   |
   v
Conclusion: Score tasks with proper calibration are effective RL environments without G.T.

The Increment

One sentence: Before RiVER, RLVR was locked to tasks with ground-truth answers; after RiVER, any task with a continuous execution score can be used to train LLMs, and the learned skills transfer back to exact-solution tasks.

Core Mechanism

RiVER follows a train loop: for each instance, the LLM generates N solution candidates. Each candidate is executed by a deterministic program (e.g., a heuristic search on a specific map) and receives a continuous score — higher is better. These N scores form a group.

The key insight is that raw scores are not comparable across instances. Instance A might have scores in [0,100], instance B in [50,55]. Without calibration, instance A dominates the gradient (scale dominance). Also, within one instance, if the model frequently samples mediocre solutions (score 60 out of 100) and rarely samples a great one (score 95), the accumulation of 10 mediocre samples can outweigh one great one (frequency dominance).

RiVER’s calibration works per instance: it ranks the N solutions by score, then maps each rank to a weight that decays from the top (weight near 1) to the bottom (small but >0). Then it multiplies the raw score by this weight. This emphasizes top solvers while still providing bounded feedback to all valid solutions. Finally, the calibrated rewards are used in a group-relative advantage computation (like GRPO) to update the policy.

Input: instance i, prompt p
   |
   v
Sampling: generate N solutions s[1..N]
   |
   v
Execution: run each solution -> get raw scores r[1..N]
   |
   v
Calibration for each solution s[j]:
   - compute rank of r[j] among \{r[1]..r[N]\}
   - convert rank to weight w[j] (top = 1, bottom = epsilon)
   - calibrated reward = w[j] * r[j]
   |
   v
Group-relative advantage: A_j = (cal_r[j] - mean(cal_r)) / std(cal_r)
   |
   v
Policy update (REINFORCE or GRPO style)

Here’s a load-bearing metaphor: a diving competition with inconsistent judges.

• Each instance is one event (e.g., a specific AtCoder heuristic map).
• The LLM is a coach that sends multiple divers (solutions) into the pool.
• Each dive is scored by a judge (the execution environment) who gives a raw score out of 10. But this judge changes per event: in Event A, the judge tends to give 6-9; in Event B, the judge gives 1-5. You cannot compare dives across events (scale dominance).
• Also, if a diver makes many 7.0 dives and only one 9.5 dive, the coach might think 7.0 is the norm and underweight the rare brilliance (frequency dominance).

RiVER is like a personalized calibrator for each event: it looks at all dives in that event, ranks them, and says: “the best dive gets a multiplier of 1.0, the second gets 0.8, …, the worst gets 0.1”. Then it multiplies the raw judge score by this multiplier. Now, a 7.0 dive that is the best in the event (rank 1) becomes 7.0; a 9.5 dive that is only rank 2 because someone else scored 9.7 becomes 9.5 ** 0.8 = 7.6, still lower than the 7.0 * 1.0 = 7.0 of the actual winner. This way, the coach learns to push for top rankings within each event, not just high raw scores, and the noise from event-to-event scale differences is removed.

Key Concepts

• Scale Dominance: When training across many task instances, each instance has its own score distribution (range, mean, variance). If you use raw scores, instances with large score ranges (say 0-100) completely overshadow instances with small ranges (say 50-60) during gradient computation. The policy becomes blind to the latter. RiVER removes this by making rewards relative within each instance.

• Frequency Dominance: During RL sampling, a model may generate a particular suboptimal solution much more often than a rare strong one. Because group-relative RL aggregates over the sampled group, the repeated mediocre solutions can have a larger total weight than the single great one. RiVER’s rank-based weighting ensures that the top solution (even if only sampled once) gets the highest weight, and lower-ranked solutions get diminishing weights, preventing frequency from overriding quality.

• Reward Shaping via Rank Calibration: The method is not simply ranking and using ranks as rewards (which would ignore magnitude differences). Instead, it multiplies the raw score by a ranked-based weight. This retains the relative ordering and magnitude information within an instance while eliminating cross-instance noise. The bounded feedback for bottom solutions avoids reward collapse (all zeros) and keeps learning signal for weak candidates.

Framework Shift

Before (mainstream RLVR):
   Input -> Sample -> Compare to G.T. answer -> Binary reward (0/1) -> Update

After (RiVER):
   Input -> Sample -> Execute on task -> Raw score (continuous) -> Rank-calibrate -> Calibrated reward -> Update

One sentence: From binary ground-truth comparison to calibrated continuous execution feedback — the core shift is removing the need for an absolute answer and instead using relative performance within the sample group to shape rewards.

Expert Assessment

Problem choice: Real gap. Many useful coding tasks (heuristic search, optimization, game-playing) have no single correct answer. Existing RLVR is artificially limited. This paper opens a large, practical space.

Method maturity: Clever hybrid of existing ideas (group-relative RL, ranking, reward shaping) — not a fundamental breakthrough but a well-engineered solution. The simplicity is a strength. I do wonder about sensitivity to the weight decay shape; the paper likely fixes it but doesn’t explore alternatives.

Experimental integrity: Fair baselines (including GRPO with raw scores). The transfer to exact-solution benchmarks (LiveCodeBench, USACO) is the strongest evidence: it shows the model learns general coding ability, not just task-specific overfitting. One red flag: the gains on exact benchmarks are small (2-3%), but consistent across two base models, so plausible.

Writing quality: The two core challenges are well motivated. The method section could be tighter — the abstract uses “scale dominance” and “frequency dominance” but I didn’t see crisp definitions in the paper body. The experimental section is thorough. Where they cut corners: the calibration weight formula is stated but not derived or intuitively explained; I had to reconstruct it.

Verdict: weak accept — addresses a real gap with a simple, effective mechanism; evidence includes surprising transfer, but the gains are modest and the method’s novelty is incremental.

Takeaways

• Rank-calibrated reward shaping is a practical tool for any RL problem where rewards come from heterogeneous sources. You can steal the idea of per-group ranking + multiplicative weight to combat scale and frequency dominance.
• Execution feedback without ground-truth can teach general coding skill. If you have a simulator or evaluator that outputs a score, you can train an LLM without any golden answers.
• The bounded weight for bottom solutions is a subtle trick: if you zero out low-ranked solutions, you lose signal; if you keep them, you avoid a sparse reward problem. This is worth adopting in other RL settings.