aiqbench analysis
This research introduces "distribution-aware programming," a framework where LLMs synthesize specialized solvers for recurring optimization problems before deployment. The approach significantly reduces runtime on specific combinatorial tasks by replacing generic search with distribution-specific computations, demonstrating that AI can learn efficient algorithmic strategies rather than just solving individual instances.
Distribution-Aware Programming: Learning Specialized Solvers from Experience
arXiv:2605.14141v3 Announce Type: replace Abstract: 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 \emph{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\times\) less on PACE 2025 Dominating Set, \(80\)--\(96\times\) less on Hitting Set, and more than \(34{,}000\times\) 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.
Abstract: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 \emph{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\times\) less on PACE 2025 Dominating Set, \(80\)--\(96\times\) less on Hitting Set, and more than \(34{,}000\times\) 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.
Artificial Intelligence (cs.AI)
arXiv:2605.14141 [cs.AI]
(or arXiv:2605.14141v3 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2605.14141 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 295 words
