@inproceedings{li-etal-2026-forge,
    title = "Forge: Quality-Aware Reinforcement Learning for {NP}-Hard Optimization in {LLM}s",
    author = "Li, Xiaozhe  and
      Fang, Xinyu  and
      Ding, Shengyuan  and
      Li, Yang  and
      Li, Linyang  and
      Duan, Haodong  and
      Liu, Qingwen  and
      Chen, Kai",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {ACL} 2026",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-acl/2026.findings-acl.1413/",
    pages = "28351--28368",
    ISBN = "979-8-89176-395-1",
    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, overlooking optimality{---}the ability to find the best solutions under constraints. We propose , the first comprehensive framework for training and evaluating LLMs on NP-hard optimization problems through quality-aware RLVR. 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 (Success Rate) and quality (Quality Ratio); and quality-aware rewards enabling 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 (29.6{\%} SR, 14.6{\%} QR). Beyond optimization, training on transfers to diverse tasks: mathematics (+2.2{\%}), logic (+1.2{\%}), knowledge (+4.1{\%}), and instruction-following (+6.1{\%}). Our analysis reveals quality-aware rewards improve solutions by 28.8{\%} over binary rewards, and task diversity drives generalization more than data quantity{---}offering insights into RLVR scaling for complex reasoning."
}