Reinforcement Learning without Ground-Truth Solutions can Improve LLMs
RiVER leverages score-based optimization with instance ranking and winner-heavy rewards, improving LLMs on algorithmic tasks by 8.9%-9.4%.
Key Findings
Methodology
The proposed RiVER (Ranking-induced VERifiable) framework transforms ungrounded optimization tasks into reinforcement learning signals by employing instance-wise ranking and winner-heavy reward shaping. For each hidden test instance, multiple candidate solutions are generated, executed, and evaluated to produce a set of continuous scores. These scores are then rank-ordered within each instance, removing scale biases across different problems. The top-performing candidate receives a significantly higher reward, while other valid solutions get bounded positive feedback, effectively addressing the issues of scale dominance and frequency bias. The approach integrates with the Group Relative Policy Optimization (GRPO) algorithm, which estimates advantages based on relative rewards rather than absolute scores, enabling stable policy updates without reliance on ground-truth solutions. Extensive experiments on 12 AtCoder tasks demonstrate that models trained with RiVER outperform baselines on both score-based and exact-solution benchmarks, with improvements of 8.9% and 9.4% in ALE ratings, and 2.4% and 3.5% in accuracy on traditional benchmarks like USACO and LiveCodeBench. The key innovation lies in reward calibration through instance ranking and winner emphasis, which leads to better transferability and robustness in complex optimization scenarios.
Key Results
- Models trained with RiVER on 12 AtCoder tasks achieved an 8.9% and 9.4% increase in ALE rating scores for Qwen3-8B and GLM-Z1-9B-0414 respectively, surpassing other reward variants.
- In exact-solution benchmarks such as USACO and LiveCodeBench, RiVER-enhanced models improved average Pass@1 accuracy by 2.4% and 3.5%, demonstrating strong transferability despite training only on score-based tasks.
- Ablation studies confirmed that instance-wise ranking and winner-heavy reward shaping are critical for performance gains, effectively mitigating scale and frequency biases in policy updates.
Significance
This research addresses a fundamental bottleneck in reinforcement learning for complex tasks lacking explicit ground-truth solutions. By leveraging verifiable, executable objectives and relative ranking, RiVER enables models to learn from continuous scores without human-labeled data. This paradigm shift opens new avenues for training AI systems in real-world scenarios where optimal solutions are unknown or infeasible to compute. The approach enhances the generalization and robustness of large language models, making them more adaptable to diverse optimization problems in industry and academia, such as automated coding, scheduling, and planning. It also reduces reliance on costly annotations, fostering scalable, self-supervised learning frameworks that can operate in weakly supervised environments.
Technical Contribution
The core technical innovation lies in integrating instance-wise ranking with a winner-heavy reward shaping mechanism within the policy gradient framework. Unlike traditional RLVR methods that rely on binary correctness or raw scores, RiVER normalizes scores within each instance, ensuring scale invariance. The ranking process assigns a relative position to each candidate, and the reward function emphasizes the top-ranked solution while bounding the feedback for others. This design effectively prevents frequent suboptimal solutions from dominating the gradient updates, addressing the issues of scale dominance and frequency bias. The method leverages the advantages of the GRPO algorithm, which estimates advantages based on relative rewards, thus enabling stable, ground-truth-free policy optimization. Extensive experiments validate that this approach significantly improves performance on both algorithmic and exact-solution benchmarks, demonstrating its potential as a general training paradigm for complex reasoning tasks.
Novelty
This work is pioneering in applying instance-wise ranking and winner-heavy reward shaping within a reinforcement learning framework for optimization tasks without ground-truth solutions. Unlike prior methods that depend on explicit labels or binary correctness signals, RiVER uses relative, verifiable scores derived from executable environments, making it applicable to a broader class of problems. The combination of ranking-based reward calibration with policy gradient optimization introduces a new dimension of robustness and transferability, setting it apart from existing answer-matching or score-aggregation approaches. This represents a significant step forward in scalable, self-supervised learning for complex, real-world tasks.
Limitations
- The success of RiVER heavily depends on the quality and availability of a deterministic, verifiable environment, which may not be feasible for all tasks.
- Computational costs increase with the number of candidate solutions and test instances, potentially limiting scalability.
- In environments with high noise or unstable evaluation metrics, ranking and reward shaping may become less reliable, affecting training stability.
Future Work
Future research could focus on extending RiVER to multi-modal and multi-task settings, integrating adaptive difficulty adjustment, and exploring more sophisticated reward shaping strategies. Additionally, developing methods to reduce computational overhead and improve robustness in noisy environments will be crucial. Exploring theoretical guarantees of convergence and transferability in broader problem classes also remains an open avenue.
AI Executive Summary
Reinforcement learning (RL) has long been a cornerstone in advancing large language models (LLMs), especially in tasks requiring reasoning, coding, and planning. Traditionally, RL approaches rely heavily on ground-truth answers or explicit correctness signals to guide policy updates. While effective in domains like mathematics or code verification, this reliance limits applicability in many real-world scenarios where such answers are unavailable or infeasible to define. This challenge has motivated the development of reward mechanisms that do not depend on explicit labels, aiming to foster more flexible and scalable training paradigms.
The paper introduces RiVER (Ranking-induced VERifiable), a novel framework designed to train LLMs on score-based optimization tasks without ground-truth solutions. Instead of binary correctness, RiVER leverages deterministic execution feedback—such as objective scores from heuristic algorithms or feasibility checks—to generate a rich, continuous supervision signal. The key innovation lies in transforming raw scores into a stable, relative ranking within each test instance, thereby removing the problematic effects of scale differences across tasks. This instance-wise ranking ensures that the model learns to distinguish better solutions from worse ones based solely on their relative performance, independent of absolute score magnitudes.
To address the issues of frequent sampling of suboptimal solutions overshadowing rare but high-quality candidates, RiVER employs a winner-heavy reward shaping strategy. The best candidate in each group receives a distinct, higher reward, while other valid solutions get bounded, graded feedback. This approach emphasizes the importance of discovering and reinforcing top solutions, reducing the bias introduced by repeated suboptimal modes. The entire framework is integrated with the Group Relative Policy Optimization (GRPO) algorithm, which estimates advantages based on relative rewards, enabling stable policy updates without the need for explicit ground-truth data.
Experimental results demonstrate the effectiveness of RiVER across multiple benchmarks. Training on 12 AtCoder heuristic contest tasks, the models achieved an 8.9% and 9.4% improvement in ALE ratings for Qwen3-8B and GLM-Z1-9B-0414, respectively. More impressively, despite being trained solely on score-based environments, RiVER models transferred well to exact-solution benchmarks like USACO and LiveCodeBench, improving accuracy by 2.4% and 3.5%. These findings highlight the potential of score-based optimization, combined with proper reward calibration, as a powerful training paradigm that does not rely on explicit ground-truth solutions.
Overall, this work represents a significant step toward scalable, self-supervised learning for complex reasoning and optimization tasks. By focusing on relative, verifiable feedback and emphasizing top solutions, RiVER enhances the robustness and transferability of LLMs, paving the way for broader applications in industrial automation, automated reasoning, and beyond. Future directions include extending this framework to multi-modal data, improving computational efficiency, and exploring theoretical guarantees of convergence and generalization in diverse problem settings.
Deep Analysis
Background
近年来，强化学习（RL）在提升大规模语言模型（LLMs）推理和生成能力方面取得了显著进展。尤其是在答案匹配和奖励模型（如RLHF）基础上，模型在数学推理、编码和规划任务中表现优异。然而，这些方法高度依赖于Ground-Truth答案或明确的奖励信号，限制了其在没有明确最优解或多样化解决方案的复杂任务中的应用。传统的奖励设计多为二元或稀疏奖励，难以捕捉解的细粒度差异，导致训练效果受限。近年来，研究者开始探索基于目标函数的连续奖励、相对排名和多样性促进机制，试图缓解奖励稀疏和偏差问题。尽管如此，如何在没有Ground-Truth的情况下，利用可验证的目标函数进行高效训练，仍是学术界的热点难题。
Core Problem
核心问题在于，许多复杂任务缺乏明确的最优解或Ground-Truth答案，传统的强化学习奖励机制难以应用。直接使用连续目标分数作为奖励，存在尺度不一致和频繁采样次优解的偏差问题。尺度偏差导致不同实例的分数范围差异影响策略更新，使模型偏向于分数较大的任务；频率偏差则使模型过度强化常见的次优策略，抑制了探索潜在更优解的能力。这些问题限制了模型在多样化优化任务中的泛化和迁移能力，亟需一种新的奖励机制来解决这一瓶颈。
Innovation
本文的创新点主要体现在两个方面：第一，提出实例级排名机制，将每个隐藏实例中的候选解按相对目标分数排序，避免尺度偏差影响，确保奖励的尺度一致性。第二，引入获胜者偏重的奖励塑造策略，将每个实例中的最佳候选解赋予更高奖励，同时对非最优但有效的解给予有限正向反馈，从而减少频繁采样次优解带来的偏差。这两个机制结合，极大改善了连续奖励在策略优化中的稳定性和有效性。
Methodology
- �� 训练任务由问题描述、确定性评估器和隐藏测试实例组成，模型生成响应后提取可执行程序。
- �� 执行程序在每个实例上得到有效性和目标分数，形成原始分数矩阵。
- �� 对每个实例内的候选解进行排名，消除尺度偏差，得到实例内的相对排名。
- �� 利用排名信息，设计获胜者偏重的奖励函数：最优候选获得最高奖励，次优候选获得有限正向奖励，无效解获得负奖励。
- �� 将每个实例的奖励进行平均，作为策略梯度的优势信号，结合GRPO算法进行策略更新。
- �� 训练过程中，模型不断优化，提升在无Ground-Truth环境下的解题能力。
Experiments
实验采用12个AtCoder竞赛任务作为训练集，环境提供目标函数和可验证的目标值，无需Ground-Truth答案。模型在训练后在ALE-Bench、LiveCodeBench和USACO等多个基准上进行评估。对比基线包括原始分数训练、二元奖励和归一化奖励等变体。主要指标为ALE评级、Pass@1准确率和精确解的成功率。超参数包括候选解数G、奖励塑造函数参数等。通过消融实验验证实例排名和获胜者偏重奖励的贡献。
Results
结果显示，RiVER在ALE评级中分别提升8.9%和9.4%，在Score-based和Exact-solution任务中均优于其他奖励设计。模型在USACO和LiveCodeBench中的平均Pass@1提升了3.5%，在复杂优化任务中表现出更强的泛化能力。消融分析表明，实例排名和获胜者偏重奖励的结合，是性能提升的关键因素。
Applications
该方法适用于需要优化目标函数但缺乏明确答案的场景，如自动代码生成、复杂调度、路径规划等。只需定义可验证的目标函数，无需标注最优解，即可实现模型自主学习。未来，结合多任务、多模态信息，可扩展到更复杂的工业自动化、智能决策等领域，推动AI自主优化能力的提升。
Limitations & Outlook
当前方法依赖于高质量的可验证目标函数，某些任务难以定义或验证目标，限制了应用范围。除此之外，训练成本较高，尤其在大规模模型和复杂任务中，计算资源消耗大。奖励塑造机制在极端噪声或不稳定环境下可能表现不佳，未来需结合鲁棒性增强技术。
Plain Language Accessible to non-experts
想象你在参加一个比赛，比赛的目标是找到最短的路线，但没有人告诉你正确的路线，也没有标准答案。你可以尝试不同的方法，比如绕路、直走、或者走一些你觉得可能更短的路线。每次你走完后，系统会告诉你这条路线的长度，但不会告诉你最短的路线到底是多少。你可以根据这些长度信息，自己判断哪些路线更好，然后不断改进。这个过程就像在用一种特殊的“评分”机制，帮助你逐步找到更优的路线，而不需要知道真正的最短路线。这种方法可以让你在没有标准答案的情况下，通过不断比较和优化，找到接近最优的解决方案。
ELI14 Explained like you're 14
你知道在玩游戏或者做作业时，有时候没有一个明确的“正确答案”，但你可以根据一些提示或得分，慢慢找到更好的方法。比如，你在拼积木，没有标准答案，但每次拼完后，老师会告诉你这个拼法的好坏，比如稳不稳、漂亮不漂亮。你可以试着拼不同的样子，然后看看哪个更稳、更漂亮。这个过程就像在用一种特别的评分系统，它帮你比较不同的拼法，告诉你哪个更好。你不用知道最完美的拼法，只要不断试、比较、改进，就能拼出很棒的作品。这就是没有标准答案的“学习”方式，用评分和比较来不断变得更厉害！
Glossary
Reinforcement Learning（强化学习）
一种让模型通过试错学习的方法，模型根据奖励信号调整行为策略。技术上，模型通过最大化累积奖励实现目标。
本文中用于训练模型以优化解的质量。
Ground-Truth（真实答案）
在任务中已知的标准答案或最优解，用于指导模型学习。技术上，作为奖励或评价的参考。
传统RL依赖Ground-Truth进行奖励设计。
Reward Shaping（奖励塑造）
通过调整奖励信号的结构，使学习过程更稳定或更有效。可以引入偏重、归一化等机制。
本文中采用获胜者偏重的奖励塑造。
Instance-wise Ranking（实例内排名）
在每个测试实例中对候选解进行排序，消除不同实例尺度差异，确保相对比较的公平性。
核心机制之一，避免尺度偏差影响。
Group Relative Policy Optimization（GRPO）
一种基于候选解相对优势的策略优化算法，避免对价值模型的依赖，适合无Ground-Truth环境。
本文采用其作为策略优化基础。
NP-hard（NP-难）
一类计算复杂度极高的问题，通常无法在多项式时间内求解最优解。
许多优化任务属于NP-难类别。
Objective Function（目标函数）
衡量解优劣的数学表达式，用于指导优化过程。
在无Ground-Truth环境中，作为可验证的奖励依据。
Verifiable Rewards（可验证奖励）
通过环境的执行和验证机制，确认解的质量，无需答案匹配。
本文的核心创新之一。
Open Questions Unanswered questions from this research
- 1 如何设计更复杂的奖励塑造机制，以适应多样化的任务目标，仍是未解决的问题。
- 2 在极端噪声或不稳定环境中，排名和奖励的鲁棒性如何保证，仍需深入研究。
- 3 模型在大规模复杂任务中的训练效率和成本优化，是未来的重要方向。
- 4 如何结合多模态信息（如图像、文本）进行跨模态优化，仍是开放问题。
- 5 在实际工业应用中，如何将RiVER与现有系统集成，提升整体效率和效果，仍待探索。
Applications
Immediate Applications
自动代码生成
利用RiVER训练模型在没有明确答案的情况下，生成高质量代码，适用于自动化编程辅助。
路径规划与调度
在复杂调度问题中，通过目标函数验证方案优劣，无需最优解，提升工业自动化效率。
优化设计与仿真
在工程设计中，通过目标函数评估方案优劣，实现无标注的自主优化。
Long-term Vision
自主优化系统
未来AI能自主在复杂环境中进行连续优化，减少对人工标注的依赖，推动智能自动化。
跨任务泛化能力
模型在多任务、多场景中实现无缝迁移，提升AI的通用推理和优化能力。
Abstract
Reinforcement learning with verifiable rewards (RLVR) for training LLMs typically rely on ground-truth answers to assign rewards, limiting their applicability to tasks where the ground-truth solution is unknown. We introduce a \textbf{R}anking-\textbf{i}nduced \textbf{VER}ifiable framework (RiVER) that trains LLMs on score-based optimization tasks without ground-truth solutions, using deterministic execution feedback as continuous-valued supervision. When applying group-relative RL to such continuous rewards, we identify two key challenges: \emph{scale dominance}, where uncalibrated score magnitudes across test instances distort policy updates, and \emph{frequency dominance}, where repeatedly sampled suboptimal solutions can outweigh rare but stronger candidates. RiVER addresses these challenges with calibrated reward shaping that uses instance-wise comparisons and emphasizes top-ranked solvers while retaining bounded feedback for other valid solutions. We train on 12 AtCoder Heuristic Contest tasks and evaluate on Algorithm Engineering Benchmark (ALE-Bench), LiveCodeBench, and USACO. RiVER advances Qwen3-8B and GLM-Z1-9B-0414 by 8.9\% and 9.4\% in ALE rating rank. More importantly, despite training exclusively on score-based tasks without any ground-truth solutions, RiVER also improves the backbones across exact-solution benchmarks such as LiveCodeBench and USACO by an absolute average improvement of 2.4\% and 3.5\%. By contrast, baselines trained with raw execution scores improve ALE rating but fail to transfer to exact-solution benchmarks. These results suggest that score-based optimization tasks, combined with proper reward calibration, can serve as effective training environments for general coding ability without ground-truth solutions.
References (20)
DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
Zhihong Shao, Peiyi Wang, Qihao Zhu et al.
Attention Illuminates LLM Reasoning: The Preplan-and-Anchor Rhythm Enables Fine-Grained Policy Optimization
Yang Li, Zhichen Dong, Yuhan Sun et al.
Entropy-Regularized Process Reward Model
Hanning Zhang, Pengcheng Wang, Shizhe Diao et al.
LLM Post-Training: A Deep Dive into Reasoning Large Language Models
Komal Kumar, Tajamul Ashraf, Omkar Thawakar et al.
HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges
Xianliang Yang, Ling Zhang, Haolong Qian et al.
Proximal Policy Optimization Algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal et al.
R-PRM: Reasoning-Driven Process Reward Modeling
Shuaijie She, Junxiao Liu, Yifeng Liu et al.
DAPO: An Open-Source LLM Reinforcement Learning System at Scale
Qiying Yu, Zheng Zhang, Ruofei Zhu et al.
Can Language Models Solve Olympiad Programming?
Quan Shi, M. Tang, Karthik Narasimhan et al.
Let's Verify Step by Step
H. Lightman, Vineet Kosaraju, Yura Burda et al.
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Haoran Ye, Jiarui Wang, Zhiguang Cao et al.
LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code
Naman Jain, King Han, Alex Gu et al.
STeCa: Step-level Trajectory Calibration for LLM Agent Learning
Hanlin Wang, Jian Wang, Chak Tou Leong et al.
NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
Lizhou Fan, Wenyue Hua, Lingyao Li et al.
WebDancer: Towards Autonomous Information Seeking Agency
Jialong Wu, Baixuan Li, Runnan Fang et al.
Large Language Models as End-to-end Combinatorial Optimization Solvers
Xia Jiang, Yaoxin Wu, Minshuo Li et al.
On the Interplay of Pre-Training, Mid-Training, and RL on Reasoning Language Models
Charlie Zhang, Graham Neubig, Xiang Yue
Group-in-Group Policy Optimization for LLM Agent Training
Lang Feng, Zhenghai Xue, Tingcong Liu et al.
NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems
Xiaozhe Li, Xinyu Fang, Shengyuan Ding et al.
Learning to Discover at Test Time
Mert Yuksekgonul, Daniel Koceja, Xinhao Li et al.