Reproduce “Budget-Efficient Automatic Algorithm Design via Code Graph” on OpenResearch

About this paper

Maxime Bouscary, Manxi Wu, Saurabh Amin

Researchers from MIT and UC Berkeley developed a graph-based framework for Automatic Algorithm Design (AAD) that queries Large Language Models (LLMs) for concise code corrections rather than full algorithms. This method enhances budget efficiency and consistently outperforms full-algorithm generation, achieving up to a 22.3% smaller optimality gap for the Traveling Salesman Problem (TSP) at equal token budgets.

Key insights

• Decomposing algorithms into reusable "corrections" within a graph structure dramatically increases the yield of accessible algorithms per LLM query, making AAD more budget-efficient.
• Explicit, correction-level credit assignment, facilitated by the graph representation, provides granular and interpretable feedback to LLMs, guiding the search more effectively toward high-impact features.
• Optimal budget allocation for AAD under cost constraints involves a dynamic balance between search depth (per-run budget) and breadth (number of runs), with increasing total budget favoring deeper exploration.
• The utility of providing explicit search context to LLMs is nuanced; it benefits problems where the LLM's prior knowledge is limited but can be counterproductive for well-known domains like TSP.

Summary by alphaXiv.