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

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).

Introduction

The Rectilinear Steiner Minimum Tree (RSMT) problem is a fundamental challenge in microchip design, requiring the shortest path to connect a set of terminals using only horizontal and vertical segments. Minimizing total wire length is essential for reducing power consumption, heat dissipation, and signal delay in modern integrated circuits. Given that RSMT is NP-complete, industry standards typically rely on heuristics like FLUTE or exact solvers like GeoSteiner, which, while optimal, suffer from exponential time complexity. While recent Neural Combinatorial Optimization (NCO) models have attempted to address this, they frequently struggle with size generalization—performing well on small datasets but failing on the massive scales required for VLSI design.

Methodology: The NN-Steiner Framework

NN-Steiner bridges the gap between classical algorithms and deep learning by embedding neural networks into Arora’s Polynomial Time Approximation Scheme (PTAS). Arora’s algorithm partitions space into a quadtree and uses Dynamic Programming (DP) to find optimal connections across cell boundaries via "portals." NN-Steiner replaces the computationally expensive DP steps with four small, fixed-size neural components:

  1. NN_base: Encodes local geometry within leaf cells.
  2. NN_DP: Simulates the bottom-up inductive step, passing cost embeddings up the quadtree.
  3. NN_top & NN_retrieve: Execute a top-down backtracking pass to place Steiner points.
Architecture of the NN-Steiner framework showing the integration of neural components within the quadtree structure.

By focusing on a fixed number of portals per cell, these neural components remain bounded in size regardless of the total number of terminals. This "algorithmic alignment" allows the model to learn a generalized language of connectivity rather than memorizing specific coordinates, enabling it to scale to instances much larger than those encountered during training.

Key Results and Generalization

The model was trained on 120,000 synthetic pointsets (up to 180 points) and tested on diverse distributions ranging from 50 to 5,000 points.

  • Accuracy: On large-scale problems (500+ terminals), NN-Steiner consistently outperformed the industry-standard FLUTE, achieving up to a 3% reduction in wire length at 5,000 points.
  • Scaling: Unlike exact solvers, NN-Steiner exhibits near-linear runtime scaling, making it suitable for massive chip layouts.
  • Robustness: The framework demonstrated impressive zero-shot generalization, maintaining high performance on clustered and non-uniform distributions despite being trained primarily on uniform data.
Runtime comparison of NN-Steiner against industry standards and other neural approaches as the number of points increases.

Conclusion

NN-Steiner represents a significant step forward in neural combinatorial optimization by combining the theoretical guarantees of classical algorithms with the representational power of deep learning. While it is slightly less accurate than lookup-table heuristics for very small instances, its superior scaling and accuracy on large-scale problems make it a promising candidate for industrial CAD tools. Future work will focus on extending the framework to 3D Steiner trees and incorporating obstacle avoidance for real-world routing constraints.

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