Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

Autonomous LLM agents optimize a state-of-the-art exact min-cut solver, achieving up to 127\times speedups on DIMACS core instances

David A. Bader; Adil Chhabra; Ernestine Großmann; Monika Henzinger; Alexander Noe; Christian Schulz· 2026· DOI 10.48550/arXiv.2609.07204

The core problem

The minimum cut problem for an undirected edge-weighted graph seeks to partition the node set into two blocks while minimizing the weighted sum of edges crossing the cut. Formally, given a graph G = (V, E) with edge weights w : E \to R^{+}, the minimum cut is: S \subset V min e \in δ (S) \sum w (e) where δ (S) is the set of edges with exactly one endpoint in S . This fundamental problem has applications in network reliability, clustering, and image segmentation. Over recent years, the authors have engineered a range of fast algorithms for this problem, culminating in an exact algorithm available in the open-source package VieCut. On real-world instances, VieCut outperformed previously fastest solvers by factors up to 2.5 sequentially and up to 12.9 in parallel. Despite extensive manual tuning, the authors hypothesize that further optimizations remain undiscovered. This paper introduces agentic algorithm engineering (AAE), a methodology where autonomous large language model (LLM) agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed ins

The AAE process discovered significant optimizations in the VieCut algorithm, despite extensive prior manual tuning. The improvements are quantified as speedup factors relative to the original algorithm. On real-world k-cores, the agent achieved speedups of 1.28\times sequentially and 1.63\times with 32 threads. On the DIMACS core instances, the speedups were substantially larger: 6.26\times sequentially and 127\times with 32 threads. These results are summarized in the following table: | Instance Type | Sequential Speedup | 32-Thread Speedup | |---------------|-------------------|-------------------| | Real-world k-cores | 1.28\times | 1.63\times | | DIMACS core instances | 6.26\times | 127\times | The DIMACS core instances are particularly challenging and are often used as a benchmark for minimum cut algorithms. The 127\times speedup with 32 threads indicates that the agent found optimizations that greatly enhance parallel scalability. The sequential speedup of 6.26\times on these instances is also remarkable, given that the original algorithm was already highly optimized. The agent's changes likely involve improvements to data structures, parallel contraction routines, or the bound-based reductions. The exact nature of the op

The minimum cut problem for an undirected edge-weighted graph seeks to partition the node set into two blocks while minimizing the weighted sum of edges crossing the cut. Formally, given a graph G = (V, E) with edge weights w : E \to R^{+}, the minimum cut is:

S \subset V min e \in δ (S) \sum w (e)

The results demonstrate that agentic algorithm engineering can yield substantial improvements even for highly tuned algorithms. The speedups on DIMACS core instances are particularly striking, suggesting that the agent discovered non-obvious optimizations that human engineers had missed. The larger speedups in parallel settings indicate that the agent may have improved load balancing, reduced synchronization overhead, or enhanced parallel contraction routines. The AAE methodology is general and could be applied to other algorithms and domains. However, several questions remain: How does the agent generate hypotheses? What is the role of the LLM's training data? How transferable are the optimizations to other instances? The authors introduce AAE as a methodology, and this work serves as a proof of concept. Future work could explore the integration of AAE into standard algorithm engineering workflows, the development of better prompting strategies, and the application to other problem domains. The open-source nature of VieCut facilitates reproducibility and further experimentation. The paper's findings suggest that LLM agents can augment human expertise in algorithm engineering, potentially accelerating the development of high-performance algorithms.

CS practitioners and researchers

Opening member content…