Train on Pins and Test on Obstacles for Rectilinear Steiner Minimum Tree
Authors: Xingbo Du
Ruizhe Zhong
Junchi Yan
Venue: NeurIPS 2025 poster ()
Keywords: rectilinear Steiner minimum tree
Obstacle-avoiding rectilinear Steiner minimum tree
reinforcement learning
end-to-end
Primary area: other
TL;DR: An end-to-end RL-based OARSMT construction method.

Abstract: Rectilinear Steiner Minimum Tree (RSMT) is widely used in Very Large Scale Integration (VLSI) and aims at connecting a set of pins using rectilinear edges while minimizing wirelength. Recently, learning-based methods have been explored to tackle this problem effectively. However, existing methods either suffer from excessive exploration of the search space or rely on heuristic combinations that compromise effectiveness and efficiency, and this limitation becomes notably exacerbated when extended to the obstacle-avoiding RSMT (OARSMT). To address this, we propose OAREST, a reinforcement learning-based framework for constructing an Obstacle-Avoiding Rectilinear Edge Sequence (RES) Tree. We theoretically establish the optimality of RES in obstacle-avoiding scenarios, which forms the foundation of our approach. Leveraging this theoretical insight, we introduce a dynamic masking strategy that supports parallel training across varying numbers of pins and extends to obstacles during inference. Empirical evaluations on both synthetic and real-world benchmarks show superior effectiveness and efficiency for RSMT and OARSMT problems, particularly in handling obstacles without training on them. Code available: https://github.com/Thinklab-SJTU/EDA-AI/.

Train on Pins and Test on Obstacles for Rectilinear Steiner Minimum Tree
Xingbo Du, Ruizhe Zhong, Junchi Yan*
School of Computer Science & School of Artificial Intelligence, Shanghai Jiao Tong University (duxingbo,zerzerzzezz 22120rz222221 hww.e//sayaannniinaaaasaaa @sjjt. edu. cn
Abstract
Rectilinear Steiner Minimum Tree (RSMT) is widely used in Very Large Scale In- tegration (VLSI) and aims connecting of pins using rectilinear edges while minimizing wirelength. Recently, learning-basee methods have been explored tackle this problem effectively. However, existing methods either suffer from excessive exploration of the search space or rely on heuristic combinations that compromise effectiveness and efficiency, and this limitation becomes notably exac- erbated when extended to the obstacle-avoiding RSMT (OARSMT), To address this, we propose OAREST, reinforcement learning- based framework for constructing an abstacle-Avoiding Rectilinear Edge Sequence (RES) Tree. We theoretically establish the optimality of RES in obstacle-avoiding scenarios, which forms the foundation of our approach. Leveraging this theoretical insight, we introduce a dynamic masking strategy that supports parallel training across varying numbers of pins and extends to obstacles during inference. Empirical evaluations on both synthetic and real-world benchmarks show superior effectiveness and efficiency for RSMT and OARSMT problems, particularly in handling obstacles without training on them. Code available: https:// / gighub...... com/ www.ccommmiiiieee Thinklab SJTU/EDA AI/.
1 Introduction
Rectilinear Steiner Minimum Tree (RSMT) and its obstacle-avoiding version named OARSMT are critical combinatorial problems in electronic design automation (EDA) in Very Large Scale Integration (VLSI) design [1, 2, 3]. As an NP-complete problem [4], the goal of RSMT is to connect a given set of pins using rectilinear edges, i.e., edges that are parallel to the axes, while minimizing the total wirelength. Recently, the RSMT problem [5, 6, 8, 9], well as the entire EDA community [10, 11, 12, 13], has received extensive attention from the machine learning (ML) community. However, with the increasing number of nets in modern technologies and particularly the incorporation of obstacles, existing ML-based methods suffer from various challenges.
We summarize the critical challenges for ML-based approaches in both vanilla RSMT and OARSMT problems in Table including: 1) Lack of efficient and accurate representations: Efficient repre- sentations are essential for reducing the searching space (e.g., the action space in the reinforcement learning (RL) agent), which can otherwise become excessively complex and computationally exhaus- tive. Accurate representations, the other hand, enable ML approaches learn the global optimum in an end-to-end manner without relying on post-processing [7, 9] or integrating heuristics [8]. 2) Multi-degree GPU parallelization: Existing ML-based techniques [5, typically require inputs of the same size, limiting their ability to handle multi-degree instances (i.e., instances with varying numbers of pins) in parallel. 3) Obstacle avoidance: The introduction of obstacles significantly increases problem complexity and further exacerbates the above two challenges.
"Corespondence to: Junchi Yan. This work was partly supported by NSFC (92370201).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparisons of ML-based methods.
obsado
Method
Representation
End-to-Kad
Multi-Degree GPU-Paralleization
Obstacle Avoidance
REST [5]
(Oysimal)
[SST
EPS
Chen et al. [7]
Steiner Points
auaillary pois.
Chen et al. [9]
Steiner Points
QAREST (ouns)
RES (Optimal)
Figure 1: a) Different components. b) Rectilinear edges in an OARSMT.
To address these challenges, first extend the rectilinear edge sequence (RES) representation, originally proposed in REST [5], to the OARSMT problem. Such an extension nontrivial as the problem's structure is fundamentally altered. We theoretically demonstrate that RES achieve optimality for both RSMT and OARSMT problems.
Building upon these theoretical insights, we propose novel RL-based framework OAREST (Obstacle- Avoiding Rectilinear Edge Sequence Tree), designed to tackle multi-degree GPU parallelization and dynamic obstacle avoidance simultancously. Within this framework, introduce dynamic masking strategy that selectively activates candidate corner vertices of obstacles, ensuring efficient and obstacle-aware decision maaiing. Empirical results on both synthetic and industrial benchmarks validate the effectiveness and efficiency OAREST in solving RSMT and OARSMT problems. Particularly, the obstacles be avoided effectively in OARSMT problems without training any obstacles. The main contributions are listed as follows:
1) Theoretical findings and derived RL framework: We prove the optimality of the rectilinear edge sequence (RES) representation for the obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem. Inspired by this, we introduce OAREST, an end-to-end RI. framework based on the RES, which combines theoretical optimality with computational efficiency. To the best of our knowledge, OAREST is the first ML-based approach handling obstacles without training obstacles.
2) Novel dynamic masking strategy: Within the RL framework, we devise novel dynamic masking strategy that can not only handle multi-degree parallel training/inference GPUs but also dynamically activate candidate obstacle vertices for effective obstacle avoidance. Thus, the OARSMT problems can be handled without training on any obstacles.
3) Empirical advancements and efficient obstacle handling: We perform experiments extensive instances with/without obstacles and demonstrate comparable performance to advanced baselines. The results particularly highlight OAREST's robust capabilities in managing parallel inference and avoiding obstacles efficiently.
Preliminaries and Main Theorem
Before introducing the RI. framework, we first propose key definitions in Sec. 2.1 and state the OARSMT problems in Sec. 2.2, based on which we introduce the main theorem Sec. 2.3 that demonstrates the optimality of rectilinear edge sequence (RES) in OARSMT problems.
2.1 Definition
We introduce various definitions in OARSMT problems and visualize components in Fig. 1(a).
P1: Definition 2.1. [Rectilinear Steiner Tree, RST] Given finite set of pins P (Po- (P. ... :Pn-1)
with each pin ps having fixed coordinates (2,, Y:), a rectilinear Steiner tree (RST) a tree that connects all pins and some non-pin auxiliary points, where each edge is parallel the coordinate axis. The non-pin auxiliary points are named Steiner points, which are used to minimize the total length.
Here, each edge is either horizontal or vertical. OARSMT problems, RSTs are required to avoid overlapping with rectangular obstacles, which are defined as:
We use 'pin' to distinguish from 'obstacle vertex' and 'Steiner points', and collectively name them 'points'.

---

Definition 2.2. [Rectangular Obstacles] Define O = foo, 01, .0m-1 as a group of rectangular
((rd)) composed of four vertices in its left-down regions. Each obstacle o; = (o]44) of (tu) _/(r)) 1i
(Id), left-up (lu), right-up (ru), and right-down (rd) corners. Denote these vertices as V(O).
Note that any complex rectilinear obstacle (e.g., rectilinear polygons) can be easily achieved by combining different rectangular obstacles. To formulate RSTs in an OARSMT problem, we apply the rectilinear edge sequence (RES) [5] representation our framework, defined as:
Definition 2.3. [Rectilinear Edge Sequence, RESJ For given set of pins P {po, .., , Pn- its RES is a sequence with n - 1 rectilinear edge pairs ((vo, hu), (V1, k1), ... (Un-2, (n-2)), where 0e, h4 {0, 1....
2} denotes the indices of pins.
Note that rectilinear edges are non-commutative rectilinear geometry, i.e., (v, h) A (h, v). Specifi- cally, (v, h) denotes path where the vertical edge starts at followed by horizontal edge ending at h. A visualized example of rectilinear edges is shown in Fig. 1(b), where (P2, 01) and (V1, P2) two distinct rectilinear edges. To keep RES always valid in RSMT construction problem, RES is required to satisfy: 1) Uo * ho; 2) For each rectilinear edge pair (14, h2), exactly one of v, h2 is visited before by previous rectilinear edge pair, and the other is not. Details given by [5] is moved to Lemma A.4 in Appendix A. Other definitions that are only related to the proof of our main theory, including Hanan Grid and extended Hanan Grid, can be found in Appendix A.1.
2.2 Problem Statement
Based on the definitions, we formulate OARSMT as:
Definition 2.4. [Obstacle-Avoiding Rectilinear Steiner Tree, OARSMT] Given finite set of pins
P = (Po. PPoPP.... Pı. ...... Pn-1} } and a set of rectangular obstacles O = {ou, 01, ... 0m-1), an obstacle-
avoiding rectilinear Steiner tree (OARSMT) is defined as:
T = argmin Σ le/.
TET eEE(T)
under constraints: 1) T is tree connecting all pins in 2) Ve E E(T): e is parallel to coordinate axes, 3) Ve E (T), Vo, E O : e n int(o;;) = 0, 4) V(T) P are Steiner points. Here, is the set of all rectilinear Steiner trees in terms of P and O Additionally, le| denotes the Manhattan length of edge e, E(T) represents the set edges in tree T, V(T) is the set of vertices in T, and int(o;) denotes the interior region of obstacle o;.
Intuitively, OARSMT aims to obtain a rectilinear tree with minimum length that avoids obstacles.
2.3 Main Theorem
Theorem 2.5. [Optimality of RES in OARSMT) For any set of pins P = (po. PI. PP-11 and a set of rectangular obstacles O (oo, 01, 0m-1), 1,, an optimal RES of (O) can always be found such that its corresponding tree is an optimal OARSMT for P under obstacles O. Here, (O) C ((O) a subset of the corner vertices of all obstacles.
This theorem demonstrates that an optimal RES can always be found to construct an optimal OARSMT. The proof can be found in Appendix A.3. Note that Theorem 2.5 gives us an insightful intuition: In order to construct an OARSMT, we are only required to construct RES that connects all pins and subset of corner vertices of obstacles.
3 Obstacle-Avoiding Rectilinear Edge Sequence Tree
Overview. We propose an RL-based framework to handle OARSMT. The overall pipeline is given in Fig. 2, while the connecting process of the rectilinear edge sequence (RES) is shown by a simple toy example in Fig. 2(d). Following [5], we use actor-critic networks to generate rectilinear edge sequence (RES) in Sec. 3. To accommodate multi-degree parallelization and obstacle handling, we introduce a novel dynamic masking strategy in Sec. 3.2. In Sec. 3.3, we provide a detailed discussion on our focus on multiple small instances OARSMT problems and analyze the time complexity of the proposed framework.
3

---

Actor Network
Input Masking
Masking
mask
Connecting Process
Positions
Encedor
Decodler
comple
Rechilineor Edge
Outpout
RES
Vertex Positions
(N
b Oritic Network
obstacle wett
Masking Strategy
Pinn Positions
vonila distributiin
Podking
poiding
Actor
Critic Erpoddrr
irput mosking
rusk all verriees
Predictor
obstacle mosking
Actual Length
Predicted Longth
masking
44 scTivoted veriices
Meon Square Error
octiections marking
Pipeline of OAREST. Actor network that generates the rectilinear edge sequence (RES) step-by-step with dynamic masking strategies. b) Critic network that fits the actual length of RES. c) Dynamic masking strategies, including input masking, obstacle masking, visited masking, and activation masking, that enable the RES generation with multi-degree forward passing and obstacle avoidance. Visualization of the connecting process of OAREST a toy sample with 3 pins (Po.P1. P2) and obstacles (6p, b2).
Figure 2:
3.1 Generate RES using Actor-Critic Network
Similar to the objectives of REST [5], utilize actor-critic network to learn the construction of the rectilinear edge sequence (RES). Given the positions all pins P = {po. P1. Pn--1,, ). the actor network Actor()(P:E) with parameters &. shown in Fig. 2(a), takes series of sequential generating r,
actions to generate the elements of the RES r E R(P) and yields the probability where (PP)) is the of all possible RES for P. The actor network here is trained generate the optimal RES. The critic network Critic(P; with parameters Ç, as depicted in Fig. 2(b), predicts the length of the RSMT of P, which is trained approximate its actual length L(P, r). Note that L(P, r) is actually the evaluation of the RES, which can be achieved linearly [5] and is assumed to approximate the actual RSMT length accurately.
More specifically, for each given pin set P. the objective of the actor network is to minimize the expected advantage of the RSMT generated by Actor(r(P:E] and use the policy gradient algorithm REINFORCE [14] to compute the gradient:
ming B(P)(P) (Critic(P: () L(P,r) Actor(r(P:E).
Conversely, the critic network's s objective is to minimize the mean square error (MSE) between its predicted length and the actual length of RSMT:
min Ey- RCP) Eei (CCiitic(P:)) L(P
practice, given batch of pin sets (Po, PI, Po-1), one RES r; is generated for each Pi(i (0, ... .b 1}}. Consequently, Eq. 2 and Eq. 3 can be reformulated as:
min {
((P)))( Acooyyy)tttorr.PPPPiPP T=1
min
-
These objectives are optimized simultaneously. In inference, only Actor(r,(P::E) required to generate the RES with the highest probability, Note that both training and inference end-to-end.

---

3.2 Dynamic Masking
The key issues in Sec. 3.1 are twofold: the actor-critic network requires inputs and outputs of fixed sizes to enable GPU parallelization, and 2) obstacle constraints are not incorporated. To address these issues, as illustrated in Fig. 2(c), we propose a dynamic masking mechanism, which dynamically adjusts valid action spaces during each decision step, enabling efficient handling of variable input sizes and the integration of obstacle constraints.
First, we use tensor E [xx(+++))x2 to represent the input of the actor net, where b is the batch
size, ît is the max number of pins of the pin set in batch {P: )a-1 )= and vi is the max number of obstacles in {O:)==o The value '4' here means the four corner vertices of an obstacle, and '2' means the x- and y-axis coordinates. For the instances with n(< n) pins or m(< m)) obstacles, we pad the corresponding elements to -1 in the input tensor. The dynamic mechanism is then devised with the following components:
Input/Obstack Masking. The input mask is devised to ignore the computations for invalid elements. is constructed using a matrix Miaput E {0, 1) 1ix((4+ The obstacle mask ensures that the actor network does not select obstacle vertex the first element of the RES, which is constructed using matrix Mob
{0, 1) (++4m)) Each element of M and Mob is defined as:
M Mimput
fo, I,,00 = I1 = 11,
M
0, if if
(5)
1,
otherwise,
11, otherwise.
Visited/Activation Masking. Based on the properties of the RES (as described in Sec. 2.1), each rectilinear edge must have exactly one visited and one unvisited element. The visited mask enforces this condition. It is represented by matrix Mvisited E {0, 1] (a On the other hand, the activation masking activates parts of the obstacle vertices and used to avoid obstacles when generating the RES, which is initialized as M = M Each time newly generated rectilinear edge overlaps with one or more obstacles, the elements in M corresponding to the corner vertices of these obstacles are activated. Each element of M visited and Maet is defined as:
0, if j is an element in RES ris
[0, j is inactivated, 1, otherwise.
vilitted
M b. =
(6)
1, otherwise.
When newly generated rectilinear edge does not overlap with obstacles, the mask is re-initialized as M = Mu In practice, the actor net sequentially determines which pin or vertex to generate. Each action is based on probability distribution matrix E (++(4+))) The combination of dynamic masks is then used select the elements in RES:
To begin with, we sample a batch of start points from Satart S o (Mimput Mob), where is the Hadamard product (element-wise multiplication) and A represents logical 'AND', which evaluates to true only when both operands are true. This ensures that only valid pins are selected as the first element of RES.
For a batch of rectilinear edges, we select a batch of visited points from Svisited = (1 visited) ). For the same batch of rectilincar edges, select batch of unvisited points from gunvisited S (Minput, A M A Meat). This implies that the selected points must be valid unvisited ones while M ensures that the rectilinear edge does not overlap with any obstacles, as governed by Eq. 6.
Equipped with the dynamic masking strategy, OAREST is capable of addressing the multi-degre training and inference for RSMT problems, and can infer directly on OARSMT problems without training with any obstacle. Functions and executions of different masks are summarized in Table 2.
3.3 Remarks
Intuition on generalization to obstacles and strategy. Theorem 2.5 suggests that it suffices to construct RES that connects all pins and a subset of obstacle corner vertices. The RL agent's 's goal then to connect these pins and selected corners. Since OAREST trained only on pins but must also connect corner vertices, natural idea is to treat corner vertices pins. However, this raises
5

---

Table 2: Functions and executions of different masks.
Masking
Function
Execution
Achieve multi degree GPU
Input
Mask invalid elements the heginning.
parallelization.
Avoid choosing corner vertex as the first element of the RES; 2) Avoid unnecessary corner vertex
Mask all obstacle vertices at the beginning. 2) When a newly generated rectilinear edge does not overlap with ohstacles, re-initialize the activation mask as obstacle mask.
Obstacle
connection.
Construct valid RES following the criterion of Lemma A.4,
Use masking generate visited point and unvisited point for each rectilinear edge.
Visited
Each time a newly generated rectilinear edge overlaps with one or more obstacles, the elements in the activation masking corresponding to the corner vertices of these obstacles activated.
Avoid generating rectilinear edges that overlap with obstacles.
Activation
two issues: (1) not all corner vertices need to be connected, and (2) the resulting edges may overlap obstacles. Accordingly. obstacle masking is used to avoid unnecessary comnr-vertex connections (issue 1), and an activation mask is used to prevent overlap with obstacles (issue 2). Notably, both masking strategies can be applied purely at inference.
Time Complexity for Inference. The overall time complexity for inference is O ((n rit) Tatchh /b). where Thach represents the inference time for single batch, and b denotes the batch size. This complexity arises because all computations within the actor network are linear with respect to ñ + m. The high efficiency of the framework can thus be attributed to the ability to handle large batch sizes, particularly for multiple small-sized instances.
Single Large Instance vs. Multiple Small Instances. Lots of previous works [7, 8, 9] primarily focus on constructing OARSMTs of large-scale instances with hundreds or even thousands of pins; however, these approaches often rely on heuristic tools, which limit their performance in GPU parallelization. In contrast, this paper takes an orthogonal approach by focusing on OARSMT construction for multiple small instances, achieving significant improvements in parallel efficiency. Furthermore, its focus small-scale instance construction makes it more aligned with practical scenarios in certain industrial applications. As shown in Table 3, we analyze benchmarks from the ICCAD19 [15] global routing contest, highly regarded industry competition. The results reveal that most nets contain fewer than 10 pins. Specifically, the proportion of nets with more than 100 pins is only 0.002%, highlighting the importance of efficient inference for multiple small instances.
4 Experiments
Experiments were conducted on machine equipped with an AMD EPYC 7402 24-Core Processor, an NV GeForce RTX 4090, and 512 GB of RAM. To ensure robust evaluations, experiments were repeated using three distinct seeds. The experimental protocols are detailed Section 4.1, while the main results for RSMT/OARSMT are presented in Sections 4.2/4.3. In Sec. 4.4, we perform ablation studies, show generality on untrained degrees, and evaluate the performance on real-world circuits.
4.1 Experimental Protocols
Datasets. We evaluated the proposed method using two datasets. The first consists of randomly generated test data as described by REST [5]. This dataset includes varying degrees ranging from 5 to 50 increments of 5, referred to as R5, R10, etc. Each subset contains k test instances. To assess the method's 's capability in handling obstacles, we further introduced 5 and 10 random obstacles to the test cases in R5, R10, etc. The second dataset consists of real-world global routing benchmarks from ICCAD19 [15], which is directly evaluated using the model trained on R5-R50.
Metrics. We employ the total wirelength as the primary metric for RSMT and OARSMT, which is calculated using the total Manhattan distance of tree:
=
length(e)= = Σ
(| - 2z5 + 18 Ug(),
(7)
333
(N.

---

Table 3: Statisties of nets (x10²) with different numbers of pins in ICCAD19 [15] benchmark.
QuaStteinct
Methode
BIS
Pins
Nete (K1(P)
aydl8 Jcxi[ [-10)
proportion (8)
+ Nets [XP(
propertion (1)
519
$7,00
1.791
57.17
5-10
387
S8.12
1.197
18.21
11:20
13
1.20
40
1:28
21-30
0.42
13
0.41
31-40
16
1.58
1.49
41-50
0.44
13
0.42
Figure 3: Runtime (seconds) of RSMT methods for testing 10 k instances on varied pins.
51-100
11
1.08
32
1,02
2100
0.02
0.02
0.06
0.00
where & is the edge set of tree. The average percentage error (L - Law Log is then utilized to measure the gap from the optimal solution opp obtained by the exact algorithm GeoSteiner [16]. For OARSMT problems, we further employ the overlap metric:
overlap(e, ok) f1
if e e int((o))) * Otherwise,
overlap(e, oR),
(8)
3E k=
where int(o:) is the interior region of obstacle Og E
Baselines. RSMT baselines include GeoSteiner [16]. R-MST [17], BGA [18], FLUTE [19), and REST [5]. For OARSMT, we evaluate wirelength, overlaps, and runtime against GeoSteiner [16],
OARST [20], and OARSMT [21], respectively, Details are shown in Appendix B.2.
Other Settings and Results. We show other experimental settings, including the model structures of the actor-crice critic networks, hyperparameters, training/inference strategies, and more visualizations in Appendix B.3 B.6.
4.2 Main Results of RSMT
Table 4 shows the average percentage error algorithms compared to the exact algorithm GeoSteiner [16] across various scales of random instances. R-MST [17] has substantial gap from the optimal GeoSteiner. Other approaches, including BGA [18], FLUTEE [19], and REST [5] demonstrate much better performance, achieving an average error of less than 1%. In partieular, FLUTE (A = 18) and REST (T 8) perform strongly in all these instances. Building on this strong foundation, OAREST surpasses other baselines R5-R40 instances and achieves competitive performance on R45 and R50. A visualized example of a 50-pin instance is shown in Fig. 4(a).
The advantages of OAREST in [5], we adopt a batch size of 100 k/dgree for inference. As illustrated in Fig. 3, while GeoSteiner produces optimal results, its runtime grows exponentially with the number of pins. FLUTE (A = 18) offers significantly better efficiency than GeoSteiner, but its runtime still increases considerably as the number of pins grows. In contrast, the inference time of OAREST scales almost linearly with the number of pins, slightly exceeding that of REST. The additional time mainly stems from the inspection of obstacles. Note that while REST performs pretty well in both wirelength and runtime, struggles with the multi-degree inference problem. This limitation results in a sharp increase in runtime when dealing with variable pin counts in real-world circuits. We will further investigate this issue in Sec. 4.4.
pronounced in terms of runtime. In line with the setup
4.3
Main Results of OARSMT
We evaluate the wirelength, overlap, and runtime of GeoSteiner, OARST, ObSteiner, and OAREST in Fig. 5, where GeoSteiner [16] and ObSteiner [21] are used as the exact solvers for the RSMT and OARSMT problems, respectively. OARST implemented by [20] serves as approximation solution for OARSMT. In this setting, we randomly add 5 and 10 obstacles to R5-R50 test cases proposed by [5], using full batch size of k0 Fig. 4(b) visualizes instance with 20 pins and 10 obstacles.
In Fig. 5(a), all algorithms, including the exact OARSMT solver, have a gap compared to GeoSteiner due to the additional complexity of accounting for overlaps. While the wirelength achieved by OAREST slightly longer than that of the exact OARSMT solution, it demonstrates clear advantage over the approximation--ant based OARST.

---

Table 4: Average percentage error (%) of RSMTs compared to the exact algorithm GeoSteiner [16]. Best results except GeoSteiner are bold.
GeoSteiner [16]
R-MST
BGA
FLUTE [19]
REST [5]
OAREST
Instances
[17]
[18]
=
A 18"
T= 1"
T 8"
(ours)
0.00
10.91
0.23
0.00
0.00
0.02
0.00
RI0
0.00
11.96
0.48
0.12
0.04
0.23
0.01
0.01
0.000
R15
0.00
12.19
0.53
0.55
0.06
0.45
0.03
0.03 0,001
R20
0.00
12.41
0.57
1.03
0.11
0.56
0.07
0.06
0,001
R25
0.00
12.47
0.58
1.44
0.18
0.69
0.12
0.10 + 0,001
R30
0.00
12.56
0,60
1.83
0.23
0.77
0.16
0.15 0.004
R35
0.00
12.63
0.62
2.13
0.26
0.84
0.21
0.19 0.002
R40
0.00
12.65
0.63
1.05
0.29
0.86
0.25
0.24 0.001
R45
0.00
12.67
0.63
1.07
0.30
0.98
0.32
0.31 - 0.002
R50
0.00
12.72
0.64
1.12
0.29
1.01
0.36
0.36 = 0.001
A=3/18 and T=1/8 different versions of FLUTE and REST, which illustrate Appendix B.2.
(a) RSMT with 50 pins.
(b) OARSMT with 20 pins and 10 obstacles.
Figure 4: a) A pair of RSMTs with 50 pins, and b) pair of OARSMTs with 20 pins and 10 obstacles, respectively run by the optimal GeoSteiner (left of each pair) and OAREST (right of each pair).
POK-O
00
44
(a) Wirelength.
(b) Overlap (log-axis).
(c) Time (log-axis).
Figure a) Average percentage error on task OARSMT compared to GeoSteiner; b) Average overlap on task OARSMT of GeoSteiner and OAREST; c) Time overhead on task OARSMT of GeoSteiner, OARST, ObSteiner, and OAREST.
Fig. 5(b) shows the average overlaps produced by GeoSteiner and OAREST. As GeoSteiner does not consider obstacles, it inherently suffers from significant overlaps. OAREST, on the contrary, reduces the overlap negligible level. Specifically, OAREST achieves >9%%/96% success rates (zero- overlap solutions) for instances with 5/10 obstacles, respectively. Detailed statistics can be achieved Appendix B. Such success rates are significant, as no obstacle visible during the training stage. The small proportion of failed cases (1-4%) typically have minor overlaps in few rectilinear edges after performing OAREST. These can be resolved using maze routing postprocessing [22, 23] with <1% additional runtime compared to OAREST's inference time, maintaining practical feasibility while preserving computational advantages. We leave further reduction of overlaps as future work.
In Fig. 5(c), we compare the time overhead of the four algorithms. Unsurprisingly. the exact OARSMT solver (ObSteiner) has the highest computational cost, reflecting the inherent complexity of solving OARSMT problems exactly. The approximation solution, OARST, achieves a faster runtime than GeoSteiner. Importantly, we are delighted to see that OAREST outperforms all baselines in most instances, with its runtime being minimally affected by the presence of obstacles. This efficiency is attributed to the GPU parallelization capabilities and the linear scalability OAREST with respect to obstacle handling.
8

---

2.5
So Errer
DAREST w/ #ytrs
Degrue 3-10
Aetoogg Puranttuu Rivee (80)
CAREST WY Fate
Drggren 80.40
Percere treve
Nathoda
Degres
1.55
Degres 30-40
Degrus
GTANEST touade
(T-4))
1.0-
Degous 3-50
00.5-
00
(a) Performance trained on varied degrees.
(b) Generality.
(c) Error/Time.
Figure 6: a) Average percentage error of OAREST trained on a varied range degrees. Average percentage enror of OAREST (40 - 50) and OAREST (3 50) on random instances with degrees 50 100. c) Experiments on ICCAD19 global routing benchmark.
4.4 Other Experiments
Ablation Studies. Equipped with the dynamic masking strategies, OAREST is capable of training or inferring across a varied range of degrees. Our training strategy first follows REST [5] that trains on single degree by one, and is then followed
quick finetuning process jointly across range of degrees, including (3, 10), (10, 20), (20, 30), (30, 40), (40, 50), and the full range of (3, 50). 50) has robust performance on all degrees; however, the
As shown Fig. 6(a), OAREST highest accuracy is consistently achieved by models trained specifically on smaller, targeted ranges of degrees. For instance, though OAREST (3 10) performs poorly on large degrees (15 50), ranks first for degrees 5 and 10. This empirical observation could offer users the flexibility to balance parallel inference and accuracy.
Generality on Untrained Degrees. OAREST has a strong capability to extend to untrained degrees. To evaluate this, we tested OAREST (40-50) and OAREST (3-50) on RSMT instances with degrees between 50 and 100. As shown in Fig. 6(b), the average percentage error for both models increases as the number of pins grows. However, even for degrees 51 100, which were not included in the training process, the error remains below 3%. highlighting the robustness of OAREST in handling unseen degrees.
Evaluation on Real-world Circuits. We evaluated OAREST on the ICCAD19 global routing [15] benchmark. In line with REST [5], we focused instances with degrees between and 100, as instances with degrees > 100 constitute only 0.002% of the dataset (see Table 3). In Fig. 6(c), OAREST outperforms baselines in efficiency with the second-best wirelength (inferior the exact algorithm GeoSteiner). The time of OAREST's is nearly half that of REST (T=8) and 1/7 of GeoSteiner, showing the scalability real-world benchmarks.
5
Related Work
5.1 Rectilinear Steiner Minimum Tree (RSMT)
Rectilinear Steiner Minimum Tree (RSMT) algorithms can be mainly divided into approxima- tion, heuristics, and machine learning (ML). Early approximation approaches target near-optimal solutions with efficiency, including R-MST [17] providing 1.5-approximation, [24] approaching apraxxproinittion and Arora [25] providing (1 + -)aaproximmation Apart from these methods, heuristic-basee approaches achieve greater efficiency and accuracy, where BGA [18] utilizes heuris- ties to optimize edges based on the pre-computed R-MSTs. FLUTÉ [26, 19]. a widely used industrial tool, leverages a lookup table for small instances with < pins and partitions larger instances into smaller sets for processing. GeoSteiner [16] is also heuristic- based but achieves exact solutions by generating all candidate Steiner Trees.
ML-based methods, especially reinforcement learning (RL), are used for constructing Steiner trees in RSMT. REST [5] proposes the rectilinear edge sequence (RES) and an RL framework based on actor-critic networks to generate the edge sequence, and EPST [6] extends the problem to Octilinear Steiner Minimum Tree (OSMT). Moreover, HubRouter [2] applies the RL-based RSMT to global

---

routing problems. NN-Steiner [27] utilizes four neural network components to replace the consuming dynamic programming in [25].
Apart from the ability to handle obstacles, our OAREST addresses the multi-degree GPU paralleliza- tion in current RL--based methods, which is crucial in VLSI designs.
5.2 Obstacle-Avoidingg Rectilinear Steiner Minimum Tree (OARSMT)
Based on the vanilla RSMT problems, various works study the strategies to avoid obstacles. Tradi- tional solutions [22, 23] propose heuristic approaches based maze routing, while EBOARST [28] utilizes a four-step algorithm to efficiently handle obstacles. FOARS [29] addresses obstacles based on FLUTE [26]. [20] proposes OARSMT algorithm by sequentially using OASG, and OARST, achieving improved wirelength. Moreover, GSLS [30] proposes guiding solution-based local search method solve the OARSMT problem, while [31] focuses selecting Steiner points handle obstacles, Apart from the approximation and heuristic algorithms, exact algorithms of OARSMT include [32, 33, 34, 21], which study edge-disjoint full Steiner trees (FSTs) building upon the GeoSteiner [16] in vanilla RSMT.
Similar to RSMT problems, RL is also widely used in OARSMT. For instance, [9] utilizes an RL agent to select Steiner points and follows a Maze-router- based Prim's 's algorithm to form an OARSMT. [7] trains an RL agent based the small grids of layouts and predicts the Steiner points. It also depends on a Maze routing as postprocessing. [8] performs a fast RI agent to connect pins, but requires the pre-construction of Obstacle-AVe Avoidding Spanning Graph (OASG) and separates it into shortest path forest (SPF), and finally, a local optimization strategy is employed for postprocessing.
Though these RL-based OARSMT algorithms can effectively handle obstacles, they either suffer from a large action space [7] or combine with heuristics [8, 9], lacking the efficiency of GPU parallelization.
5.3 Beyond RSMT in VLSI design
Beyond RSMT, various works in VLSI design employ reinforcement learning (RL) to address specific problems. For example, MaskPlace [35] uses RL to place macros sequentially during placement. Beyond macro placement, MaskRegulate [36] uses an RL policy to adjust existing layouts with dense rewards. Additionally, HAVE [37] introduces hierarchical adaptive multi-task RL and achieves higher hypervolume. In floorplanning, CBL [38] designs floorplanner using the Corner Block List representation under an RL framework. Also within an RL framework, FlexPlanner [39] extends the problem to 3D floorplanning. For routing, Liao et al. [40] employ deep Q-network (DQN) for global routing. Note that RSMT is an essential subproblem in routing, where we envision that OAREST makes promising contribution.
Beyond VLSI design, combinatorial optimization problems form the fundamental basis of various applications, such as molecule generation [41, 42] and protein-protein docking [43]. Within the domain of EDA, our work provides train-and-test perspective on generalization, specifically regarding varying degrees and obstacle constraints.
6 Conclusion and Outlook
We have introduced an RL-based OARSMT solver that supports multi-degree parallel inference and dynamic obstacle avoidance. The main contributions of this work include the theoretical demonstration of the optimality of the rectilinear edge sequence (RES) in OARSMT problems, as well as empirical validation both synthetic and real-world benchmarks.
Despite its strengths, OAREST has some limitations that present potential areas for future research: 1) In instances with a large number of pins, the error in OAREST increases due to its training being limited to degrees between 3 and 50. 2) some extreme scenarios, overlaps may still oceur with OAREST. To address these issues, Training OAREST on instances with obstacles to further improve its ability to avoid obstacles while maintaining minimal wirelength; 2) Testing OAREST on more complex real-world global routing datasets and incorporating additional constraints, such as overflow; 3) Developing methods to completely eliminate overlaps in OARSMT problems.
propose the following directions for future work: I)
10

---

References
[1] Sheng-Fn David Lin and Dae Hyun Kim. Construction of all rectilinear steiner minimum trees the hanan grid and its applications vlsi design. IEEE Transuctions on Computer-Aided Design of Integrated Circuits and Systems, 39(6): 166-1176, 2019.
[2] Xingbo Du, Chonghua Wang, Ruizhe Zhong, and Junchi Yan. Hubrouter: Learning global routing via hub generation and pin-hub connection. Advances in Neural Information Processing Systems, 36: 1-10, 2023.
[3] Ruizhi Liu, ZhishengZeng, Shizhe Ding, Jingyan Sui, Xingquan Li, and Dongbo Bu. Neuralsteiner: Learning steiner tree for overflow-avoiding global routing chip design. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[4] Michael R Garey and David S. Johnson. The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 32(4):826 834, 1977.
[5] Jinwei Liu, Gengjie Chen, and Evangeline FY Young. Rest: Constructing rectilinear steiner minimum tree via reinforcement learning. In 2021 58th ACM/IEFE Design Automation Conference (DAC), pages 1135-1140. IEEE, 2021.
[6] Zhenkun Lin, Genggeng Liu, Xing Huang. Yibo Lin, Jixin Zhang, Wen-Har Liu, and Ting-Ch Chi Wang. A unified deep reinforcement learning approach for constructing rectilinear and octilinear steiner minimum tree. IEEE Transactions on Computer-Aided Design of Integruted Circuits and Systems, 2024.
[7] Po- Yan Chen, Bing-Ting Ke, Tai- ChinChen Lee. 1-Ching Tsai, Tai-Wei Wei Kung, Li- Yi Lin, En Cheng Liu, Yun-Chih Chang, Yih-L.ang Li, and Mango C-T Chao. reinforcement learning agent for obstacle-avoiding rectilinear steiner tree construction. In Proceedings of the 2022 international symposium on physical design, pages 107-115, 2022.
[8] Zhenkun Lin, Yuhan Zhu, Xing Huang, Liliang Yang, and Genggeng Liu. Obstacle-avoiding rectilincar steiner minimal tree algorithm based on deep reinforcement learning. In 2023 International Conference on Artificial Intellignnce of Things and Systems (AloTSys), pages 149-156. IEEE, 2023.
[9] Liang-Time Chen, Hung-R Ru Kuo, Yih-Lang Li, and Mango C-T Chao, Arbitrary sisttarr--izzeeea size multi-layer oarsmt router trained with combinatorial monte-carlo tree search. In Proceedings of the 61st ACM/IEEE Design Automation Conference, pages 1-6, 2024.
[10] Zijie Geng, Jie Wang, Ziyan Liu, Siyuan Xu, Zhentao Tang. Shixiong Kai, Mingxuan Yuan, Jianye HAO, and Feng Wu. LaMPlace: Learning optimize cross-stage metrics in macro placement. In The Thirteenth International Conference on Learning Representations, 2025.
[11] Pengyi Li, YAN ZHENG, Hongyao Tang, Xian Fu, and Jianye HAO. Evorainbow: Combining improve- ments in evolutionary reinforcement learning for policy search. In Forty-first International Conference on Machine I Learning, 2024.
[12] Zijic Geng, Jie Wang, Ziyan Liu, Siyuan Xu, Zhentao Tang, Mingxuan Yuan, Jianye HAO, Yongdong Zhang, and Feng Wu. Reinforeement learning within tree search for fast macro placement. In Forty-first International Conference on Machine Learning, 2024.
[13] Yao Lai, Jinxin Liu, Zhentao Tang, Bin Wang, Jianye Hao, and Ping Luo. ChiPFormer: Transferable chip placement via offline decision transformer. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 18346-1836A PMLRR 23-29 Jul 2023.
[14] Ronald J Williams. Simple statistical learning. Machine learning, 1992.
algorithms for connectionist reinforcement
[15] Sergei Dolgov, Alexander Volkov, Lutong Wang, and Bangqi Xu. 2019 cad contest: Leffdee based global routing. In 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1-4. JEEE, 2019.
[16] David Michael Warme. Spanning trees in hypergraphs with applications to Steiner trees. University of Virginia, 1998.
[17] Frank K Hwang. An o (n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM (JACM), 26(2):177-18 1979.
11

---

[18] Andrew B Kahng, Ion Mändoiu, and Alexander Z. Zelikovsky. Highly scalable algorithms for rectilinear and octilinear steiner trees. In Proceedings of the 2003 Asia and South Pacific Design Automation Conference, pages 827-833, 2003.
[19] Yiu-Chung Wong and Chris Chu. A scalable and accurate rectilinear steiner minimal tree algorithm. In 2008 IEFE International Symposium on VLSI Design, Automation and Test (VLSI-DAT), pages 29-34. IEEE, 2008.
[20] Chung- Wei Lin, Szu- Yu Chen, Chi-Feng Li, Yao-Wen Chang, and Chia-Lin Yang. Efficient obstacle- avoiding rectilinear steiner tree construction. In Proceedings of the 2007 international symposium on Physical design, pages 127-134, 2007.
[21] Tao Huang and Evangeline FY Young. Obsteiner: An exact algorithm for the construction of rectilinear steiner minimum trees in the presence of complex rectilinear obstacles. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 32(6):882-88) 2013.
[22] Liang Li and Evangeline FY Young. Obstacle-avoiding rectilinear steiner tree construction. In 2008 IEEE/ACM International Conference on Computer-Aided Design, pages 523-528. IEEE, 2008
[23] Kuen-Wap Wey Lin, Ych-Sheng Lin, Yih-Lang Li, and Rung-Bin Lin. A maze routing- based methodology with bounded exploration and path-assessed retracing for constrained multilayer obstacle- obstacle-avoiding rectilincar steiner tree construction. ACM Transactions on Design Automation of Electronic Systems (TODAES), 23(4):1-26, 2018.
[24] Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, and Alexander Zelikovsky. Ap- proaching the 5/4 approximation for rectilinear steiner trees. In Algorithms- -Eaeess-SAAAA 19: Second Annual European Symposium Utrecht, The Netherlands, September 26-28, 1994 Proceedings 2, pages 60-71. Springer, 1994.
[25] Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753- 782, 1998.
[26] Chris Chu. Flute: Fast lookup table based wirelength estimation technique. In JEEE/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004, pages 696-701. IEEE, 2004.
[27] Andrew Kahng, Robert R Nerem, Yusu Wang, and Chien-Yi Yang. Nn-steiner: A mixed neural- algorithmic approach for the rectilinear steiner minimum tree problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13022-13030 13030, 2024.
[28] Jieyi Long, Hai Zhou, and Seda Ogrenci Memik. Eboarst: An efficient edge-based obstacle- rectilinear steiner tree construction algorithm. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 27(12):2169 2182, 2008
[29] Gaurav Ajwani, Chris Chu, and Wai-Kei Mak. Foars: Flute based obstacle-avoiding rectilinear steiner construction. In Proceedings of the 19th international sympoxium on Physical design. pages 27-34, 2010.
[30] Tiancheng Zhang, Zhipeng Lü, and Junwen Ding. Guiding solution based local search for obstacle- avoiding rectilinear steiner minimal tree problem. IEEE Transactions on Emerging Topics in Computational Intelligence, 2023.
[31] Chih-Hung Liu, Sy-Yen avoiding rectilincar steiner tree construction: A steiner steiner-point- boint-bascd algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(7):1050-1060 2012.
Yen Kuo, DT Lee, Chun- Lin, Jung-Hung Weng, and Shih-Yi Yuan. Obstacle-
[32] Liang Li. Zaichen Qian, and Evangeline FY Young, Generation of optimal obstacle-avoidiag rectilinear steiner minimum tree. In Proceedings of the 2009 International Conference Computer-Aided Design, pages 21-25, 2009.
[33] Tao Huang and Evangeline FY Young. Obstacle-avoiding rectilinear steiner minimum construction: An optimal approach. In 2010 JEEF/ACM International Conference on Computer-Aided Design (ICCAD), pages 610-613. IEEE, 2010.
[34] Tao Huang, Liang Li, and Evangeline FY Young. On the construction of optimal obstaclc-vvoiding rectilinear stciner minimum trees. IEEE transactions on computer-aided design of integrated circuits and systems, 30(5):000-)3) 1737773,,33,, 2011.
[35] Yao Lai, Yao Mu, and Ping Luo. Maskplace: Fast chip placement via reinforced visual representation learning. Advances in Neural Information Processing Systems, 35:24019- 240000, 2022.
12

---

[36] Ke Xue, Ruo-Tong Chen, Xi Lin. Yunqi Shi, Shixiong Kai, Siyuan Xu, and Chao Qian. Reinforcement regulator rather than macro placer. Advances in Neural Information Processing Systems, 4055561405888, 2024.
learning policy
[37] Zhihai Wang, Jie Wang. Dongsheng Zuo, Ji Yunjie, Xilin Xia, Yuzhe Ma, Jianye Hao, Mingxuan Yuan. Yonglong Zhang. and Feng Wu. A hierarchical adaptive multi- reinforcement learning framework for multiplier circuit design. In Forty-first International Conference on Machine Learning, 2024.
[38] Mohammad Amini, Zhanguang Zhang, Surya Penmetsa, Yingxue Zhang, Jianye Hao, and Wulong Liu. Generalizable floorplanner through comer block list representation and hypergraph embedding. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages
2692 2702, 2022.
[39] Ruizhe Zhong, Xingbo Du, Shixiong Kai, Zhentao Tang, Siyuan Xu, Jianye Hao, Mingxuan Yuan, and Junchi Yan. Flexplanner: Flexible 3d floorplanning via deep reinforeement learning in hybrid action space with multi modti-moddlity representation. Advances Neural Information Processing Systems, 37:49252 49278, 2024.
[40] Haiguang Liao, Wentai Zhang, Xuliang Dong, Barnabas Poczos, Kenji Shimada, and Levent Burak Kara. A deep reinforcement learning approach for glohal routing. Journal of Mechanical Design, 142(6))01771, 2020.
[41] Huanjin Wu, Xinyu Ye, and Junchi Yan. Qvae-mole: The quantum vae with spherical latent variable learning for 3-d molecule generation. Advances in Newral Information Processing Systems, 37:22745- 22771, 2024.
[42] Nianzu Yang, Huaijin Wu, Kaipeng Zeng, Yang Li, Siyuan Bao, and Junchi Yan. Molecule generation for drug design: graph learning perspective. Fundamental Research, 2024.
[43] Huaijin Wu, Wei Liu, Yatao Bian, Jiaxiang Wu, Nianzu Yang, and Junchi Yan. Ebmdock: Neural probabilistic protein-protein docking via a differentiable energy model. In The Twelfth International Conference on Learning Representations, 2024.
[44] Maurice Hanan. On steiner's s problem with rectilinear distance. SIAM Journal on Applied mathematics, 14(2):255-26,, 1966.
[45] Frank K Hwang. On steiner minimal trees with rectilinear distance. SIAM journal on Applied Mathematics, 30(1):104-114, 1976.
[46] Sergey Toffe. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 167, 2015.
[47] A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[48] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[49] Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.66.,,, 2014.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: This paper discusses the limitations in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
This paper provides complete assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: This paper provides experimental details, and particularly, the code is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification: All the data used in this paper are open-sourced, and the code is provided in the GitHub link.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. ec/
ooiccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: halliii/ggiee//ee
/ /nips...
ssiissii wwwssssoiccyyyyyc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper provides details of the experimental protocols and ablation studies.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: This paper reports the standard deviation of the average percentage error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This paper provides detailed introduction to computing resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https /tttpp:://eerrre http///eeerppppeeeee httpe//////c///ccceeeiiiiiiaaaaa
Answer: [Yes]
Justification:
This research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: As shown in the introduction, this paper presents work whose goal is to advance the field of Machine Learning and the field of Artificial Intelligence for Electronic Design Automation (A14EDA). Its negative impact is shown in the conclusion.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not refer to data or models that have high risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: This paper follows the license when using existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The new assets well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not refer to research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM is only used for editing in some parts.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https //taarrppp.c//ooofeeeree////0250 for what should or should not be described.
20

---

A Theoretical Results
1.0
1.0
0.8
0.8
0.6-
2.6-
0.4
0.4
0.2
0.2-
0.0
3.0
(a) Hanan Grid.
(b) Extended Hanan Grid.
Figure 7: Visualization of a) Hanan Grid, and b) Extended Hanan Grid. The grids are shown as grey
dashed lines.
A.1 Additional Definitions
In this section, we propose additional definitions apart from those in Sec. 2.1. The visualizations of Hanan Grid and Extended Hanan Grid are shown in Fig. 7(a) and Fig. 7(b).
Definition A.1. [Hanan Grid [44]]) For a given set of pins P {po, Pl. P its Hanan grid (P)) is defined as the grid composed of the intersection points of the horizontal and vertical lines of all pins. Formally,
(9) Definition A.2. [Extended Hanan Grid] For given of pins {po+ PI.... -Pn-13 1 and of rectangular obstacles O = foo, 01 , mm-1h J. its extended Hanan grid (P, O) is defined as the grid composed of the intersection points of the horizontal and vertical lines of all pins and the corners of all obstacles. Formally,
H(P) = {z, 1)12
or y = ys Vp: = (z,, 9:}}
(P,, 0) ((x, v)(= x, or yc, V(r, v.) PUV(()),
(10)
where V(O) represents all corner vertices of obstacles O.
A.2 Assumption and Lemma
In order prove our main theorem in Sec. 2.3, we first put forward and prove some theoretical findings in this section. Though some theorems/lemmas originate from other works [44, 5], they lack corresponding proofs.
Assumption A.3. For given set of pins P <Poo P .Pa-1). }. its rectilinear edge sequence (RES) is valid iff. such RES connect all pins in P.
Lemma A.4. |Validity of RES] For a given set of pins P = {po, Pr......... Pn--), its rectilinear edge sequence (RES) res = ((vo, ho), (V1, (1), (.. (Un-2, f2n) is guaranteed to be valid if
1. Vo * ho-
2. For each rectilinear edge pair (vi, h:) (1 2 1), exactly one of 0s h2 is visited before by previous rectilinear edge pairs, and the other is not.
Proof. The lemma obviously holds when n = 3. For n > 3, consider the construction process of RES. Since vo * ho. the first pair contains distinct points that connected. For the i-th (i > 1) pair, due to the second requirement, the newly-visited pin connected to the previously pins, and the number of connecting pins plus 1, and so forth, when
pins are connected. O
Lemma A.S. [Hanan's Theorem] For any set of pins P (po.Pr. -Pn-1), there always exists an optimal Rectilinear Steiner Tree (RST), ie., Rectilinear Steiner Minimum Tree (RSMT), that all Steiner points lie the Hanan Grid.
21

---

Proof. Suppose there exists optimal RST that has a series of Steiner points S = {su $1.". .--1 not lying on the Hanan Grid. For each s; S, denote its coordinate (xz, Vr). then least one of Fi; Vi is not equal to any of the pin coordinates.
Without loss of generality, we suppose I; is not equal any pin coordinates, then move such Steiner point 9; to the nearest x-coordinate of pins. Due to the characteristic of Manhattan distance, after this movement, the length of the connection path referred to s; equal the previous one.
Repeat the above process on all other Steiner points in S, finally we obtain an optimal RST whose Steiner points are all the Hanan Grid.
Theorem A.6. [Optimality of RES] For any set of pins P = .p..P...... . P can always be found such that its corresponding tree an optimal RSMT for P.
Pn-1), 1,, an optimal RES of
Proof. Let T be an optimal RSMT for P with length L", and let R(P) be the set of all valid RES for P. Denote by
r" arg
min (length(T(r))) PER(P)
(11)
an optimal RES in RPP), where T(r) is the corresponding tree of RES R(P).
Suppose, for contradiction, that length(T(r")) I."
By Lemma A.5, we may assume all Steiner points in T lie on the Hanan grid H(P). Consider traversing T in manner similar to breadth-first search (BFS), starting from arbitrary pin. Each time a new pin Pj is encountered, it is connected to an already visited pin p; via a path that follows the Hanan grid and possibly passes through Steiner points.
Since Steiner points are on the Hanan grid, the path from p; to P3 consists of horizontal and vertical segments whose total length equals the Manhattan distance between pt and py. Therefore, each such path can be represented as a direct sequence of horizontal and vertical edges between pins in the RES framework, implicitly accounting for any Steiner points.
Construct the RES by recording each connection (i.j) where pj is connected to pt. By construction:
Each edge (i,j) in r' corresponds to a rectilinear path in T with length equal to the Manhattan distance between p; and Pj-
2. The sequence r' satisfies the conditions of Lemma A.4, ensuring that r' is valid RES.
3. The total length of T(r') equals L since each RES edge represents the minimal rectilinear distance required to connect pj to the existing tree.
Thus, we have r' R(P) and length(T(r')) L This contradicts our assumption that (enrth(T((r)) L". Therefore, must be that
length(T((")) = L",
(12)
and r* corresponds to an optimal RSMT.
n
Lemma A.7. [Extended Hanan's 's Theorem] For any set of pins P {po, Spo.Pr........ Pa-11) } and a set of rectangular obstacles O = {oo, "1.".. ,00-11, 1 there always exists an RSMT, that all Steiner points are lying on the extended Hanan Grid H1' OP))..
Proof. The proof is similar to Lemma A.5. Suppose there exists an optimal RST that has series of Steiner points = {sp, $1, ... 3 not lying on Hanan Grid H (P). For each s; E S, denote its coordinate as (x,, 8:), then at least one of 2;, Yi is not equal to any of the pin coordinates.
Without loss of generality, we suppose 2; not equal to any of the coordinates of pins, then we try to move such Steiner point to the nearest x-coordinate of pins. Consider two situations:
1. If the movement is successful, then the length of the connection path referred to 8; equal to the previous one due to the characteristic of Manhattan distance.
22

---

2. If the movement fails (caused by obstacles), we can move to the nearest x- x-coordinate of pins as far as possible until it is adjacent an obstacle og. This operation will also not lead to longer length and the Steiner point 8; is moved to the extended Hanan Grid (P,,O)
Repeat the above process on all other Steiner points in S, finally we obtain an optimal RST whose Steiner points are all on the extended Hanan Grid O),
Assumption A.8. For given of pins {po. Pi. -Pn-1) 1 and set of rectangular obstacles its rectilinear edge sequence (RES) is valid iff.
0 = = 01,"
,00-1 ,
Such RES connect all pins in P.
2. Vedge E r, Vo; E O edge n int((;)) = 0, where int(o;) denotes the interior region of obstacle o,.
Lemma A.9. [Existence of valid RES in OARSMT] For any set of pins P a set of rectangular obstacles = {oo, 01, 0m-1), 1, suppose there exists a rectilinear Steiner tree (RST), then there always exists subset of obstacles V (O) and the corresponding valid rectilinear edge sequence (RES) P U (O).
(PooPi.... Pn-1) and
Proof. Clearly, it holds for the case without obstacles, so we only consider the case when RES overlaps with obstacles.
Define an empty set UI and a RES of P. Suppose a rectilinear edge (wt, h2) in r overlaps with obstacle 0g E O, then we can choose an unvisited comer vertex "y of obstacle 0j and divide (u;, h,) into (us, u;), (u,: ht).
Add uj to l and replace (us, h4) with two rectilinear edges (vi, uz): (uj, h2) in r. Traverse all rectilinear edges until none of them overlap with any obstacle. Note that U V(O), so we denote a (O))
The split of (v;, h₂) will simultaneously increase the number of rectilinear edges by and the number of unvisited points by 1, so it satisfies the validity of RES stated in Lemma A.4.
A.3 Proof of the Main Theorem
Theorem A.10. [Optimality of RES in OARSMT) For any set of pins P = (po. PI.......... PP--1) and a set of rectangular obstacles O {ou, 01. ,0m1.,,.mm1) an optimal RES of (V) can always be found such that its corresponding tree is optimal OARSMT for P under obstacles O. Here, (O) c V(O) is a subset of the corner vertices of all obstacles.
Proof. The proof is similar to that of Theorem A.6. Let T be an optimal OARSMT for P under obstacles O with length L" and overlaps, and let R(P') be the set of all non-overlapping and valid RES for P' A (OV) According Lemma A.9, R('') + 0. Denote by
r" arg min (leng rER(PT)
(13)
an optimal non-overlapping RES in R(P"), where T(r) is the corresponding tree of RES R(P'). Suppose, for contradiction, that length(T((r)) > L".
By Lemma A.7, we may assume all Steiner points in 7 lie on the extended Hanan grid H' O). Consider traversing T* in manner similar treadth-first search (BFS), starting from arbitrary pin. Each time a new pin/ hent/verte pj is encountered, it is connected to an already visited pin/vertex p; via path that follows the extended Hanan grid and possibly passes through Steiner points.
Since all Steiner points are on the extended Hanan grid, the path from ps to Pj consists of horizontal and vertical segments whose total length equals the Manhattan distance between P; and pj. Therefore,
23

---

each such path can be represented as direct sequence of horizontal and vertical edges between pins the RES framework, implicitly accounting for any Steiner points.
Construct the RES by recording each connection (i,j) where Pj is connected to pt. By construction:
1. Each edge (i,j) in r' corresponds to rectilinear path in T with length equal to the Manhattan distance between p; and Pj-
2. The sequence r' satisfies the conditions of Lemma A.4, ensuring that r' is valid RES.
3. The total length of Tr') equals L* since each RES edge represents the minimal rectilinear distance required to connect Pj to the existing tree.
Thus, have r' RPP)) and length(T(r')) L'. This contradicts assumption that length(T(r")) L*. Therefore, must be that
length(T(r")) L",
(14)
and r* corresponds to an optimal OARSMT.
B Experiments
B.1 Success Rate
Table 5: Success rate (%) of GeoSteiner and OAREST R5-R50 instances with 5/10 obstacles.
GeoSteiner
OAREST (ours)
Instances
Obstacles
Obstacles
Obstacles
10 Obstacles
RS
34.45
19.68
99.51
99.11
R10
27.65
13.60
98.55
97.64
R15
26.57
12.78
98.41
97.02
R20
28.03
12.03
98.06
96.38
R25
28.15
12.48
98.01
96.26
R30
29.75
11.37
98.14
96.44
R35
30.21
12.70
98.35
96.36
R40
30.37
12.10
98.35
96.52
R45
31.50
98.27
96.69
R50
32.29
11.98
98.57
96.71
We conduct success rates of GeoSteiner [16] and OAREST in Table 5. Instances with no overlaps are regarded as successes. The failure cases are due 1) Generalization error: For example, the R50 data with 10 obstacles occupy 90 points (50 pins + 40 obstacle corners) for each instance, exceeding the maximum number of 50 pins during training. This results in generalization error and could be improved by covering the 50-90 pins during training. 2) Dense obstacles between pins: For some extreme cases when obstacles are dense and the generated rectilinear edges frequently overlap with these obstacles, OAREST will stop updating the activation masking to keep the linearity of batch inference. is common for one hard sample in a batch harm the efficiency of the entire batch in machine learning. In our setting, pay more attention to GPU parallelization for multiple instances.
In some cases, the RL framework also generate redundant edges in the RES; these removed in post-processing step.
B.2 Baselines
GeoSteiner [16]. GeoSteiner is efficient exact algorithm to solve RSMT problems. Based on the characteristics that an optimal RSMT can always be found by combining full Steiner trees only, it first enumerates all possible full Steiner trees and then forms RSMT. However, the time complexity is exponential to the number of pins.
R-MST [17]. Rectilinear Minimum Spanning Tree (R-MST) is an approximation approach for RSMT. can efficiently construct RSMT within Onn log n) time complexity and proved [45] have the length most 1.5x that of RSMT.

---

BGA [18]. BGA employs heuristics to optimize the result. By computing an R-MST first, BGA then repeatedly replace bad edges with better ones to minimize the total length of the R-MST.
FLUTE [19]. FLUTE computes a look-up table in advance for the instances <9 pins, and thus is an exact algorithm for these instances. For large instances with >9 pins, FLUTE breaks the net into small nets that can be handled by the look-up table. Within this algorithm, the authors introduce an accuracy parameter A, which allows users control the trade-off between accuracy and runtime when generating RSMTs. A = 3 is the default accuracy level of FLUTE, where the runtime and error are moderate. Conversely, A 18 represents a higher accuracy level, which invests more computational resources to further reduce the error in wirelength estimation.
REST [5]. REST is RL-based framework that trains actor-critic network random data. The actor network is responsible for predicting the next rectilinear edge pair to connect while the critic network is utilized rapidly predict the total wirelength of the tree. The generated rectilinear edge sequence (RES) finally forms an RSMT. In this method, the authors introduce 8 transformations (I' = 8) that rotate the point set by O, 90, 180, 270 degrees, with/without the x- and y- axes swapping. and select the best result. These transformations will not change the RSMT solution but bring promising improvement in wirelength. The time overhead of REST (T' 8) approximately 8x that of REST (T' = 1).
OARST [20]. OARST is OARSMT algorithm, but it contains sequential process, including gen- erating the obstacle-ave avoiding spanning graph (OASG), the obstacle-avoiding spanning tree (OAST), the obstacle-avoiding rectilinear spanning tree (OARST), and finally obtains the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT). We use its intermediate result of OARST as a strong baseline.
ObSteiner [21]. ObSteiner implements OARSMT by employing a geometric approach that decom- poses the problem into constructing and concatenating full Steiner trees (FSTs) among complex obstacles, while enhancing computational efficiency through virtual terminal additions and pruning strategies.
B.3 Model Structure
The main structure is revised from [5], which contains an actor network and critic network. Both of these networks take a set of points P (Po. P1,-.. ; Pu-1) as the input and pass through an embedder and an encoder. The actor network has an additional decoder mechanism. During training. P only contains pins. For inference, P is combination of pins and obstacle vertices. Detailed illustration is as follows:
Embedder. Given the set P, denote its position matrix as P E R=x2, Before passing it into the encoder, they are processed by an embedder module to transform the raw input into a higher- dimensional space suitable for encoding. The embeddings are masked by m impui Specifically, the embedder is defined as:
Embedder (P) = BatchNNrmmConv I(P T)
m
input
(15)
where CD is a x 1 convolution that projects the input from to demb dimensions, and BatchNorm [46] applies batch normalization to stabilize the embeddings.
The embedder ensures that the input points are transformed into embeddings Eembed Dx with richer feature representation, which are then fed into the encoder.
Encoder. The encoder is mapping Encoder X - Rxdxx Specifically, the Encoder is constructed using a multi-head attention mechanism [47]. The encoder operates with a stack of layers, where each layer is composed of two sublayers: a multi-head attention layer and a position-wise feedforward layer. These sublayers are connected through residual connections, followed by batch normalization to stabilize and accelerate the training process. Formally, given the input X to an encoder layer:
X BatchNorm MaatiNNecmMMiliiieeaattttttntttt (X, X,X.X) + +X,
(16)
Y SanchNormmFeddForwarr/33 X').
Note that the vectors in this section are instance-level for simplicity, different from the batch level matrices in Sec. 3.2.
25

---

The multi-head attention mechanism computes attention as:
QK Vik
Attention( Q, K, V) = softmax
V
(17)
where K, are the query, key, and value matrices derived from the input X, and dy is the dimensionality of the keys. Multiple attention heads are concatenated and linearly projected back to the original dimension.
The position-wal wise feedforward layer applies two linear transformations with a ReLU activation in between:
FeedForward (X) = ReL.U(X,, + b1) W2 + b2-
(18)
This encoder ensures that the representations are enriched with global contextual information while maintaining computational efficiency.
Forward Pass of Actor Network. The overall forward pass through the model begins with the embedder. The embeddings are then processed by the encoder, followed by series of ID convolutions to extract specific features:
Eembeed = Emhedder(P))
Egnc = Encoder( (Eembed)
E, Conv (E E, = CoCCConDDD ID, (B,cc)
E, = CDnvID,
(19)
Exy Ex, Eyl,
where Conv 1D,, Conv and Conv are x convolution layers applied to the encoder output Eene. and [ represents concatenation along the feature dimension. This structured processing pipeline ensures that the model captures local and global information from the input points, preparing the features for subsequent decoding tasks.
Forward Pass of Critic Network. The critic network is designed to evaluate the quality of solution by predicting the expected output length, providing baseline for reinforcement learning. The forward pass of the critic network is as follows:
E emeeed CrifEmbedder(P), E = CritEncoder(Eemteee
G = Glimpse(Eenc) = softmax(tanh( ) Egnc:
(20)
MLP(G),
where CritEmbedder and CritEncoder respectively have the same structures of Embedder and Encoder with different learnable parameters. Glimpse computes weighted sum of the encoded representations with g' E Rdd= Finally, a multi-layer perception (MLP) is used that outputs the final predictions o.
Decoder Actor Network. The decoder of the actor network operates as a sequential decision- making process to generate rectilincar edges along with their associated probabilities. We show the whole process in Alg. 1, where the steps marked in blue means that they are executed only for inference phase. This decoder leverages pointer networks [48] with various masking strategies to compute logits. These logits are generated using encoded features and dynamically updated query vectors inputs. At each step, the decoder selects indices based on computed logits, ensuring constraints such as unvisited points and obstacle avoidance are met. Additionally, the decoder employs activation masks handle overlaps with obstacles, iteratively refining selections until valid edge is identified. This mechanism helps the output rectilinear edge sequence and the cumulative log-pn bog-prbbabilities adhere the given spatial and logical constraints.
B.4 Training Strategy
Our training strategy consists two phases. The first phase follows the methodology described in [5], while the second phase involves quick multi-degres finetuning.
In the first phase, the model is sequentially trained from degree 50. After completing training at
degree I, the parameters are used to initialize training at degree L. + 1. Each degree-specific training involves 40,000 iterations with batch size B that decreases as the degree increases. Specifically, B starts at 4096 for degree 3 and is progressively reduced to 2048, 1024, and 512 for degrees 10, 20, and
26

---

Algorithm Actor Decoder
Input: Encoded features Eene. E,, Exy. obstacles O.
Output: RES and cumulative bog-probabilities p.
I: Initialize input mask m mput visited mask m visiited obstacle mask m and activation masks m
2: Initialize the log probabilities p 0 of selecting RES.
3: Define zero-initialized query vector Qoo
4: Compute logits So PointerStart (Er: qo) (alupus/mo))
Select the start point.
5: Sample starting index up from 5p. Denote y(2) = 10-
6: Update visited mask m visited
7: for j = to n 1 do
8: Compute the first query 41 based u(2)
9: Compute logits s(1) Pointerl (E,, q1 (m A m mistted)
Select the unvisited point.
Sample or determine first index v1 from s(1)
11:
Compute the second query Q2 based on (1)
12:
Compute logits g(2) Pointer2 q2) (1 m risled).
Select the visited point.
Sample or determine second index (2) from s(2).
14:
Decode indices æ; y from y(1) v(2) while (x, y) overlaps obstacles O do
15:
Update activation masks m
17:
Compute logits ( Pointerl (E,, q1) unvisited point.
(m input A m visited m=)).
Select the new
18:
Sample or determine first index (1) from s())
Compute logits s2) Pointer2(EA) Exy. ky: q2) (1 m visited). Select the new visited point.
20:
Sample or determine second index (2)) from s(2)
21:
Decode indices x, y from v()), y(2)
22:
end while
23:
Add the rectilinear edge (I. 3) to RES r.
24:
Compute log p(v()), log p(e(2)) from ( s(?)) and add to p.
25:
Update visited mask m visited
26:
end for
40, respectively. The Adam optimizer [49] is employed with initial learning rate of 2.5 10-4 which decays by factor of 0.96 after each degree's 's training.
In the second phase, leverage dynamic masking strategy to jointly train the model across range of degrees, from nı to n2.. The Adam optimizer is again utilized, this time with a learning rate of 5 x 10 The total number of iterations in this phase is limited to the number of iterations required for training single degree in the first phase. Specifically, we conduct training for the degree ranges (n1, n2) as follows: (3, 10), (10, (20, 30), (30, 40), (40, 50), and (3)5
B.5 Inference Strategy
For the RSMT problems, we use OAREST (3-10) to test R5 and RI0, OAREST (10-20) to test R15 and R20, and so forth. For each group of instances, batch size of 100 100k k/dgree is used for parallel inference. To further enhance the performance, we use transformations proposed by [5] that rotate the point set by 0, 90, 180, 270 degrees, with/without the x- and y- axises swapping, and select the best result. These transformations will not change the RSMT solution but bring promising improvement in wirelength.
For the OARSMT problems, we use OAREST (40-50) for all groups of instances due to large occupations of obstacles. To demonstrate the efficiency of GPUs, we use the full batch size, i.e., 10 k, for parallel inference. To keep the linearity of inference, the model only inspects the obstacles once for the 'while' in Alg. 1. Here, 8 transformations are also used.
27

---

B.6 Visualization
In this section, we present the visualized results OARSMTs with 5-50 pins and 0/5/10 obstacles. When no obstacles are present, the OARSMT results are the same the vanilla RSMTs. As shown Fig. 8-17, each line represents three pairs of instances with the same number of pins, including the pair without obstacles (left), with 5 obstacles (middle), and with 10 obstacles (right). Within each pair, the left means the result obtained by the exact RSMT algorithm GeoSteiner [16] and the right represents the result obtained by OAREST.
(a) pins.
(b) pins & obstacles.
(c) pins & obstacles.
Figure 8: OARSMT with 5 pins and 0/5/10 obstacles.
1.
(a) 10 pins.
(b) 10 pins & 5 obstacles.
(c) 10 pins & 10 obstacles.
Figure OARSMT with 10 pins and 0/5/10 obstacles.
(a) 15 pins.
(b) 15 pins & 5 obstacles.
(c) 15 pins & 10 obstacles.
Figure 10: OARSMT with 15 pins and 0/5/10 obstacles.
28

---

(a) 20 pins.
(b) 20 pins obstacles.
(c) 20 pins 10 obstacles.
Figure 11: OARSMT with 20 pins and 0/5/10 obstacles.
(a) 25 pins.
(b) 25 pins & 5 obstacles.
(c) 25 pins & 10 obstacles.
Figure 12: OARSMT with 25 pins and 0/5/10 obstacles.
(a) 30 pins.
(b) 30 pins & obstacles.
(c) 30 pins & 10 obstacles.
Figure 13: OARSMT with 30 pins and 0/5/10 obstacles.
(a) 35 pins.
(b) 35 pins obstacles.
(c) pins 10 obstacles.
Figure 14: OARSMT with 35 pins and 0/5/10 obstacles.
(a) 40 pins.
(b) 40 pins & 5 obstacles.
(c) 40 pins & 10 obstacles.
Figure 15: OARSMT with 40 pins and 0/5/10 obstacles.
(a) 45 pins.
(b) 45 pins & 5 obstacles.
(c) 45 pins & 10 obstacles.
Figure 16: OARSMT with 45 pins and 0/5/10 obstacles.
(a) 50 pins.
50 pins & obstacles.
(c) 50 pins 10 obstacles.
Figure 17: OARSMT with 50 pins and 0/5/10 obstacles.
29


Reviews:
[{"review_id": "8M3lDfX2D6", "reviewer": "Reviewer_Ln85", "summary": "This paper presents OAREST, a reinforcement learning-based framework for solving the Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) problem. The key contribution is extending the Rectilinear Edge Sequence (RES) representation to handle obstacles through a dynamic masking strategy that enables multi-degree GPU parallelization and obstacle avoidance without training on obstacles. The authors provide theoretical proof of RES optimality for OARSMT and demonstrate empirical results on synthetic and real-world benchmarks.", "questions": "1. **Scalability Analysis**: How does the approach scale to larger instances (100+ pins)? Could the dynamic masking strategy be extended to handle larger problems, and what are the fundamental bottlenecks?\n\n2. **Failure Case Analysis**: Can you provide more detailed analysis of the 2-4% failure cases where overlaps occur? What characteristics of problem instances lead to failures, and how might this inform future improvements?\n\n3. **Baseline Comparisons**: Why weren't recent ML-based OARSMT methods like QUAR-VLA included in the comparison? How does OAREST compare to these more directly related approaches?\n\n4. **Generalization Beyond Small Instances**: While the paper justifies focusing on small instances, how would you adapt the approach for the remaining 5% of nets with more pins that are still critical in modern designs?\n\n5. **Training Strategy Justification**: What is the theoretical or empirical justification for why training only on pins enables effective obstacle avoidance? Could this insight be applied to other combinatorial optimization problems?", "limitations": "The authors adequately discuss some limitations but could be more thorough in addressing:\n\n- **Generalization Limits**: The approach's effectiveness on instances significantly larger than training data (>50 pins) is unclear\n- **Obstacle Complexity**: Only rectangular obstacles are considered; complex rectilinear obstacles might pose additional challenges\n- **Runtime Scalability**: While GPU parallelization helps with batch processing, single-instance runtime scaling is not thoroughly analyzed\n- **Hyperparameter Sensitivity**: Limited discussion of how sensitive the approach is to the various hyperparameters in the dynamic masking strategy", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### **Strengths**\n\n**Strong Theoretical Foundation**: The paper provides rigorous theoretical analysis proving the optimality of RES representation for OARSMT problems (Theorem 2.5). The mathematical framework extending Hanan grids to include obstacle vertices is well-established and the proofs appear sound.\n\n**Novel Dynamic Masking Strategy**: The dynamic masking mechanism is technically sophisticated, enabling the model to handle varying numbers of pins and obstacles during inference without explicit training on obstacles. This is a significant practical advance for the field.\n\n**Comprehensive Experimental Design**: The evaluation covers both synthetic datasets (R5-R50) and real-world benchmarks (ICCAD19), with systematic comparison against multiple baselines including exact solvers (GeoSteiner, ObSteiner) and heuristic methods.\n\n**Practical Relevance**: The focus on small-scale instances (3-50 pins) aligns well with real-world EDA applications, as evidenced by the ICCAD19 statistics showing 95% of nets have <10 pins.\n\n### **Weaknesses**\n\n**Limited Novelty in Core Components**: While the combination is novel, the individual components (RES representation, diffusion transformers, PPO) are largely borrowed from existing work. The main contribution is the engineering integration rather than fundamental algorithmic innovation.\n\n**Obstacle Handling Limitations**: Despite the paper's claims, the approach still produces overlaps in 2-4% of cases, requiring post-processing with maze routing. The \"training on pins, testing on obstacles\" paradigm, while interesting, has clear performance limitations.\n\n**Insufficient Baseline Comparisons**: The paper lacks comparison with other recent ML-based OARSMT methods like QUAR-VLA and some recent RL-based approaches mentioned in related work. This makes it difficult to assess the true advancement over state-of-the-art.\n\n**Scalability Concerns**: The approach is explicitly designed for small instances (≤50 pins), which limits its applicability to larger modern circuit designs. The time complexity analysis focuses on batch efficiency rather than single-instance scalability.", "was_revised": true, "final_justification": "All my concerns have been addressed.", "rebuttal": "We sincerely appreciate your valuable feedback. Please find our point-by-point response below:\n\n> **W1: Limited Novelty in Core Components.**\n\nWhile the RES representation and actor-critic framework are inspired by REST, our key contributions lie in theoretical and engineering extensions to handle obstacles without retraining:\n- **Novel theoretical guarantee**: Theorem 2.5 proves that an optimal RES for OARSMT can be constructed using only pins and obstacle corner vertices, which is non-trivial and enables zero-shot obstacle avoidance.\n- **Engineering extensions**: Unlike prior work, our masking strategy enables **multi-degree GPU parallelization** and **end-to-end obstacle handling during inference**, addressing scalability and efficiency gaps in existing methods.\n\n> **W2: Obstacle Handling Limitations.**\n\nWe acknowledge that the overlaps still occur in some extreme cases; however, they are relatively few in number and often close to success, requiring <1% additional runtime compared to OAREST’s inference time. Note that this performance is achieved without training on any obstacles, and OAREST, to the best of our knowledge, is the first ML-based approach to handle obstacles without training on them.\n\nBeyond the current success rate and easily-integrated postprocessing, as stated in the conclusion, we leave future work to completely eliminate overlaps in OARSMT problems.\n\n> **W3: Insufficient Baseline Comparisons. & Q3: Baseline Comparisons.**\n\nThank you for raising the concern.  We carefully considered the inclusion of additional baselines, but ultimately excluded them for the following reasons:\n\n- **Code unavailability**: Closed-source is common in the EDA community, and we have no access to these repositories. Ensuring a fair, reproducible comparison, therefore, remains intractable.\n\n- **Different focuses**: These works have other targets other than RSMT. For example, QUAR-VLA[1] focuses on quadruped robot navigation rather than RSMT problems. EPST[2] focuses primarily on the integration of Octilinear Steiner Minimum Tree (OSMT) and does not consider obstacles. Literature [3-5] are highly heuristic-driven. Chen et al.[3-4] use RL to generate Steiner points, but use heuristic algorithms to execute the connection phase. Lin et al.[5] uses RL to generate heuristic algorithms for solving the OARSMT problem.   \n\n- **Close to the Optimal**: Note that we have compared the optimal methods, including GeoSteiner for exact RSMT and ObSteiner for exact OARSMT, indicating we are already operating near theoretical limits.\n\n[1] QUAR-VLA: Vision-Language-Action Model for Quadruped Robots.  \n[2] A Unified Deep Reinforcement Learning Approach for Constructing Rectilinear and Octilinear Steiner Minimum Tree.  \n[3] A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction.  \n[4] Arbitrary-Size Multi-Layer OARSMT RL Router Trained with Combinatorial Monte-Carlo Tree Search.  \n[5] Obstacle-Avoiding Rectilinear Steiner Minimal Tree Algorithm based on Deep Reinforcement Learning.\n\n> **W4: Scalability Concerns. & Q1: Scalability Analysis. & Q4: Generalization Beyond Small Instances.**\n\nThank you for your insightful comment. We only train on instances with 3-50 pins, based on our observation in Table 2 that nearly 99% of nets have fewer than 50 pins, and moreover, 99.998% of nets have fewer than 100 pins in the commonly used real-world ICCAD19 benchmark.\n\nOur OAREST can be easily extended to 100-pin cases. Even without training on larger cases (>50 pins), OAREST can generalize to 100-pin cases with <3% error as shown in Figure 6b.\n\nFor some extremely large cases, e.g., >1000 pins, we would like to initially claim that they are not within the scope of OAREST, as discussed in Sec. 3.3 (Single Large Instance vs. Multiple Small Instances), and it is common in EDA that we use different tools to tackle with instances with different scales. However, if we must do so, OAREST can be integrated into the hierarchical approach: partition nets into 50-pin subnets, apply OAREST in parallel, and merge the solutions. Such a hierarchical approach is very common in the industry [1-2], but is heuristic and is not our primary focus. Notably, existing pure ML-based methods cannot be extended to such large scales.\n\n[1] Flute: Fast Lookup Table based Wirelength Estimation Technique.  \n[2] A Scalable and Accurate Rectilinear Steiner Minimal Tree Algorithm.\n\n> **Q2: Failure Case Analysis.**\n\nThank you for raising the constructive question. The failure cases are due to the following reasons:\n\n**Generalization Error**: For example, the R50 data with 10 obstacles occupy 90 points (50 pins + 40 obstacle corners) for each instance, exceeding the maximum number of 50 pins during training. This results in generalization error and could be improved by covering the 50-90 pins during training.\n\n**Dense Obstacles between Pins**: For some extreme cases when obstacles are dense and the generated rectilinear edges frequently overlap with these obstacles, OAREST will stop updating the activation masking to keep the linearity of batch inference. It is common for one hard sample in a batch to harm the efficiency of the entire batch in machine learning. In our setting, we pay more attention to GPU parallelization for multiple instances.\n\nBased on the above reasons, failure cases do exist in our experiments. We will clarify the failure case analysis in the revised manuscript and attempt to eliminate overlaps in future work. \n\n> **Q5: Training Strategy Justification.**\n\nThank you for your insightful question. We provide more discussions in terms of generalization in the following three-fold:\n\n- **Theoretical Insight**: Theorem 2.5 gives us an intuition that we only need to construct a RES that connects all pins and a subset of corner vertices of obstacles. Then, the aim of the designed RL agent is to connect these pins and corner vertices. Since our model is trained only on pins and we want it to connect corner vertices as well, a natural idea is to also regard the corner vertices as pins. However, this could lead to two issues: 1) not all corner vertices are required to connect, and 2) the connected edge might be overlapped with the obstacles.\n- **Dynamic Masking**: Building on the theoretical insight, the dynamic masking is proposed with a strong motivation to address the above two issues. Specifically, in Sec. 3.2, the obstacle masking is designed to prevent unnecessary corner vertex connections (issue 1), and the activation mask is designed to avoid overlapping with obstacles (issue 2). Notably, these masking strategies can be achieved purely in the inference stage.\n- **Empirical Validation**: Table 4 shows >96 % zero-overlap success on 5–10 random obstacles and significantly surpasses the obstacle-unaware baseline GeoSteiner—confirming that the policy learned on pins transfers directly.\n\nWe will clarify the above generalization discussions in our revised manuscript. \n\nAdditionally, for **Transferability to Other Combinatorial Problems**, the paradigm “train on the base instance, generalize to constrained variants” hinges on two ingredients: \n1) Theoretically optimal (or near-optimal) representation that compactly encodes constraints (here: RES + obstacle corners). \n2) Dynamic action masking that instantiates constraints at inference time without retraining. \n\nTo the best of our knowledge, this constitutes a new paradigm in RL-based combinatorial optimization. We plan to systematically investigate its applicability to other classical problems in future work, such as constrained routing and scheduling.\n\n> **Other Limitation Discussion.**\n\n- **Generalization Limits**: We explore the generalization capability in Fig. 6b by testing on 50-100 pins with the model trained on <=50 pins. More pins can be included in training dataset for a better generalization. For extremely large number of pins, it could be a limitation for OAREST and is not within the scope of OAREST.\n- **Obstacle Complexity**: Any complex retilinear obstacle can be divided into multiple rectangular obstacles, so it is still within our problem scope.\n- **Runtime Scalability**: As OAREST focuses on batch processing, single-instance scaling could be a limitation. We will detail it in the conclusion part.\n- **Hyperparameter Sensitivity**: We did not introduce hyperparameters in the dynamic masking strategy, but we execute the ablation studies with varied degrees in Fig. 6a.\n\n***\n\nWe hope this response could answer your questions and address your concerns. Thank you again for your suggestion, which has made our work more complete."}, {"review_id": "AMS7uL0ZJY", "reviewer": "Reviewer_G4SK", "summary": "The authors introduce a reinforcement-learning model for solving the obstacle-avoiding rectilinear Steiner minimum tree problem. The model is shown to have sufficient expressivity to solve any OARSMT problem exactly. Substantial experimental results show that this model outperforms SOTA methods for the problem in both run time and solution quality. The model demonstrates strong generalization ability to problems with more pins than seen in training. Surprisingly, the model generalizes to problems with obstacles despite being trained only on instances without obstacles.  The main innovation aiding in this generalization ability is a masking strategy that naturally handles problems of different sizes and different amounts of obstacles.", "questions": "The phrasing of Theorem 2.5 indicates that the tree corresponding to the RES is only an RSMT for P, not necessarily an OARSMT for P. Is this correct? The sentence following the theorem statement suggests not, but it is also not immediately clear from the proof if the tree avoids obstacles. Similarly, it is unclear if V’(O) is a particular subset of obstacle vertices. \n\nGiven the title of the paper, I suspect the authors believe the OOD generalization of this model is the most remarkable result, and I agree.  However, the paper lacks any real discussion of why the model is able to achieve this generalization. It would be great if the authors could speak to this. Stronger discussion on how OOD generalization was enabled would greatly add to the relevance of this paper beyond VLSI.\n\nDo the real-world datasets contain obstacles? How are the randomly added obstacles to the R5-R50 test cases distributed? The distribution of obstacles seems likely crucial to the ability of the model to generalize to problems with obstacles. Also, the authors motivate the study of OARSMT with rectangular obstacles, because any rectilinear obstacle can be represented by multiple rectangular obstacles. Thus, it would be interesting to know if there are overlapping obstacles in their evaluation instances, and if having many overlapping obstacles harms performance. \n\nGiven the apparent strong similarities with REST, it would be nice if the authors could offer a direct comparison. Is the main innovation over REST the dynamic masking strategy?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "— Strengths — \n\n- Superior performance to SOTA methods\n- Strong OOD generalization to larger point sets and instances with obstacles \n- Expressivity result is an interesting theoretical insight into the model \n\n\n— Weaknesses — \n\n- Unclear why masking strategy lends itself to generalization, no theoretical insights into generalization, and insufficient discussion on generalization \n- Masking strategy lacks motivation. It would be interesting to understand why the authors chose this method and why it is effective\n- Distribution of obstacles used in evaluation appears to be limited. (Only uniform random obstacles, no real world obstacles)", "was_revised": true, "final_justification": "The authors have addressed all my concerns. I believe the additional discussion is very helpful. I have increased my rating and significance score as I think the out-of-distribution generalization achieved and the techniques used to achieve it may have interest beyond VLSI.", "rebuttal": "We sincerely appreciate your valuable feedback. Please find our point-by-point response below:\n\n> **W1: Unclear why masking strategy lends itself to generalization, no theoretical insights into generalization, and insufficient discussion on generalization.**\n\nThank you for your constructive comment. We provide more discussions in terms of generalization in the following three-fold:\n\n- **Theoretical Insight**: Theorem 2.5 gives us an intuition that we only need to construct a RES that connects all pins and a subset of corner vertices of obstacles. Then, the aim of the designed RL agent is to connect these pins and corner vertices. Since our model is trained only on pins and we want it to connect corner vertices as well, a natural idea is to also regard the corner vertices as pins. However, this could lead to two issues: 1) not all corner vertices are required to connect, and 2) the connected edge might be overlapped with the obstacles.\n- **Dynamic Masking**: Building on the theoretical insight, the dynamic masking is proposed with a strong motivation to address the above two issues. Specifically, in Sec. 3.2, the obstacle masking is designed to avoid unnecessary corner vertex connections (issue 1), and the activation mask is designed to avoid overlapping with obstacles (issue 2). Notably, these masking strategies can be achieved purely in the inference stage.\n- **Empirical Validation**: Table 4 shows >96 % zero-overlap success on 5–10 random obstacles and significantly suppasses the obstacle-unaware baseline GeoSteiner—confirming that the policy learned on pins transfers directly.\n\nWe will clarify the above generalization discussions in our revised manuscript.\n\n> **W2: Masking strategy lacks motivation.**\n\nThank you for proposing this concern. Please refer to our strong motivation of proposing the dynamic masking strategy in the response to **W1**. In addition, we highlight a more detailed motivation table of the masking strategies as follows:\n\n|Masking|Motivations|Execution|\n|-|-|-|\n|**Input Masking**|Achieve multi-degree GPU parallelization.|Mask invalid elements at the beginning.|\n|**Obstacle Masking**|1) Avoid choosing a corner vertex as the first element of the RES; 2) Avoid unnecessary corner vertex connection.|1) Mask all obstacle vertices at the beginning. 2) When a newly generated rectilinear edge does not overlap with obstacles, re-initialize the activation mask as the obstacle mask.|\n|**Visited Masking**|Construct valid RES following the criterion of Lemma A.4.|Use masking to generate a visited point and an unvisited point for each rectilinear edge.|\n|**Activation Masking**|Avoid generating rectilinear edges that overlap with obstacles.|Each time a newly generated rectilinear edge overlaps with one or more obstacles, the elements in the activation masking corresponding to the corner vertices of these obstacles are activated.|\n\n\n> **W3: Distribution of obstacles used in evaluation appears to be limited. & Q3: Do the real-world datasets contain obstacles? ... and if having many overlapping obstacles harms performance.**\n\nThank you for raising this concern and proposing the insightful questions.\n\n**Obstacles in real-world datasets** do exist in different kinds of patterns, including unaccessible regions and local congested regions (we tend not to connect pins via these congested regions). Take global routing, an EDA task, as an example, local congested regions are grid cells with no capacity. Based on this, these obstacles are **rectilinear, sparse, non-overlapped, and dynamically changing during routing**. Though no obstacles are overlapped in real-world datasets, our method can easily handle overlapped obstacles because the vertex corner of one obstacle within another obstacle will not be connected, or there will exist a rectilinear edge overlapped with such obstacle. Thus, overlapping obstacles will not harm performance.\n\n**How do we generate obstacles?** As the obstacles are dynamically changing, we randomly generate obstacles with width/height in [0.05, 0.95] for a 1x1 rectangular region, where obstacles are not overlapped with each other, not overlapped with any given pins, and always within the 1x1 rectangular region. This setting is versatile to span a wide range of obstacle patterns. Please refer to visualizations in Fig. 8-17 for clarification, where polygons (adjacent rectangular obstacles in Fig. 8c) and dense obstacles (Fig. 15c) are all included in the datasets.\n\n> **Q1: The phrasing of Theorem 2.5 indicates that the tree corresponding to the RES is only an RSMT for P ...  it is unclear if V’(O) is a particular subset of obstacle vertices.**\n\nThank you for correctly pointing it out. For more rigor, the theorem statement should read: “…its corresponding tree is an optimal **OARSMT** for $P$ under obstacles $O$.” We will update it in our revised manuscript and note that it does not affect our main conclusion.\n\nOn the other hand, $V′(O)$ is dynamically determined during inference: the masking strategy activates obstacle corners only when an edge intersects an obstacle (Sec. 3.2). This avoids enumerating all corners and avoids unnecessary corner vertex connection.\n\n> **Q2: Given the title of the paper, I suspect the authors believe the OOD generalization ... would greatly add to the relevance of this paper beyond VLSI.**\n\nThank you for your constructive suggestion and the insightful anticipation towards more generalized fields. Apart of the answers to **W1** and **W2**, the paradigm “train on the base instance, generalize to constrained variants” hinges on two ingredients: \n1) Theoretically optimal (or near-optimal) representation that compactly encodes constraints (here: RES + obstacle corners). \n2) Dynamic action masking that instantiates constraints at inference time without retraining. \n\nTo the best of our knowledge, this constitutes a new paradigm in RL-based combinatorial optimization. We plan to systematically investigate its applicability to other classical problems in future work, such as constrained routing and scheduling.\n\n> **Q4: Given the apparent strong similarities with REST, it would be nice if the authors could offer a direct comparison. Is the main innovation over REST the dynamic masking strategy?**\n\nKey innovations lie in theoretical and engineering extensions to handle obstacles without retraining:\n- **Novel theoretical guarantee**: Theorem 2.5 proves that an optimal RES for OARSMT can be constructed using only pins and obstacle corner vertices, which is non-trivial and enables zero-shot obstacle avoidance.\n- **Engineering extensions**: Unlike prior work REST, our masking strategy enables **multi-degree GPU parallelization** and **end-to-end obstacle handling during inference**, addressing scalability and efficiency gaps in existing methods.\n\nIn summary, we have the following direct comparison to REST beyond Table 1:\n\n|Aspect|REST|OAREST (ours)|\n|-|-|-|\n|**Obstacle Avoidance**|❌ Handle pins only|✅ Zero-shot obstacle handling via obstacle masking and activation masking|\n|**Degree flexibility**|❌ Fixed input size|✅ Multi-degree GPU parallelization via input masking|\n|**Theoretical guarantee**|Optimality of RES in RSMT|Optimality of RES in OARSMT by connecting pins and a selected subset of obstacle corners|\n|**Inference time**|Scales poorly for mixed sizes|Linear via batching|\n|**Rectilinear edge representation**|Pins only|Pins + selected obstacle corners|\n\n> **C1: Font in Table 3 is too small for readability.**\n\nThank you for proposing this concern. We will increase the font size in the revised manuscript.\n\n***\n\nWe hope this response could answer your questions and address your concerns. Thank you again for your suggestion, which has made our work more complete."}, {"review_id": "5vpM4bYoYt", "reviewer": "Reviewer_qtQz", "summary": "This paper presents OAREST, a reinforcement learning-based framework for constructing obstacle-avoiding rectilinear Steiner trees, supported by a theoretical guarantee of optimality for the RES formulation. Experimental results demonstrate that OAREST achieves superior effectiveness and efficiency on both RSMT and OARSMT benchmarks, particularly in obstacle avoidance, without requiring obstacle-specific training.", "questions": "- What are the model shapes of the encoder and the decoder?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n- This paper presents a novel RL-based approach to solving the obstacle-avoiding RSMT problem. The overall method is innovative and provides a fresh perspective for this challenging task.\n- The visualizations in this paper are well-designed and effectively illustrate the proposed method. Furthermore, experimental results show that the proposed approach achieves significant performance improvements over previous methods.\n- Theoretical analysis is provided to guarantee the feasibility of obtaining optimal solutions through RES generation, which further strengthens the contribution of this work.\n\n\n\nWeakness:\n- The scalability of the proposed method is still limited, as it has only been evaluated on instances with a moderate number of pins.\n- The paper introduces a large number of formal mathematical formulas, some of which seem unnecessary and may make the work harder to understand.\n- I suggest that the authors cite more works on reinforcement learning (RL) for EDA, such as [1].\n\n[1] Lai, Yao, Yao Mu, and Ping Luo. \"Maskplace: Fast chip placement via reinforced visual representation learning.\" NeurIPS (2022).", "was_revised": true, "final_justification": "I keep my score.", "rebuttal": "We sincerely appreciate your valuable feedback. Please find our point-by-point response below:\n\n> **W1: The scalability of the proposed method is still limited, as it has only been evaluated on instances with a moderate number of pins.**\n\nThank you for raising this point. While our current experiments focus on ≤50 pins, this range already covers nearly **99% of nets in the widely-used ICCAD19 benchmark** (Table 2). Moreover, Fig. 6(b) shows that the model generalizes gracefully to unseen 51-100-pin instances with only a modest error increase (<3 %). We agree that exploring even larger scales is an exciting future direction and have added a discussion in Section 6 to clarify this roadmap.\n\n> **W2: The paper introduces a large number of formal mathematical formulas, some of which seem unnecessary and may make the work harder to understand.**\n\nThank you for pointing this out. To balance rigor with readability, we have:\n\n- **Streamlined the main text**: only necessary definitions 2.1–2.4 and theorem 2.5 remain; all auxiliary lemmas and proofs are relocated to the appendix.  \n- **Added intuition**: a concise, non-technical sketch immediately precedes Theorem 2.5 (lines 207–209), clarifying why and how RES optimality enables obstacle avoidance.  \n\nWe hope these efforts make the theory more approachable while preserving the contribution.\n\n> **W3: I suggest that the authors cite more works on reinforcement learning (RL) for EDA.**\n\nThank you for your suggestion. In the revised manuscript, we will provide a more detailed discussion of RL4EDA beyond RSMT, including additional literature [1-3].\n\n[1] Maskplace: Fast chip placement via reinforced visual representation learning.  \n[2] A Hierarchical Adaptive Multi-Task Reinforcement Learning Framework for Multiplier Circuit Design.  \n[3] Reinforcement Learning Policy as Macro Regulator Rather than Macro Placer.\n\n> **Q1: What are the model shapes of the encoder and the decoder?**  \n\nThe encoder and decoder architectures are standard and therefore relegated to **Appendix B.3**.  \n\n- **Encoder**: a **multi-head attention** stack (Transformer-style) that maps the embedded pin/obstacle positions into a latent representation of shape. \n- **Decoder**: a **pointer network** that autoregressively attends to the encoder output and returns a sequence of $(n-1)$ rectilinear edge pairs, as outlined in **Algorithm 1**.\n\nExact layer dimensions, hidden sizes, and parameter counts are provided in `./models/actor_critic.py` of the anonymous repository.\n\n***\n\nWe hope this response could answer your questions and address your concerns. Thank you again for your suggestion, which has made our work more complete."}]

Author rebuttal:

Meta-review: This paper proposes OAREST, a reinforcement learning-based framework for constructing an Obstacle-Avoiding Rectilinear Edge Sequence (RES) Tree for VLSI. The raised concerns are addressed by the rebuttal, and the reviewers give score 5. The strengths of the paper include: 

- Solid theory: sound optimality result tailored to obstacles; clarifications provided (wording fix for Theorem 2.5).

- Practical innovation: masking strategy that cleanly instantiates constraints at inference, enabling both batching and obstacle avoidance without retraining.

- Strong results: better quality and runtime vs. SOTA baselines (incl. GeoSteiner/ObSteiner); >96% obstacle-avoidance success on random obstacles; generalizes to 100-pin cases with <3% error increase.

- Relevance to EDA: Focus on 3–50 pins matches ICCAD19 distribution (vast majority of nets); method slots into existing flows.

- Clarity improvements post-rebuttal: added intuition around masking/generalization and a cleaner theory presentation.

It is a clear acceptance.
Decision: Accept (poster)