LLM-Guided Evolutionary Search for Constraint Model...

LLM-Guided Evolutionary Search for Constraint Model... | AI Research

Key Takeaways

LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency explores how to automate the process of refining constraint mo...
Combinatorial problems appear in numerous industrial applications.
A common approach is to formulate these problems as declarative constraint models that can subsequently be compiled to and solved by a range of back-end solvers.
Recent work shows that Large Language Models (LLMs) can produce correct models from natural language, but even a correct model can be expensive to solve because performance remains sensitive to modelling choices.
In this work, we investigate whether LLMs can automate performance-oriented model reformulation.

Paper AbstractExpand

Combinatorial problems appear in numerous industrial applications. A common approach is to formulate these problems as declarative constraint models that can subsequently be compiled to and solved by a range of back-end solvers. Recent work shows that Large Language Models (LLMs) can produce correct models from natural language, but even a correct model can be expensive to solve because performance remains sensitive to modelling choices. In this work, we investigate whether LLMs can automate performance-oriented model reformulation. Inspired by Automatic Heuristic Design (AHD), we use an evolutionary framework in which an LLM proposes candidate reformulations that are verified and benchmarked against the user-defined baseline model. We compare AHD-adapted search strategies that control which prior attempts, instructions, and measured feedback enter each prompt. Existing retention strategies prioritize recency or performance, but do not explicitly diversify the context. To cover this gap, we introduce Profile-Diverse Retention (PDR), which applies Maximal Marginal Relevance (MMR) to instance-level runtime vectors to retain behaviourally diverse attempts. We systematically evaluate the strategies on eight CSPLib problems using validation-based final model selection. The results show that: (i) iterative reformulation can produce substantial held-out speedups; (ii) strategies that keep the retained context diverse outperform those that retain only recent or the fastest attempts; and (iii) validation-based selection improves the held-out speedup of every strategy.

LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency explores how to automate the process of refining constraint models to make them solve faster. While Large Language Models (LLMs) can generate correct models from natural language, these models are often inefficient. The authors propose an evolutionary framework where an LLM iteratively proposes and improves model reformulations, using feedback from solver performance to guide future attempts.

Automating Model Reformulation

In constraint programming, the way a problem is modeled—such as the choice of variables, constraints, and encodings—significantly impacts how quickly a solver can find a solution. Traditionally, this is a manual, expert-driven task. The authors introduce an iterative loop where an LLM generates a model, which is then benchmarked against a baseline model on training instances. The system evaluates the model's validity and its solving time, using this performance data to inform the LLM's next attempt.

Profile-Diverse Retention

A key challenge in evolutionary search is deciding which past attempts to show the LLM in its next prompt. The authors introduce "Profile-Diverse Retention" (PDR) to address this. Instead of only keeping the most recent or the fastest models, PDR uses Maximal Marginal Relevance (MMR) to select a set of models that are both fast and behaviorally distinct. By analyzing per-instance runtime vectors, the system ensures the LLM receives a diverse set of examples, which helps it explore different strategies rather than getting stuck on a single approach.

Performance and Selection

The researchers evaluated their framework on eight constraint satisfaction problems from CSPLib. Their findings indicate that iterative reformulation can lead to significant speedups on held-out test instances. The study highlights that strategies maintaining a diverse context for the LLM consistently outperform those that focus only on the fastest or most recent attempts. Additionally, the authors found that performing a final model selection on a separate validation set—a step often omitted in similar automated design pipelines—improves the performance of every strategy tested.

Considerations for Implementation

The framework relies on the ability to verify that a reformulated model is "solution-valid," meaning it produces the same answers as the baseline model. The authors note that verifying equisatisfiability can be computationally difficult, so they use a solution-level validation method where the model's output is checked against the baseline. Because the process involves multiple iterations of model generation and solver benchmarking, the efficiency of the final model depends on the quality of the feedback provided to the LLM and the diversity of the retained history.