Training a Small Open Model to Write Feature Extractors for Solver Selection

Hard combinatorial problems, such as vehicle routing, scheduling or circuit verification, are usually solved by picking one of several solvers. No solver wins everywhere, so the field of algorithm selection learns to predict, from a few numbers describing an instance, which solver will be fastest on it. Those numbers are called features. Writing the code that computes them has always been the bottleneck: someone who understands the problem must hand-design statistics like constraint-graph density or clause-to-variable ratios, and must do it again for every new problem family. A recent result showed that a frontier language model, run in a loop that writes, executes and repairs code, can write these feature-extraction scripts and beat the human-designed ones. The same study found that open-weight models could not even follow the loop.

We propose to close that gap with domain specialization. We train a compact open model of roughly 8B parameters to write feature extractors. It learns by reinforcement learning, and its reward is not "the code compiles" but "the features this code produces let a cheap selector pick the right solver quickly." The reward charges for the time the extractor takes to run, because in algorithm selection feature computation is pure overhead. If this works, a laboratory could get a working solver selector for a brand-new constraint problem locally and within hours, without a domain expert and without a commercial API.

Core Claim

A compact code model trained with execution-grounded reinforcement learning can become a reliable synthesizer of feature extractors. It can be judged by the quantity algorithm selection actually cares about: the fraction of the gap between the single best solver and the per-instance oracle that gets closed, net of feature-computation time. The claim is new in two ways. It is new relative to the frontier-prompting system, because the synthesizer is small, open and trained. It is new relative to other specialized code models, because the reward comes from a downstream decision made from the program's outputs, not from the program's own correctness. The claim is falsifiable on held-out problem families. It fails if the trained model does not match frontier-generated extractors on families it never saw, or if simply imitating frontier outputs does just as well without reinforcement learning.

Where This Sits

The motivating evidence comes from Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection. That system, LLM2feat, takes a MiniZinc problem specification and uses o4-mini or Claude 3.5 Sonnet in a check–fix–verify loop to write a Python script computing structural features. It beat the expert tool mzn2feat by 8.3 percentage points of test selection accuracy on error-correcting-code instances. It beat transformer embeddings of the instance text by 7.4 points on those instances and by 5.4 points on car sequencing. It also reports that Llama 3.3 and DeepSeek R1 failed the protocol in 10 of 10 trials. That is exactly the gap we attack, and it also constrains us: an untrained open model is not a viable starting point, so we need supervised warm-starting before reinforcement learning.

The method comes from the domain-specialization line. AutoTriton fine-tunes an 8B code model and then trains it with Group Relative Policy Optimization (GRPO), a reinforcement-learning method that compares several sampled outputs per prompt. Its rewards are syntax and execution checks, and the resulting model beats much larger general models at writing GPU kernels. VeriGen shows that narrow-domain fine-tuning of 16B-scale models improves syntactic validity of hardware code. Both reward a program for being right. We reward a program for being useful to a learner, which is a different and noisier signal.

The target quantity comes from classical selection. SATzilla predicts log-runtime from 48 hand-built features and caps feature time at 60 seconds. AutoFolio automatically tunes the whole selection pipeline and reaches 1.3× to 15.4× speedups over the single best solver on ASlib. Btor2-Select uses keyword counts and graph-kernel features to close 65.3% and 67.8% of the gap between single best and oracle on hardware model checking. We reuse their evaluation logic and their insistence on charging feature time.

One adjacent line, which does not solve our problem, uses language models to represent the algorithms rather than the instances. Large Language Model-Enhanced Algorithm Selection and AS-LLM embed solver code with frozen CodeBERT-style models and match it to problem features. They leave specialization of the language model to future work, and they still need instance features from somewhere. Our extractors could feed their pipeline.

Research Program

The system has three parts.

The first part is a training pool of problem families. Each family consists of a MiniZinc specification, a data schema, a set of instances, and measured runtimes for a fixed portfolio. We reuse the five-solver portfolio from LLM2feat (Gurobi, CPLEX, SCIP, Gecode, OR-Tools) so results are comparable. Generating these runtimes is the known cold-start cost of algorithm selection, and we pay it once, offline. VRP, car sequencing and FLECC are held out entirely as test families.

The second part is the synthesizer. We start from an open 8B code model. We warm-start it with supervised fine-tuning on successful extractor-writing traces, both frontier-generated and self-generated, so that it learns the check–fix–verify protocol. We then train it with GRPO.

For a sampled extractor script $s$ on training family $f$, the reward is

$$R(s,f) = \mathrm{GapClosed}_{\mathrm{CV}}(s,f) - \lambda \,\frac{T_{\mathrm{feat}}(s,f)}{T_{\mathrm{cap}}},$$

with $R=0$ if the script crashes or exceeds the time cap. The terms are defined as follows. $\mathrm{GapClosed}_{\mathrm{CV}}$ is the cross-validated fraction of the single-best-to-oracle penalized-runtime gap that is closed. It is measured when a fixed random-forest selector is trained on the script's features over that family's instances. $T_{\mathrm{feat}}$ is mean per-instance extraction time, $T_{\mathrm{cap}}$ is a SATzilla-style budget, and $\lambda$ sets the price of overhead.

Scripts may run short solver probes, since SATzilla uses probing features, but the time penalty prices them. Cross-validation inside the family discourages features that memorize instance identity.

The third part is analysis. We ask what the trained model learns to compute. We check whether its features look like known graph invariants, how redundant they are (LLM2feat reported 48.5% lower correlation than mzn2feat on VRP), and whether the time penalty shifts it away from probing toward cheap syntactic statistics.

Baselines

The naive reference is the single best solver: always run the solver that is best on average over the training instances. Every method is reported as a fraction of the gap between this and the virtual best solver, which is the per-instance oracle. That makes the do-nothing point zero and the ceiling one.

The strongest existing method is LLM2feat run with o4-mini and Claude 3.5 Sonnet under its published protocol, as described in Synthesizing Feature Extractors. The file reports only relative figures: +8.3 points over mzn2feat on FLECC, and +7.4 and +5.4 points over trans2feat on FLECC and car sequencing. No absolute LLM2feat selection accuracy on these families was found in the Lacuna file, so we will rerun it ourselves. We will give it the same number of repair iterations and the same wall-clock extraction cap as our model. For a fair comparison, all feature sets feed an identical downstream selector trained on the same instance splits. We also report a second, AutoFolio-configured selector per feature set, so that a feature set is not penalized by a poorly matched learner. The trained 8B model beats this baseline if it matches or exceeds LLM2feat's gap closure on at least two of the three held-out families, net of extraction time.

The expert reference is mzn2feat with the same selector. It represents decades of hand engineering. Beating it on held-out families is the minimum bar for usefulness.

The text-embedding reference is trans2feat, which is transformer embeddings of the instance. It stands in for the dense-embedding routing used by language-model router work such as HierRouter.

Two ablations isolate the key ingredient. The first is the same 8B model after supervised fine-tuning only, with no reinforcement learning. The second is the same model trained with reinforcement learning where the reward is only "script runs and emits well-formed features." That second ablation is the AutoTriton-style reward. Comparing it to the full reward tells us whether the downstream selection signal matters, or whether executability alone is enough. A third ablation sets $\lambda=0$ to measure what the overhead penalty costs and saves.

Why not just…?

Why not just call a frontier model, since LLM2feat already works? For many users that is the right answer, and our comparison against LLM2feat measures exactly how much is lost by going local. The case for a trained open model rests on three things. It avoids sending proprietary instance data to an API. It runs where solvers are deployed. And it gives us a synthesizer we can study and train further. If our model falls well short of frontier extractors on held-out families, the honest conclusion is that this capability does not yet compress to 8B, and we will report it that way.

Why not just distill frontier traces with supervised fine-tuning and skip reinforcement learning? This is the most serious threat. Imitating LLM2feat outputs may fix protocol-following, which is the 10/10 open-model failure, and that may be most of the problem. The supervised-only ablation settles it. If it matches the full system on held-out families, reinforcement learning is unnecessary and we will say so. We expect the reward-trained model to pull ahead mainly on extraction-time-adjusted gap closure, because imitation has no signal about overhead or predictive value.

Why not just use generic features plus a better-configured selector? AutoFolio shows that tuning the selection pipeline matters a great deal, so part of any feature-set gain could instead come from the learner. That is why every feature set, including mzn2feat and trans2feat, is also evaluated under an AutoFolio-configured selector. If generic features plus configuration close the same gap, the extractor contributes nothing.

Why not just skip features and run a static portfolio? Learning Static Parallel Portfolios of Algorithms splits CPU time among fixed solvers and needs no features at all. We include an optimized time-share schedule as a reference. Btor2-Select reports beating a three-engine parallel portfolio with per-instance selection, which suggests features pay off when they are cheap enough. Our time penalty is aimed directly at that condition.

Decisive Checks

The main experiment is leave-families-out evaluation on VRP, car sequencing and FLECC with the five-solver MiniZinc portfolio. For each family we report selection accuracy, the fraction of the penalized-runtime gap closed with and without extraction time charged, and the rate at which the synthesizer returns a working script unassisted. That last number is directly comparable to the 0/10 success of untrained open models.

A stronger transfer test moves outside MiniZinc to the 3,498 Btor2 hardware tasks. The trained model receives only the format description and must write extractors whose features feed the same selector. The reference numbers are Btor2-Select's 65.3% (bit-vector) and 67.8% (array) gap closure with hand-built keyword and graph-kernel features. Approaching those figures from a format description alone would show that the model learned how to design features rather than memorizing MiniZinc idioms. Falling far short would show that the specialization is format-bound.

The last check is the cross-ablation. The full reward must beat both the supervised-only model and the "runs correctly" reward on held-out gap closure. Otherwise the core claim, that a downstream-decision reward is what makes a small model a good feature designer, is refuted.