Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers

• URL: http://arxiv.org/abs/2605.18374v1
• Date: Mon, 18 May 2026 13:21:40 GMT
• Title: Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers
• Abstract summary: Large language models (LLMs) typically approach optimization as an inference-time procedure, solving each instance separately.<n>We study this question on Synergistic Dependency Selection (SDS), a controlled variant of constrained Quadratic Knapsack.<n>We fine-tune Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization using a feasibility-gated reward and light structural scaffolding.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) typically approach combinatorial optimization as an inference-time procedure, solving each instance separately through sampling, search, or repeated prompting. We ask whether reinforcement learning can instead shift part of this reasoning cost into the weights of a code LLM, so that the model synthesizes a reusable solver for an entire problem family. We study this question on Synergistic Dependency Selection (SDS), a controlled variant of constrained Quadratic Knapsack designed to expose a specific failure mode: local signals and strict feasibility constraints make greedy heuristics attractive but unreliable. Under identical scaffolding, Best-of-64 base-model sampling saturates at an approximately 28.7% gap to the global Virtual Best Solver (VBS); code audits show that the base model often retrieves Simulated Annealing templates but misimplements the Metropolis acceptance rule. We fine-tune Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization (GRPO) using a feasibility-gated reward and light structural scaffolding. The resulting policy converges to a constraint-aware Simulated Annealing template in 99.8% of feasible SDS outputs, achieves a 5.0% gap to that VBS, and is 91 times cheaper in post-generation execution/search cost than cumulative Best-of-64 evaluation. A compile-once check shows that one best frozen solver per seed remains highly competitive when reused unchanged across the SDS test set, while an additional-domain evaluation on Job Shop Scheduling provides narrower but positive evidence that the scaffold transfers beyond SDS. Negative ablations reveal the limits of this recipe: standard stabilizers degrade performance, a soft feasibility gate fails, and results remain sensitive to reward normalization and domain-specific design choices.

Related papers

• Harnessing LLMs for Reliable Academic Supervision: A Comparative Study [0.0]
  Large language models routinely produce fluent answers to single-shot prompts, yet deploying them as reliable components of a domain decision system is substantially harder.<n>Closing this gap is the work of harness engineering: the deliberate composition of deterministic scaffolding.<n>We present a case in academic supervision, a domain combining high-stakes recommendation, longitudinal accountability, and structured operational study.
  arXiv  Detail & Related papers  (2026-07-16T08:14:27Z)
• Efficient Data Selection for Multimodal Models via Incremental Optimization Utility [6.698411108146732]
  We propose One-Step-Train (OST), a framework that reformulates data selection as an incremental optimization utility ranking problem.<n>By selecting the top-50 subset, OST reduces training costs by 43% (and total time consumption by 17) while surpassing the strong LLM-as-a-Judge baseline by 1.8 points.
  arXiv  Detail & Related papers  (2026-05-08T09:28:26Z)
• Confidence-Aware Alignment Makes Reasoning LLMs More Reliable [65.44962502963378]
  We introduce CASPO, a framework that aligns token-level confidence with step-wise logical correctness without training a separate reward model.<n>During inference, we propose Confidence-aware Thought (CaT), which dynamically prunes uncertain reasoning branches with negligible O(V) latency.<n>Experiments across ten benchmarks and multiple model families show that CASPO consistently improves reasoning reliability and inference efficiency.
  arXiv  Detail & Related papers  (2026-05-08T07:08:25Z)
• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• JANUS: Structured Bidirectional Generation for Guaranteed Constraints and Analytical Uncertainty [0.0]
  JANUS (Joint Ancestral Network for Uncertainty and Synthesis) is a framework that unifies capabilities using a DAG of Bayesian Decision Trees.<n>Key innovation is Reverse-Topological Back-filling, an algorithm that propagates constraints backwards through the causal graph.<n>Janus achieves state-of-the-art fidelity (Detection Score 0.497), eliminates mode collapse on imbalanced data, and provides exact handling of complex inter-column constraints.
  arXiv  Detail & Related papers  (2026-03-04T05:36:11Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization [0.0]
  We introduce ConstraintBench, a benchmark for evaluating large language models on direct constrained optimization.<n>We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck.<n>No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference.
  arXiv  Detail & Related papers  (2026-02-25T22:54:26Z)
• Optimistic Feasible Search for Closed-Loop Fair Threshold Decision-Making [0.0]
  We study online learning of a one-dimensional threshold policy from bandit feedback.<n>We propose Optimistic Feasible Search (OFS), a simple grid-based method that maintains confidence bounds for reward and constraint residuals.
  arXiv  Detail & Related papers  (2025-12-26T10:44:40Z)
• Enhancing the Outcome Reward-based RL Training of MLLMs with Self-Consistency Sampling [90.87033586963828]
  Outcome-reward reinforcement learning (RL) is a common and increasingly significant way to refine the step-by-step reasoning of multimodal large language models (MLLMs)<n>We propose Self-Consistency Sampling (SCS) to correct this issue.<n>Based on Qwen2.5-VL-7B-Instruct, SCS improves accuracy by up to 7.7 percentage points on six multimodal benchmarks with negligible extra computation.
  arXiv  Detail & Related papers  (2025-11-13T18:59:57Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• Reverse Preference Optimization for Complex Instruction Following [61.39734201711077]
  We propose a simple yet effective method called Reverse Preference Optimization (RPO)<n>It mitigates noise in preference pairs by dynamically reversing the constraints within the instruction to ensure the chosen response is perfect.<n>RPO scales effectively across model sizes, with the 70B RPO model surpassing GPT-4o.
  arXiv  Detail & Related papers  (2025-05-28T09:44:27Z)

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.