PaperlayerView exact revision on arXiv

Source-linked AI summary

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

David A. Bader, Adil Chhabra, Ernestine Großmann, Monika Henzinger, Alexander Noe, Christian Schulz

arXiv:2609.07204v1cs.AI

TL;DR

The paper addresses how to further improve shared-memory exact minimum-cut algorithms after extensive manual optimization. It introduces agentic algorithm engineering, in which autonomous LLM agents iteratively modify and benchmark an existing code base. The resulting accepted changes produce substantial speedups, especially on DIMACS core instances, while evaluation remains tied to the workload used for tuning.

  • Problem

    Exact minimum-cut algorithms are important for large graph applications, but the fastest practical solvers have nonlinear running time and do not parallelize easily.

  • Method

    Agentic algorithm engineering has an autonomous LLM inspect code, form hypotheses, implement candidate optimizations, benchmark fixed instances, and retain or discard changes.

  • Results

    The accepted changes reduce geometric-mean running time by a factor of 3.44 on one thread and 21.49 at 32 threads over the applicable reported instances.

  • Takeaways & Limitations

    AAE can further optimize an extensively hand-tuned exact minimum-cut implementation, with especially large gains on DIMACS core instances.

  • Takeaways & Limitations

    The reported thresholds were fitted on the same 53 instances used for evaluation, so performance on held-out workloads remains to be evaluated.

Abstract

from arXiv · show

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model 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 instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.

1 Introduction

Minimum cut is a practically important graph problem whose exact algorithms can be difficult to parallelize. The paper introduces agentic algorithm engineering and applies it to an already optimized exact solver, obtaining substantial additional speedups.

  • Problem: Minimum cut partitions graph vertices into two nonempty sets while minimizing the total weight of crossing edges.Its value is also called the graph's edge connectivity.
  • Problem: Minimum cuts support network reliability, VLSI design, and branch-and-cut algorithms for the traveling salesman problem.These applications require fast computation on large inputs.
  • Motivation: Exact minimum-cut algorithms have nonlinear running time, while the fastest practical solvers do not parallelize easily.This motivates improving shared-memory exact algorithms.
  • Contribution: Agentic algorithm engineering uses autonomous LLM agents to inspect code, hypothesize optimizations, modify the implementation, benchmark a fixed instance set, and retain successful changes.Unlike classical auto-tuning, the agent changes the code itself rather than selecting among fixed parameter values.
  • Results: Factors of 1.28 sequentially and 1.63 at 32 threads were achieved on real-world k-cores, versus 6.26 and 127 on DIMACS core instances.These results come from applying the agent to the exact algorithm on the reported challenge and original-publication instances.

2 Preliminaries

The exact VieCut algorithm combines a heuristic upper bound, contraction-based reductions, bounded priority queues, and parallel traversal and contraction. These components use the bound to identify safe contractions and shrink the graph efficiently.

  • Exact algorithm: The algorithm is based on Nagamochi et al.'s contraction-based exact method, using CAPFOREST to compute edge lower bounds q(e).An edge with q(e) ≥ ˆλ can be safely contracted, and at least one such edge is found per run.
  • Lowering the upper bound: A heuristic first obtains a valid upper bound ˆλ, allowing more edges to be contracted when the bound is smaller.Faster shrinking reduces the number of CAPFOREST runs.
  • Bounded priority queues: CAPFOREST priorities can be limited to ˆλ, enabling bucket priority queues with FIFO or LIFO order alongside a binary heap.The bounded priorities preserve correctness while changing the queue implementation.
  • Parallelization: Parallel CAPFOREST assigns each vertex to one process while retaining coverage of vertices in sparse graph regions.The resulting q(e) values remain valid lower bounds for safe contraction.
  • Overall algorithm: The complete algorithm alternates parallel CAPFOREST and graph contraction until two vertices remain, updating ˆλ when a collapsed vertex has smaller degree.If no contractible edge is found, CAPFOREST is rerun sequentially.

3 Agentic Algorithm Engineering

Agentic algorithm engineering turns algorithm engineering into an autonomous, measurement-driven loop over a modifiable code base. The agent forms falsifiable hypotheses, tests isolated changes, records outcomes, and builds on accepted improvements.

  • Algorithm engineering: Algorithm engineering cycles through design, analysis, implementation, and experimental evaluation using realistic machines and inputs.Experimental outcomes guide subsequent design decisions.
  • AAE overview: AAE gives an autonomous LLM agent a target program, optimization metric, reproducible benchmark, and per-experiment time budget.The first experiment establishes a baseline, and later results are measured relative to it.
  • Cycle: Each iteration maintains a performance model, states a falsifiable one-change hypothesis, predicts its effect, and evaluates the implementation experimentally.The agent updates its model when measurements contradict its expectations.
  • Bookkeeping: Every experiment, including failures, is logged with its commit hash, metric value, resource usage, decision, and motivating hypothesis.The sessions in this paper began from the code base without a curated list of optimization ideas or the community knowledge base.
  • Scope: In this paper, AAE optimizes running time, but the framework can also target heuristic solution quality or memory footprint.The metric is therefore determined by the optimization task rather than fixed by the methodology.

4 Experiments and Results

The experiments evaluate AAE optimizations of VieCut on 53 instances under controlled hardware and acceptance criteria requiring faster geometric mean runtime, completion, and identical cuts. The accepted changes substantially improve performance, especially on DIMACS core instances, while targeting memory use, contraction, traversal, and data structures.

  • Experimental setup: 53 instances were benchmarked on a single-NUMA AMD EPYC 7702P machine, with 44 experiments run across single-threaded and 32-thread sessions.Experiments used C++ with g++ 13.3, -O3 -march=native, and OpenMP; 23 changes were accepted only when the geometric mean improved, all instances completed, and cuts matched the baseline.
  • Optimization targets: The exact algorithm’s hottest path is CAPFOREST’s inner loop, which scans every directed edge once per contraction round.Rounds cost Θ(n + m), and DIMACS core instances resist contraction, making per-round costs especially consequential.
  • Overall results: Overall, runtime fell from 25.0 s to 7.28 s sequentially and from 23.0 s to 1.07 s on 49 common instances at 32 threads.These correspond to factors of 3.44 and 21.49; the accepted changes reduced peak memory from 492 GiB to 193 GiB, while real-world k-cores improved by 1.28 and 1.63 and DIMACS core instances by 6.26 and 127.
  • Single-threaded session: 1.544 speedup came from selecting a binary heap when the cut value exceeds the graph size and 10 000, avoiding queues sized by enormous cut values.On one weighted instance, runtime fell from 215 s to 3.5 s and memory from 202 GiB to 2.2 GiB.
  • Single-threaded session: 1.277 and 1.216 speedups came from contracting in place in the sequential and parallel exact loops, eliminating repeated graph reconstruction and retained intermediate graphs.Additional inner-loop changes included byte flags, fewer queue-position lookups, one adjacency-vector resolution per edge list, and omitted unused allocations.
  • Parallel session: At 32 threads, partitioning contraction by contracted vertex removed duplicate-edge hashing and critical-section serialization, yielding a 1.294 speedup.The optimization assigns neighbor lists to threads and sums parallel edges in thread-private dense arrays when groups are comparable in size.

5 Discussion

The paper introduces agentic algorithm engineering for optimizing an extensively hand-tuned exact minimum cut implementation. Its accepted changes improve performance beyond the original design envelope while preserving correctness through assertions and whole-instance-set evaluation.

  • 5 Discussion: AAE runs autonomous LLM agents through hypothesis formation, implementation, benchmarking, and selective retention of optimizations on an existing code base.Accepted changes become the starting point for subsequent rounds, while rejected changes and their failure reasons are discarded.
  • 5 Discussion: The agent did not invent a new algorithm; it combined adaptations to violated tuning assumptions, standard performance engineering, and alternative execution decisions.One example is probing whether parallel passes share the visited array.
  • 5 Discussion: Correctness assertions, geometric-mean performance over the full instance set, and human review constrain the optimization process.The paper reports that optimizing runtime alone can produce fast but incorrect code or changes that help one instance while slowing the set.

A Detailed Related Work

Exact minimum cut algorithms include flow-based and contraction-based approaches, while recent near-linear theoretical algorithms largely lack practical implementations. Existing work also leaves distributed and GPU implementations largely unavailable.

  • A Detailed Related Work: Flow-based algorithms derive global minimum cuts from repeated maximum-flow computations, while contraction-based methods shrink graphs while preserving at least one minimum cut.The flow-based line includes push-relabel adaptations, whereas contraction-based work uses local tests or randomized contractions.
  • A Detailed Related Work: Recent theoretical results achieve near-linear randomized or deterministic bounds for minimum cut, including weighted and parallel settings.The cited approaches include improved randomized bounds, random 2-out contractions, isolating cuts, deterministic algorithms, and a parallel algorithm with polylogarithmic depth.
  • A Detailed Related Work: None of these recently described algorithms has been implemented, so their practical performance remains unknown.The paper also states that only one distributed implementation was known and that no GPU implementation existed.

B Pseudocode

The paper presents pseudocode for parallel CAPFOREST and the overall exact minimum cut algorithm. The overall routine obtains an upper bound, repeatedly identifies contractible edges and contracts the graph, and finishes when two vertices remain.

  • B Pseudocode: The pseudocode routines are taken from the original exact algorithm, whose correctness proofs appear in the earlier paper.The present paper summarizes these routines to make the algorithm self-contained.
  • B Pseudocode: Parallel CAPFOREST takes a graph, an upper bound ˆλ, and a shared vertex-visit array, returning a union-find structure marking contractible edges.The routine initializes visits, edge values, a blacklist, and a priority queue before traversing vertices.
  • B Pseudocode: During traversal, CAPFOREST updates connectivity-related values and unions an edge when its endpoint value crosses the current upper-bound threshold.The pseudocode tests whether r(y) < ˆλ ≤ r(y) + c(e) before marking an edge for contraction.
  • B Pseudocode: The overall algorithm initializes ˆλ with VieCut, alternates parallel CAPFOREST with parallel graph contraction, and falls back to sequential CAPFOREST when no contractible edge is found.It returns ˆλ after the contracted graph has been reduced to two vertices.

C Instance Set

The evaluation uses generated graph families, DIMACS core instances, and real-world web and social k-cores. The instance table reports each graph’s size and minimum cut value.

  • C Instance Set: The instance set combines generated families with DIMACS core instances and k-cores of real-world web and social graphs.This collection supplies the graph families used for evaluation.
  • C Instance Set: For every evaluated instance, the table records its size and minimum cut λ.The listed size and λ characterize each graph in the benchmark set.

Generated Families: The DIMACS Core Instances

The evaluation uses generated graph families designed to expose weaknesses in contraction-based minimum-cut algorithms. Instance sizes are extended until runtime reaches seconds to minutes, but memory limits the largest cases.

  • Seven generator families reimplement prior problem families, including cycles, heavy-component graphs, random graphs, and Padberg–Rinaldi constructions.
  • Memory, rather than runtime, limits scaling: retained contracted graphs require Θ(n · m) for low-cut families, while pr2’s priority queue grows with its cut value.The stated limits include n = 12 800 for reg2, n = 64 000 for irreg, and 8 000 vertices for pr2.
  • Bicycle wheels and interleaved cycles are adversarial because they remove cheap contraction opportunities and cause contraction-based algorithms to degrade.Bicycle wheels have n equal-valued trivial cuts; interleaved cycles hide one cut of 2000 among Θ(n2) cuts of value 2006.
  • Minimum-cut values were independently cross-checked against implementations, with all instances agreeing with the predicted values.The checks used VieCut’s Nagamochi–Ibaraki code and either Stoer–Wagner or the parallel exact algorithm, depending on instance size.

Real-World Graphs

The real-world evaluation uses k-cores from web and social graphs, selecting connected components whose minimum cut differs from the minimum degree. These graphs are much larger than the generated DIMACS core instances yet are solved faster through aggressive contraction.

  • The real-world set consists of four k-cores from each web and social graph, using the largest connected component after excluding cases where minimum cut equals minimum degree.
  • The selected graphs reach 68 141 228 vertices and 3 134 185 720 edges, exceeding the size of the DIMACS core instances.
  • Table 1 reports vertices, edges, and minimum-cut value λ for each instance, distinguishing generated DIMACS cores from real-world k-cores.
Loading 2609.07204v1…