mlsanityData to 14 Oct 2026

Distribution-Aware Algorithm Design with LLM Agents

arXiv 2605.14141 ↗First posted 13 May 2026cs.AIcited by 0

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

Abstract (arXiv)

Many optimization problems are solved repeatedly on instances drawn from the same underlying distribution. In this setting, a system can begin with a general-purpose solver and use experience from previous instances to learn a cheaper way to solve future ones. We formalize this as distribution-aware programming: samples from an unknown deployment distribution are used to produce executable solver code whose quality and runtime generalize to new instances. A simple analysis shows how sample access interpolates between distribution-oblivious and distribution-informed algorithm design, and when the offline cost of specialization is recovered through lower deployment cost. We instantiate this framework with an LLM agent that proposes structural hypotheses, analyzes training instances, and synthesizes specialized solver code; the LLM is used only before deployment. Across (21) structured combinatorial-optimization distributions, the synthesized solvers achieve high quality while often replacing generic search or optimization with smaller distribution-specific computations. Against released PACE competition solvers, our method remains competitive while using substantially less runtime: (75)--(125×) less on PACE 2025 Dominating Set, (80)--(96×) less on Hitting Set, and more than (34,000×) less on the PACE 2024 OCM exact track. More broadly, the results suggest using AI not only to solve optimization problems, but to learn how recurring distributions should be solved.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. Builds on 43 of its 106 references that are in the map. First posted on arXiv 13 May 2026.

Builds on

43 of 106 references.

References · 43

  1. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  2. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  3. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  4. 2022Competition-Level Code Generation with AlphaCodecited by 1,462
  5. 2021Measuring Coding Challenge Competence With APPScited by 902
  6. 2015Pointer Networkscited by 895
  7. 2018Attention, Learn to Solve Routing Problems!cited by 656
  8. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  9. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  10. 2017BranchyNet: Fast Inference via Early Exiting from Deep Neural Networkscited by 596
  11. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  12. 2024BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructionscited by 546
31 more
  1. 2024MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineeringcited by 469
  2. 2023MLAgentBench: Evaluating Language Agents on Machine Learning Experimentationcited by 366
  3. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  4. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 276
  5. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  6. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 268
  7. 2018Competitive caching with machine learned advicecited by 195
  8. 2020Algorithms with Predictionscited by 153
  9. 2016DeepCoder: Learning to Write Programscited by 149
  10. 2017RobustFill: Neural Program Learning under Noisy I/Ocited by 126
  11. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  12. 2015Parallelizing the dual revised simplex methodcited by 89
  13. 2022Self-Supervised Primal-Dual Learning for Constrained Optimizationcited by 61
  14. 2015A PAC Approach to Application-Specific Algorithm Selectioncited by 58
  15. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  16. 2019Learning to Infer Program Sketchescited by 44
  17. 2019Online Mixed-Integer Optimization in Millisecondscited by 38
  18. 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 35
  19. 2023Learning to Warm-Start Fixed-Point Optimization Algorithmscited by 32
  20. 2016Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problemscited by 30
  21. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  22. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  23. 2020Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysiscited by 14
  24. 2023Enabling Research through the SCIP Optimization Suite 8.0cited by 14
  25. 2018LeapsAndBounds: A Method for Approximately Optimal Algorithm Configurationcited by 13
  26. 2018Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphscited by 9
  27. 2019Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configurationcited by 9
  28. 2020Universal Average-Case Optimality of Polyak Momentumcited by 9
  29. 2022Only Tails Matter: Average-Case Universality and Robustness in the Convex Regimecited by 7
  30. 2020Average-case Acceleration for Bilinear Games and Normal Matricescited by 5
  31. 2020A Generalization of Self-Improving Algorithmscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization
  2. 2026Rethinking LLM-Driven Heuristic Design: Generating Efficient and Specialized Solvers via Dynamics-Aware Optimization
  3. 2026Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits
  4. 2026FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization
  5. 2025HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization
  6. 2026ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization
  7. 2025Toward a Trustworthy Optimization Modeling Agent via Verifiable Synthetic Data Generation
  8. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization