Provably Optimal HBT Legalization in Seconds: Certified Optima Reveal Where the Headroom Really Lies

Kadhir Parani, Manjunath Bezawada, Divya M, Kesana Jathin, Kolli Sarath, Sm ZobaedarXiv 2026 · arXiv

TL;DR

This paper introduces GEO-Exact, a solver that achieves provably optimal legalization for 3D IC hybrid bonding terminals (HBTs) in mere seconds. By establishing a certified "ground truth" for displacement, the authors reveal that traditional sliding-window heuristics are already within 0.011% of perfection at nominal pitches, suggesting that recent claims of massive gains from reinforcement learning may be due to suboptimal baselines rather than untapped potential.

What Problem Does This Paper Address?

In face-to-face 3D IC integration, signals travel between dies through Hybrid Bonding Terminals (HBTs). While a 3D placer determines "ideal" terminal locations, these must be snapped to a regular physical grid—a process called legalization. The goal is to assign each terminal to a unique grid site while minimizing the total Manhattan (L1) displacement.

Recently, the Open3DBench benchmark reported that Reinforcement Learning (RL) legalizers could reduce displacement by ~20% compared to traditional sliding-window (SW) heuristics. However, because the code for these legalizers wasn't public, it was impossible to verify if this 20% gain represented a breakthrough or simply a comparison against a weak baseline. The authors of this paper set out to find the "headroom"—the maximum possible improvement any legalizer could ever achieve—by calculating the mathematically exact optimum for these designs.

Methods

The authors treat HBT legalization as a bipartite assignment problem. Their primary contribution is GEO-Exact, an exact solver designed for speed and scale:

  • Successive Shortest Augmenting Paths: Instead of using the classic (and often slow) Hungarian method, GEO-Exact uses a heap-based Dijkstra search to find the cheapest "chain of moves" to place terminals.
  • Lazy Edge Generation: To avoid the memory explosion of a full $N \times M$ cost matrix, the solver uses a uniform spatial grid to only consider nearby candidate sites, generating edges only when the search requires them.
  • Optimality Certificates: The solver doesn't just claim to be best; it proves it. Using linear programming duality, it generates a "dual certificate." If the total displacement (primal) matches the calculated dual value, the solution is mathematically guaranteed to be optimal.
  • Baselines: The authors reconstructed several common heuristics, including a sliding-window (SW) approach (ViaLegal-style), a density-guided heuristic (DGHL), and a simple greedy approach.

Datasets

The study uses an open benchmark harness consisting of 21 design/pitch instances derived from Open3DBench placement data.

  • Designs: Includes ariane133, bp, swerv, and others, ranging from ~1,500 to nearly 40,000 terminals.
  • Pitches: Nominal pitches of 4 µm and 6 µm, plus high-utilization sweeps at 2 µm.
  • Scale: The largest instance, bp_quad, involves assigning 39,814 terminals to 387,506 possible sites.

Key Insights and Ideas

  • The "Headroom" is Vanishingly Small: At nominal pitches, the standard sliding-window heuristic is incredibly effective. It sits just 0.011% above the theoretical optimum. This implies that for most standard designs, there is virtually no room for RL or any other advanced method to provide significant displacement gains.
  • Utilization is the Stress Test: Significant gaps between heuristics and the optimum only appear at very high utilization (above 58%). In these "crowded" scenarios, the sliding-window approach can be up to 27.5% worse than optimal because it lacks the global view to coordinate long chains of moves.
  • L1 vs. L2 Objectives: The paper notes that L1 (Manhattan) optima are highly non-unique. An assignment that is optimal for L1 might be suboptimal for L2 (Euclidean) displacement. Breaking L1 ties by minimizing squared L2 distance can improve the Euclidean quality of the result.
  • Exact is Faster than Heuristic: Surprisingly, GEO-Exact (written in C) is often an order of magnitude faster than the Python-based heuristics it replaces, proving that you don't have to sacrifice optimality for performance.

Key Results

  • Optimality: GEO-Exact achieved the certified optimum on all 21 instances, with a relative primal-dual gap of essentially zero ($< 8.2 \times 10^{-16}$).
  • Heuristic Gaps: At nominal pitch, SW was 0.011% above optimal, while BTAssign-style and DGHL were 3.0% and 6.9% above, respectively. Greedy placement was a disastrous 64.5% above optimal.
  • Speedup: GEO-Exact was roughly 8x faster than DGHL and 40x faster than SW on average.
Figure 3. Per-instance speed-up of GEO-Exact over DGHL (circles) and SW (squares), run 1, log scale. The shaded band marks ties (within 1.2×).
  • Utilization Sweep: As shown in Figure 2, the SW heuristic only begins to fail significantly when HBT utilization nears 60-90%.
Figure 2. SW gap above the certified optimum against utilization, for the 21 nominal instances (crosses) and the pitch sweeps of bp and the five Test B designs. The 21 nominal and 217 further Test B optima are dual-certified; the 10 bp optima are GEO-Exact solutions checked against an independent sparse exact reference.

Limitations and Future Work

  • Reconstructed Baselines: The authors had to reconstruct the SW and RL baselines from descriptions, as the original implementations were not public. While they swept parameters to find the best configurations, a direct code-to-code comparison remains a goal.
  • Single Objective: The study focuses strictly on L1 displacement. It does not account for downstream effects like routing congestion, timing, or power, which might be influenced by different legalization patterns.
  • Adversarial Inputs: While fast on real designs, GEO-Exact can slow down on "hotspot" instances where all terminals are clustered in a tiny fraction of the die.
  • Future Directions: The authors suggest that future work should focus on multi-objective legalization and developing predictors to identify exactly when windowed heuristics are likely to fail.

Summary updated

Abstract

Hybrid bonding terminal (HBT) legalization assigns every terminal of a face-to-face 3D IC to its own pitch-grid site with minimum total Manhattan displacement. Open3DBench reports that a reinforcement-learning (RL) legalizer reduces displacement by 19-22% relative to a sliding-window (SW) heuristic, but none of its legalizers is publicly released. We ask how much displacement any legalizer can still recover. We build an open benchmark of 21 design/pitch instances from Open3DBench placement data, with reconstructed greedy, SW (ViaLegal-style) and BTAssign-style baselines, and GEO-Exact, an exact solver that runs successive shortest augmenting paths over lazily generated spatial candidate edges. An independent dual certificate proves its assignment optimal on all 21 instances (relative primal-dual gap at most $8.2 \times 10^{-16}$). Against these optima, our SW reconstruction with ViaLegal's default configuration is on average 0.011% above optimal (worst 0.119%), while on the 16 contended instances BTAssign-style, a density-guided heuristic (DGHL) and greedy are 3.0%, 6.9% and 64.5% above. Headroom does appear outside this regime: with 2x2 windows SW reaches 34.1%, and above about 58% utilization, on three of six swept designs, it reaches 21.1% on bp, 27.5% on swerv and 8.9% on jpeg (217 further certified instances, and ten bp points checked against an independent exact solver). If the published 19-22% gain were measured on instances like ours, SW would have to be at least 24-28% above optimal on average, far more than any SW variant we tested at nominal pitch; the RL paper's own comparison with the Hungarian optimum puts its SW 3.05% above optimal on average. GEO-Exact is also about an order of magnitude faster than DGHL and SW in our harness (geometric means 8.1x and 40x; a compiled core against Python baselines on a shared server). Code, optimal values and certificates are released.
BibTeX
@misc{parani2026provably,
  author = {Kadhir Parani and Manjunath Bezawada and Divya M and Kesana Jathin and Kolli Sarath and Sm Zobaed},
  title = {{Provably Optimal HBT Legalization in Seconds: Certified Optima Reveal Where the Headroom Really Lies}},
  year = {2026},
  eprint = {2611.14928},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14928},
}
Figure