Distribution-Aware Algorithm Design with LLM Agents
Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano, Tomer Galanti
Why It Matters
What makes this one worth your time
This research could lead to more efficient algorithm design by leveraging LLMs to tailor solver code to specific distributions, potentially reducing computational costs and improving performance in practical applications.
The paper introduces a framework using LLM agents to design efficient, distribution-aware solver algorithms.
Summary
The paper presents a framework for designing distribution-aware algorithms using large language model (LLM) agents to generate solver code that is both correct and efficient in terms of runtime. The framework leverages solver hints derived from task distribution samples to compile specialized solver code, demonstrating significant improvements in execution speed and solution quality across multiple combinatorial optimization problems.
Key contributions
- Introduction of a framework for distribution-aware algorithm design using LLM agents.
- Demonstration of significant runtime and quality improvements in solver code across multiple problem classes.
- Empirical validation of the framework on structured combinatorial optimization tasks.
Notable insights
- The use of solver hints to compile distribution-specific solver code is a clever approach to improving both runtime and solution quality.
- The empirical results suggest that LLM-generated solvers can outperform traditional heuristics and exact solvers in terms of speed and quality.
Possible limitations
- Not stated in the abstract
Abstract
arXiv:2605.14141v1 Announce Type: new Abstract: We study learning when the learned object is executable solver code rather than a predictor. In this setting, correctness is not enough: two solvers may both return valid solutions on the deployment distribution while differing substantially in runtime. Given samples from an unknown task distribution, the learner returns code evaluated on fresh instances by both solution quality and execution time. Our central abstraction is a \emph{solver hint}: reusable structure inferred from samples and compiled into specialized solver code. We prove that the empirically fastest sample-consistent solver from a fixed library generalizes in both correctness and runtime, and that statistically identifiable hints can be recovered and compiled from polynomially many samples. Empirically, we instantiate the framework with LLM code agents on \(21\) structured combinatorial-optimization target distributions across seven problem classes. The synthesized solvers reach mean normalized quality \(0.971\), improve by \(+0.224\) over the average heuristic pool and by \(+0.098\) over the highest-quality heuristic, and are \(336.9\times\), \(342.8\times\), and \(16.1\times\) faster than the quality-best heuristic, Gurobi, and the selected time-limited exact backend, respectively. On released PACE 2025 Dominating Set private instances, the synthesized solver is valid on all \(100\) graphs and runs about two orders of magnitude faster than top competition solvers, with a moderate quality gap. Inspection shows that many gains come from changing the computational scale: replacing ambient exponential search or general-purpose optimization with compiled distribution-specific computation.