Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

Computing a minimum $s$-$t$ cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, we revisit the BK algorithm from both a theoretical and practical point of view. We improve the analysis of the time complexity of the BK algorithm to $O(mn|C|)$ and propose a new algorithm, the fast and compact BK (fcBK) algorithm, with a time complexity of $O(m|C|)$, where $m$, $n$, and $|C|$ are the number of edges, number of vertices, and the capacity of the cut, respectively. We additionally propose a compact graph representation that allows our implementation to find a minimum $s$-$t$ cut in a graph with upwards of $10^9$ vertices and $10^{10}$ edges on a machine with 128 GB of memory. We find our implementation of the BK algorithm to be the fastest available implementation of the BK algorithm when evaluating on a comprehensive set of benchmark datasets, highlighting the importance of memory-efficient implementations. We make our implementations publicly available for further research and implementation development within minimum $s$-$t$ cut algorithms.

Large language models (LLMs) have emerged as powerful tools for automatic algorithm design (AAD). However, existing pipelines remain inefficient. They operate at the granularity of full algorithms, redundantly rewriting recurring substructures and discarding low-fitness candidates that may contain valuable algorithmic features. We formalize budget-efficient automatic algorithm design, wherein the search policy maximizes realized fitness subject to limited computational cost. We propose a directed acyclic graph representation of algorithms and build a search framework that fully exploits the LLM's output. Instead of querying the LLM for full algorithms, we use it to obtain corrections: compact operators that add, replace, or remove code blocks. Each correction augments the graph, yielding new algorithms that compose with prior corrections. This graph structure decomposes algorithms into sets of corrections, enabling correction-level credit assignment that informs subsequent queries. We complement this framework with theoretical insights into the ideal balance between search depth and breadth at different budget levels. We validate our method empirically on three combinatorial optimization problems, demonstrating consistent superiority of our graph-based search over full-algorithm search at equal token budget. Finally, our experiments suggest that rich contexts help only when the LLM's prior knowledge is shallow, and can hinder performance otherwise.

Many optimization problems arise repeatedly from a fixed but unknown distribution. Even when the worst-case problem is hard, this distribution may carry reusable structure, such as recurring geometry, decompositions, or resource patterns. We study how to infer such structure from sample instances and compile it into solver code that runs faster on future instances while preserving solution quality. Our central abstraction is a \emph{solver hint}: distribution-specific structure inferred from samples and used to specialize a solver. We prove that the empirically fastest sample-consistent solver generalizes in both correctness and runtime over fixed solver libraries, and that identifiable hints can be recovered from polynomially many samples. We instantiate the framework with LLM code agents on $21$ combinatorial-optimization distributions across $7$ problem classes. The synthesized solvers reach mean normalized quality $0.971$ while running orders of magnitude faster than classical heuristics, Gurobi, and time-limited exact backends, though they do not dominate every baseline on every family. Against LLM synthesis baselines, they are faster than one-shot Codex, one-shot Claude Code, and a best-of-$5$ open-model variant; they improve quality over Claude Code and best-of-$5$, while nearly matching Codex quality and running substantially faster. This isolates the contribution of the iterative synthesis loop without claiming uniform domination over every LLM baseline. On the PACE 2025 Dominating Set private instances, the synthesized solver is valid on all $100$ graphs and runs roughly $75\times$--$125\times$ faster than released competition solvers, within a few percent of their solution size. These results suggest LLM agents can discover distribution-specific computational shortcuts and compile them into efficient solver code.