TLDR: X-evolve is a novel method that combines large language models (LLMs) with evolutionary algorithms to solve complex optimization problems. Unlike previous approaches that evolve individual solutions, X-evolve evolves entire “solution spaces” defined by tunable programs. This strategy significantly reduces the number of LLM calls needed, making the process more efficient and cost-effective. It has achieved new records in problems like the cap set problem and Shannon capacity of cycle graphs, and developed superior heuristics for online bin packing.
In the rapidly evolving field of artificial intelligence, combining large language models (LLMs) with evolutionary algorithms (EAs) has shown great promise for tackling complex optimization challenges. However, existing methods often face a significant hurdle: the high cost associated with numerous LLM interactions, as they typically focus on refining individual solutions one at a time.
A groundbreaking new approach, called X-evolve, is shifting this paradigm. Instead of evolving single solutions, X-evolve focuses on evolving entire “solution spaces”—collections of potential solutions. This innovative strategy dramatically reduces the number of times an LLM needs to be called, making the optimization process far more efficient and accessible.
At its core, X-evolve leverages LLMs to generate what are termed “tunable programs.” These are special pieces of code where certain parts are designated as “parameters” that can be adjusted. These tunable parameters define a flexible solution space. Once a tunable program is generated, a specialized score-based search algorithm, known as X-search, takes over. This algorithm efficiently explores the parametrically defined space, guided by feedback from how well each potential solution performs against the problem’s objective function.
The process is iterative: X-search samples different combinations of parameters from the tunable program, evaluates their performance, and uses these scores to refine its search in subsequent rounds. This continuous feedback loop allows for a broader and more effective exploration of the problem landscape, leading to faster convergence and significantly lower search costs. In fact, X-evolve can require up to two orders of magnitude fewer LLM calls compared to previous leading methods.
X-evolve addresses two fundamental challenges in this domain: the lack of direct performance feedback for LLMs and the difficulty of defining effective search spaces for evolutionary algorithms. By having LLMs generate the structure of the solution space itself, and then using score-based feedback to navigate it, X-evolve provides the crucial evaluative loop that LLMs typically lack when working on optimization problems independently. This also reduces the need for deep expert knowledge in designing the search space.
The effectiveness of X-evolve has been demonstrated across three challenging optimization problems:
Cap Set Problem
For the notoriously difficult cap set problem, X-evolve discovered a larger partial admissible set, establishing a new, tighter asymptotic lower bound for the cap set constant (C ≥ 2.2203). It also matched state-of-the-art results for constructing maximal cap sets in dimensions 3 through 8, achieving this with significantly improved search efficiency.
Shannon Capacity of Cycle Graphs
In information theory, X-evolve successfully uncovered a larger independent set for the 15-vertex cycle graph (size 19,946), thereby raising the known lower bound on its Shannon capacity. It also rediscovered the best-known maximum independent set sizes for other cycle graphs.
Also Read:
- AdaptFlow: Teaching AI Workflows to Learn and Adapt Like Humans
- AI Framework Transforms Power System Descriptions into Solver-Ready Models
Online Bin Packing Problem
For the NP-hard online bin packing problem, X-evolve generated new strategies (heuristics) that consistently outperformed standard approaches like “first-fit” and “best-fit” across established benchmarks and custom datasets. These generated heuristics are not only effective but also interpretable, cost-efficient, and robust.
The efficiency of X-evolve means that high-quality solutions can often be achieved with fewer than 20,000 LLM calls, sometimes even just a few hundred. This makes advanced optimization techniques more accessible to typical researchers. While the frequency of LLM calls has dropped significantly, the large number of evaluations performed by X-search can become a new bottleneck, an area for future research.
X-evolve represents a significant step forward in combining the power of large language models with the exploratory capabilities of evolutionary algorithms, paving the way for breakthroughs in complex scientific and engineering problems. You can read the full research paper for more details. Learn more about X-evolve here.
