🤖 machine learning

Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers

This paper demonstrates that training a code LLM with reinforcement learning to synthesize reusable, constraint-aware solvers for combinatorial optimization problems significantly outperforms traditional inference-time search methods in both solution quality and computational efficiency.

Original authors: Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

Published 2026-05-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: From "Guessing Every Time" to "Writing a Manual"

Imagine you have a very smart but slightly chaotic assistant (a Large Language Model, or LLM). Every time you give them a difficult puzzle, they try to solve it from scratch by guessing, checking, and guessing again. Sometimes they get it right, but often they get stuck or make silly mistakes. This is how most AI solves problems today: it reasons every single time you ask a question.

This paper asks a different question: What if, instead of solving the puzzle every time, the AI learned how to write a perfect instruction manual (a "solver") that anyone could use?

The researchers wanted to see if they could train the AI to stop being a "guessing assistant" and start acting like a "compiler." Instead of doing the work for every new customer, the AI would learn the rules once, write a reusable program, and then that program could solve thousands of future problems instantly.

The Test: The "Deceptive" Puzzle Box

To test this, the researchers created a specific type of puzzle called Synergistic Dependency Selection (SDS).

The Analogy: Imagine a treasure hunt where you have a backpack with a weight limit. You want to pick items that are valuable. But here's the catch: some items are only valuable if you pick them together (synergy), and some items cancel each other out if you pick both (conflict). Also, some items require you to pick a specific other item first (precedence).
The Trap: The puzzle is designed to be "deceptive." A simple, greedy strategy (like "just pick the heaviest items first") looks like it should work, but it actually leads you into a dead end. It's like a maze where the path that looks straight and easy actually leads to a wall.

The Problem with the "Base" AI

The researchers first tried using a standard, untrained AI model to solve these puzzles. They let the AI try 64 different times for every single puzzle (a method called "Best-of-64") and picked the best answer.

The Result: Even with 64 tries, the AI only got about 71% of the value it could have achieved (a 28.7% gap).
Why? The AI was "hallucinating" the logic. It knew the name of a good strategy (like "Simulated Annealing," which is a fancy way of saying "shake the box to find the best arrangement"), but when it wrote the code for that strategy, it made a critical logic error. It was like a chef who knows the recipe for a cake but forgets to turn on the oven, or worse, puts the cake in the freezer.

The Solution: Teaching the AI to "Fix" Its Own Logic

The researchers then used a technique called Reinforcement Learning (RL). Think of this as a strict coach who doesn't just say "Good job!" or "Bad job!" but gives specific feedback:

The "Feasibility Gate": The coach says, "If your code breaks the rules (like picking two conflicting items), you get zero points, no matter how good the score looks." This forces the AI to prioritize following the rules over just getting a high number.
The "Anti-Lazy" Penalty: The coach punishes the AI if it tries to take the easy way out (like just sorting items by weight and ignoring the complex interactions).
The "Scaffold": They gave the AI a specific thinking template: "Deconstruct the problem, guess a strategy, critique your own guess, and then write the code."

The Results: A Reusable "Solver" is Born

After this training, the AI didn't just get better at guessing; it fundamentally changed how it worked.

The "Compiler" Effect: The AI learned to write a single, reusable piece of code (a solver) that correctly implemented the "Simulated Annealing" strategy.
The Magic: In 99.8% of the cases, the AI wrote code that followed this correct pattern. It fixed the logic errors that the untrained AI kept making.
The Performance: The new "Hero" solver achieved a score within 5% of the theoretical best possible answer.
The Cost: This is the most exciting part.
- The old way (guessing 64 times per puzzle) took a lot of computer time for every single new puzzle.
- The new way (writing the solver once) meant the computer only had to do the heavy lifting once. After that, the solver could run on thousands of puzzles instantly.
- The Math: The new method was 91 times cheaper in terms of computer time per puzzle compared to the old "guessing" method.

What Didn't Work (The "Negative" Lessons)

The paper also tested what happens if you remove the special training tricks:

No Rules: If you just let the AI try to be creative without strict rules about following constraints, it goes back to making mistakes.
Soft Rules: If you tell the AI "it's okay to break rules a little bit if the score is high," it fails. The AI needs a hard "stop" signal to learn to respect the rules.
Just the Prompt: If you just tell the AI "be smart" in the instructions but don't train it with the reward system, it still fails. The instructions are just a map; the training is the vehicle that actually drives the car.

The Conclusion

This paper proves that we can train AI models to stop being "instant guessers" and start being "programmers." By using reinforcement learning with strict rules, the AI can synthesize a reusable tool that solves a whole family of hard problems correctly, rather than struggling to solve each one individually.

It's the difference between hiring a person to solve a math problem for you every day (expensive and slow) versus teaching that person to build a calculator that solves the problem for you forever (cheap and fast). The researchers showed that with the right training, AI can build that calculator.

Technical Summary: Beyond Inference-Time Search

1. Problem Statement

Current Large Language Models (LLMs) typically treat combinatorial optimization as an inference-time procedure, solving each problem instance separately through sampling, search, or repeated prompting. This paradigm incurs a "marginal cost" of reasoning for every new query. The authors investigate whether Reinforcement Learning (RL) can shift this reasoning cost into the model's weights, enabling the synthesis of a reusable solver for an entire problem family rather than generating per-instance solutions.

The study focuses on Synergistic Dependency Selection (SDS), a controlled, strongly NP-hard variant of the Quadratic Knapsack Problem. SDS is designed as a "deceptive" optimization landscape where:

Local signals contradict global optimality: Quadratic interaction terms dominate linear weights, causing greedy heuristics to fail.
Strict feasibility constraints: Solutions must satisfy cardinality, precedence, mutual exclusion, and group limits.
Template retrieval vs. operationalization: While base models can often retrieve the syntax of appropriate solvers (e.g., Simulated Annealing), they frequently fail to implement the executable logic correctly (e.g., misapplying acceptance rules).

The paper addresses three core research questions:

Competence Wall: Can extensive test-time sampling (Best-of-N) recover the performance of an RL-trained policy in deceptive landscapes, or does the base model hit a ceiling?
Semantic Repair: When RL succeeds, does it merely sharpen the frequency of correct solutions, or does it repair executable algorithmic logic that naive sampling cannot recover?
Amortized Solver Synthesis: Can training-time optimization distill reasoning into a lightweight, reusable program that outperforms repeated per-instance search?

2. Methodology

The authors propose Hero, a policy fine-tuned using Group Relative Policy Optimization (GRPO) on the Qwen2.5-Coder-14B-Instruct model. The approach is intentionally minimalist, stripping away common stabilizers (e.g., KL penalties, oracle anchoring) to isolate the effects of a feasibility-first recipe.

Key Components:

Scaffolded System Prompt: The prompt enforces a "Deconstruct-Hypothesize-Critique" reasoning loop. It explicitly warns the model against greedy heuristics and encourages the design of search strategies that balance exploration and exploitation.
Hierarchical Reward Design: A composite reward $r(o)$ $r (o)$ prioritizes structural compliance over raw optimality:
- Format & Execution ( $R_{exec}$ ): Ensures valid Python syntax, schema compliance, and graph-theoretic structure. Crucially, it includes an anti-lazy sorting penalty to suppress the pre-trained model's tendency to use linear greedy heuristics that ignore quadratic interactions.
- Feasibility-Gated Optimality ( $R_{nom}$ ): The primary optimization signal is strictly gated. If a solution violates any hard constraint (cardinality, precedence, etc.), the reward is zero, regardless of the objective score. This forces the policy to prioritize constraint satisfaction before optimizing the objective.
Training Regime: The model is trained for 90 global steps on 12 NVIDIA GH200 GPUs, observing only ~4.5% of a full prompt-level epoch but generating 23,040 reasoning traces.

3. Key Contributions

The paper's contributions are empirical and mechanistic rather than algorithmic:

Identification of a Competence Wall: Under identical prompting, Best-of-64 sampling of the base model saturates at a 28.7% gap to the Virtual Best Solver (VBS). Despite retrieving superficially appropriate solver templates (e.g., 21.9% of unique base codes resemble Simulated Annealing), the base model fails to operationalize them correctly.
Demonstration of Semantic Repair: The RL-trained policy (Hero) converges to a constraint-aware Simulated Annealing template in 99.8% of feasible outputs. It repairs the "Global Best Bug" prevalent in base model samples, where the acceptance logic incorrectly compares neighbors to the running global best rather than the current state. This correction enables true annealing behavior.
Validation of Amortized Solver Synthesis:
- Performance: Hero achieves a 5.0% gap to VBS, significantly outperforming the base model and classical heuristics like Local Search (10.0% gap).
- Efficiency: Hero is 91× cheaper in post-generation execution/search cost compared to the cumulative cost of Best-of-64 evaluation.
- Reusability: A "compile-once" evaluation shows that a single frozen solver generated per seed remains highly competitive (97.87% pass rate, 4.34% gap) when reused unchanged across the entire test set, proving the model synthesizes a reusable artifact rather than a per-instance generator.

4. Results and Ablations

Main Performance: Hero achieves a 97.8% pass rate and a 5.0% gap to VBS. It outperforms the refreshed ShinkaEvolve baseline (which uses strong proprietary models at deployment time) and approaches the performance of CP-SAT (1.0% gap) while being 6.3× faster in execution.
Ablation Studies:
- Structural Scaffolding: Removing the structural reward (anti-lazy sorting and graph-structure checks) causes performance to collapse to a 34.7% gap, as the model reverts to brittle greedy heuristics.
- Feasibility Gate: Replacing the hard feasibility gate with a soft penalty degrades performance significantly (57.4% pass rate vs. 97.8%), confirming that the hard gate is necessary to prevent mode collapse into invalid solutions.
- Oracle/Diversity: Adding oracle anchoring or diversity penalties degrades performance, suggesting that sparse, feasibility-first feedback is more effective than dense outcome shaping in this domain.
Generalization:
- No Catastrophic Forgetting: The model retains general coding capabilities (HumanEval Pass@1: 80.9% vs. Base 82.3%).
- Cross-Domain: Applying the same recipe to Job Shop Scheduling (JSSP) yields positive results (99.3% pass rate, 6.12% gap), though the authors note this is narrower evidence of transfer rather than proof of domain-agnostic robustness.

5. Significance and Claims

The paper claims to demonstrate that RL can move a code LLM from a regime of per-instance search to reusable solver synthesis. The significance lies in the finding that RL acts not merely as a "distribution sharpener" (improving the efficiency of finding existing solutions) but as a functional compiler that repairs executable logic (e.g., fixing the Metropolis acceptance rule) that naive sampling cannot reliably recover.

The authors emphasize that this success relies on a disciplined, feasibility-first scaffolding rather than a universal recipe. The method depends on specific design choices, such as the hard feasibility gate and structural penalties, and is sensitive to reward normalization. The work suggests that for complex, deceptive optimization landscapes, the "reasoning" required to build a solver can be distilled into the model's weights, creating a deployable artifact that is significantly more efficient than repeated inference-time search.