Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
David A. Bader, Adil Chhabra, Ernestine Großmann, Monika Henzinger, Alexander Noe, Christian Schulz
cs.AI · cs.DC · cs.DS
Quick verdict
Introduces agentic algorithm engineering: an LLM agent speeds a hand-tuned exact min-cut solver 3.4-21.5x; candid limits, but timings are single-run.
Summary
The paper introduces agentic algorithm engineering (AAE), a methodology in which an autonomous LLM agent runs the full algorithm-engineering cycle on an existing code base: it inspects code and profiling data, forms falsifiable hypotheses about where runtime is lost, implements one change per git commit, benchmarks on a fixed 53-instance set, and keeps or discards each change. The authors apply AAE, using Claude Opus 5, to their own extensively hand-tuned shared-memory exact minimum cut algorithm (VieCut). Across two sessions (1 and 32 threads) comprising 44 experiments, 23 changes were accepted at about $350 of API cost. Geometric-mean runtime over all 53 instances falls from 25.0 s to 7.28 s (3.44x) on one thread and from 23.0 s to 1.07 s (21.49x) at 32 threads over the 49 instances both configurations solve; the optimized code also solves 4 DIMACS core instances the baseline cannot. Split by workload, gains are 1.28x/1.63x on the 20 real-world k-cores and 6.26x/127x on the 33 DIMACS core instances. The largest wins remove asymptotic bottlenecks: cut-sized bucket queues replaced by heaps, in-place graph contraction, and repartitioned parallel contraction. Main limitations: timings are single runs without variance estimates, thresholds were fitted on the same instances used for reporting, and generalization to held-out workloads remains untested.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Agentic algorithm engineering lets an autonomous LLM agent (Claude Opus 5) run the complete algorithm engineering cycle on an existing code base under correctness assertions, a fixed benchmark, and immutable measurement rules.
- Applied to the authors' hand-tuned exact minimum cut algorithm, the agent produced 23 accepted changes across 44 experiments for about $350, cutting geometric-mean runtime from 25.0 s to 7.28 s (3.44x) on one thread and from 23.0 s to 1.07 s (21.49x) at 32 threads over the 49 commonly solved instances.
- On the workload split, the accepted changes yield factors of 1.28x (1 thread) and 1.63x (32 threads) on 20 real-world k-cores and 6.26x and 127x on the 33 DIMACS core instances, and make 4 previously unsolvable instances solvable.
- The largest gains remove asymptotic bottlenecks that the original hand tuning implicitly assumed away (bucket queues sized by the cut value, per-round graph rebuilds), rather than fitting constants to the benchmark.
Strengths
Unusually rigorous experiment hygiene
The first experiment is always the baseline (Section 3), every experiment is exactly one git commit, a ledger records hypothesis/metric/resources/decision for all 44 experiments including 21 rejections, acceptance requires identical cuts and completion on all 53 instances, and a human read all 23 accepted diffs (Section 4.1, Correctness).
Honest scoping of the tuning-vs-generalization question
Section 1 and Section 4.1 (Tuning and the instance set) state explicitly that the agent tunes on the same 53 instances the speedups are reported on, that held-out generalization remains to be evaluated, and that the research question is workload tuning — not universal speedups.
Large, fully decomposed and cross-checked effects
Reproducible instance specification
Candid cost and failure accounting
Weaknesses
Single timing per instance, no variance reporting
All headline numbers are in-tuning-set measurements
No external baselines in this paper
Instance set depends on unpublished reimplemented generators
No ablation of the methodology itself
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper makes three contributions: a self-contained summary of the authors' prior shared-memory exact minimum cut algorithm (Section 2.1, Algorithms 1-2 — all prior work); a new methodology, agentic algorithm engineering (AAE, Section 3), in which an autonomous LLM agent runs the algorithm engineering cycle — falsifiable hypothesis, one-commit implementation, benchmark on a fixed instance set, keep or discard — under correctness assertions and immutable measurement rules; and an empirical demonstration applying Claude Opus 5 to the authors' own extensively hand-tuned VieCut implementation (Section 4). Headline claims: geometric-mean runtime over the 53-instance benchmark drops from 25.0 s to 7.28 s (3.44x) on one thread, and from 23.0 s to 1.07 s (21.49x) at 32 threads over the 49 instances both configurations solve; workload-split factors are 1.28x/1.63x (1/32 threads) on the 20 real-world k-cores and 6.26x/127x on the 33 DIMACS core instances; 4 DIMACS instances the baseline cannot solve at 32 threads become solvable. Agent cost: about $350 (1.1M output tokens).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is agentic algorithm engineering (AAE)?
A methodology introduced in this paper in which an autonomous LLM agent (here Claude Opus 5) runs the full algorithm-engineering cycle on an existing code base: it inspects the code and profiling data, forms falsifiable hypotheses about where runtime is lost, implements one change per git commit, benchmarks on a fixed instance set, and keeps improvements while discarding regressions — all under correctness assertions and fixed measurement rules the agent may not change.
How much faster did the LLM agent make the minimum cut code?
On the paper's 53-instance benchmark, geometric-mean runtime fell from 25.0 s to 7.28 s (3.44x) on one thread and from 23.0 s to 1.07 s (21.49x) at 32 threads, counting the 49 instances both versions solve. On the 20 real-world k-cores the gains are 1.28x (1 thread) and 1.63x (32 threads); on the 33 DIMACS core instances they are 6.26x and 127x. Four instances the baseline could not solve within two hours became solvable, and peak memory dropped from 492 GiB to 193 GiB.
Did the AI agent invent a new minimum cut algorithm?
No. The authors state explicitly that the agent did not invent a new algorithm and that correctness assertions pin its output to the baseline's cut values. The gains come from removing asymptotic bottlenecks (e.g., priority queues sized by the cut value, per-round graph rebuilds, serialized contraction) and standard performance engineering, with a human reviewing every accepted change.
What did running the optimization agent cost?
About $350 in API usage (1.1 million output tokens) across two sessions totaling 44 experiments, of which 23 changes were accepted and 21 discarded. The wall-clock bottleneck was benchmark evaluation over the 53 instances, not the agent's reasoning or implementation time.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure 1 appears in the extracted text only as its caption and axis labels; the plotted per-instance data points cannot be verified from the extraction, so per-instance claims rely on the reported text and Table 1.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.