💻 computer science

LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency

This paper proposes an LLM-guided evolutionary search framework enhanced by a Profile-Diverse Retention (PDR) strategy that maintains behavioral diversity in candidate reformulations, demonstrating that such diverse context selection combined with validation-based model choice significantly improves solver efficiency on combinatorial problems compared to strategies relying solely on recency or performance.

Original authors: Kostis Michailidis, Dimos Tsouros, Nguyen Dang, Tias Guns

Published 2026-07-31

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kostis Michailidis, Dimos Tsouros, Nguyen Dang, Tias Guns

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

Imagine you are trying to solve a massive, mind-bending puzzle. In the world of computer science, this is called "Constraint Programming." It's the magic behind everything from scheduling airline flights and organizing factory assembly lines to cracking secret codes and planning the perfect school timetable. The tricky part isn't just finding an answer; it's finding the answer fast. To do this, humans write "models"—a set of strict rules and instructions that tell a computer solver exactly how to look for the solution. Think of the model as a map. A good map gets you to the destination quickly, but a bad map might send you in circles for hours, even if it technically leads to the right place.

For a long time, experts have known that the way you draw this map matters more than the solver itself. But drawing the best map is hard work. Recently, we've met a new assistant: Large Language Models (LLMs). These are the super-smart AI chatbots that can read a problem description and write the rules for you. They are great at getting the rules right, but they aren't always great at making the rules fast. It's like having a chef who can perfectly follow a recipe but doesn't know how to chop vegetables efficiently. This paper asks a big question: Can we teach these AI chefs to not just cook the meal, but to redesign the kitchen so the meal gets cooked in record time?

The researchers behind this study decided to treat model creation like a game of evolutionary survival. Instead of asking the AI to write the perfect model in one go, they set up a loop where the AI tries, fails, learns, and tries again. They call this an "evolutionary search." Here's how it works: The AI proposes a new version of the puzzle rules (a "reformulation"). A computer then tests this new version against the old one. If the new version is faster, it gets to stay in the game. If it's slower or wrong, it gets cut. The AI then looks at its past attempts and the feedback it received to write the next, hopefully better, version.

The team tested ten different strategies for how the AI should remember its past attempts. Some strategies told the AI to only look at its very last try (like a student who only studies the night before). Others told it to only remember the fastest attempts it ever made (like a runner who only looks at their personal bests). But the researchers suspected that these approaches were too narrow. They wondered if the AI needed a more diverse "memory bank"—a mix of fast attempts and attempts that solved the puzzle in completely different ways.

To test this, they invented a new strategy called Profile-Diverse Retention (PDR). Imagine you are a coach training a team of runners. A coach who only remembers the fastest runner might miss the fact that one runner is great at sprints while another is great at long distances. PDR is like a coach who keeps a roster of runners who are not only fast but also have unique running styles. By keeping a diverse group of "fast but different" attempts in the AI's memory, the AI can mix and match ideas to create something truly new and efficient.

The results were exciting. Across eight different types of complex puzzles (from "Social Golfers" to "Tail Assignment"), the evolutionary search consistently found models that were significantly faster than the original human-written ones. In fact, for some problems, the new models were hundreds of times faster. The study showed that the strategy of keeping a diverse memory (PDR) worked better than just keeping the most recent or the single fastest attempts. It also proved that checking the models on a separate set of "test" puzzles (validation) was crucial; without this step, the AI sometimes just memorized the training puzzles rather than learning how to solve them generally.

Interestingly, the researchers also compared their "whole-model redesign" approach against a method that just adds small extra rules to the original model (like adding a few extra hints to a map). Their "whole redesign" approach won every time, suggesting that sometimes you need to redraw the whole map, not just add a few arrows.

In the end, this paper suggests that we can use AI to not just solve problems, but to reinvent how we tell computers to solve them. By letting the AI evolve its own strategies and keeping a diverse library of its best ideas, we can build constraint models that are dramatically more efficient. It's a step toward a future where computers don't just follow our instructions, but help us write better instructions for themselves.

Technical Summary: LLM-Guided Evolutionary Search for Constraint Model Reformulation

Problem Statement

Combinatorial problems are ubiquitous in industrial applications, often modeled using Constraint Programming (CP). While Large Language Models (LLMs) have demonstrated the ability to generate correct declarative constraint models from natural language, correctness alone does not guarantee efficiency. A model that is semantically correct may still be computationally expensive to solve due to suboptimal modeling choices (e.g., variable viewpoints, constraint formulations, or encodings). Manually reformulating these models to improve solver performance is a critical bottleneck. Existing automation approaches often rely on rule-based transformations or append "streamliners" (additional constraints) to a fixed model structure, rather than performing holistic reformulations that change the model's viewpoint or variable encodings.

Methodology

The authors propose an LLM-guided evolutionary search framework for performance-oriented constraint model reformulation. Inspired by Automatic Heuristic Design (AHD), the system iteratively generates, evaluates, and selects model reformulations.

Core Workflow

Initialization: A baseline model ( $B$ ) is established, and its runtime performance is measured on a training set ( $D_{tr}$ ).
Iterative Loop: For $T$ $T$ iterations:
- Context Selection: A search strategy ( $\sigma$ ) selects a subset of previous attempts (rationale, model, and feedback) to form the prompt context ( $R_t$ ).
- Generation: The LLM receives a prompt containing the task description, baseline model, runtime history, and selected context. It outputs a rationale ( $\rho_t$ ) and a candidate model ( $m_t$ ).
- Evaluation: The candidate is executed on $D_{tr}$ . The evaluator checks for solution validity (ensuring the candidate's answer matches the baseline's answer for the same instance) and measures the total runtime.
- History Update: The attempt is recorded in the history $H_t$ .
Final Selection: After the search terminates, all solution-valid incumbents are evaluated on a separate validation set ( $D_{val}$ ). The model with the lowest total runtime on $D_{val}$ is selected as the final output. This step is crucial to prevent overfitting to the training instances.

Search Strategies

The paper compares ten strategies for selecting the context $R_t$ provided to the LLM:

Baselines: Sampling (no context), Full-history (all previous attempts), Last-k (recency), and Top-k (quality/fastest).
Hybrid: Combines recency and quality.
Evolution of Heuristics (EoH): Maintains a population of models and uses specific operators (e.g., "distinct approach," "compatible combination") to guide generation, with and without performance feedback.
Profile-Diverse Retention (PDR): A novel strategy introduced in this work. PDR explicitly seeks behavioral diversity. It represents each model as a vector of normalized runtimes across training instances. It uses Maximal Marginal Relevance (MMR) to select a set of attempts that are both fast (high quality) and behaviorally distinct (low similarity in runtime profiles) from one another.

Experimental Setup

Benchmarks: Eight satisfaction problems from CSPLib (e.g., Tail Assignment, Car Sequencing, Covering Arrays).
Model: DeepSeek V4 Flash (1M token context).
Solver: OR-Tools CP-SAT via CPMpy.
Metrics: Geometric Mean (GM) of speedups on held-out test instances ( $D_{test}$ ), using PAR2 (penalized average runtime) for timeouts.

Key Contributions

Evolutionary Framework: An adaptation of AHD specifically for whole-model reformulation of declarative CP models, allowing the LLM to change viewpoints, variables, and encodings, not just append constraints.
Profile-Diverse Retention (PDR): A context selection strategy that applies MMR to instance-level runtime vectors. It retains attempts that are fast but exhibit different solving behaviors, aiming to diversify the search space beyond simple recency or quality metrics.
Systematic Evaluation: A comprehensive comparison of ten search strategies across eight problems, demonstrating that diverse context retention outperforms strategies that retain only the most recent or fastest attempts.
Validation-Based Selection: The introduction of a validation-based final model selection step (often absent in AHD pipelines) is shown to consistently improve held-out performance and mitigate overfitting.

Results

Performance Gains: The evolutionary search produces substantial speedups on held-out test instances. The best strategy (PDR) achieved a geometric mean speedup of 2.26× across all problems, with specific instances showing gains up to 250.7× (on Covering Arrays).
Diversity Matters: Strategies that maintain a diverse context (PDR, EoH with feedback) generally outperform those relying solely on recency (Last-1) or quality (Top-1). PDR outperformed the quality-only Top-5 strategy by a factor of 1.30×.
Whole-Model vs. Streamliners: The proposed whole-model reformulation approach significantly outperformed an adapted baseline that only generates additive streamliners (StreamLLM-single), which achieved only a 1.02× speedup.
Cost Efficiency: While Sampling generated the most tokens, Full-history remained cost-effective due to KV caching. PDR delivered the highest speedup at a lower cost than Sampling.
Reliability: No selected models returned invalid answers or false-unsat results on test instances. Validation-based selection successfully filtered out candidates that overfitted to training data.

Significance and Claims

The paper claims that iterative reformulation guided by LLMs can automate the discovery of high-performance constraint models, achieving significant speedups without human intervention. It highlights that behavioral diversity in the search context is a critical factor for success, surpassing traditional metrics like recency or raw speed.

The authors modestly note that while the results are promising, the study is limited to a single LLM, a single solver configuration, and eight specific satisfaction problems. They suggest future work could explore optimization problems, different solvers, and more explicit use of solver-rich feedback (e.g., conflict counts, search tree depth) to further refine diversity metrics. The work positions itself as a step toward automating the "holy grail" of constraint modeling, moving beyond mere correctness to performance-oriented automation.