NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem

Andrew B. Kahng, Robert R. Nerem, Yusu Wang, Chien-Yi Yang

Introduction

Presented at AAAI-24, NN-Steiner is a hybrid framework that integrates deep learning into classical approximation algorithms to solve the Rectilinear Steiner Minimum Tree (RSMT) problem—a cornerstone of modern computer chip design. By embedding neural networks within the structural "skeleton" of Arora’s Polynomial-Time Approximation Scheme (PTAS), NN-Steiner achieves superior scalability and generalization compared to existing heuristics and end-to-end neural models.

The RSMT Problem in VLSI Design

The RSMT problem involves finding the shortest path to connect a set of points using only horizontal and vertical segments. In Very Large Scale Integration (VLSI), this is critical for routing wires to minimize power consumption and signal delay.

Because RSMT is NP-complete, industry standards typically rely on:

  • Exact Solvers (e.g., GeoSteiner): Provide optimal solutions but are computationally prohibitive for large designs.
  • Heuristics (e.g., FLUTE): Fast but often sub-optimal as point density increases.
  • Neural Approaches: Recent Reinforcement Learning models often fail to scale as the search space expands exponentially with the number of points.

Methodology: Algorithmic Alignment

NN-Steiner’s core innovation is algorithmic alignment. Rather than treating the problem as a black-box end-to-end task, the authors utilize the hierarchical structure of Arora’s PTAS.

The NN-Steiner pipeline: from quadtree construction to local refinement.

The process follows a structured pipeline:

  1. Quadtree Construction: The space is partitioned into a hierarchical grid.
  2. Neural Network Tree Construction:
    • Bottom-up encoding (NN_base, NN_DP): These networks compute connection costs within local grid cells.
  3. Top-down retrieval (NN_top, NN_retrieve): These predict the most likely "portals" (connection points on cell boundaries) to form the optimal tree.
  4. MST Computation & Refinement: A final pass uses classical Minimum Spanning Tree (MST) algorithms and local geometric polishing to finalize the routing.

By restricting neural networks to local sub-problems of fixed size, the model's complexity remains independent of the total point count, ensuring massive scalability.

Key Results and Scaling

NN-Steiner demonstrates remarkable performance on both uniform and non-uniform point distributions.

Runtime comparison showing NN-Steiner's linear scaling compared to other solvers.
  • Superior Scaling: For large-scale problems ($n \ge 500$), NN-Steiner consistently outperforms FLUTE. At 5,000 points, it produces trees approximately 3% shorter than the industry standard.
  • Generalization: Unlike previous neural models like REST, which degrade as problem size increases, NN-Steiner maintains its edge. It successfully generalizes from small training sets (approx. 180 points) to test instances of 5,000 points.
  • Efficiency: The framework exhibits near-linear runtime scaling, making it a viable candidate for real-world electronic design automation (EDA) tools.

Conclusion and Future Directions

NN-Steiner proves that "size independence" is achievable by learning the recursive logic of an algorithm rather than just memorizing patterns. While it currently faces overhead on very small instances and is limited to 2D space, future work aims to extend the framework to 3D multi-layer routing and incorporate obstacle-avoidance—features essential for modern semiconductor manufacturing.

Summary updated

Abstract

Recent years have witnessed rapid advances in the use of neural networks to solve combinatorial optimization problems. Nevertheless, designing the "right" neural model that can effectively handle a given optimization problem can be challenging, and often there is no theoretical understanding or justification of the resulting neural model. In this paper, we focus on the rectilinear Steiner minimum tree (RSMT) problem, which is of critical importance in IC layout design and as a result has attracted numerous heuristic approaches in the VLSI literature. Our contributions are two-fold. On the methodology front, we propose NN-Steiner which is a novel mixed neural-algorithmic framework for computing RSMTs that leverages the celebrated PTAS algorithmic framework of Arora to solve this problem (and other geometric optimization problems). Our NN-Steiner replaces key algorithmic components within Arora's PTAS by suitable neural components. In particular, NN-Steiner only needs four neural network (NN) components that are called repeatedly within an algorithmic framework. Crucially, each of the four NN components is only of bounded size independent of input size, and thus easy to train. Furthermore, as the NN component is learning a generic algorithmic step, once learned, the resulting mixed neural-algorithmic framework generalizes to much larger instances not seen in training. Our NN-Steiner, to our best knowledge, is the first neural architecture of bounded size that has capacity to approximately solve RSMT (and variants). On the empirical front, we show how NN-Steiner can be implemented and demonstrate the effectiveness of our resulting approach, especially in terms of generalization, by comparing with state-of-the-art methods (both neural and non-neural based).
BibTeX
@inproceedings{kahng2024nn,
  author = {Andrew B. Kahng and Robert R. Nerem and Yusu Wang and Chien-Yi Yang},
  title = {{NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29200},
}
Figure