PaperlayerView exact revision on arXiv

Source-linked AI summary

Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection

Hai Xia, Carlos Ansótegui, Stefan Szeider

arXiv:2608.17170v1cs.AI

TL;DR

Algorithm selection for constraint satisfaction problems depends on structural features, but designing extractors manually requires substantial expertise. This paper uses an LLM check–fix–verify loop to synthesize interpretable Python extractors, whose selectors outperform expert-curated and transformer-based baselines across three benchmarks.

  • Problem

    Algorithm selection needs structure-aware features, yet manually designing extractors requires expert knowledge and may miss solver-relevant properties.

  • Method

    An LLM agent reads MiniZinc models and uses a check–fix–verify loop to synthesize executable Python programs that produce interpretable graph-based features.

  • Results

    Across VRP, CS, and FLECC, selectors using synthesized features outperform expert-curated mzn2feat and transformer-based trans2feat baselines.

  • Takeaways & Limitations

    The framework provides inspectable, problem-specific extractors that experts can read, validate, and refine for MiniZinc-expressible problems.

  • Takeaways & Limitations

    Reliable synthesis currently depends on backends that follow the protocol, as both tested open-weight models failed in all 10 trials.

Abstract

from arXiv · show

Algorithm selection for constraint satisfaction problems requires extracting features that capture problem structure. Manually designing feature extractors demands deep domain expertise and quickly becomes a bottleneck when new problem classes appear. We present an automated approach that uses Large Language Models (LLMs) in an agentic check--fix--verify loop to synthesize executable Python scripts that act as interpretable, problem-specific feature extractors. Given a high-level MiniZinc model and an instance, the LLM agent generates code that constructs a typed graph representation and computes structural properties such as graph density, variable clustering, and constraint tightness. We evaluate our approach on three combinatorial problems (vehicle routing, car sequencing, fixed-length error-correcting codes) with a portfolio of five state-of-the-art solvers. The synthesized extractors yield algorithm selectors that consistently outperform both expert-curated mzn2feat features (up to $8.3$ percentage points (pp) test-set accuracy on FLECC) and the best transformer-based trans2feat variants. In the meanwhile, the synthesized feature extractors remain inspectable.

1 Introduction

Algorithm selection for hard combinatorial problems is limited by the expertise and time required to design and validate informative feature extractors. This work automates extractor synthesis with an LLM agent while retaining executable, interpretable features and improving selector performance across three problem classes.

  • Motivation: Solver performance can vary by orders of magnitude because combinatorial instance difficulty depends strongly on structural properties.Examples include customer density, time-window tightness, and constraint coupling.
  • Motivation: Feature-extractor design requires substantial domain expertise, and validating efficiency and effectiveness across instances is time-consuming.These costs have limited algorithm selection primarily to domains with mature formalisms, chiefly SAT.
  • Approach: An LLM agent synthesizes executable Python feature extractors from high-level MiniZinc descriptions through a check–fix–verify error-correcting loop.The generated program serves as the extractor.
  • Interpretability: The framework generates explicit graphical features, including graph density, variable clustering, and constraint tightness, rather than opaque neural embeddings.These Python programs and their outputs remain inspectable and interpretable.
  • Empirical validation: Across VRP, CS, and FLECC, synthesized-feature selectors outperform selectors using expert-curated mzn2feat and transformer-based trans2feat.Evaluation uses five state-of-the-art solvers: Gurobi, CPLEX, SCIP, Gecode, and OR-Tools.

2 Related Work

Algorithm selection predicts which portfolio algorithm to run for each instance using extracted feature representations, with performance bounded by the Virtual Best Solver. Prior work spans hand-engineered, graph-based, LLM-generated, and neural features, while this work synthesizes reusable extractors directly from MiniZinc specifications.

  • Algorithm Selection Problem: Algorithm selection maps each instance to a feature vector and learns a selector that chooses an algorithm under a resource budget.The Single Best Solver applies one algorithm to all instances, whereas the Virtual Best Solver selects the best algorithm per instance and upper-bounds any strategy.
  • MiniZinc: MiniZinc models define variables, constraints, and optional objectives, while data files provide instance parameters.A model file uses the .mzn extension, and an instance-parameter file uses .dzn.
  • Expert-curated features: Classical algorithm selection relies on hand-engineered feature sets, including SATzilla and mzn2feat.Hand-crafted features also support per-instance policy selection inside solvers, such as SAT-based tree decomposition.
  • Graph-based features without LLMs: Graph encodings can support algorithm selection without LLMs, but prior work applies one fixed, hand-specified encoding and feature set across domains.Stone et al. convert instances from three problem domains into domain-agnostic graph and image encodings and extract generic graph metrics.
  • LLM-based feature engineering and program synthesis: Unlike tabular LLM feature engineering, this work synthesizes a complete reusable extractor program from declarative .mzn/.dzn specifications.CAAFE and FeatLLM operate on existing tabular inputs, whereas the proposed extractor computes structural and semantic properties of the problem specification itself.
  • Neural embeddings for algorithm selection: Neural algorithm-selection approaches learn high-dimensional embeddings from algorithm artifacts, CNF structure, or textual constraint-optimization representations.The cited approaches use LLMs for source-code and documentation embeddings, graph neural networks with expert knowledge, or transformer encoders applied directly to instance text.

3 Problem-Specific LLM-Based Agent

The problem-specific agent converts MiniZinc models, instances, and a data schema into executable Python feature extractors through a prompt-controlled Clear–Insert–Check/Fix–Execute workflow. The 50-feature outputs vary across runs but repeatedly recover core structural metrics, while all four loop steps are necessary for successful synthesis.

  • Agent inputs and outputs: The agent takes MiniZinc model and data files plus a schema, then outputs a Python script extracting a feature vector for any instance.Two prompts govern script generation and domain-specific feature extraction, with the specialized prompt targeting 50 standardized structural features.
  • Agent workflow: The general prompt enforces four steps: Clear previous content, Insert the complete script, Check/Fix validation issues, and Execute the script to validate output.The workflow continues until an executable script produces a validated feature vector.
  • Feature synthesis: Across 10 independent syntheses per problem, core metrics such as graph density, degree statistics, and clustering recur, while other problem-specific features vary.The agent chooses the identity of the 50 features anew in every run; per-run feature lists and value tables are provided in the supplement.
  • Ablation findings: Removing any one of the four loop steps produced zero executable extractors, while weaker LLM backends that drift from the protocol failed in 10/10 trials.These results come from pilot ablations and the reported evaluation of weaker backends.

4 Experimental Analyses · 4.1 Experimental Settings · 4.2 Algorithm-Selection Toolchains

The experiments evaluate LLM2feat against mzn2feat and trans2feat across three constraint-problem benchmarks, five solvers, and multiple algorithm-selection toolchains. They examine feature correlation, utilization efficiency, selector accuracy, and synthesis variability under the stated experimental protocol.

  • 4 Experimental Analyses: The study evaluates agentic feature synthesis on three problem-specific algorithm-selection benchmarks, analyzing feature correlation, utilization efficiency, and selector accuracy.
  • 4.1 Experimental Settings: The solver portfolio contains Gurobi, CPLEX, SCIP, Gecode, and OR-Tools, spanning mixed-integer programming, constraint programming, and hybrid paradigms.Gurobi and CPLEX are commercial MIP solvers; SCIP combines CP and MIP techniques, while Gecode and OR-Tools represent CP-oriented coverage.
  • 4.1 Experimental Settings: Each synthesized extractor returns exactly 50 characteristics covering problem size, graph properties, data distribution, and structural complexity.The extraction template includes variables and constraints, density, clustering, centrality, statistical properties, symmetries, and sparsity.
  • 4.1 Experimental Settings: The benchmark suite comprises VRP, CS, and FLECC, with minimization, maximization, and decision tasks evaluated using an orientation where larger performance values are better.Each problem is split 7:3 into training and test sets.
  • 4.1 Experimental Settings: The agent backend is OpenAI o4-mini-2025-04-16 with default generation parameters, and stochasticity is quantified through 10 independent synthesis runs per problem.The stated defaults are fixed temperature 1.0 and medium reasoning effort.
  • 4.2 Algorithm-Selection Toolchains: Algorithm selection uses an instance-to-feature-vector table and an instance-to-per-solver-performance table to compare LLM2feat, mzn2feat, and trans2feat.The three extractors are respectively LLM-synthesized, expert-curated, and transformer-based.
  • 4.2 Algorithm-Selection Toolchains: Selector training uses Random Forest and AutoSklearn with Acc and Rank losses, while AutoFolio and LLAMA use default Acc loss; all training applies 5-fold cross-validation.AutoFolio and LLAMA are also reported as established tools in algorithm-selection surveys and challenges.

4.3 Research Questions … 4.9 Cost Analysis

Across seven sections, the paper shows that LLM2feat produces diverse, efficiently utilized, solver-aware features that improve algorithm-selection accuracy over curated and transformer-based baselines. Synthesis succeeds reliably with commercial LLMs at modest one-time cost, while tested open-weight backends fail to sustain the required protocol.

  • 4.3 Research Questions: The evaluation asks whether LLM2feat features are diverse, efficiently utilized, and competitive with mzn2feat- and trans2feat-based selectors.The questions target feature correlation, feature importance, and resulting algorithm-selection accuracy.
  • 4.4 Feature Correlation Analysis (Q1): 48.5% lower average absolute correlation is achieved by LLM2feat than mzn2feat on VRP, with lower correlations also reported on FLECC and CS.On VRP, average |r| is 0.221 for LLM2feat versus 0.429 for mzn2feat; FLECC is 0.306 versus 0.330, and CS is 0.551 versus 0.725.
  • 4.5 Feature Utilization Efficiency (Q2): LLM2feat meaningfully utilizes more generated dimensions than mzn2feat across all three problems.The effectively utilized shares are 96% versus 56.8% on VRP, 58% versus 23.2% on FLECC, and 84% versus 45.1% on CS.
  • 4.6 Accuracy Analysis (Q3): LLM2feat-based selectors reach higher accuracy with fewer features and continue improving where mzn2feat plateaus.On VRP, mzn2feat flatlines near 81% after 10 features, whereas LLM2feat peaks beyond 20 features; LLM2feat matches or exceeds mzn2feat at every size.
  • 4.6 Accuracy Analysis (Q3): Up to 8.3 pp improvement over mzn2feat is achieved by LLM2feat, alongside gains over the best trans2feat variants on FLECC and CS.The improvements over trans2feat are 7.4 pp on FLECC and 5.4 pp on CS, with the highest accuracy and lowest ranking on every problem–toolchain pair except AF’s trivial SB fallback.
  • 4.7 Head-to-Head Comparison with trans2feat: Even the worst LLM2feat run beats the best trans2feat variant on FLECC under RF and clearly dominates on CS.The head-to-head comparison evaluates 10 independent LLM2feat syntheses against 20 released trans2feat variants.
  • 4.8 Qualitative Feature Analysis: +2.9 pp test-accuracy gain over mzn2feat on VRP is associated with interpretable, complementary, solver-aware features rather than feature-set size.Examples include demand-distribution statistics and depot-centrality metrics; LLM2feat uses 50 features versus mzn2feat’s 95 and trans2feat’s 116, while extracting structural and solver-aware quantities such as tightness, propagation strength, supports, and distributional summaries.
  • 4.9 Cost Analysis: 10 of 10 trials succeed for o4-mini and Claude Sonnet 4, while DeepSeek R1 and Llama 3.3-8b-instruct fail in all 10 trials to follow check–fix–verify.A successful o4-mini synthesis costs ≈210 s and ≈$0.27 on average, and the resulting extractor can be reused indefinitely across instances of the same problem family.

5 Conclusion and Future Work

The paper concludes that an LLM-based agent can synthesize interpretable graph-theoretic feature extractors from MiniZinc models for algorithm selection. Its check–fix–verify workflow produces refinable Python scripts on demand, and the resulting selectors outperform expert-curated and transformer-based baselines across three benchmarks.

  • The framework synthesizes graph-theoretic, interpretable feature extractors from symbolic MiniZinc constraint models for algorithm selection.
  • The agentic check–fix–verify loop produces Python scripts that experts can refine in a gray-box manner.Extractor synthesis is described as cheap enough to perform on demand.
  • Across VRP, CS, and FLECC benchmarks with a five-solver portfolio, synthesized extractors yield algorithm-selection models that outperform mzn2feat and trans2feat baselines.

Impact Statement

The work automates interpretable feature-extractor creation from high-level MiniZinc models to reduce manual engineering and support algorithm selection in new constraint-optimization domains. Its explicit, testable, auditable code helps mitigate errors or biases when validated by domain experts.

  • Impact Statement: Automating interpretable feature-extractor creation reduces the manual engineering burden limiting algorithm selection to well-studied domains.The approach generates auditable Python extractors from high-level MiniZinc models.
  • Impact Statement: Auditable Python extractors can help practitioners build solver portfolios quickly for new problem classes, including scheduling, routing, and resource allocation.The stated applications extend algorithm selection beyond currently well-studied domains.
  • Impact Statement: Explicit, testable, and auditable extractor code mitigates errors or biases that may arise when LLM-generated code is deployed without validation.Domain experts can inspect and validate the generated code.

A Hyperparameters

The section specifies where the Random Forest and AutoSklearn hyperparameter settings are documented. Random Forest settings are shared with LLAMA’s random-forest classification mode.

  • Random Forest: Random Forest hyperparameters are provided in Table 5.The table covers settings shared by Random Forest training and LLAMA’s random-forest classification mode.
  • Random Forest: LLAMA’s random-forest classification mode uses the settings listed alongside Random Forest training.These shared settings are documented in Table 5.
  • AutoSklearn: AutoSklearn’s standard configuration is provided in Table 6.The section separately identifies Table 6 as the source for AutoSklearn settings.

B Additional Feature-Correlation Heatmaps

Figures 5–6 compare feature-correlation matrices for FLECC and car sequencing (CS). LLM2feat features show lower average absolute correlation than mzn2feat in both problems, indicating greater feature diversity for CS.

  • FLECC: For FLECC, LLM2feat features have average absolute correlation |r| = 0.306 versus |r| = 0.330 for mzn2feat.Figure 5 presents the corresponding feature-correlation matrices.
  • CS: For CS, LLM2feat features have |r| = 0.551 versus |r| = 0.725 for mzn2feat, a 24% improvement in diversity.Figure 6 presents the corresponding feature-correlation matrices.

C LLM Model Selection and Sensitivity

Agentic model capability determines whether the check–fix–verify protocol succeeds: o4-mini and Claude Sonnet reliably followed it, while Llama 3.3 and DeepSeek R1 failed under the prompts. Using o4-mini-2025-04-16, the study ran 10 independent syntheses per problem; top runs consistently beat mzn2feat, though full-run results were more variable.

  • LLM backend selection: o4-mini and Claude Sonnet reliably followed the check–fix–verify protocol, whereas Llama 3.3 and DeepSeek R1 failed under the prompts.The smaller open-source models’ failures are referenced in Section 4.9.
  • LLM backend selection: The framework used OpenAI o4-mini-2025-04-16 and ran 10 independent syntheses per problem.Tables 10–15 show the three highest-scoring runs per problem and toolchain, while Appendix D contains all 10 LLM2feat runs and 20 trans2feat variants.
  • Performance sensitivity: The full 10-run distribution was wider on CS/AutoSK, including two under-fitting syntheses with test accuracy ≈0.528 and correspondingly low training accuracy.Formal significance analysis for the full distributions appears in Section 4.7.

D Detailed Transformer Comparison

The study compares 20 official trans2feat feature sets across Random Forest and AutoSklearn toolchains for Car Sequencing and FLECC. Timeout and degenerate AutoSklearn fits are excluded from aggregate statistics and significance tests.

  • D Detailed Transformer Comparison: 20 trans2feat feature sets from the official repository are evaluated with both Random Forest and AutoSklearn toolchains.Tables 16–19 report per-variant results for Car Sequencing and FLECC.
  • D Detailed Transformer Comparison: 1800 s is the AutoSklearn training budget; runs exceeding it without producing a model are marked “TO.”TO runs are excluded from all aggregate statistics and significance tests.
  • D Detailed Transformer Comparison: Test accuracy <1% defines a degenerate constant-class AutoSklearn fit, marked “F” and excluded from aggregate statistics and significance tests.Raw result files for F runs are provided with the supplement.
Loading 2608.17170v1…