Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs

• URL: http://arxiv.org/abs/2605.08905v1
• Date: Sat, 09 May 2026 11:57:25 GMT
• Title: Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs
• Abstract summary: We propose OPT-BENCH, the first comprehensive framework for training and evaluating Large Language Models (LLMs)<n> OPT-BENCH provides three key components: a scalable training infrastructure with instance generators, quality verifiers, and optimal baselines across 10 tasks; a rigorous benchmark with 1,000 instances evaluating both feasibility, measured by Success Rate, and quality, measured by Quality Ratio; and quality-aware rewards that enable continuous improvement beyond binary correctness.<n>Our analysis reveals that quality-aware rewards improve solutions by 28.8% over binary rewards, and that task diversity drives generalization more than data quantity, offering insights into RLVR scaling for complex reasoning
• Score: 37.25886192772028
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) have achieved remarkable success on reasoning benchmarks through Reinforcement Learning with Verifiable Rewards (RLVR), excelling at tasks such as math, coding, logic, and puzzles. However, existing benchmarks evaluate only correctness, while overlooking optimality, namely the ability to find the best solutions under constraints. We propose OPT-BENCH, the first comprehensive framework for training and evaluating LLMs on NP-hard optimization problems through quality-aware RLVR. OPT-BENCH provides three key components: a scalable training infrastructure with instance generators, quality verifiers, and optimal baselines across 10 tasks; a rigorous benchmark with 1,000 instances evaluating both feasibility, measured by Success Rate, and quality, measured by Quality Ratio; and quality-aware rewards that enable continuous improvement beyond binary correctness. Training on Qwen2.5-7B-Instruct-1M with 15K examples achieves 93.1% SR and 46.6% QR, significantly outperforming GPT-4o, which achieves 29.6% SR and 14.6% QR. Beyond optimization, training on OPT-BENCH transfers to diverse tasks, including mathematics (+2.2%), logic (+1.2%), knowledge (+4.1%), and instruction following (+6.1%). Our analysis reveals that quality-aware rewards improve solutions by 28.8% over binary rewards, and that task diversity drives generalization more than data quantity, offering insights into RLVR scaling for complex reasoning.

Related papers

• Reinforcement Learning without Ground-Truth Solutions can Improve LLMs [47.0243847990524]
  Reinforcement learning with verifiable rewards (RLVR) for training LLMs typically rely on ground-truth answers to assign rewards.<n>We introduce a textbfRanking-textbfinduced textbfVERifiable framework (RiVER) that trains LLMs on score-based optimization tasks without ground-truth solutions.
  arXiv  Detail & Related papers  (2026-06-25T17:59:36Z)
• ComplexConstraints and Beyond: Expert Rubrics for RLVR [1.173565897471208]
  We present a systematic analysis of expert-curated rubric-based evaluation as an alternative paradigm.<n>We first articulate five design principles for constructing high-quality rubrics, including Maximum Viable Atomicity and intent-aware criterion design.<n>We demonstrate that these expert rubrics are not only better evaluation instruments but also highly effective training signals.
  arXiv  Detail & Related papers  (2026-06-08T07:11:56Z)
• Test-time Recursive Thinking: Self-Improvement without External Feedback [120.80790108733942]
  Test-time Recursive Thinking (TRT) is an iterative self-improvement framework.<n>Open-source models reach 100% accuracy on AIME-25/24, and on LiveCodeBench's most difficult problems, closed-source models improve by 10.4-14.8 percentage points without external feedback.
  arXiv  Detail & Related papers  (2026-02-03T04:37:37Z)
• CVeDRL: An Efficient Code Verifier via Difficulty-aware Reinforcement Learning [57.24524263804788]
  Code verifiers play a critical role in post-verification for LLM-based code generation.<n>Existing supervised fine-tuning methods suffer from data scarcity, high failure rates, and poor inference efficiency.<n>We show that naive RL with only functionality rewards fails to generate effective unit tests for difficult branches and samples.
  arXiv  Detail & Related papers  (2026-01-30T10:33:29Z)
• What Makes Low-Bit Quantization-Aware Training Work for Reasoning LLMs? A Systematic Study [59.44848132298657]
  Post-training quantization (PTQ) usually comes with the cost of large accuracy drops, especially for reasoning tasks under low-bit settings.<n>In this study, we present a systematic empirical study of quantization-aware training (QAT) for reasoning models.
  arXiv  Detail & Related papers  (2026-01-21T11:22:29Z)
• CUARewardBench: A Benchmark for Evaluating Reward Models on Computer-using Agent [46.41047559759938]
  Computer-using agents (CUAs) enable task completion through natural interaction with operating systems and software interfaces.<n> Reward models offer promising alternatives, but their effectiveness on CUA evaluation remains largely underexplored.<n>We present CUARewardBench, comprising four key contributions.
  arXiv  Detail & Related papers  (2025-10-21T12:53:40Z)
• Foundational Automatic Evaluators: Scaling Multi-Task Generative Evaluator Training for Reasoning-Centric Domains [97.5573252172065]
  We train a family of Automatic Reasoning Evaluators (FARE) with a simple iterative rejection-sampling supervised finetuning approach.<n>FARE-8B challenges larger specialized RL-trained evaluators and FARE-20B sets the new standard for open-source evaluators.<n>As inference-time rerankers, FARE-20B achieves near-oracle performance on MATH.
  arXiv  Detail & Related papers  (2025-10-20T17:52:06Z)
• Critique-GRPO: Advancing LLM Reasoning with Natural Language and Numerical Feedback [59.078756231841574]
  Critique-GRPO is an online RL framework that integrates both natural language and numerical feedback for effective policy optimization.<n>We show Critique-GRPO consistently outperforms supervised learning and RL-based fine-tuning methods across eight challenging mathematical, STEM, and general reasoning tasks.
  arXiv  Detail & Related papers  (2025-06-03T17:39:02Z)
• J1: Incentivizing Thinking in LLM-as-a-Judge via Reinforcement Learning [54.85131761693927]
  We introduce J1, a reinforcement learning framework for teaching LLM judges to think before making decisions.<n>Our core contribution lies in converting all judgment tasks for non-verifiable and verifiable prompts into a unified format with verifiable rewards.<n>We then use RL to train thinking-judges at scales of 8B, 32B, and 70B and show that they obtain state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-05-15T14:05:15Z)
• Reinforcement Learning from Automatic Feedback for High-Quality Unit Test Generation [12.503002900186997]
  Large Language Models (LLMs) have gained popularity for code generation, including the automated creation of test cases.<n>LLMs are often trained on vast amounts of publicly available code, which may include test cases that do not adhere to best practices.<n>We propose a novel technique called Reinforcement Learning from Static Quality Metrics (RLSQM)
  arXiv  Detail & Related papers  (2023-10-03T18:48:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.