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

"Limitations and Failure Cases with More Than 8 Terminals": Thank you for highlighting the importance of addressing MazeNet’s limitations in scenarios with significantly more than 8 terminals. We acknowledge that MazeNet does not guarantee convergence or optimal path length in such cases. To manage these limitations, MazeNet incorporates a predefined maximum number of iterations. If a solution fails to converge or terminals remain unreachable, the algorithm halts and marks the attempt as unsuccessful. These constraints will be explicitly stated in the revised manuscript to ensure clarity.

"Parallelization Process and Figure 14 Details": We appreciate the request for more specific details on the parallelization process. In Figure 14, the x-axis represents the number of image chunks into which the input is divided, with a 10-pixel overlap between chunks. This overlap ensures no errors are introduced at chunk boundaries, considering the kernel size for convolutions is 3. If the overlap is smaller than the number of convolutions per iteration, errors accumulate at chunk boundaries. By maintaining a 10-pixel overlap, we ensure equivalence to performing a convolution on the entire image, regardless of how terminals are distributed across image sections. These details will be added to Section 3.4 to provide a comprehensive explanation of the parallelization process. We will include these specific details in the revised manuscript to provide a complete explanation. Thank you for highlighting this aspect, as it has allowed us to improve the clarity of this section.

"Replicability and Code Release": We deeply value the reviewer’s emphasis on replicability. To facilitate this, we are preparing the MazeNet codebase for public release. The released version will include detailed documentation, implementation instructions, and explanations to enable researchers to replicate our work accurately. Furthermore, we will elaborate on the T! complexity, which arises from permuting terminals and sequentially connecting them in pairs, ensuring all possible orderings are considered.

"Progressive Training Algorithm and Cycle Detection": The paragraph in lines 174–182 refers to the progressive training algorithm of Bansal et al., which is explicitly employed in this work. While our intention was to provide context for our approach, we appreciate the reviewer’s suggestion for greater clarity. In the revised text, we will explicitly state our use of their algorithm to ensure understanding.

"For cycle detection": We thank the reviewer for bringing attention to this point. The TC module discards solutions when cycles are detected, requiring additional iterations to clear the incorrect solution. We will clarify this process further in the revised manuscript.

"Algorithm 1": We are grateful for the opportunity to refine the explanation of Algorithm 1. The algorithm explicitly prohibits retracing steps by storing the last move. We agree that Algorithm 1 requires additional clarity, and we will explicitly redefine the condition "junction found" for consistency. Additionally, we will provide further detail on how the direction with the highest "whiteness" is selected, and emphasize that backward moves are explicitly disallowed in the revised version.

"Training configurations": We appreciate the reviewer’s insights regarding training maze configurations. To balance complexity and simplicity, we selected setups with 2, 3, or 4 terminals. Configurations with fewer terminals are less computationally expensive to generate using exact optimal methods, enabling us to create a high-quality training dataset of 0.5 million examples. As the number of terminals increases, the time required per maze becomes significant, making larger configurations impractical at this scale. We will ensure this reasoning is clearly articulated in the revised manuscript.

"Random Variables": We thank the reviewer for their observation regarding the random variable n. The random variable n, mentioned in lines 293–295, is sampled from a uniform distribution. We will explicitly include this detail in the revised manuscript for clarity. Once n is determined, k is also determined so that it satisfies the constraint n+k=m.

"RB Module Iterations and Scaling Limitations": We appreciate the reviewer’s observation regarding the 20 MazeNet iterations referenced in line 378. These iterations correspond to the number of RB module iterations used for comparison with the TC module. Without the TC module, the RB module runs for a predefined number of iterations, which we set to 20 in Table 1. We will clarify this in the revised text.

"Motivation and Limitations of Previous Solutions to the OARSMT Problem": Thank you for emphasizing the need for clearer motivation. In the revised manuscript, we have explicitly highlighted the motivation behind MazeNet. This work addresses the gap between probabilistically correct approximation methods and the demand for deterministic accuracy in small-scale environments. For problems within the 11×11 regime, probabilistic methods may be effective, but they lack justification for failing to discover the true shortest path. MazeNet is designed to achieve deterministic accuracy comparable to exact graph-based methods while maintaining the runtime efficiency of approximation algorithms. This approach fills the gap for small but complex maze-like problems where suboptimal paths are unacceptable. Additionally, we discuss MazeNet's ability to generalize beyond this specific regime, while noting that scaling to larger mazes is an interesting avenue for future research, albeit outside the scope of this work.

"Evaluation Metric and Experimental Design": We appreciate the reviewer's insight regarding the evaluation metric and experimental design. Accuracy, as used in our evaluation, reflects the ability to determine whether the shortest path is found, particularly in small-scale mazes where exact solutions can be determined using methods like Dijkstra's exhaustive algorithm. While this may not be a conventional metric for OARSMT problems, it aligns with our goal of ensuring deterministic correctness in this regime. To complement this, we have now included a wirelength ratio comparison to provide additional context. Furthermore, we present the average wirelength percentage increase conditioned on approximation errors. These results highlight the operational significance of errors in suboptimal paths and demonstrate how MazeNet, achieving 100% accuracy, avoids this issue entirely.

"Significance of This Research and Comparison with RCNNs": The significance of this work lies in demonstrating the capability of RCNNs to solve more complex graph-based problems through the incorporation of novel modules such as the Termination Condition (TC) module and reorganized recurrent blocks in a batch module. These enhancements enable MazeNet to achieve deterministic accuracy and runtime efficiency for small maze-like problems, addressing the trade-off between accuracy and speed that is seen in competing methods. As shown in Tables 1, 2, and Figure 8, MazeNet achieves optimality and practicality within the 11×11 regime, handling up to 8 terminals. This experimentally demonstrates that RCNNs can address complex graph-based problems in this setting, contrasting with prior RCNN applications, which have been limited to simpler tasks like connecting two nodes in a maze.

"Figures 2b and 2c Resolution": We acknowledge the issue with the resolution of Figures 2b and 2c. While the underlying data is represented in a 48×48 format, we will update these figures with higher-resolution versions in the revised manuscript to improve their clarity and visual quality.

"English Proficiency and Writing Style": We apologize for any lack of clarity or instances where the writing appeared to have traces of translation. We appreciate the reviewer’s feedback on this matter and are committed to improving the quality of the manuscript. If the reviewer could point to specific examples or sections where the language could be refined, we would be grateful and will address these issues in the revision.

"How does the proposed method differ from prior RCNN-based approaches for maze problems?": Thank you for highlighting this important question. Previous works using Recurrent Convolutional Neural Networks (RCNNs) have largely focused on simpler maze-related problems, such as connecting two nodes. These problems often have efficient optimal algorithmic solutions, making neural network-based approaches less compelling for such tasks. While these prior works are valuable for their exploration of architecture and extrapolation pipelines, the problems addressed remain insufficiently complex to advance beyond state-of-the-art methods. In contrast, our work applies RCNNs to an actual NP-hard problem. We extend existing architectures by introducing a novel Termination Condition (TC) module and reorganizing batch modules, enabling the model to solve small but relevant maze-like problems optimally. These contributions address a gap not explored in prior RCNN-based research.

"Does MazeNet require separate training for different grid and terminal configurations?": MazeNet’s architecture is designed to handle arbitrary maze sizes and terminal configurations without requiring separate training for each setup. However, in the absence of experimental guarantees for larger mazes or configurations, we acknowledge its potential limitations compared to approximation methods when scaling beyond the demonstrated 11×11 regime. Our focus in this paper is on achieving deterministic optimality in small mazes, where suboptimal solutions are unacceptable. While the architecture can generalize to larger mazes, this is outside the scope of the current work, and we aim to explore these possibilities in future research.

"What strategies can reduce the time and computational complexity of generating training data?": We are currently exploring the use of exact solvers to generate training labels, as these ensure the model learns to consistently find optimal solutions. Approximation methods, while computationally faster, are unsuitable for this purpose as they cannot guarantee optimality. Ensuring the correctness of training labels is a priority, even at the expense of additional computational effort. Moving forward, we aim to optimize the solver to accelerate training data generation while maintaining label accuracy.

"How does training time scale with increased problem complexity, and what optimizations could reduce this duration?": In our experiments, increasing maze size did not significantly affect training time. For the 11×11 regime, the training duration (~48.12 hours across four GPUs) was sufficient for the intended application. While this work does not focus on reducing training duration, we are actively investigating optimizations to scale the process efficiently for larger problems.

"Runtime Measurement in Figure 8": We appreciate the opportunity to clarify this point. The runtime reported in Figure 8 corresponds to executions without parallelization for smaller 48×48 images, as we observed that the overhead introduced by parallelization outweighed any potential benefits in these cases. However, for synthetic 1k×1k images (~500×500 node graphs), parallelization demonstrated significant runtime improvements, which is why those results are highlighted in Figure 14. We hope this clarification provides a clearer understanding of the context and focus of our runtime analysis.

"Evaluation on Small Mazes (11x11)": Thank you for pointing out the potential limitations of evaluating MazeNet on small 11x11 mazes. Our motivation for MazeNet, which we acknowledge was not sufficiently clarified in the original manuscript, is rooted in the observation that while probabilistic methods are often necessary for approximating shortest paths, there seems to be no justification for failing to discover the true shortest path in small-scale environments such as 11x11 mazes. This work focuses on applications where such environments suffice and suboptimal paths are unacceptable. Although our architecture supports arbitrary maze sizes for both training and testing, we concentrated on exploring the complexity introduced by varying the number of terminals rather than increasing the maze size. Scaling to larger mazes is beyond the scope of this work but represents an exciting direction for future exploration.

"Comparison with Modern Algorithms": We sincerely thank the reviewer for their thoughtful recommendation to include additional modern approaches, such as learning-based and reinforcement learning methods. We will carefully revise the manuscript to incorporate insights from [4] and other relevant recent methods as valuable considerations for further direction. Additionally, we wish to clarify that methods such as [1], [2], and [3] are specifically designed for input layouts in VLSI design and are not directly adapted to maze-like settings. This distinction will be explicitly highlighted in the revised version to provide a clearer understanding of the scope and focus of our work. Our primary emphasis in this paper is on achieving deterministic accuracy in small-scale environments, a feature that sets our approach apart from probabilistic methods. We will ensure this distinction is elaborated in the revised manuscript and greatly appreciate the reviewer’s guidance in helping us strengthen our work.

"TC Threshold (0.65)": The threshold value of 0.65 is a hyperparameter that was empirically chosen to achieve 100% accuracy on the test set. Although we did not perform a detailed ablation study of different thresholds, we observed that this value consistently produced the desired results in our experiments. We agree that further analysis of this parameter could provide additional insights and will include a discussion of this in future work.

"Tree Extension and Binary Matrix": Thank you for the opportunity to clarify this point. MazeNet operates as an image-processing technique rather than a traditional graph-based algorithm. As such, trees are extended irregularly during each iteration based on model predictions. Consequently, the notion of a specific number of cells added per iteration does not directly apply. This distinction highlights a fundamental departure from traditional graph-based algorithms, and we will revise the manuscript to make this explicit.

"Performance on Large Mazes (e.g., 256x256)": While MazeNet theoretically supports larger maze sizes, this work focuses on small, low-complexity environments where deterministic accuracy is critical. The scalability of MazeNet to larger mazes is an intriguing direction for future research. For the purposes of this work, however, we emphasize its effectiveness in small, maze scenarios. We will include a discussion of this limitation and future directions in the revised manuscript.

"Synthetic Benchmarks": Thank you for your detailed feedback regarding the evaluation on synthetic benchmarks and comparisons with recent methods. We originally defined the performance metric of accuracy as whether a method could find the shortest path for a given environment. MazeNet's motivation, which we acknowledge was not sufficiently clarified in the original paper, was rooted in addressing a gap in the literature. While probabilistic methods are often necessary for approximations of shortest paths, we believe that for a small 11x11-scale environment, discovering the true shortest path should be achievable. Thanks to your insightful comments, we have now included the wirelength ratio comparison in our analysis. However, we recognize that the wirelength ratio alone does not fully capture the operational significance of errors in determining the shortest path. To address this, we have also included an analysis of the average percentage increase in wirelength, conditioned on the occurrence of approximation errors. This addition will provide a more comprehensive evaluation of the method.

"Compare to old methods": We appreciate the reviewer highlighting recent literature and will cite and discuss each of these methods in the revised paper. While these contributions are important and solve related problems, they do not directly tackle our specific Obstacle-Avoiding Rectilinear Minimum Spanning Tree (OARMST) problem on planar, unweighted grid graphs with obstacles. That said, we will integrate in future work FLUTE as a benchmark due to its well-known suitability for such graphs. We also considered methods such as Chen et al.’s "A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction" and Kahng et al.’s "NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem." While these approaches are significant, Chen et al.’s method involves transforming layouts into weighted graphs, which diverges from our problem setting. Similarly, Kahng et al.’s method does not support obstacles, which limits its relevance to maze-like scenarios. Nonetheless, we will study these methods for inspiration in extending our work to related problems.

"Evaluation on real-world datasets": We recognize the importance of testing our method on real-world datasets. While our current focus has been on maze-like scenarios, we are exploring adaptations of our approach to other type of data, such as layout images, as suggested. For maze-like settings, we believe our method remains particularly suitable due to its consistent achievement of optimal solutions without errors and its demonstrated scalability.

"Figure 14 and accuracy discrepancy": Thank you for pointing out the potential confusion regarding Figure 14. To clarify, this figure shows the accuracy without the application of the Termination Condition (TC) module. The TC module is only applied during testing, where it ensures 100% accuracy, as presented in Tables 1 and 2. During training, the TC module is not applied, which explains why training accuracy does not reach 100%, as observed in Figure 6b. We will update the text to make this distinction clearer.

"Iterations": We appreciate the opportunity to clarify this aspect. The statement refers to the high-level module diagram abstraction of our approach, where the solution is achieved through a smaller number of abstract modules. We will ensure this is better explained in the revised version.