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 \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 structured combinatorial-optimization target distributions across seven problem classes. The synthesized solvers reach mean normalized quality , improve by over the average heuristic pool and by over the highest-quality heuristic, and are , , and 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 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.
AI Impact Assessments
(1 models)Scientific Impact Assessment
Core Contribution
This paper formalizes distribution-aware program learning, where the learned object is executable solver code rather than a predictor, and success is measured by both solution quality and deployment runtime. The key abstraction is a solver hint: reusable structure inferred from distribution samples that is compiled into specialized solver code. The paper provides: (1) a theoretical framework showing that empirically fastest sample-consistent solvers generalize in both correctness and runtime; (2) a practical instantiation using LLM code agents that decompose synthesis into hypothesis formation, distributional analysis, and solver compilation; and (3) extensive empirical evaluation across 21 combinatorial optimization distributions.
The central insight—factoring learning into sample → hint → solver—is genuinely clarifying. It reframes LLM-based code generation not as one-shot synthesis but as a structured inference process where the agent proposes distributional hypotheses, estimates reusable summaries, and writes code conditioned on those summaries. This decomposition connects algorithm selection, program synthesis, and average-case complexity in a novel way.
Methodological Rigor
Theory: The theoretical results (Theorems 5.1-5.3) are clean but use standard concentration and union-bound arguments. The authors acknowledge this explicitly. Theorem 5.1 provides runtime-aware generalization for library selection—essentially showing that empirical runtime minimization among correct solvers approaches the best distribution-specialized runtime up to O(T_max√(log|C|/n)). Theorem 5.2 on hint recovery is straightforward finite-class estimation. The SAT backdoor example (Theorem 5.3) is illustrative but idealized. The gap between theory and practice is significant: the theorems assume known score families and finite hint spaces, while the practical method searches over an unknown, unbounded space of possible structural hypotheses using an LLM.
Experiments: The empirical evaluation is thorough. The benchmark covers 7 problem classes × 3 distributions = 21 targets with properly separated train/validation/test splits. The baseline catalog of 78 registered entries (including Gurobi, OR-Tools, specialized exact solvers, and diverse heuristics) is commendably comprehensive. The evaluation protocol is well-designed: geometric means for speedup ratios, arithmetic means for quality, and careful separation of synthesis-time and deployment-time costs.
However, there are concerns. The benchmark distributions are designed by the authors to contain exploitable structure, which somewhat inflates the apparent gains. Real-world optimization distributions may have less regular or less discoverable structure. The perturbation ablation (Table 15-16) reveals meaningful presentation dependence—quality drops from 0.945 to 0.867 under graph relabeling, with severe degradation on specific targets (Ring-template: -0.228, Geometric-anchor: -0.464). This suggests some generated solvers exploit incidental presentation features rather than true distributional structure.
Potential Impact
The framework has several impactful aspects:
1. Conceptual clarity: The hint abstraction provides a useful vocabulary for understanding when and how distribution-specific algorithm design works. The Figure 1 taxonomy (worst-case → average-case → sample-access) is pedagogically valuable.
2. Practical relevance: The PACE 2025 comparison provides external validation—the synthesized solver is valid on all 100 private instances and ~100× faster than competition solvers, though with a quality gap. This demonstrates real-world applicability beyond synthetic benchmarks.
3. Bridge between communities: The paper connects learning theory, algorithm design, program synthesis, and LLM agents in a principled way. The "learned object is code" perspective could influence how the community thinks about LLM-generated algorithms.
4. Scalability concerns: The method requires GPT-5.2 API calls (463 calls, 16.1M tokens per run across 21 distributions), which is expensive. The one-time synthesis cost is justified only when amortized over many future instances from the same distribution.
Timeliness & Relevance
This is highly timely. The explosion of LLM-based code generation has created urgent need for frameworks that go beyond correctness to reason about computational efficiency. The paper directly addresses the current gap between "LLMs can write code" and "LLMs can write *good* code for specific deployment contexts." The connection to algorithm selection and automated algorithm configuration (a mature field) grounds the contribution, while the LLM instantiation makes it contemporary.
Strengths
Limitations
Overall Assessment
This is a well-executed paper that introduces a clarifying conceptual framework and backs it with both theory and extensive experiments. The main contribution is more in the formalization and systematic evaluation than in any single technical novelty. The empirical results are strong but should be interpreted with the caveat that the benchmarks are designed to be exploitable. The work opens a productive research direction connecting distribution-specific algorithm design with modern program synthesis.
Generated May 15, 2026
Comparison History (20)
Paper 2 addresses a broader societal challenge—democratizing access to Earth science simulation models for climate-vulnerable communities—with demonstrated generalization across 119 models and 14 domains. Its knowledge infrastructure framework is domain-general and tackles both accessibility and integration barriers. Paper 1 is technically strong with rigorous theory and impressive empirical results on combinatorial optimization, but its impact is more specialized. Paper 2's breadth across Earth sciences, equity implications, and potential to create a 'living scientific commons' gives it wider cross-disciplinary impact and real-world relevance.
Paper 1 presents a novel framework combining learning theory with LLM code generation for distribution-aware algorithm design, backed by both theoretical guarantees and strong empirical results across 21 distributions and 7 problem classes. The 100-340x speedups over strong baselines (Gurobi, PACE competition solvers) demonstrate substantial practical impact. The theoretical contributions (generalization bounds for runtime, hint recovery) are rigorous and novel. Paper 2 offers useful interpretability insights and a test-time intervention for reasoning models, but is more incremental—analyzing and patching existing model behaviors rather than introducing a fundamentally new paradigm. Paper 1's breadth across combinatorial optimization and its blend of theory and practice give it higher potential impact.
Paper 2 likely has higher impact: it introduces a broadly applicable learning-theoretic framework for “distribution-aware” synthesis of executable solvers (not just predictors), with generalization guarantees for correctness and runtime plus identifiability of reusable solver hints. The empirical results show dramatic speedups across multiple combinatorial-optimization classes and strong performance on a competitive benchmark, suggesting immediate practical relevance for operations research, systems, and LLM-based code generation. Paper 1 is a valuable biomedical infrastructure resource, but its novelty is more incremental (integration/standardization) and its impact is more domain-specific.
Paper 1 is more likely to have higher scientific impact: it introduces a broadly applicable learning-theoretic framework for distribution-aware synthesis of executable solvers, with provable generalization of both correctness and runtime—an important and under-addressed objective. It also demonstrates large empirical gains across multiple combinatorial optimization classes and competitive performance on real benchmark instances (PACE), indicating near-term practical adoption in operations research, systems, and automated algorithm design. Paper 2 offers strong mechanistic interpretability tools (GAR) and insights, but its immediate real-world leverage is narrower and more diagnostic than transformative.
Paper 2 presents a fundamental breakthrough in AI-driven algorithm design, combining theoretical guarantees with massive empirical speedups (e.g., 342x over Gurobi) on foundational combinatorial optimization problems. While Paper 1 provides a valuable domain-specific benchmark for CAD, Paper 2's methodology and application to ubiquitous NP-hard problems have far broader cross-disciplinary impact, potentially revolutionizing computer science, operations research, and automated software engineering.
Paper 2 introduces a novel theoretical framework (distribution-aware algorithm design with solver hints) backed by strong formal guarantees and impressive empirical results across 21 distributions and 7 problem classes. The 336x speedups and competitive performance on PACE 2025 instances demonstrate substantial practical impact. The work bridges learning theory, algorithm design, and LLM code generation in a principled way with broad applicability to combinatorial optimization. Paper 1 addresses an important safety problem but is narrower in scope (post-execution harm recovery for computer-use agents) with a smaller benchmark and more incremental contributions.
Paper 1 identifies a fundamentally new geometric structure in LLM representations—temporal knowledge drift as an independent axis orthogonal to correctness and uncertainty—which is a profound conceptual discovery. It explains why all existing hallucination/uncertainty detection methods fail at detecting outdated knowledge, opening an entirely new research direction. The rigorous geometric verification across multiple models and the mechanistic insight (stale recall vs confabulation indistinguishability) have broad implications for AI safety, trustworthiness, and deployment. Paper 2 is strong applied work but more incremental in combining LLMs with algorithm design. Paper 1's foundational insight will likely reshape how the field thinks about knowledge representation in LLMs.
Paper 2 likely has higher scientific impact: it introduces a general, distribution-aware framework for synthesizing executable solvers with theoretical generalization guarantees for both correctness and runtime, plus strong empirical results across multiple optimization classes and a notable competition benchmark. Its methodological rigor (formal results + broad experiments) and cross-field applicability (ML, algorithms, OR, systems) suggest wider and longer-lasting influence. Paper 1 is timely and useful as a domain-specific benchmark revealing LLM limitations in molecular simulation workflows, but it is narrower and primarily diagnostic/benchmarking rather than providing a new broadly reusable algorithmic framework.
Paper 1 introduces a novel theoretical framework (solver hints, generalization bounds for runtime and correctness) combined with strong empirical results across 21 distributions and 7 problem classes, achieving orders-of-magnitude speedups over Gurobi and competition solvers. It bridges algorithm design, learning theory, and LLM code generation in a fundamentally new way—learning distribution-aware solver code rather than predictors. Paper 2 is a solid engineering contribution combining DAG-structured tool libraries with co-evolution, but its advances are more incremental within the existing tool-augmented LM paradigm. Paper 1's broader theoretical contributions and practical impact on combinatorial optimization give it higher potential.
Paper 2 has higher potential scientific impact due to its broad applicability across computer science and operations research. While Paper 1 offers a strong, practical framework for e-commerce agent simulation, Paper 2 tackles the fundamental problem of algorithm design for combinatorial optimization. By leveraging LLMs to synthesize distribution-aware solvers, it provides both theoretical guarantees on generalization and runtime, as well as massive empirical speedups over state-of-the-art exact solvers like Gurobi. This bridging of LLM code generation with formal algorithmic theory promises broader cross-disciplinary impact.
Paper 1 presents a novel theoretical and empirical framework for distribution-aware algorithm synthesis using LLMs, with strong formal guarantees (generalization bounds, sample complexity) and impressive empirical results across 21 distributions and 7 problem classes, showing orders-of-magnitude speedups over state-of-the-art solvers. It bridges learning theory, algorithm design, and LLM code generation in a fundamentally new way. Paper 2 applies existing techniques (BERT models, LLMs) to mental health monitoring in a relatively incremental combination, with narrower scope and less methodological novelty.
Paper 2 has higher estimated impact due to a clearer conceptual leap and broader generality: it formalizes distribution-aware learning of executable solver code (not just predictors), with theoretical guarantees for both correctness and runtime generalization, plus empirical validation across many optimization classes and a strong external benchmark (PACE 2025). This spans ML, algorithms, and OR, with immediate real-world applicability where runtime matters. Paper 1 is valuable for bio/PPIs and agentic automation/interpretability, but appears more domain-specific and its agentic framing is less foundational than Paper 2’s unified theory+systems contribution.
Paper 1 introduces a novel framework combining learning theory with LLM code generation for distribution-aware algorithm design, with strong theoretical foundations (generalization bounds, sample complexity) and impressive empirical results across 21 distributions and 7 problem classes. Its breadth of impact spans algorithm design, combinatorial optimization, and AI-assisted programming. The demonstrated orders-of-magnitude speedups over established solvers like Gurobi and competitive PACE results suggest significant real-world utility. Paper 2, while technically sound, addresses a narrower problem in physics-based character animation with more limited cross-domain applicability.
Paper 1 has higher impact potential: it introduces a principled learning-the-solver setting with formal generalization guarantees for both correctness and runtime, plus a reusable “solver hint” abstraction with identifiability/sample-complexity results. Empirically it demonstrates large speedups and strong solution quality across many combinatorial optimization distributions and a real competition benchmark, suggesting broad, practical applicability to operations research and automated algorithm design. Paper 2 offers a valuable interpretability/methodology contribution for agent studies, but its empirical scope is narrow (single task, small N) and results on LLM revision are mixed, limiting near-term cross-field and real-world impact.
Paper 1 presents a novel framework combining learning theory with LLM code generation for distribution-aware algorithm design, backed by both theoretical guarantees and strong empirical results across 21 distributions and 7 problem classes. It demonstrates orders-of-magnitude speedups over state-of-the-art solvers, with practical impact on combinatorial optimization. The theoretical contributions (generalization bounds for runtime and correctness) combined with the practical framework represent a significant advance. Paper 2 offers useful insights about citation faithfulness in GraphRAG but is narrower in scope, primarily an empirical analysis of an existing paradigm rather than introducing a new methodology with broad applicability.
Paper 2 has higher estimated impact: it introduces a concrete, timely paradigm (learning distribution-specialized executable solvers) aligned with current LLM-agent capabilities, with both theory (generalization of correctness and runtime; recoverable hints) and strong empirical validation across many domains plus a notable benchmark result (PACE 2025). Its applications to combinatorial optimization and automated algorithm design are immediate and broad, spanning ML, OR, and systems. Paper 1 is conceptually novel but more meta-theoretical; its real-world leverage and testability are less direct, likely limiting near-term cross-field uptake.
Paper 2 presents a novel and rigorous framework combining theoretical guarantees with strong empirical results, introducing the concept of 'solver hints' that bridge distribution-aware algorithm design with LLM code generation. It demonstrates dramatic speedups (100-300x) with near-optimal quality across 21 distributions and 7 problem classes, with formal generalization bounds. This has broad impact across combinatorial optimization, algorithm design, and AI-assisted programming. Paper 1, while addressing an important topic (privacy in embodied AI), is a position paper proposing a conceptual framework (SPINE) with only preliminary validation, offering less concrete methodological contribution.
Paper 2 presents a fundamentally novel framework combining learning theory with LLM-based code synthesis for algorithm design, backed by strong theoretical guarantees and impressive empirical results (336x speedups, competitive with PACE 2025 solvers). It bridges multiple fields—learning theory, combinatorial optimization, and LLM agents—with clear real-world applications. Paper 1 is a proof-of-concept for prompt annotation optimization with acknowledged limitations and modest contributions. Paper 2's theoretical depth, practical impact, and breadth of applicability give it significantly higher scientific impact potential.
Paper 2 introduces a highly novel framework using LLMs to generate distribution-aware algorithmic solvers, supported by theoretical guarantees and impressive empirical speedups over state-of-the-art solvers like Gurobi. This fundamental innovation in computational optimization has broader applications and deeper methodological rigor compared to Paper 1, which primarily offers an empirical benchmark for existing LLM agents in a specific clinical domain.
Paper 2 has higher likely impact due to a stronger novelty leap and broader relevance: it frames LLM-based solver synthesis as distribution-aware executable code learning with explicit quality–runtime generalization, provides theoretical guarantees (generalization in correctness and runtime; sample complexity for hint recovery), and demonstrates large empirical gains across 21 distributions and seven problem classes plus a notable PACE 2025 result. Paper 1 is a solid systems contribution (multi-agent evolutionary architecture) with good efficiency results, but is more incremental and narrower in conceptual reach and cross-field applicability.