Reinforcement Learning without Ground-Truth Solutions can Improve LLMs
Source: arXiv:2606.27369 · Published 2026-06-25 · By Yingyu Lin, Qiyue Gao, Nikki Lijing Kuang, Xunpeng Huang, Kun Zhou, Tongtong Liang et al.
TL;DR
This paper addresses the limitation of existing Reinforcement Learning with Verifiable Rewards (RLVR) techniques for large language models (LLMs), which heavily rely on ground-truth answers or binary correctness to assign rewards. Such approaches cannot be applied when the optimal or ground-truth solution is unavailable, as in many open-ended optimization problems dealing with algorithmic heuristics or NP-hard tasks. The authors introduce RiVER, a Ranking-induced VERifiable reinforcement learning framework that can leverage continuous, score-based, deterministic execution feedback without any ground-truth solutions. RiVER applies instance-wise ranking and winner-heavy reward shaping to convert raw, uncalibrated, heterogeneous objective scores into stable, scale-invariant, and informative policy-gradient signals.
They evaluate RiVER by training on 12 AtCoder Heuristic Contest problems (score-based, no ground-truth) and test on both score-based benchmarks (ALE-Bench) and exact-solution correctness benchmarks (LiveCodeBench and USACO). RiVER significantly improves the ALE ranking by 8.9% and 9.4% over strong LLMs (Qwen3-8B, GLM-Z1-9B), while also transferring to exact-solution tasks with 2.4% and 3.5% average absolute accuracy boosts—something baseline approaches relying on raw or binary scores fail to achieve. These results highlight that proper reward calibration when leveraging score-based optimization tasks enables LLMs to learn coding and reasoning skills beyond the limitations of ground-truth based RLVR.
Key findings
- RiVER improves Qwen3-8B ALE rating rank by +142 points (+8.9% relative) and GLM-Z1-9B by +157 points (+9.4%) on ALE-Bench.
- On exact-solution code correctness benchmarks LiveCodeBench (v5, v6) and USACO, RiVER yields average absolute improvements of +2.4% for Qwen3-8B and +3.5% for GLM-Z1-9B over base models.
- Baseline methods optimizing raw execution scores (Raw-GRPO, RS-GRPO) improve ALE rating but fail to transfer to exact-solution pass/fail benchmarks, sometimes degrading performance.
- Instance-wise ranking without winner-heavy shaping (Instance-Norm, Rank-uniform) improves ALE rating moderately but shows near-zero or negative gains on exact-solution benchmarks.
- Winner-heavy reward shaping in RiVER reduces the frequency dominance problem by emphasizing the highest-ranked candidate while still giving bounded feedback to others, critical for transfer learning.
- RiVER's training on only 12 AtCoder Heuristic Contest tasks (no ground-truth) generalizes to diverse downstream benchmarks, indicating optimization problems alone provide strong supervision.
- Difficulty breakdown on LiveCodeBench shows RiVER benefits mainly medium and hard problems (+5.0% and +1.4% improvements in accuracy), while easy problems remain near ceiling.
- In the training dynamics study, RiVER discovered stronger heuristics earlier on 8 out of 12 tasks compared to raw-score baselines.
Threat model
The work does not focus on adversarial threats but assumes a benign environment where the evaluator deterministically verifies solution feasibility and computes objective scores reliably. The adversary capabilities and attack surfaces are not modeled, reflecting a research focus on training efficacy rather than security.
Methodology — deep read
Threat Model and Assumptions: The approach assumes an LLM policy model generating candidate programs for optimization tasks where the ground-truth or globally optimal solution is unknown or intractable. The environment provides deterministic execution feedback: whether the output is valid and a continuous objective score for valid outputs. The adversary is not explicitly modeled; rather, the setting is about training robust policies from relative feedback without ground-truth labels.
Data and Tasks: Training uses 12 open-ended AtCoder Heuristic Contest (AHC) tasks (AHC047–AHC062 excluding 4 incompatible tasks), each with hidden evaluation instances. Each task is NP-hard and score-based, with no reference solutions; evaluation is done by running code on 10 hidden test instances per task. The learned policies are further evaluated on Algorithm Engineering Benchmark (ALE-Bench), LiveCodeBench versions 5 and 6, and USACO benchmarks, which test both score-based optimization and exact-solution correctness. Preprocessing includes negating objectives in minimization tasks for a unified larger-is-better convention.
Architecture and Algorithm: Beginning from pretrained reasoning-capable LLMs (Qwen3-8B and GLM-Z1-9B checkpoints), RiVER applies Group Relative Policy Optimization (GRPO), a variant of PPO that uses group-relative sample advantages without a learned value function. Instead of binary correctness rewards, RiVER shapes rewards using a rank-induced scheme:
- For each hidden test instance, candidate programs are ranked by scores; invalid executions score lowest.
- A winner-heavy shaping is applied: the top-ranked candidate receives reward +1, invalid executions -1, and all other valid outputs receive bounded graded rewards in [-0.5, 0.5] based on rank position.
- This removes scale dominance (arbitrary score ranges per instance) by rank-transforming within instances and mitigates frequency dominance by emphasizing the best candidate. The LLM policy is trained with the resulting scalar rewards averaged across test instances and used as the group-relative advantage in GRPO.
Training Regime: AdamW optimizer with learning rate 1e-6, KL divergence coefficient 0.001. Rollout group size G=16, global batch size 64. Training is done by sampling multiple candidate programs per prompt, executing on hidden instances, applying RiVER reward shaping, and updating the policy network. The policy update uses clipped surrogate GRPO objective with KL regularization. Seeds and hardware specifics are not detailed.
Evaluation Protocol: Metrics include ALE rating and percentile rank for optimization tasks, and Pass@1 accuracy averaged over three runs on LiveCodeBench and USACO. Baselines include raw execution score GRPO, binary winner-take-all rewards, instance-wise normalized scores, and uniform rank rewards without winner shaping. Ablations confirm the importance of instance-wise ranking and winner-heavy shaping. Training dynamics are visualized by best-so-far score curves per problem.
Reproducibility: The paper does not mention public code or weight release. Tasks originate from public AtCoder contests, but hidden evaluation instances and model checkpoints are not disclosed. Experimental details are thorough enough for partial reproduction but require access to contest environments and base LLMs.
Technical innovations
- Introducing a rank-induced reward shaping technique that ranks candidates per-instance to achieve score-scale invariance in RL training without ground-truths.
- Designing a winner-heavy reward shaping that assigns a unique high reward to the best solution while giving bounded graded feedback to other valid solvers, mitigating frequency dominance.
- Leveraging executable optimization problems with only feasibility checks and objective evaluation as verifiable, ground-truth-free environments for LLM reinforcement learning.
- Extending Group Relative Policy Optimization (GRPO) by replacing binary or raw score rewards with calibrated ranking-based advantages derived from deterministic execution feedback.
Datasets
- AtCoder Heuristic Contest (AHC) — 12 tasks (AHC047–AHC062, excluding 4) — public contest problems
- Algorithm Engineering Benchmark (ALE-Bench) — multiple optimization tasks derived from AHC — public benchmark
- LiveCodeBench versions 5 and 6 — exact-solution correctness benchmarks with programming tasks — public
- USACO — programming contest benchmark testing exact correctness — public
Baselines vs proposed
- Raw-GRPO: ALE rating = 903 (Qwen3-8B) vs RiVER = 987 (+84 points); Pass@1 avg = 40.2% vs 43.3%
- RS-GRPO: ALE rating = 904 vs RiVER = 987; Pass@1 avg = 40.0% vs 43.3%
- Raw-Binary: ALE rating = 926 vs RiVER = 987; Pass@1 avg = 41.2% vs 43.3%
- Instance-Norm: ALE rating = 935 vs RiVER = 987; Pass@1 avg = 39.6% vs 43.3%
- Rank-uniform: ALE rating = 960 vs RiVER = 987; Pass@1 avg = 39.7% vs 43.3%
- Similar patterns hold for GLM-Z1-9B-0414, with RiVER improving ALE rating from 931 to 962 and Pass@1 avg from ~32-33% to 34.3%.
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.27369.
Fig 1: Comparison between traditional answer-matching verification and our group-wise rank-induced verifiable
Fig 2 (page 2).
Fig 3 (page 2).
Limitations
- RiVER training is conducted on only 12 heuristic contest tasks—scalability to larger, more diverse optimization or reasoning tasks is not demonstrated.
- Evaluation focuses mainly on benchmarks related to coding and algorithmic optimization; generalization to broader reasoning domains remains untested.
- No explicit adversarial robustness or attack analysis against malicious code outputs or faulty evaluation environments.
- Training details such as exact hardware, seeds, and reproducibility artifacts are limited, hampering direct replication.
- The framework depends on a deterministic evaluator that can check feasibility and compute a scalar objective; tasks without reliable execution or scoring mechanisms are unsupported.
- While RiVER improves transfer, absolute performance gains on exact-solution benchmarks are modest (~2-3.5%), suggesting room for further improvement.
Open questions / follow-ons
- How does RiVER perform on other non-coding, non-optimization reasoning tasks requiring ground-truth-free feedback, e.g., multi-agent planning or open-ended generation?
- Can the rank-induced winner-heavy reward shaping be integrated with learned value models or combined with human feedback signals for richer supervision?
- How robust is RiVER training under noisy, stochastic, or partially observable execution feedback environments?
- Would combining RiVER with contrastive or diversity-promoting exploration techniques further improve sample efficiency and solution quality?
Why it matters for bot defense
For engineers designing CAPTCHA or bot-defense systems, RiVER offers an approach to train LLMs on verification signals that do not rely on known ground-truth responses, instead exploiting execution-based ranking and scoring. This is pertinent when facing tasks where exact solution verification is infeasible or ill-defined, and where reward signals are continuous and loosely calibrated. RiVER’s calibration techniques mitigate unstable policy updates caused by raw score magnitudes and repeated sampling bias, which is crucial for learning robust models in open-ended problem spaces.
However, applying RiVER directly to bot-defense requires caution: the method presumes deterministic evaluation and executable solution generation, conditions that may not align with many CAPTCHA challenges. Yet the core principle of using pairwise or group ranking with winner-focused shaping to generate stable learning signals could inspire new ways to reward bot classifiers or puzzle-generators where precise labels are unavailable. Overall, RiVER underscores the importance of reward design in reinforcement learning from executable, verifiable environments without ground-truths, which could inform future CAPTCHA training frameworks that rely on comparative scoring rather than binary passes/fails.
Cite
@article{arxiv2606_27369,
title={ Reinforcement Learning without Ground-Truth Solutions can Improve LLMs },
author={ Yingyu Lin and Qiyue Gao and Nikki Lijing Kuang and Xunpeng Huang and Kun Zhou and Tongtong Liang and Zhewei Yao and Yi-An Ma and Yuxiong He },
journal={arXiv preprint arXiv:2606.27369},
year={ 2026 },
url={https://arxiv.org/abs/2606.27369}
}