# MazeNet: An Accurate, Fast, and Scalable Deep Learning Solution for Steiner Minimum Trees

arXiv: https://arxiv.org/abs/2410.18832 · HTML: https://mlsanity.com/paper/2410.18832/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 16 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Builds on (most cited first, 3 of 3)

- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking](https://mlsanity.com/paper/2202.05826/) (2022)

## Abstract (arXiv)

The Obstacle Avoiding Rectilinear Steiner Minimum Tree (OARSMT) problem, which seeks the shortest interconnection of a given number of terminals in a rectilinear plane while avoiding obstacles, is a critical task in integrated circuit design, network optimization, and robot path planning. Since OARSMT is NP-hard, exact algorithms scale poorly with the number of terminals, leading practical solvers to sacrifice accuracy for large problems. We propose MazeNet, a deep learning-based method that learns to solve the OARSMT from data. MazeNet reframes OARSMT as a maze-solving task that can be addressed with a recurrent convolutional neural network (RCNN). A key hallmark of MazeNet is its scalability: we only need to train the RCNN blocks on mazes with a small number of terminals; larger mazes can be solved by replicating the same pre-trained blocks to create a larger network. Across a wide range of experiments, MazeNet achieves perfect OARSMT-solving accuracy, significantly reduces runtime compared to classical exact algorithms, and can handle more terminals than state-of-the-art approximate algorithms.