cs.AINov 11, 2026

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

Authors: Kadhir Parani, Manjunath Bezawada, Divya M, Kesana Jathin, Kolli Sarath, Sm Zobaed

Organizations: Boltzmann Labs, Hyderabad, India · Department of Agricultural & Biological Engineering, Purdue University, West Lafayette, IN, USA · Department of Computer Science & Engineering Technology, University of Maryland Eastern Shore, Princess Anne, MD 21853, USA

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×10−168.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.

Explore similar work

Oct 14, 2026

Design Space Exploration of Reinforcement Learning Configurations for Post-Legalization Placement

Graph Neural Networks (GNNs) and Reinforcement Learning (RL) have recently been explored for VLSI placement optimization, but their effectiveness for post-legalization placement refinement remains unclear. This paper presents a systematic design space exploration of a GNN-Proximal Policy Optimization (GNN-PPO) framework across three ISPD2015 benchmarks. We evaluate 18 configurations covering reward functions, GNN architectures, action spaces, candidate-set sizes, and training strategies. We analyse the results we obtain to identify pitfalls and to assess the prospects and opportunities of the RL methods for post-legalization placement. On top of that we propose a design classification approach to guide the design decisions of RL models.
Aug 10, 2026

DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces constraint-coupled learning, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of 0.0573%0.0573\% from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in 9.559.55 batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves 81.46%81.46\% edge-decision coverage. The mean gap is 67.1%67.1\% smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.
Jun 2, 2026

Optimizing Explicit Unit-Distance Lower-Bound Certificates

The 2026 disproof of Erdős's unit-distance conjecture and Sawin's quantitative refinement show that the maximum number u(n)u(n) of unit distances among nn planar points can exceed n1+εn^{1+\varepsilon} for a fixed positive ε\varepsilon. Sawin's explicit bound gives more than n1.014n^{1.014} unit distances for arbitrarily large nn and exposes integer parameters whose choice is not fully optimized. This report treats Sawin's parameter selection as a nonlinear integer optimization problem and develops an open-source Python optimization and verification pipeline for certificates involving prime sets TT and SQS_Q, integer multiplicities k(p)k(p), and a rationally encoded real parameter RR. After reproducing Sawin's certificate with δ=0.014114…δ=0.014114\ldots, the pipeline yields improved certificates with the same TT. We develop a tailored integer evolution strategy achieving a certificate with δ=0.015263…δ=0.015263\ldots and supporting the cautious statement u(n)>n1.0152u(n)>n^{1.0152} for arbitrarily large nn. For extended ramified prime ranges, the Emmerich--Cordella certificate obtained with the same framework reports u(n)>n1.031u(n)>n^{1.031} for #T=67\#T=67, illustrating the importance of enlarging TT. Very recent MathOverflow discussions, brought to the author's attention as of version~4, report further improvements, including certificates above δ>0.035δ>0.035 and beyond δ>0.036δ>0.036. Some of these improvements may rely not only on larger prime ranges but also on modified constraint systems and additional degrees of freedom that deviate from Sawin's original formulation. Beyond this application, the work illustrates how randomized optimization heuristics can improve, verify, and refine explicit certificates for combinatorial geometry through nonlinear integer optimization.