Distribution-Aware Algorithm Design with LLM Agents

Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano, Tomer Galanti · 2026

Read Distribution-Aware Algorithm Design with LLM Agents by Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano, Tomer Galanti (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14141.txt.

Introduction

Koganti and three co-authors formalize distribution-aware programming: learning specialized solvers from experience. Many optimization problems recur on cases drawn from one underlying source, so a system can start with a general solver and learn a cheaper way to solve future cases. Samples from an unknown deployment source yield working solver code whose quality and runtime carry over to new cases. Analysis shows when the offline cost of specialization pays off through lower deployment cost, and a model agent that proposes structural guesses applies the idea.

Catalog record

CREATORSaharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano, Tomer Galanti
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115920
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14141

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distribution-Aware Algorithm Design with LLM Agents Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano, Tomer Galanti 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 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 21 structured combinatorial-optimization target distributions across seven problem classes. The synthesized solvers reach mean normalized quality 0.971 0.971 , improve by + 0.224 +0.224 over the average heuristic pool and by + 0.098 +0.098 over the highest-quality heuristic, and are 336.9 × 336.9\times , 342.8 × 342.8\times , and 16.1 × 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 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. 1 Introduction Classical learning theory ( 54 ; 55 ; 56 ) is largely organized around correctness and generalization. But when the learned object is an executable procedure ( 51 ) , such as an algorithm, solver, or piece of code, correctness is only part of the objective. Two procedures may both return valid solutions on the deployment distribution while differing substantially in runtime. In that setting, they have not learned equally well. The learned object must generalize not only in quality, but also in computation. We study this through distribution-aware program learning : from samples of an unknown deployment distribution, a learner returns solver code evaluated on fresh instances by both solution quality and runtime. For decision problems, quality is correctness; for optimization problems, it measures proximity to optimality. The goal is not merely to solve the ambient problem class, but to learn an algorithm whose execution is specialized to the target regime. Our central abstraction is a solver hint : reusable structure inferred from samples and compiled into solver code. Hints may be backdoors in SAT, latent decompositions in graph problems, active-resource patterns in packing problems, or geometric structure in routing problems. The sample-to-solver map therefore factors as S\;\longmapsto\;\widehat{h}_{S}\;\longmapsto\;\widehat{c}_{S}=\mathrm{Comp}(\widehat{h}_{S}) . This factorization is also how we interpret LLM synthesis. The agent is not best viewed as writing a solver in one shot; it proposes structural hypotheses, estimates reusable summaries from the sample, and writes a deployment solver conditioned on those summaries. Solver hints are computational shortcuts. In SAT, for example, the hint might be a reusable backdoor set. Correctness need not be learned: a complete solver can always be used as fallback. What the sample learns is which shortcut to compile so that future instances are solved faster. This separation between correctness and learned computation is central to both our theory and our experiments. The framing connects to a long-standing question in complexity theory: what does it mean for a problem to be hard on average ? Worst-case complexity has a clean primary object, the language, but average-case complexity ( 34 ; 28 ; 5 ) also requires a distribution. In practice, deployment distributions often lack closed-form descriptions amenable to classical analysis. Smoothed analysis ( 52 ) , parameterized complexity ( 14 ) , and structural backdoors ( 57 ) each give hand-designed routes to distribution-specific tractability. We propose a complementary constructive route: treat the distribution as accessible only through samples, learn a solver against it directly, and use the learned solver as a witness of distribution-specific tractability. Contributions. In this paper we make the following contributions: 1. We introduce distribution-aware program learning : a setting in which the learned object is executable solver code, and success is measured by both solution quality and deployment runtime. The key abstraction is a solver hint , a reusable description of distribution-specific structure inferred from samples and compiled into specialized solver code. 2. We formalize when samples can improve computation. For fixed solver libraries, the empirically fastest sample-consistent solver generalizes in both correctness and runtime. For structured hint classes, statistically identifiable hints can be recovered from polynomially many samples and compiled into specialized solvers. A hidden SAT-backdoor model makes the mechanism concrete: fallback preserves correctness, while the recovered hint yields exponential per-instance speedup on the deployment distribution. 3. We instantiate the sample-to-hint-to-solver view with an LLM synthesis procedure in which each candidate consists of a distributional hypothesis, a train-time analysis program, and a deployment solver. Across 21 structured combinatorial-optimization target distributions, 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. 4. We inspect the synthesized solvers and find that many gains come from changing the computational scale: generated code often replaces ambient exponential search or full general-purpose optimization with lower-order, distribution-specific computations. As an external diagnostic, on released PACE 2025 43 Dominating Set private instances, the synthesized solver returns valid solutions on all 100 graphs and runs about two orders of magnitude faster than top competition solvers, with a moderate quality gap. access to D learned representation deployed solver Worst-case algorithm design Average-case complexity This paper none (worst case over D ) algorithm with worst-case guarantee analyze D specified analytically algorithm tuned to D analyze sample S\sim D^{n} solver hint \hat{h}_{S}\in\mathcal{H} solver \widehat{c}_{S}\in\mathcal{C} learn compile \mathrm{Comp} effective class \mathrm{Comp}(\mathcal{H})\subseteq\mathcal{C} Figure 1: Three access models for designing solvers against a distribution D . Worst-case design assumes no distributional information, while average-case complexity assumes an analytic specification of D . We study the intermediate sample-access regime: from S\sim D^{n} , the learner infers a solver hint \hat{h}_{S}\in\mathcal{H} and compiles it into a deployed solver \widehat{c}_{S}=\mathrm{Comp}(\hat{h}_{S}) . Thus the effective search space is the structured subfamily \mathrm{Comp}(\mathcal{H})\subseteq\mathcal{C} . Our agents approximate this sample-to-hint-to-solver map. 2 Related Work We treat execution runtime as part of generalization when the learned object is executable solver code. Several established literatures touch parts of this picture. We therefore situate the contribution narrowly: the main novelty is not the broad idea that data can improve computation, but the explicit sample \to hint \to solver formalization and the theory-plus-benchmark package built around it. Average-case and beyond-worst-case analysis. Average-case complexity ( 34 ; 28 ; 5 ) asks when problems become tractable under input distributions, but often requires an analytic distribution before the analysis can begin. Smoothed analysis ( 52 ) , parameterized complexity ( 14 ) , and SAT backdoor analyses ( 57 ) give hand-designed routes to distribution-specific tractability. Our framework is complementary and sample-driven:

Read the complete text