acceptodds
Under review as a conference paper at ICLR 2027

EvoPart: An Open, Lightweight, and Strong Hypergraph Partitioner Evolved with LLM Coder

Abstract

Hypergraph partitioning is a fundamental NP-hard problem in VLSI physical design, scientific computing and, increasingly, LLM infrastructure. Yet the field lacks an open partitioner that is at once lightweight, strong and fast: the most influential tool, hMETIS, is closed-source, and the leading open framework, KaHyPar, spans some 27,000 lines of C++, so recent work typically wraps hMETIS as a black box or replaces a single sub-step of KaHyPar. Coding agents such as AlphaEvolve and its open-source counterpart OpenEvolve offer a way forward, having already found better programs for problems including matrix multiplication. Building on OpenEvolve, we design a harness for evolving a whole solver rather than a single heuristic: it places programs in the MAP-Elites grid by behavior (running time and relative strength across k) rather than text, deduplicates programs by partition fingerprinting, and feeds the measured per-instance cut and wall time back into the prompt. Starting from a round-robin initial program whose cut is 97× KaHyPar's, a single 200-iteration run yields EvoPart: a lightweight and strong partitioner of 1,186 lines of single-threaded C++ in one file, 22.5× less code than KaHyPar. On the full ISPD98 and Titan23 benchmarks, its cut is 5.5% lower than KaHyPar's in 70% of KaHyPar's wall time and 5.1% lower than hMETIS's at equal wall time, with 30 of the 40 instances unseen during evolution. Two of its components are, to our knowledge, absent from existing partitioners: racing two coarsenings with opposite net-size priorities inside the restarts, and re-partitioning the final blocks pair by pair. We release the partitioner and the harness at https://anonymous.4open.science/r/EvoPart-4F6C.

Primary area:
optimization
Keywords:
hypergraph partitioning, physical design, electronic design automation, LLM-driven program evolution, automatic heuristic design, combinatorial optimization, OpenEvolve

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kaswOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the hypergraph partitioning problem. In this paper, the authors design a harness to generate the hypergraph partitioner, including placing the programs in the MAP-Elites grid by behavior and feeding the measured data into the LLM prompt. Then, the authors propose EvoPart, a lightweight partitioner which is better than KaHypar.

Critical strengths

S1. Using the harness to address the hypergraph partitioning problem is interesting.

S2. This paper is well-motivated.

S3. The harness pipeline is described in detail.

Critical weaknesses

W1. The reason why the authors use KaHyPar in harnessing could be more explained more clearly.

W2. Harness may lead to a better hypergraph partitioning algorithm. However, harnessing incurs high runtime and memory cost.

Questions for authors

Q1. In this paper, the harness process focuses on KaHypar. Since more recent hypergraph partitioning algorithms (e.g., SIGHP [1]) have been proposed, could the authors discuss whether and how harnessing could be applied to this method?

Q2. Could the authors provide a discussion of the trade-off mentioned in W2?

[1] Guan et al. SIGHP: Scalable Information-Guided Hypergraph Partitioner. KDD 2026

2 comments

We sincerely thank the reviewer for the positive assessment. We are glad that you found the use of a harness for hypergraph partitioning interesting, the paper well motivated, and the pipeline described in detail.

Your questions on the role of KaHyPar and on the cost of the harness helped us make both points explicit in the paper. Our detailed responses follow.


W1. The reason why the authors use KaHyPar in harnessing could be more explained more clearly.

Authors' answer: KaHyPar serves only as a reference. The score is computed from the ratio of a candidate's cut and running time to KaHyPar's on the same training instance. The model cannot see KaHyPar's code and cannot run it; the evolution starts from a program that assigns vertices round-robin. We chose KaHyPar because it is the most widely used open-source single-threaded partitioner, so "lower cut, less time, less code" has a clear meaning against it. In principle, any other partitioner could take this role.

Authors' action: We added this explanation to the description of the score in Section 3.


W2. Harness may lead to a better hypergraph partitioning algorithm. However, harnessing incurs high runtime and memory cost.

Q2. Could the authors provide a discussion of the trade-off mentioned in W2?

Authors' answer: Two costs should be separated. EvoPart itself is a single-threaded C++ program that calls no LLM when it is used; its running time and memory are those of a partitioner, as reported in the paper. The cost of the evolution is paid once. The reported run took 8.7 hours of wall time, including the evaluation of all candidates with four workers in parallel, and about 150 USD of API calls (4.4 million input and 0.9 million output tokens). Its memory cost is not significant: the harness only compiles and runs the candidate partitioner on the training instances, and its peak memory was about 5 GB.

The trade-off is therefore as follows. For the standard hypergraph partitioning problem, EvoPart can be used directly and no further evolution is needed. Only when the objective or the constraints change does the harness have to be adapted and run again, at the one-time cost above, in return for a solver tailored to the new problem. This is why we release both the partitioner and the harness.

Authors' action: We report the cost of the evolution runs (tokens, wall time) in Table 15 in the appendix and added a discussion of this trade-off there.


Q1. In this paper, the harness process focuses on KaHypar. Since more recent hypergraph partitioning algorithms (e.g., SIGHP [1]) have been proposed, could the authors discuss whether and how harnessing could be applied to this method?

Authors' answer: Yes, in two ways. First, as the reference: the harness needs only the objective value and running time of the reference partitioner on each training instance, so KaHyPar can be replaced by other recent hypergraph partitioners such as SIGHP. Second, as the starting point: the evolution could start from an implementation of an existing partitioner such as SIGHP, instead of the round-robin program. In both cases, the prompt, the score and the training set should follow the target method: SIGHP minimizes the (k−1) metric on large real-world hypergraphs for distributed processing, whereas this paper uses the cut-net metric on VLSI benchmarks.

Authors' action: We added this discussion to Appendix G.

Thank you for your response. My concerns are addressed. I choose to maintain my positive score.

Reviewer_iZSxOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The authors use LLM code evolution to produce a complete hypergraph partitioner: starting from a ~100-line round-robin program, an OpenEvolve-based harness — modified with behavioral MAP-Elites descriptors and partition-fingerprint deduplication — evolves a 1,186-line single-file C++ partitioner. On ISPD98 + Titan23 it reportedly improves cut over both KaHyPar (-5.5%) and hMETIS (-5.1%), with 30 of 40 benchmark instances held out from the evolution loop entirely.

Critical strengths

This is one of the more convincing demonstrations that LLM code evolution can yield an entire competitive solver rather than a short heuristic inside a fixed skeleton. The evaluation hygiene is better than usual for this line of work: a large held-out set where the improvement essentially replicates, generalization to unseen k in {5,...,8}, and a direct three-run ablation showing the behavioral descriptors beat OpenEvolve's default text features.

The artifact itself is a real community asset — a readable, single-file, open partitioner competitive with a ~27k-line framework — and the evolved components (the coarsening tournament, pair sweeps) come with ablations and look transferable to handwritten partitioners.

Critical weaknesses

The baseline set has notable gaps for a paper claiming a "strong" partitioner: SpecPart/K-SpecPart, which the paper itself cites as having improved on hMETIS, are never compared against; neither are PaToH, Mt-KaHyPar, or any higher-quality KaHyPar preset (only the sea20 cut configuration). The quality-time claims are also muddied — KaHyPar appears unusually slow on Titan23, while on ISPD98 with k=3/4 EvoPart is actually about 3x slower.

Second, everything rests on a single 200-iteration evolution run, and the cost of that run (API tokens, wall-clock hours) is never reported; the harness ablation is three runs without statistics. It is hard to judge whether the final program is typical or a lucky sample, and whether the pipeline is reproducible for groups without a large API budget.

Questions for authors
  1. What did the reported evolution run cost (tokens/USD, wall time), and how many full runs were performed in total? How much does the final program's cut quality vary across runs?
  2. How does EvoPart rank against SpecPart/K-SpecPart and a higher-quality KaHyPar preset? Could you also report the connectivity (λ-1) metric and results at other imbalance factors?
  3. How is EvoPart's instance-adaptive time budget set, and do the headline margins survive an explicitly equal-time comparison?
3 comments

We sincerely thank the reviewer for the positive and careful assessment. We are glad that you see the paper as a convincing demonstration that LLM code evolution can yield an entire competitive solver, and that you value the held-out evaluation and the released single-file partitioner.

Your questions on baselines, running time and reproducibility were precise and helped us strengthen the paper. In response, we added three baselines, a comparison at equal wall time, the connectivity metric, results under a looser balance constraint, and two further evolution runs together with their cost. We hope that these additions address your concerns, and we would be grateful if you would take them into account in your final assessment. Our detailed responses follow.


W1 (a). The baseline set has notable gaps for a paper claiming a "strong" partitioner: SpecPart/K-SpecPart, which the paper itself cites as having improved on hMETIS, are never compared against; neither are PaToH, Mt-KaHyPar, or any higher-quality KaHyPar preset (only the sea20 cut configuration).

Authors' answer: We added Mt-KaHyPar (highest-quality preset), PaToH (quality preset) and K-SpecPart as baselines. All systems run single-threaded on the same machine under the setting of the main experiments. The two tables below extend Tables 2 and 3 of the paper: cut size and wall time are normalized to KaHyPar (= 1.00), as geometric means of per-instance ratios; lower is better.

R2-Table: ISPD98 (18 instances, 3 seeds).

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS0.9941.0072.331.0051.0201.950.9931.0051.85
Mt-KaHyPar1.0040.9931.051.0241.0211.111.0071.0061.08
PaToH1.0371.0150.381.0901.0720.401.0681.0610.41
K-SpecPart0.9780.98346.50.9840.99632.70.9790.99235.0
EvoPart0.9920.9930.880.9991.0082.930.9860.9982.94

R2-Table: Titan23 (22 instances, 3 seeds).

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS1.0051.0130.380.9671.0070.271.0151.0230.22
Mt-KaHyPar1.0841.0220.241.0601.0490.191.0431.0220.16
PaToH1.0111.0060.070.9771.0120.071.0291.0240.07
K-SpecPart0.9170.9425.730.9300.9595.010.9560.9555.80
EvoPart0.9450.9680.130.8660.9090.480.9150.9290.45

On the KaHyPar preset: the current version of KaHyPar provides four configurations, for the cut-net or the connectivity metric, each in direct k-way or recursive-bisection mode. We use cut_kKaHyPar_sea20.ini, the direct k-way configuration that the official KaHyPar repository recommends for the cut-net metric. KaHyPar does not offer separate quality levels beyond these.

Because the systems differ widely in running time, we also compare them at equal wall time. Each system is run with a number of seeds such that all systems spend about the same total time, that of one run of K-SpecPart, the slowest system, and the best cut over these seeds is reported, normalized to KaHyPar's best over its own seeds.

R2-Table: Best cut at equal wall time (ε = 0.02), normalized to KaHyPar (= 1.000); lower is better. The best value in each column is in bold.

SystemISPD98 k=2ISPD98 k=3ISPD98 k=4Titan23 k=2Titan23 k=3Titan23 k=4
KaHyPar1.0001.0001.0001.0001.0001.000
hMETIS1.0100.9980.9910.9530.9781.005
Mt-KaHyPar1.0010.9811.0600.9430.9400.999
PaToH1.0061.0390.9970.9350.9590.970
K-SpecPart1.0091.0161.0051.0151.0321.056
EvoPart1.0000.9940.9710.9300.8950.936

In summary, with three seeds per system, EvoPart has the lowest average cut among the multilevel partitioners (hMETIS, KaHyPar, Mt-KaHyPar, PaToH) in all six settings, and K-SpecPart reaches a lower cut on ISPD98 and on Titan23 at k = 2 at a much longer running time. At equal wall time, EvoPart has the lowest cut in five of the six settings (tied with KaHyPar on ISPD98 at k = 2); Mt-KaHyPar is lower on ISPD98 at k = 3.

Authors' action: We added Mt-KaHyPar, K-SpecPart and PaToH to Tables 2 and 3, added the equal-time comparison as Table 4, stated the configuration of every system in Section 5.1, and revised the corresponding experimental analysis.

W1 (b). The quality-time claims are also muddied — KaHyPar appears unusually slow on Titan23, while on ISPD98 with k=3/4 EvoPart is actually about 3x slower.

Authors' answer: Both observations are correct. We run KaHyPar with the configuration recommended by its authors for the cut objective (cut_kKaHyPar_sea20.ini), single-threaded, on the same machine as all other systems. Its running time depends strongly on the instance: its mean time is 152–307 s on Titan23 against 4–6 s on ISPD98, and the other baselines (hMETIS, Mt-KaHyPar, PaToH) need only 0.07–0.38× of its time on Titan23. The cause is KaHyPar's treatment of large nets: it removes only nets above 50,000 pins, so nets of up to 50,000 pins take part in coarsening and in its n-level FM, whose gain updates traverse each such net at every uncontraction step. Titan23 has many such nets and ISPD98 has none. The other baselines simplify large nets instead: Mt-KaHyPar uses the same removal threshold but ignores large nets in its coarsening rating and refinement, which is why it needs only 0.16–0.24× KaHyPar's time on Titan23, at the price of a 4–8% higher cut. EvoPart's race between two coarsenings, which triggers only where large nets hold a real share of the pins, handles these nets quickly without that price. On ISPD98 at k = 3 and 4, EvoPart is 2.9× slower than KaHyPar (13.6 s against 5.0 s, and 16.7 s against 6.0 s on average), because for k ≥ 3 it runs the whole recursion twice and then re-partitions the final blocks pair by pair. To compare the systems independently of these differences, we added a comparison at equal wall time (Table 4; see W1 (a)).

Authors' action: We added these two explanations to the ISPD98 and Titan23 paragraphs of Section 5.2.


W2. Second, everything rests on a single 200-iteration evolution run, and the cost of that run (API tokens, wall-clock hours) is never reported; the harness ablation is three runs without statistics. It is hard to judge whether the final program is typical or a lucky sample, and whether the pipeline is reproducible for groups without a large API budget.

Q1. What did the reported evolution run cost (tokens/USD, wall time), and how many full runs were performed in total? How much does the final program's cut quality vary across runs?

Authors' answer: At submission time we had performed one run with the final harness, and EvoPart is the program selected from that run; it was not picked from several runs. To measure the variation across runs, we have now repeated the evolution twice with the same pipeline (R2 and R3 below). Every run starts from the same round-robin program and uses the same models, score, population and training grid; each selected program is evaluated on the full benchmark with the protocol of Tables 2 and 3.

R2-Table: Cost of the evolution runs and quality of the selected programs. Tokens are the input / output tokens of the 200 LLM calls (millions); cut and time are normalized to KaHyPar (= 1.00) and pooled over k ∈ {2, 3, 4}.

RunLoCTokens (in / out)HoursISPD98 AvgISPD98 BestTitan23 AvgTitan23 BestTime
R1 (paper)11864.4 / 0.98.70.9920.9990.9080.9350.70
R210554.7 / 0.97.60.9931.0020.9140.9420.59
R37123.9 / 0.86.10.9981.0050.9210.9370.67

A run costs about 4–5 million input and 0.8–0.9 million output tokens, about 150 USD at API prices, and 6–9 hours of wall time, so the pipeline can be reproduced without a large API budget. The three runs give similar results: the average cut differs by at most 0.6% on ISPD98 and 1.4% on Titan23, and all three programs are below KaHyPar on both suites. Their scores on the training grid are all about 1.08; the runs settle on slightly different trade-offs among cut, time and code size. The reported run has the lowest cut of the three, but the other two are close, so we do not consider it a lucky sample.

Authors' action: We added the cost and the results of the three runs as Table 15 in the appendix.

Q2. How does EvoPart rank against SpecPart/K-SpecPart and a higher-quality KaHyPar preset? Could you also report the connectivity (λ-1) metric and results at other imbalance factors?

Authors' answer: The first two points are answered under W1 (a).

On the connectivity metric: EvoPart optimizes the cut-net metric only and contains no step aimed at λ−1. We recomputed λ−1 on the partitions of Tables 2 and 3 for all systems. Since these partitions were all computed for the cut-net objective, λ−1 is a by-product here rather than what any of the systems was run to minimize. At k = 2 the two metrics are identical; the results at k = 3 and 4 are given in the two tables below, normalized to KaHyPar (= 1.000). A partitioner for the connectivity metric would require evolving with that objective, which the released harness supports after the corresponding changes to the score, the evaluator and the prompt.

R2-Table: Connectivity (λ−1) on ISPD98; lower is better.

Systemk=3 Avgk=3 Bestk=4 Avgk=4 Best
KaHyPar1.0001.0001.0001.000
hMETIS0.9670.9760.9590.964
Mt-KaHyPar1.0401.0371.0331.048
PaToH1.0521.0251.0981.080
K-SpecPart0.9470.9520.9510.954
EvoPart1.0020.9861.0211.027

R2-Table: Connectivity (λ−1) on Titan23; lower is better.

Systemk=3 Avgk=3 Bestk=4 Avgk=4 Best
KaHyPar1.0001.0001.0001.000
hMETIS0.9140.9390.9370.958
Mt-KaHyPar1.0361.0661.0601.039
PaToH0.9540.9950.9580.961
K-SpecPart0.8820.9110.8870.875
EvoPart0.8740.9130.8850.878

On other imbalance factors: we repeated the main experiment at ε = 0.2, a value that the evolution never saw (it only used ε = 0.02). The results are given in the two tables below, in the format of Tables 2 and 3; every partition of every system was verified to satisfy the balance constraint.

R2-Table: ISPD98 at ε = 0.2, normalized to KaHyPar (= 1.00); lower is better.

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS1.0081.0191.221.0771.0650.361.0571.0520.71
Mt-KaHyPar1.0021.0020.811.0161.0050.301.0031.0000.58
PaToH1.0511.0480.311.1781.1560.101.1181.1130.23
K-SpecPart1.0011.01726.71.0571.0537.801.0371.03922.1
EvoPart0.9970.9940.521.0001.0040.630.9930.9921.51

R2-Table: Titan23 at ε = 0.2, normalized to KaHyPar (= 1.00); lower is better.

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS0.9871.0720.231.2691.3120.191.1181.1320.15
Mt-KaHyPar0.9180.9190.151.0371.0230.121.0271.0210.10
PaToH1.0261.1020.071.3931.3990.071.2091.1980.07
K-SpecPart0.8360.8938.031.0901.1044.451.0041.0295.38
EvoPart0.8400.9190.080.9360.9870.320.9430.9590.36

Authors' action: We added the connectivity results as Table 13 and the results at ε = 0.2 as Table 14 in the appendix.


Q3. How is EvoPart's instance-adaptive time budget set, and do the headline margins survive an explicitly equal-time comparison?

Authors' answer: The budget is derived from an estimate of KaHyPar's running time. After reading the hypergraph, the program computes tK=pk/2 (10−5+3.2⋅10−4β)t_K = p \sqrt{k/2}\,(10^{-5} + 3.2 \cdot 10^{-4} \beta) seconds, where pp is the number of pins and β\beta the share of pins in nets with more than 60 pins, and sets its own wall-clock target to T=0.22 tKT = 0.22\, t_K, clamped to [1.2 s, 240 s]. TT is a soft target: a fixed minimum number of restarts per bisection runs regardless, and TT only limits the further restarts and V-cycles.

The program never runs KaHyPar; the formula and its constants were written by the model during evolution, under a score that contains a time term relative to KaHyPar. EvoPart's running time relative to KaHyPar is therefore a design choice of the evolved program rather than an independent result.

In the comparison at equal wall time (Table 4; see W1 (a)), EvoPart has the lowest cut in five of the six settings.

Authors' action: We rewrote the description of the instance-adaptive budget in Section 4 accordingly.

Reviewer_1m7VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an open source framework for hypergraph partitioner EvoPart. main contributions are: First, adding two new algorithmic components to OpenEvolve. Those are racing two coarsenings with opposite net-size priorities inside the restarts and re-partitioning pairs of final blocks. Second, it provides harness for evolving a whole solver. Specifically it organizes the MAP-Elites grid by behavior rather than text. also removes behavioral duplicates from each island with partition fingerprints in harness. The paper provides validation on two known benchmark datasets and against the KaHypar and hMETIS partitioners where it shows it matches or performs slight better than two partitioners.

Critical strengths
  1. The paper creates a compact and fully open-source hypergraph partitioner (1,186 lines of C++ in a single file, compared to roughly 26.6K lines for KaHyPar). Further, it constructs well engineering framework around it show the evaluation results.
Critical weaknesses
  1. Incremental or limited Novelty. The main contribution is the evolved partitioner and it is not a new method. The harness is OpenEvolve with small changes. The paper itself says it differs from the defaults in only two places (behavioral MAP-Elites dimensions and partition fingerprinting), plus feeding cut and wall time back into the prompt. These are fairly standard ideas. Furthermore. I also don’t agree that the two components have “no counterpart in existing partitioners.” Re-partitioning pairs of blocks has been done before in multiway partitioning. For example, Wang et al.[1] re-bipartition pairs of blocks to improve a k-way partition. The authors should discuss these works and explain what is different in their version.

[1] Maogang Wang, Sung Kyu Lim, J. Cong and M. Sarrafzadeh, "Multi-way partitioning using bi-partition heuristics," Proceedings 2000. Design Automation Conference.

  1. Missing comparisons with strong baselines.

The paper says the goal is an algorithm “better than the leading hypergraph partitioners,” but it only compares with hMETIS and KaHyPar. SpecPart and K-SpecPart (Bustany et al., 2022; 2023) are mentioned but not compared, because they use hMETIS inside. However, they report some of the best results on exactly ISPD98 and Titan23, so they should be included. Mt-KaHyPar [2], the newer version of KaHyPar, is also missing, and so is MedPart [1]. Recent works such as GenPart 2.0 [3] and Li et al. [4] also report better results than hMETIS and KaHyPar on ISPD98. Without these comparisons, the claim that EvoPart is stronger than the leading partitioners is not well supported.

[1] Rongjian Liang, Anthony Agnesina, and Haoxing Ren. 2024. MedPart: A Multi-Level Evolutionary Differentiable Hypergraph Partitioner. In Proceedings of the 2024 International Symposium on Physical Design (ISPD '24).

[2] Lars Gottesbüren, Tobias Heuer, Nikolai Maas, Peter Sanders, and Sebastian Schlag. 2024. Scalable High-Quality Hypergraph Partitioning. ACM Trans.

[3] Chen, Magi, and Ting-Chi Wang. “GenPart 2.0: Enhanced hypergraph partitioning with vertex weight handling using a generative model.” ACM Transactions on Design Automation of Electronic Systems 31.3 (2026): 1–24.

[4] Li, Yingying, et al. “Multi-objective k-way parallel hypergraph partitioning with proximal gradient algorithm.” Computational Optimization and Applications 93.3 (2026): 1069–1105.

Questions for authors
  1. Can authers provides what is novelty in the proposed partitioner methodology against the existing ones?
  2. Can authers show the comparison with recent works to back the claims?
6 comments

We sincerely thank the reviewer for the detailed and constructive feedback. We are glad that you found EvoPart to be a compact and fully open-source partitioner, and we are grateful for the pointer to Wang et al. [1], which helped us state the relation of our work to earlier work precisely.

In response to your comments, we revised our statements on novelty and added new baselines, together with a comparison at equal wall time. We hope that these changes address your concerns, and we would be grateful if you would reconsider your rating in light of the new results and the revised paper. Our detailed responses follow.


W1 (a): Incremental or limited Novelty. The main contribution is the evolved partitioner and it is not a new method. The harness is OpenEvolve with small changes. The paper itself says it differs from the defaults in only two places (behavioral MAP-Elites dimensions and partition fingerprinting), plus feeding cut and wall time back into the prompt. These are fairly standard ideas.

Authors' answer: We agree that the harness builds on OpenEvolve; it is our secondary contribution. Our main contribution is EvoPart itself. We respectfully disagree that it is not a new method: it contains a new coarsening technique, and it re-partitions pairs of final blocks with a combination of techniques that differs from existing methods [1,2]; it is also a strong, small and open partitioner.

It contains a new coarsening technique. When large nets hold at least 12% of the pins, the restarts of every bisection alternate between two coarsenings and keep the better bisection. One is the usual heavy-edge (first-choice) clustering, which favours small nets. The other first contracts whole nets of 8–512 pins at every level, largest first, so that large nets can be kept uncut, and then applies heavy-edge clustering to the remaining vertices. Known whole-net contraction differs: hMETIS's hyperedge coarsening prefers small nets, and BiPart [3], which can prioritise large hyperedges, may merge a large hyperedge only in part; neither combines the contraction with heavy-edge clustering. To our knowledge, both this coarsening (whole, disjoint large nets first, heavy-edge clustering for the rest) and racing it against plain clustering inside every bisection are new. On Titan23 either coarsening alone has a 3% or 14% higher cut.

It revives an instructive step. After recursive bisection, EvoPart re-partitions pairs of final blocks with a combination of a V-cycle, flow refinement and, when the time budget allows, a multilevel bisection from scratch. The idea is related to that of Wang et al. [1] (see W1 (b) for the differences). To the best of our knowledge, none of the leading partitioners re-partitions pairs of blocks in this way: hMETIS and PaToH [4] have no such step, and KaHyPar and Mt-KaHyPar refine pairs with flows, but only in a region around the cut [2]. On Titan23 the step lowers the cut by 4–9% (Figure 6).

It is strong. Starting from a 103-line program that assigns vertices round-robin, a single 200-iteration run produced a complete partitioner whose cut is lower than that of hMETIS, KaHyPar and, in the new experiments, Mt-KaHyPar, in about 70% of KaHyPar's wall time over the whole benchmark. The gain carries over to the 30 instances never seen during evolution (5.4% lower cut than KaHyPar) and to k = 5–8, which the evolution never evaluated.

It is small and open. EvoPart is a single file of 1,186 lines of single-threaded C++ without dependencies, 22.5× smaller than KaHyPar. hMETIS is closed-source, and because of the size of KaHyPar's codebase, works built on it typically modify only one stage of its pipeline. A partitioner of this size that can be read and changed as a whole gives the community a different starting point for future work.

As for the harness, we do not claim an entirely new evolution framework. We changed OpenEvolve in two places and measured the effect: with its default textual descriptors and everything else unchanged, the best programs of three independent runs have a 1–3% higher average cut on ISPD98 and a 3–6% higher one on Titan23 (Table 5).

Authors' action: We revised the related statements in the abstract, the introduction, Section 4 and the conclusion. The coarsening technique is presented as new, with its relation to hyperedge coarsening in hMETIS and to BiPart now stated. Pairwise re-partitioning is described as a combination of techniques; Section 4 states how EvoPart differs from Wang et al. [1] and Heuer et al. [2].

W1 (b): Furthermore. I also don't agree that the two components have "no counterpart in existing partitioners." Re-partitioning pairs of blocks has been done before in multiway partitioning. For example, Wang et al.[1] re-bipartition pairs of blocks to improve a k-way partition. The authors should discuss these works and explain what is different in their version.

Authors' answer: Thank you for this reference. We agree that re-partitioning pairs of blocks is not entirely new: our step is closely related in idea to the all-way bi-partitioning of Wang et al., although the operation applied to each pair differs. Our statement that it has "no counterpart" was too strong. We have revised it, cite Wang et al., and discuss both the relation and the differences in the paper. (The coarsening component is discussed in our response to W1 (a).)

Operation. Wang et al. apply a bi-partitioner, hMETIS in their experiments, to pairs of blocks of a k-way partition. Neither hMETIS 1.5.3 nor 2.0pre1 accepts an existing partition as a starting solution, so each call bisects the pair from scratch. EvoPart first improves the current split of the pair: it runs a V-cycle whose coarsening never merges vertices of different blocks, followed by flow refinement. When the time budget allows, it also bisects the pair from scratch with the full multilevel procedure and keeps the better of the two results. A pair is committed only if its cut strictly decreases. The main difference is therefore that EvoPart re-partitions a pair starting from its current split, with a V-cycle and flow refinement, and combines this with a bisection from scratch, whereas Wang et al. only bisect from scratch. To the best of our knowledge, existing multilevel partitioners such as hMETIS and PaToH have no step that re-partitions pairs of blocks, and KaHyPar and Mt-KaHyPar refine pairs with flows, but only in a region around the cut.

Ablation. To measure what this difference is worth, we added an ablation that keeps only one operation at a time: flow refinement of each pair only, as in KaHyPar and Mt-KaHyPar, and bisection of each pair from scratch only, as in Wang et al. For a fair comparison, the latter is given the same time budget as the full step.

R1-Table: Average cut of the re-partitioning variants, relative to EvoPart with the full step (= 1.000); lower is better. These are the values shown in Figure 6(c).

VariantTitan23 k=3Titan23 k=4ISPD98 k=3ISPD98 k=4
No re-partitioning1.1001.0441.0151.019
Flow refinement only1.1001.0371.0151.018
Bisection from scratch only1.0151.0081.0051.006
Full step (EvoPart)1.0001.0001.0001.000

The full step gives the lowest cut in all four settings. Flow refinement alone hardly improves on no re-partitioning. Bisection from scratch alone is 0.5–1.5% behind the full step at the same time budget. Compared with no re-partitioning, the full step lowers the cut by 4–9% on Titan23 and by 1.5–1.9% on ISPD98 (the running times are compared in Figure 6(d)).

Authors' action: We revised the related statements in the abstract, the introduction, Section 4 and the conclusion. Section 4 now states how the step differs from Wang et al. [1] and Heuer et al. [2], and Section 5.3 reports the new ablation (Figure 6(c, d)).

W2. Missing comparisons with strong baselines. The paper says the goal is an algorithm "better than the leading hypergraph partitioners," but it only compares with hMETIS and KaHyPar. SpecPart and K-SpecPart (Bustany et al., 2022; 2023) are mentioned but not compared, because they use hMETIS inside. However, they report some of the best results on exactly ISPD98 and Titan23, so they should be included. Mt-KaHyPar [2], the newer version of KaHyPar, is also missing, and so is MedPart [1]. Recent works such as GenPart 2.0 [3] and Li et al. [4] also report better results than hMETIS and KaHyPar on ISPD98. Without these comparisons, the claim that EvoPart is stronger than the leading partitioners is not well supported.

Authors' answer: We added Mt-KaHyPar (highest-quality preset), PaToH (quality preset) and K-SpecPart as baselines. All systems run single-threaded on the same machine under the setting of the main experiments. The two tables below extend Tables 2 and 3 of the paper: cut size and wall time are normalized to KaHyPar (= 1.00), as geometric means of per-instance ratios; lower is better.

R1-Table: ISPD98 (18 instances, 3 seeds).

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS0.9941.0072.331.0051.0201.950.9931.0051.85
Mt-KaHyPar1.0040.9931.051.0241.0211.111.0071.0061.08
PaToH1.0371.0150.381.0901.0720.401.0681.0610.41
K-SpecPart0.9780.98346.50.9840.99632.70.9790.99235.0
EvoPart0.9920.9930.880.9991.0082.930.9860.9982.94

R1-Table: Titan23 (22 instances, 3 seeds).

Systemk=2 Avgk=2 Bestk=2 Timek=3 Avgk=3 Bestk=3 Timek=4 Avgk=4 Bestk=4 Time
KaHyPar1.0001.0001.001.0001.0001.001.0001.0001.00
hMETIS1.0051.0130.380.9671.0070.271.0151.0230.22
Mt-KaHyPar1.0841.0220.241.0601.0490.191.0431.0220.16
PaToH1.0111.0060.070.9771.0120.071.0291.0240.07
K-SpecPart0.9170.9425.730.9300.9595.010.9560.9555.80
EvoPart0.9450.9680.130.8660.9090.480.9150.9290.45

We also ran MedPart. Its paper and public code cover bipartitioning only, so it can be compared at k = 2 only, and it runs on a GPU, so its running time is not directly comparable. On ISPD98 its average cut is 1.001× KaHyPar's at 1528× KaHyPar's time. On Titan23 we could complete 16 of the 22 instances within the rebuttal period; on these its average cut is 1.073× KaHyPar's at 197× the time. Since these results cover k = 2 only and not the full benchmark, we report them here and do not include them in the tables of the paper.

GenPart 2.0 [5] and Li et al. [6] have no public code, and their experimental settings differ from ours, so a direct comparison is not possible.

Because the systems differ widely in running time, we also compare them at equal wall time. Each system is run with a number of seeds such that all systems spend about the same total time, that of one run of K-SpecPart, the slowest system, and the best cut over these seeds is reported, normalized to KaHyPar's best over its own seeds.

R1-Table: Best cut at equal wall time (ε = 0.02), normalized to KaHyPar (= 1.000); lower is better. The best value in each column is in bold.

SystemISPD98 k=2ISPD98 k=3ISPD98 k=4Titan23 k=2Titan23 k=3Titan23 k=4
KaHyPar1.0001.0001.0001.0001.0001.000
hMETIS1.0100.9980.9910.9530.9781.005
Mt-KaHyPar1.0010.9811.0600.9430.9400.999
PaToH1.0061.0390.9970.9350.9590.970
K-SpecPart1.0091.0161.0051.0151.0321.056
EvoPart1.0000.9940.9710.9300.8950.936

In summary, with three seeds per system, EvoPart has the lowest average cut among the multilevel partitioners (hMETIS, KaHyPar, Mt-KaHyPar, PaToH) in all six settings, and K-SpecPart reaches a lower cut on ISPD98 and on Titan23 at k = 2 at a much longer running time. At equal wall time, EvoPart has the lowest cut in five of the six settings (tied with KaHyPar on ISPD98 at k = 2); Mt-KaHyPar is lower on ISPD98 at k = 3.

Authors' action: We added Mt-KaHyPar, K-SpecPart and PaToH to Tables 2 and 3, added the equal-time comparison as Table 4, stated the configuration of every system in Section 5.1, and revised the corresponding experimental analysis.

Comments on the paper

2 comments

We sincerely thank all reviewers for their careful reading and constructive feedback. We are encouraged that they found EvoPart a compact and fully open-source partitioner (Reviewer 1m7V), a convincing demonstration that LLM code evolution can yield an entire competitive solver, with a careful held-out evaluation (iZSx), and well motivated, with the harness described in detail (kasw).

We have answered every comment in the individual responses and revised the manuscript; all revisions are highlighted in blue. Below we summarize the core contributions, the new experiments and the revisions to the text.


Core contributions

  • EvoPart, an open, lightweight and strong hypergraph partitioner (main contribution). A single file of 1,186 lines of single-threaded C++, 22.5× less code than KaHyPar, evolved from a round-robin initial program in a single 200-iteration run. On the full ISPD98 and Titan23 benchmarks, its cut is 5.5% lower than KaHyPar's in 70% of KaHyPar's wall time; 30 of the 40 instances were never seen during evolution. Two of its components are instructive for future partitioners: a new coarsening technique, which races two coarsenings with opposite net-size priorities inside the restarts, and a re-partitioning of pairs of final blocks that combines a V-cycle, flow refinement and a multilevel bisection from scratch.
  • A harness for evolving a whole solver (secondary contribution). Built on OpenEvolve, it places programs in the MAP-Elites grid by behavior rather than by text, removes behavioral duplicates by partition fingerprinting, and feeds the measured cut and wall time back into the prompt. With OpenEvolve's default textual descriptors, three independent runs end with a 1–3% (ISPD98) and 3–6% (Titan23) higher average cut (Table 5).

New experiments

  1. Three new baselines (1m7V, iZSx; Tables 2 and 3). We added Mt-KaHyPar (highest-quality preset), PaToH (quality preset) and K-SpecPart. All running times are single-threaded on the same machine; EvoPart has the lowest average cut among the multilevel partitioners (hMETIS, KaHyPar, Mt-KaHyPar, PaToH) in all six settings (two suites, k ∈ {2, 3, 4}). K-SpecPart reaches a lower cut on ISPD98 (by 0.7–1.5%) and on Titan23 at k = 2 (by 3.0%), at a much longer running time; on Titan23 at k = 3 and 4, EvoPart's cut is 4–7% lower than K-SpecPart's.
  2. Comparison at equal wall time (iZSx, 1m7V; Table 4). All systems are given about the same total time, that of one run of K-SpecPart, and the best cut over the seeds that fit is reported. EvoPart has the lowest cut in five of the six settings (tied with KaHyPar on ISPD98 at k = 2); Mt-KaHyPar is lower on ISPD98 at k = 3.
  3. Ablation of pairwise re-partitioning (1m7V; Section 5.3, Figure 6(c, d)). Flow refinement of each pair alone, as in KaHyPar and Mt-KaHyPar, recovers almost none of the gain of the full step. Bisection of each pair from scratch alone, as in Wang et al. (2000), is 0.5–1.5% behind the full step at the same time budget.
  4. Cost and repeatability of the evolution (iZSx, kasw; Appendix G, Table 15). We repeated the evolution twice with the same pipeline. A run costs about 150 USD in API calls and 6–9 hours of wall time. The average cut of the three selected programs differs by at most 0.6% on ISPD98 and 1.4% on Titan23, and is below KaHyPar's on both suites for all three.
  5. Connectivity metric and a looser balance constraint (iZSx; Appendices E and F, Tables 13 and 14). EvoPart optimizes the cut-net metric only; on the same partitions, its connectivity (λ − 1) is the lowest on average on Titan23 and close to KaHyPar's on ISPD98, where hMETIS and K-SpecPart are lower. At ε = 0.2, its average cut is the lowest, or tied for the lowest, in five of the six settings.
  6. MedPart (1m7V). It supports k = 2 only and runs on a GPU; its results are given in our response to Reviewer 1m7V.

Revisions to the text

  • Statements on novelty (1m7V; abstract, Sections 1 and 4, conclusion). We revised the statement that the two components have no counterpart in existing partitioners. The coarsening technique is presented as new, with its relation to hyperedge coarsening in hMETIS and to BiPart. Pairwise re-partitioning is presented as a combination of techniques, with its relation to, and differences from, Wang et al. (2000) and Heuer et al. (2019).
  • Analysis of running time (iZSx; Section 5.2): why KaHyPar is slow on Titan23, and why EvoPart is slower than KaHyPar on ISPD98 at k = 3 and 4.
  • Instance-adaptive time budget (iZSx; Section 4): we now state that the budget is derived from an estimate of KaHyPar's running time, a rule written by the model during evolution.
  • Role of KaHyPar in the harness (kasw; Section 3): it serves only as the reference of the score, and the model never sees its code.
  • One-time cost of the evolution, and use of the harness with other partitioners (kasw; Appendix G).
  • Correction of one value (Table 5): For EvoPart, the pooled best-cut ratio on ISPD98 is 0.99945. The submission listed it as 1.000, because it had been computed from the per-k values after rounding; it is now 0.999, consistent with Table 15.

We hope that these additions address the reviewers' concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.