DSBRouter: End-to-end Global Routing via Diffusion Schr\"{o}dinger Bridge
Authors: Liangliang Shi
Shenhui Zhang
Xingbo Du
Nianzu Yang
Junchi Yan
Venue: ICML 2025 poster (2025)
Keywords: Global Routing
Diffusion Schrodinger Bridge
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: Global routing (GR) is a fundamental task in modern chip design and various learning techniques have been devised. However, a persistent challenge is the inherent lack of a mechanism to guarantee the routing connectivity in network's prediction results, necessitating post-processing search or reinforcement learning (RL) to enforce the connectivity. In this paper, we propose a neural GR solver called DSBRouter, leveraging the Diffusion Schr\"{o}dinger Bridge (DSB) model for GR. During training, unlike previous works that learn the mapping from noise to routes, we establish a bridge between the initial pins and the routing via DSB, which learns the forward and backward mapping between them. For inference, based on the evaluation metric (e.g. low overflow), we further introduce a sampling scheme with evaluation-based guidance to enhance the routing predictions. Note that DSBRouter is an end-to-end model that does not require a post-step to ensure connectivity. Empirical results show that it achieves SOTA performance on the overflow reduction in ISPD98 and part of ISPD07. In some cases, DSBRouter can even generate routes with zero overflow.

DSBRouter: End-to-end Global Routing via Diffusion Schrödinger Bridge
Liangliang Shi" Shenhui Zhang
Xingbo Du
Nianzu Yang* Junchi Yan 12
Abstract
Global routing (GR) is fundamental task mod- ern chip design and various learning techniques have been devised. However, persistent chal- lenge is the inherent lack of mechanism to guar- antee the routing connectivity in network's 's predic- tion results, necessitating post-processing search or reinforcement learning (RL) to enforce the con- nectivity. In this paper, we propose neural GR solver called DSBRouter, leveraging the Diffu- sion Schrödinger Bridge (DSB) model for GR. During training, unlike previous works that learn the mapping from noise to routes, we establish a bridge hetween the initial pins and the routing via DSB, which learns the forward and backward mapping between them. For inference, based on the evaluation metric (e.g. low overflow), we fur- ther introduce a sampling scheme with evaluation- based guidance to enhance the routing predictions. Note that DSBRouter is an end-to-end model that does not require post-step to ensure connectiv- ity. Empirical results show that achieves SOTA performance on the overflow reduction in ISPD98 and part of ISPD07. In some cases, DSBRouter can even generate routes with overflow.
Chip Carves
(b) Raw data
(c) Predicted bubs
(d) Rourcs
Net
DPM
HubRouter
DSBRuuter
Steiner poiza
(a) Chip
DSB prikal by gralian
(c) Initial pins
(1) Routes
Figure I. Global routing in chip design via different methods. (a) a real chip canvas from ISPDU7. (b) The data is fed into DPM in HubRouter. The red stripe represents the congestion in the existing chip, while the green stripe is the stripe mask. (c) predicted hubs. (d) generated routes by RL or other prot-processing algorithms. (c) Input pins DSBRouter. (f) generated routes by DSBRouter.
2022a), placement (Hao et al., 2021; Shi et al., 2023c), etc. With VLSI netlists containing millions or billions of nets, global routers must interconnect pins while minimizing wirelength and avoiding overflow in a limited area. However, even in the simplified '2-pin' scenario that connects cach net with only two pins under specific constraints, has proven to be No-complete (Paulus et al., 2021).
1. Introduction
Traditional works (Cho et al., 2007; Kastner et al., 2002) often rely on heuristics to solve greedily. However, the diver- sity and scale in the modern chip design industry, introduce new challenges for classical algorithms, requiring continu- ous updates and improvements by human experts. To reduce reliance on manual efforts and enhance overall design au- tomation and quality, learning-basee methods have been introduced, yet these methods suffer from notable limita- tions as shown in Tab. 1. For instance, approaches like (Liao et al., 2020) leverage deep reinforcement learning (RL) to obtain solutions but require substantial time for route gen- eration. Others, e.g. HubRouter (Du et al., 2023) produce solutions directly via generative methods (Li et al., 2022b; Yan et al., 2018; Li et al., 2021). However, the generated re- sults often rely on second-stage heuristics or RL techniques to ensure global connectivity. This raises a natural question: Can we directly generate high-quality, connected routes in
Global routing (GR) (MeMurchie et al., 1995; Liao et al., 2020; Cheng et al., 2022) has emerged as one of the most intricate and time-consuming phases in the modern design flow of Very Large Scale Integration (VLSI) (Kramer & Van Leeuwen, 1984), distinet from other stages such logic synthesis (Neto et al., 2021), floorplannning (Li et al.,
"qqual contribution Correspondence author 'Shanghai Insti- tute for Mathematics and Interdisciplinary Sciences, Shanghai, China "Scoool of Artificial Intelligence and School of Com- puter Science, Shanghai Jiao Tong University, China. Correspon- dence to: Junchi Yan <yanjunchi @ www..ssuuuc..m edu.ueedd.n..... This work is supported by NSFC (92370201, 62222607). Code available at https://gtthub.com wwt.tthuuu.ooocccooooooeooeetttt Thinklab SSTEAa---TSTEEEAAALL...
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
an End-to-End manner without second-phase corrections? This property is algorithmically nice as it aligns the training and inference without additional steps in inference.
of Hanan grid (Hanan, 1966) and escape graph (Ganley & Cohoon, 1994) are frequently utilized to formulate the short- est RSMT while cireumventing obstacles (Liu et al., 2012), considering the intersection points within these graphs as potential locations for Steiner points.
In this paper, we propose DSBRouter, which utilizes the Dif- fusion Schrödinger Bridge (DSB) model (De Bortoli et al., 2021) for route generation. Unlike previous generative mod- els (Du et al., 2023) that treat initial pins as conditions and learn a mapping from noise routes, the proposed DS- BRouter learns both the forward and backward mappings between initial pins and routing results, enhancing perfor- mance through alternating parameter learning. During the inference process, to better align with the final evaluation metrics (e.g., low overflow) for the routing task, we fur- ther introduce an evaluation-bass -based guidance technique that improves the accuracy of the generated results. Extensive experiments show that DSBRouter significantly improves overflow and achieves fate-of-thhear performance on pub- lic benchmarks. This paper contributes as follows:
Traditional Global Router. combinatorial problem and can be formulated as 0-1 inte- ger linear programming problem thus one can solve it with general solver. Traditional routing algorithms commonly split global routing into two primary stages to manage con- gestion: Steiner topology generation and rip-up and reroute (RRR). The former employs the FLUTE algorithm (Chu & Wong, 2005), utilizzig lookup tables to create Steiner trees with minimal wirelength for each net. However, FLUTE does not consider congestion. During this phase, most routers use edge shifting to alleviate congestion by mov- ing edges out of congested regions (Chu & Wong, 2005), while Nthu-Route 2.0 (Chang et al., 2008) introduces a novel history-base basse cost function that records and analyzes previ- ous routing congestion, dynamically adjusting the routing cost to enhance overall routing quality and efficiency. To re- solve congestion within the RSTs, traditional routers employ RRR, iteratively removing initially routed nets in congested zones and utilizing maze routing to optimize wirelength and congestion simultaneously. This process becomes signifi- cantly time-consuming as chip design complexity and scale increase. Thus, accelerating congestion resolution through deep learning-basee methods can improve the overall per- formance of global routing algorithms.
Global routing is actually a
1) To our best knowledge, we are the first to successfully introduce DSB (De Bortoli et al., 2021) to the global routing problem while incorporating the alignment of data, and the devised DSBRouter establishes the forward and backward mappings between the initial pins and the routing.
2) We show how to effectively integrate optimization evaluation-based guidance into the DSB model, with direct gradient feedback from the instance- wise objective score, enabling it to optimize while ensuring general feasibility (i.e. connectivity in this paper).
3) It achieves strong performance without post-processing techniques for the feasibility of final results. In particu- lar, DSBRouter achieves SOTA performance and, in some datasets, even achieves an overflow reduction of 100%.
Learning-based Router. the feasibility and benefits of optimizing wire length, as well as the effectiveness of applying neural networks to global routing. These studies include generating pin- connection orders (Liao et al., 2020), segments (Cheng et al., 2022), or customized hub points for rectilinear Steiner trees (RST) (Du et al., 2023). However, the primary challenges in practical global routing lie in managing the complexity of large-scale nets and preventing overflow when routing resources are limited. In such cases, detours play a critical role in mitigating congestion, since the shortest RST-such as the one shown in Fig.1 produced by HubRouter (Du et al., 2023) may not be feasible in practice. The chip layout can be analogized to an image, where each pixel signifies a tile in global routing. Images of varying channels denote pin locations and grid edge capacities. The resultant points can also be represented as binary image.
Various works have explored
2. Related Work
2.1. Global Routing
The Task of Global Routing. Given the intricate nature of VLSI routing dilemmas, the circuit layout, such Fig. 1a, is divided into rectangular regions termed global cells (Cho et al., 2007). The challenge of global routing can be con- ceptualized as a grid graph G(V, E), where each GCell is depicted as a vertex (v E V), and neighboring GCells are linked by an edge (e E E) symbolizing their shared bound- ary. Chip designs commonly incorporate two or more metal layers for routing purposes. Each metal layer is assigned to either a horizontal or vertical orientation, and their mapping onto a two-dimensional grid graph is illustrated in Fig. lb. The global router will designate a cluster of interconnected GCells, connected by multiple edges, to each net as its rout- ing outcome to link all pins, typically forming a Rectilinear Steiner Tree (RST) (Chu& & Wong, 2005). The principles
2.2. Diffusion Schrüdinger Bridges and Applications
Given two marginal distributions and reference stochas- tic process between them, the Schrödinger Bridge (SB) (Schrödinger, 1932) aims to find a process that mini- mizes the Kullback-Ledd Leibler divergence relative to the refer-
2

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Table 1. Characteristics of global routing approaches. Classical and RI-bbased methods are sensitive to pin scale, while existing generative based methods typically decompose the task into a two-stage point generation and connection pipeline. DSBRouter, in this paper, only one model is needed to ensure end-to to-eto- generation from large-scale pins to routes, while also considering the quality and connectivity of the generated routes, without any post-processing.
MODEL
TYPE
MULTI-PIN
CONNECTIVITY
SCALABILITY
END-TO-END
DRL (Lian et al., 2020)
RL GENERATIVE GENERATIVE + RL
X
PRNet (Cheng et al.. 2022)
X
A'
HubRouter (Du el al., 2023)
V
V
X
NeuralSteiner (Liu el al., 2024)
ML + CLASSICAL POST-PROCESSING GENERATIVE
V
X
DSBRouter (Ours)
6" SCALARLE FOR SOE-SHOT GENERATION, BUT NOT SCALARLE FOR POST-PROCESSING.
ence process in path spaces, which is a generalization of en- tropic optimal transport (Shi et al., 2023a; 2024b). Although a closed-form solution for the SB problem is generally not available, it can be approached numerically via Iterative Proportional Fitting (IPF) (Fortet, 1940) or Iterative Marko- vian Fitting (IMF) (Shi et al., 2023b). (De Bortoli et al., 2021) propose the Diffusion Schrödinger Bridge (DSB), viewed as numerical approximation of IPF. The first it- eration of DSB recovers the score-based generative model (SGM) introduced by Song et al. (2021b). With further it- crations, DSB parametrizes not only the backward process but also the forward process. Subsequent studies (Shi et al., 2023b; Peluchetti, 2023) have built upon DSB, introducing refinements that further improve its theoretical foundations and practical applicability. In particular, Tang et al. (2024) proposes theoretical simplification of DSB that integrates SGM as the initialization for DSB, accelerating its conver- gence. However, existing DSB algorithms generally fail to utilize the aligned data (Somnath et al., 2023).
3. Methodology
In this section, we present our proposed DSBRouter, starting with an approach overview.
3.1. Preliminaries and Approach Overview
Overflow (OF). Let edge e(u, v) represent the boundary between GCell and GCell v. The capacity c(u, v) is the available routing resource on edge e, while the demand d(u, v) is the number of routes that traverse it. The resource r r(u, v), which can actually be utilized for routing is defined:
r(u, v) c(u, v) d(u. v).
(I)
When r(u, v) O. overflow occurs. Global routing results with excessive overflow may require time-consuming rip- up and reroute process (Chen & Chang, 2009) or even place- ment adjustments to ensure successful routing, Hence, in addition to finding the shortest paths for each net, the global router must also aim to minimize overflow occurrences. To reduce OF in the generated routes. DSBRouter proposes an Or-enietted objective score function to perform sampling with guidance in the inference stage, which will be intro- duced in Sec. 3.3. The overview of DSBRouter is illustrated in Fig. 2. As an End-to- FaddttoEnnt -nd learning model, DSBRouter takes the initial pins with congestion heatmap as inputs and directly outputs a route with strong connectivity. During training, defined in dsb as the backward process from pins to routes, we provide the model with distribution XN and train it to produce distribution Xo. The transition of X N to X also relies on the noiser scheduler introduced in Tang et al. (2024), besides the backbone neural network of DSBRouter. In the inference stage, we introduce an RSMT-based ap- proach to output the Steiner map M,(shown in the right part of Fig. 2) based on the predicted routing results So at any given timestamp. Then the suboptimal intermediate ex- pected route Si generated given M, through algorithm I. The objective score function g" is then employed to com- pute the gradient on any corner or Steiner pins (Liu et al., 2024; Du et al., 2023) in S to perform the evaluation- based guidance, as detailed in algorithm 2. After several rounds of optimization guidance by generated route is refined, preserving connectivity while
Shi et al. (2023b) investigates the performance of DSB in various application scenarios, including generative mod- eling (De Bortoli et al., 2021), optimal transport (Villani et al., 2009; Peyré et al., 2019), and high-dimensional data transition (Chen, 2023; Hoogeboom et al., 2023). Unlike optimal transport (Shi et al., 2024c;a; 2025a), focusing on optimizing the transport path between two distributions, and unconstrained high-dimensional data transition problems (e.g.. converting images of cats those of dogs), our study addresses the Global Routing problem. It involves generat- ing high-quality connected routing image distributions from the original circuit image distribution under constraints such as geometric and resource limitations. It represents a high- dimensional data transition problem with optimization con- straints. The trained DSB can directly perform transitions between seen distributions. However, the Global Routing problem, with the incorporation of geometric and resource constraints, also requires transition on unseen circuit distri- butions, generating high-quality connected routes, which is undoubtedly a significant challenge. In this paper, a Router based on DSB and an objective-oriented gradient feedback optimization (i.e., DSBRouter) is proposed to address this challenge.
steps, the final
3

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
S/2
Sampling
Inferencing
p(9"(s))
So
Steiner Map M₁
Si
S₂ Refined Routing
Sampling
((g))S))
N steps
So
S₂ Refined Routing
Outout Routing
SH
5
Backward Process
(1 a) XN + X
(1 a) XN a X2
Xg
Training
XR
a) Xo + KW
(1 (1-a) Xn + a X3 Forward Process
Aatis& Looel
Xv
X
Figure 2. Overview of DSBRouter. During training, DSBRouter straightly learns the transition between initial pins with congestion heatmap X v and connected routes Xo, in bi-direction, The hottom blue part shows how DSBRouter generates a transition trajectory between two marginal distributions, through noiser scheduler A.3.2. During the inference stage, DSBRouter performs transitions from initial pins to connected routes guided by the objective as shown in the left purple part. The right part shows that, in every step, DSBRouter constructs the Steiner map, based on the existing predicted routing results So to output the suboptimal expected routing results St. Then the optimal objective g" is computed, and the gradient of Equation 11 is employed to refine the generated route with low connectivity. After several rounds of optimization, the final routing results Sx is derived. at coefficient parameter, X6: predicted Xo.
optimizing overflow and wirelength. In general combina- torial optimization problems, it often very difficult- even practically infeasible-tu to directly specify the objective score of given instance. However, in the Global Routing problem, DSBRouter can output solution at each infer- ence step to make the computation of the objective score for the given instance possible, even if the routing solution disconnected. We respectively introduce the details of DSB training and gradient feedback in See. 3.2 and Sec. 3.3. Training and inference phases are detailed in Appendix A.
initially drawing XN ~ Ps and iterate the ancestral sampling T Conversely, the sampling x ~ Pa (c.g.. the forward transition) is also feasible. To solve the SB problem, many researchers employ the Iterative Proportional Fitting (IPF) (Ruschendorf, 1995) to address it and (Tang et al., 2024) dissect the optimization of the joint density into a series of conditional density optimization problems by introducing the Diffusion technologies:
w 2011 = arg min ( [K L(TgR /
(ajeer)) m ON+1: Ps).
2n
2n+1 : ON+1, mo pr]- 7 2n+22 = arg min (agnn(KZen ( [1|])
3.2. Global Routing Learning via Schrödinger Bridge
To optimize Eq. 3, DSB follows the common practice em- ployed in SGM (Ho et al., 2020; Song & Ernon, 2019) to assume Tt+1je- Tej++1 as Gaussian distributions and model the bi-directional transitions. The training loss of DSB is:
The SB problem is a famous entropy regularized (OT) prob- lem first introduced in (Schrödinger, 1932) and further dis- cussed in De Bortoli et al. (2021); Tang et al. (2024). Given reference diffusion Pref E ΦN++1 with finite N steps, the data distribution (i.e. the distribution of routes pr in this paper) and the prior (i.e. the distribution of initial pins with congestion ps) are often set as known to solve the SB to find the closest diffusion π to the reference (w.rt. Kull- back-Leibler divergence on path spaces) which satisfies '²* arg min, ( L(T (Prr)) π 11:
CBE,1 -16 Pp
[[ (X6+1) X + 1 113)
Ppp+1 =E =B(xxxx01 10
[1 (xx) - -x 12
(4)
where V1
P (x(+1) BB+1 (x++1); 9"
FF(()). 12
(xx) p" 22++1 denote the forward and backward joint densities, respectively.
22n and
11, To Pr.
TN Tr.
p.).
(2)
More specifically, Rk (xx+1 = [Xxx+11; X + 7 (xx); 27 is the forward process and Phc++1 (xx()+++) N N(x;; X + 7 b (x++1), 27x+11 I) is the backward
where To and N are the marginals of π at time step 0 and N, respectively. Upon acquiring the optimal solution of T",
we can sample Xy ~ Pr (e.g., the backward transition) by
4

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Algorithm 1 Expectation Route Generate
the backward process (i.e., Ps - Pr), and use the sampling method in Tang et al. (2024):
1: Input: Initial pins 77: route distribution X at the
timestamp k;
Po (xx|XE+1) -X(x 14+1 (xx+1, (0)+ ok)11
2: Output: Expected route distribution S
3: Initialize Sü = 0;
xx + Not1 (xo- Xx+1),
4: Compute predicted route distribution
76+1
(6)
Xx po(xx|xx+1);
271++
0k++1
5: for instance j E 2t do
7k+1
6: Extract routing result S for instance
7: Extract hubs h² (Du et al., 2023) in S and merge hi
3.3. DSBRouter with Gradient Feedback
with Tál to n/ - 1/0 h²:
The incorporation of objective optimization is necessary and important, which enables the direct involvement of objective and effective search over the solution space towards mini- mizing the score. Note that our task focus on the backward process P.. (xx [x++ Ps - Pr- At each step k, the model is to estimate p& (xx xx++)). For the purpose of objective optimization, we aim to estimate pa (x Xx++1 g") where g" is the optimal objective score given route distribution X₁:
8: for combation c(i,c) in r7' (x+) where i E rp (xx) A
e E Tp' (xx) Ai + do
9:
if i. # e.I or i.y # e.y then
10:
(xx) - s (xx) U (i.z, e.y) U (e.rr
11:
end if
12:
end for
13:
Construct the steiner map M. utilizing 7 (xxx:
14:
Obtain the RST S/ from M through algorithm 3;
15:
Update S₁ < S₁ US/:
g" arg min S(Xx)
16: end for
17:
Return S1.
to effectively guide the backward inference process toward P. = arg min S(X,). We will later show that this guidance X,
Algorithm 2 Evaluation -raauatton-Based Guidance
can be realized by the model trained in Sec. 3.2 without relying on additionally trained nets.
1: Input: Expected route distribution S1; Predicted route
distribution X₁ at timestamp k; Noiser N;
2: Output: Noiser distribution X6+1;
Objective. As the generated samples X pr (xxx) at any given step i are not guaranteed to satisfy the con- straints, we propose an easy RSMT algorithm 3 to cor- rect the predicted routes so that we can obtain the expec- tation overflow (Ru (7)())) and wirelength E "a (7({x) given X2 ~ Pr Pr (x+xx)+)) where ()xx) represents pins in given routes Xg. The implementa- tion of the algorithm is detailed in Appendix A.6. Then the objective function can be defined as:
3: Obtain E xx--p.(x xx11) (x11)((((A))) (1())) from S₁ and (x)(x))
from Ny;
4: Compute p(g" (.rx)) as
exp(1Vxx-1 (D (x x(+2) (1(x++1))-
((n(x++))))
5: Update X2 with Proposition 3.1;
6: X++1 = ((x)).
7: Return X-+1-
S(xx) =
(8)
process, where (x) and (x)+1) are drift functions. Normally, DSB uses two separate neural networks to approximate BB (ki, x) Re (x) = x + (x) and (k, = FT (x) = x FF (x), 8¹ and 6² denote the network parameters. In DSBRouter, we employ the terminal reparameterized DSB used in Tang et al. (2024) to tailor loss by Eq. 4 into:
1 (xe (17(8x)) 0(n((x)) + c(xx)),
where c(xx) E Ex (p. Ny ( (x+)) W (xx()) rep- resents the penalty function that focuses on minimizing the wirelength. ((7(3x)) and W(n(xx)) represent the overflow and wirelength of predicted samples 5 out- put by the model at timestamp k + 1. To enhance the model's ability to generate highly connected probabil- ity matrices with low overflow, at step k, we aim to bridge the gap between the overflow ((n(xx)) and the expected overflow Eg Eg. (K./xxa))))))
[I] [ (X6+11) xoll]]
fgg.
E (xxx
Ca Exxxxx))ng [ (xx) - xN (5)
(n7(x)) (1))))))))))(()))))))) given density X ~ Pr (&x (x++1) with the gap between W (17(+)) and E Sampp (Kx (8u1xa+1) (xxx)
In practice, DSBRouter uses two uvit-b based SGM to ap- proximate the transitions between P. and py.. For (2n+11 1) -thh epoch of DSB, we refer to the optimization of the backward network B and we optimize the forward network in F with (2m + 2)th epoch. During the inference stage, we focus on
)) as the penalty.
Evaluation- Guidance in Backward Transitions. With the optimization objective prepared, we aim to estimate Po Po (xx 1 g*). While po (xx [ g*) can be estimated
5

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Table Correctness rate and generation time on ISPD07 benchmark. Comparison with hubrouter variants w/o RL as post-process.
HUBROUTER
HUBROUTER (GAN)
HURROUTER (DMM)
METRIC
CASE
DSBROUTER
(VAE)
SMALL-4
0 0
0.44 = 0.009
0.38 + 0.008
1.000
Correctness Rate
SMALL
0 0
0.09 + 0.003
0.06 + 0.005
1.000
LARGE-4
0
0 = 0
0 0
1.000
LARGE
0
0 0 0
0 0
1.000
SMALL-4
1.101 0.018
1.012 0.003
1.060 + 0.010
1.015
Wirelength Ratio
1.041 0.004
1.002 0.001
1.172
1.001
LARGE-4
1.114
1.005
0.002
1.100 1.001
1.001
LARGE
1.044 0.011
1.001
0.000
1:244:2.000
1.450
SMALL-4
6,11 + 0.23
6.96 0.07
742.33 4.41
2643
Generation Time (GPU Sec)
SMALL
8,88 1: 0.13
9.10
739.04 8.20
2671
LARGE-4
7.39 0.41
8.01 0.09
741.09 + 3.19
2687
LARGE
11.01 1 0.11
12.34
742.11 + 4.20
2571
via the following proposition 3.1, which is adapted in the classifier guidance technique (Dhariwal Nichol, 2021):
Set Z = SE exp(-E(E', (x,,((EE xx441)), then we have
(13)
Proposition 3.1. The optimization-eenooreed denois- ing probability estimation po(Xx|x<+1.g') equals to (Z is normalizing constant).
Ex Xx- (x442) ( (n7(x++1) - 0(7(x++1)) log Z.
The gradient of Eq. 12 can be obtained as
Though DSB not a denoising tion still works well as Ho & Salimans (2021) points out that guidance can also be applied the SDE process and DSB uses SGM (Song al., 2021b) the backbone. The can
model, this proposi-
Vxet1 [gg(("[xx+1]
(14)
Vxet1 (D (x412) (m((x++1) -(((x))))))
proof is listed in Appendix A.5. While p=(xx directly obtained from the trained neural network, the main challenge is to estimate (xgg(>)). Since X is not accessible at step & + 1, we apply Taylor expansion to approximate p(g" xx++1) around X = X given that X₁: Xx+1:
Thus, in this framework, p(g" (xx) can be estimated as p(g (xx) & exp([Vx, (P (oteppp--eelllll (x442) (1xx)) (n(xx+1)) ((g(xe+)))) by Eq. 10 and 13. Finally, the guided backward transition is achieved by Proposition 3.1.
4. Experiment and Analysis
log p(g" [xx) R
logp(g' xx++) + [xx++ logp(g" [xx+1]] x++1)
4.1. Datasets and Setups
[V log Xx+1 Tx + log (xx+1)
Datasets. For training, We use ISPD07 benchmarks (Nam et al., 2007) to build the marginal distribution P. and nthurouter (Chang et al., 2008) to perform routing to con- struct distribution pr. The size of figures in the training set fixed to 64 x 64, following the settings in et al. (2023). Additionally, we also introduce the ISPD98 routing benchmarks (Alpert, 1998) perform global routing and compare metrics between different methods.
[Vx, log.(g" x ]] Xx+1,
(9)
where log p(g" xx+1) [xx+, log (xx (xk44)]]xx*++ is irrelevant to Xg. By exponentiation, we have:
p(g" (xx) exp([Vxx:
(10)
To determine p(g" (x++)), we energy-based model (Le-
Cun et al., 2006) to describe the density p(g" (x++)x+) and use former part of the objective of Eq. 8 as the energy function:
Metrics. For ISPDO7 routing benchmarks, we select the metrics: correctness rate (Crrt, the percentage of routes where all pins are connected within a single route), wire- length ratio (WLR (Cheng et al., 2022), the ratio of the gen- erated route length the GT length), generation time (taken to generate the route), and connectivity ratio (percentage of the routes of complete connection). In the experiments involving ISPD98, we use wirelength (WI., overflow (OF), and runtime as metrics.
EEE, x = E E (xa 1)) (n((x)) - (1)))))))))))))))))
-()(x))). (11)
It measures how closely (x)())) aligns with expectation ~ (x xx41) (n)xx))). This design aligns with our goal of optimizing the overflow naturally Then, Gibbs distribu- tion is employed to tailor the probability density:
exp(-E((E, xx+1))
Baselines. Three traditional routers (Geosteiner (Juhl et al., 2018), Labyrinth (Kastner al., 2002), Flute (Wong
p(g 1x++1) p[g1|x++1) J exp(-E(E)) X(+1))
(12)
6

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Table Wirelength (WL) & overflow (OF) on ISPD98 & ISPD07. Comparison of classical global routing and ml-based methods.
METRICS
MODEL
IBMÜ1
1BM03
IBM04
IBMU5
ADA03
ADA04
GEOSTEINER"
60142
165863
145678
162734
409709
9330748
8865643
LARYRINTH"
75909
201286
187345
195856
420581
ESS
61560
168841
146819
167233
412816
9422071
8883791
HR VAE
64703 1: 1498
176492
6830
159968 1: 3281
179895
5274
434942 1: 2916
WL
HR-DPM
66464
1586
190588
2337
168454 2486
183696
1736
475820 + 5516
HR-GAN
61056 151
167545
236
147050 + 208
164298 + 326
411857 472
9347032
8879952
NEURALSTEINER
61735
170405
148036
166648
415684
9459117
9003952
DSBROUTER OURS)
61435
174016
152862
163942
420464
29478326
24276147
GEOSTEINCR'
3342
7399
3944
7420
401
142254
45050
FLUTE+ES'
3100
7121
3699
6889
317
136661
41996
HR-VAR VAE
4721 1:
9919
692
10433 1: 1299
OF
HR. DPM
4933 700
14117 1 1309
9344 818
11471 871
2390
126
HR-GAN
3491 - 64
7481 + 31
4010 + 42
7551 + 22
419 +
142119
45411
NEURALSTEINER
2200
3800
2100
2700
18
728
97
RSBROUTER(OURS
EXPERIMENTAL RESULTS CITED FROM (LIU ET AL., 2024)
without RL as post-processing, For HubRouter, we repeat the experiments 3 times and present the mean values. The ISPD07 benchmarks, outside the training set, are divided into 'small-4", 'small', 'large-4', and 'large'. '4' in their names represents no more than 4 pins in the chip. 'small' and 'large' represent the Half perimeeri wirelength of the net is less or more than 16. Additionally, we cancel RI. as post-processing while using the generated routes as the terminal distribution for HubRouter. As an e2e model, DS- BRouter not only maintains strong connectivity but also generates competitively shorter routes. Tab. 2 highlights DSBRouter's s ability to generate routes with high Crrt, all 100% connected across all tested cases. However, all vari- ants of HubRouter achieve an average connectivity ratio of only 27% in the smallest-scale route generation (small-4). In other route generation cases, the connectivity ratio is approximately exactly 0. And the third line in Tab. 2 shows DSBRouter's 's ability to generate routes in low WLR. Due to the gradient recomputation and multiple inferencing steps, DSBRouter is behind in generation time. It needs to be mentioned that we do not include PRNet (Cheng et al., 2022) shows poor connectivity in (Du et al., 2023).
Table Training epochs DSBRouter and inference time (sec-
onds) with varying inferencing steps on ibm01.
Steps
Training (epochs)
Inference (s)
OF
WL
10
2774
924
64237
24
64
4378
784
68982
50
64
10881
421
70172
24
192
4491
1428
61433
Table Module ablation in DSBRouter. Comparison of the unchanged DSBRouter with modified models removing gradient guidance (GD) module and neural network (NN), respectively.
METRICS
MODEL
IBM01
WITHOUT GD
3561
OF
WITHOUT NN
5971
DSBROUTER
1430
WITHOUT GD
61003
WL
WITHOUT NN
75975
DSBROUTER
61435
Chu, 2008) and ES (Chu & Wong, 2005)) well as two ML-based state-of-the-ea art methods (HubRouter (Du et al., 2023) and NeuralSteiner (Liu et al., 2024)) are employed as baselines. However, Neural's preprocessing steps using CUGR (Liu et al., 2020) and the corresponding core code have not been made publicly available. Consequently, for NeuralSteiner, only report the results provided in its original paper (Liu et al., 2024).
4.3. Routing Results on Real-Worke Benchmarks
WL, OF, and generation time are evaluated on ISPD98 (ibm01-05) and ISPD07 (adaptec and 4) across various methods. As shown in Tab. 3, DSBRouter significantly reduces the total overflow compared all other tested meth- ods. Compared with the SOTA ML-based method Neu- ralSteiner, DSBRouter hits an average reduction of 90.4% and up to 100% on ibm02, ibm05, ada03, and ada04. For wirelength, DSBRouter has better performance on median and small-scale benchmarks. DSBRouter does not incur too many additional nets on ISPD98, maintaining within 3.2% compared with NeuralSteiner and even outperforming NeuralSteiner ibm01 and ibm04. However, on ISPD07, DSBRouter produces longer wirelength compared to Neu-
Other Implementation Details. Details of training/test datasets and other protocols are given in Appendix A. Addi- tional results are listed in Appendix B.
4.2. Correctness/oomectiiity on Unconnected Cases
We conducted the Crrt and WLR evaluation on the same test cases from part of ISPD07 benchmarks and compared DSBRouter with three different structures of HubRouter
7

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Table 6. Generation time on ISPD98 and ISPD07 benchmark. Generation time evaluated across all tested methods.
METRIC
MODEL
IBM01
IB002
IB00
IBM04
IM05
ADA03
ADA04
GROSTEINER
1.00
2.25
1.66
2.10
3.70
331.23
266.51
LABYRINTH
7.11
11.08
11.61
42.03
12.70
FLUTE+RES
3,14
4.90
5.88
15.49
7.88
403.61
371.11
TIME
HR- VAE
10.14 0.07
9.81
11.20:10.05
10. 10.18.00111
12.39:0.300
HR-DPM HR TR-GAN
1833.48
# 42.11
2816.77
22.21
3009. 100011--0 + 19.00
3842.61
24.41
4191.71 = 36.29
39.22 1.03
44.41 + 0.92
49.79 + 1.99
68.11 3.38
76.28 + 3.42
1442.71
1501.11
DSBROUTER(OURS)
4491
5667
8418
10745
11313
115438
125589
ralSteiner. We declare that this is reasonable because the ISPD07 test set (ada03 and ada04) we choose includes a massive number of pins and even contains nets with an HPWL exceeding 2000, and thus, it is much larger in scale than the training set. The evaluation- guidance used by DSBRouter during sampling imposes constraint on op- timizing overflow, which may allow it to bypass congested areas and generate routes with longer WL but lower OF. In terms of generation time, as shown in Tab, 6, DSBRouter lags behind other methods, which we attribute to the longer sampling steps required by DSB during inference.
backbones. Results in Tab. 4 indicate that as the number of inferencing steps increases, inference time also increases, from 2774 to 10881 as inferencing steps increase from 10 to 50. As the number of inferencing steps increases, the infer- encing time naturally increases well. When the number of inferencing steps increases from 10 to 50, the inferencing time increases from 2774 to 10881, However, under the same training step size, the effect of increasing the number of inferencing steps is not entirely negative. As shown in the first three rows of Tab. 4, with the same training depth, as the number of inferencing steps increases, DSBRouter can generate routes with lower OF, but correspondingly. the WL also increases. As the training depth increases, DSBRouter generates routes with shorter WL at the cost of OF.
4.4. Ablation Study
Influence of FG and NN. To study the influence of the introduced evaluation-based guidance (EG) module in DS- BRouter, we ablate the guidance module from the model architecture. Additionally, to study the role of predicted routes at any timestamp during inference of DSB, we also ablate the output of the neural network (NN). The modi- fied models are tested in comparison with the unchanged DSBRouter on ibm01. We state that the modified model without EG cannot guarantee connectivity of the generated route in the testing case so we employ Geosteiner the post-processing to complete the routing. Tab. 5 indicates that OF is affected by both EG and the output of the NN. We can witness a significant increase both in WL and OF from the output of model without NN. We also claim that the model without EG but with Geosteiner as post- processcns can generate a shorter route all due to the inherent devotion of Geosteiner optimizing WL. an increase of OF is con- firmed. The results on ibm01 imply that both EG and DSB can help DSBRouter acquire congestion-avoidite
5. Further Discussion and Conclusions
End-to-End design for global routing. We have investi- gated the potential of DSB for the global routing task in VLSI. In supervised scenarios, DSB can directly establish a bidirectional transformation bridge between data Distri- bution and prior Distribution. Mcanwhile, we introduce the goal-oriented sampling with evaluation- guidance technique from SGM into the inference phase of DSB, en- abling DSBRouter to produce high-quality, connected routes even in unsupervised settings. To the best of our knowledge, DSBRouter is the first learning-basee end-to-end router.
Conclusion. In this paper, we propose an End-to-End ml- based DSBRouter for the global routing problem in VLSI. DSBRouter is the first End-to-Ent router to perform routing tasks and outperforms other state-of-art two-stage routers in reduction of overflow by an average of 90%.
routes.
Influence of inferencing steps. In DSB, the forward and backward processes share the same number of inferencing steps. The number of inferencing steps determines the step size required for the DSB transform the marginal distribu- tion ps (or p.) to pr (or p.). We conduct evaluations the inferencing steps of DSB to study the effect of inferencing steps on the generation time, OF, and WL. We fixed the training (inferencing) steps to 64 (192 in all other exper- iments mentioned above) and set the inferencing steps to 10, 24 (the default value in all other experiments mentioned above), and 50, respectively, to train three different DSB
Limitations. Due to the non-monotonically noise injection strategy and meaningful pr, Ps in the DSB-based sampling process, accelerated sampling techniques such as DDIM in DPM cannot be directly applied. Also, at each step k, computing the g" and subsequent gradients based on the network's reparameterized outputs requires substantial computational resources. Consequently, despite employing parallel processing techniques, DSBRouter still suffer from long running time. In the future, we will accelerate the inference with the distillation-base models (Song et al., 2023; Shi et al., 2025b) to improve the efficiency.
8

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Impact Statement
Dosovitskiy, A., Beyer, L.,, Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
This paper presents work whose goal is to advance the field of Machine Learning and Artificial Intelligence for Elec- tronic Design Automation (AI4EDA). There are many po- tential societal consequences of our work, none of which we feel must be specifically highlighted here.
Du, X., Wang, C., Zhong, R., and Yan, J. Hubrouter: Learn- ing global routing via hub generation and pin-hub connec- tion. Advances in Neural Information Processing Systems, 36, 2023.
References
Alpert, C. The ispd98 circuit benchmark suite. In Proceed- ings of the 1998 international symposium on Physical design, pp. 80-85, 1998.
Fortet, R. Résolution d'un système d' d'équations de m. schrödinger. Journal de Mathématiques Pures et Ap- pliquées, 19(1-4)83--105, 1940.
Anderson, B. D. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313- 326, 1982.
Ganley, J. L. and Cohoon, P. Routing a multi-terminal
critical net: Steiner tree construction in the presence of obstacles. In Proceedings of IEEE International Sympo- sium on Circuits and Systems-ISCAS" 994, volume 1, pp. 113-116. IEEE, 1994.
Chang, Y.-J,, Lee, Y.-T., and Wang, T.-C. Nthu-route 2.0: A fast and stable global router. In 2008 IEEE/ACM In- terntiional Conference Computer-Aided Design, pp- 338 343. IEEE, 2008
Hanan, M. On steiner's problem with rectilinear distance. SIAM Journal on Applied mathematics, 14(2):255-265, 1966.
Chen, H.-Y. and Chang, Y.-W. Global and detailed routing. In Electronic Design Automation, pp. 687-749. Flsevier, 2009.
Hao, R., Cai, Y.. Zhou, Q. and Wang, R. Drplace: A deep learning based coutability-drivee visi placement al- gorithm. Journal of Computer-Aided Design & Computer Graphics, 33(4):622-633 2021.
Chen, T. On the importance of noise scheduling for diffusion models. arXiv preprint arXiv:2301.1097) 2023.
Chen, Z., He, G., Zheng, K., Tan, X., and Zhu, J. Schrodinger bridges beat diffusion models on text-to- speech synthesis. arXiv preprint arXiv:23 2023.
Ho, and Salimans, T. Classifier-free diffusion guidance. In NeurlPS 202/ Workshop on Deep Generative Models and Downstream Applications, 2021.
Cheng, R., Lyu, X., Li, Y., Ye, J., Hao, J., and Yan, The policy-gradices placement and generative routing neural networks for chip design. Advances in Neural Information Processing Systems, 35:26350-26366 2022.
Ho, J., Jain, A., and Abbeel, Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851, 2020.
Cho, M., Lu, K., Yuan, K., and Pan, D. Z. Boxrouter 2.0: Architecture and implementation of a hybrid and robust global router. In 2007 IEEE/ACM International Conference Computer-Aided Design, pp. 503-508. IEEE, 2007.
Hoogeboom, E., Heek, J., and Salimans, T. simple diffu- sion: End-to-end diffusion for high resolution images. In International Conference on Machine Learning, pp- 13213-13232 PMLR, 2023.
Hyvärinen, A. and Dayan, P. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Chu, and Wong, Y.-. Fast and accurate rectilinear steiner minimal tree algorithm for vlsi design. In Proceedings of the 2005 international symposium on Physical design, pp. 28 35, 2005.
Juhl, D., Warme, D. M., Winter, P., and Zachariasen, M. The geosteiner software package for computing steiner trees in the plane: an updated computational study. Mathemat- ical Programming Computation, 1054)2487-532, 2018.
De Bortoli, V., Thorton,, J., Heng, J., and Doucet, A. Diffu- sion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695-17709 2021.
Kastner, R., Bozorgzadeh, E.,, and Sarrafzadeh, M. Pattern routing: Use and theory for increasing predictability and avoiding coupling. JEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 21(7): 777-790, 2002.
Dhariwal, P. and Nichol, A. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794 2021.
9

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Kramer, M. and Van Leeuwen, J. The complexity (or wire- routing and rinding minimum area layouts for arbitrary vlsi circuits. 1984.
McMurchie, L.., Ebeling, C., and PathFinder. A negotiation- based performance-driven router for fpgas. In Proceed- ings of the 1995 ACM 3rd International Symposium on Field-Phe Programmable Gate Arrays, PP. 111-117, 1995.
LeCun, Y., Chopra, S., Hadsell, R., Ranzato, M., Huang, F., et al. A tutorial on energy-based learning, Predicting structured data, 1()), 2006.
Nam, G.-J,, Yildiz, M., Pan, D. Z.,, and Madden, P. H. Ispd placement contest updates and ispd 2007 global routing contest. In Proceedings of the 2007 international sympo- sium Physical design, pp. 167-167, 2007.
Léonard, C. A survey of the schr\," odinger problem and some of its connections with optimal transport. arXiv preprint X11:11308.0215,2000 2013.
Neto, W. L., Moreira, M. T., Li, Y., Amarù, L., Yu, C., and Gaillardon, P.-E. Slap: A supervised learning ap- proach for priority cuts technology mapping. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pp. 359-864. IEEE, 2021.
Li, X., Peng, K., Huang, F., and Zhu, W. Pef: Poisson's equation-based large-scale fixed-outline floorplanning. IEEE Transactions on Computer- Design of Inte- grated Circuits and Systems, 2006):200,,,015, 2022a.
Paulus, A., Rolinek, M., Musil, V., Amos, B., and Martius, G. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In International Con- ference on Machine Learning, pp. 8443-8453, PMLR, 2021.
Li, Y., Shi, L.,, and Yan, J. lid-gan: an iid sampling per- spective for regularizing mode collapse. arXiv preprint arXiv:2106.00550 2021.
Li, Y., Mo, Y., Shi, L., and Yan, J. Improving generative ad- versarial networks via adversarial learning in latent space. Advances in neural information processing systems, 35: 8868 8881, 2022b.
Peluchetti, Diffusion bridge mixture transports, schrödinger bridge problems and generative modeling. Journal of Machine Learning Research, 24(374):1-51, 2023.
Liao, H., Zhang, W., Dong, X., Poczos, B., Shimada, K., and Burak Kara, L. A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 142 (6):061701, 2020.
Peyré, G., Cuturi, M., et al. Computational optimal trans- port: With applications to data science. Foundations and Trends in Machine Learning, 11 11(5-6)3355-611, 2019.
Lipman, Y., Chen, R. T. Q., Ben-Hamu, H., Nickel, M., and Le, M. Flow matching for generative modeling. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Ruschendorf, Convergence of the iterative proportional fitting procedure. The Annals of Statistics, pp. 1160-1174, 1995.
Schrödinger, E. Sur la théorie relativiste de l'électron et I'interprétation de la mécanique quantique. In Annales de I' T'institu Henri Poincaré, volume 2, pp. 269-310, 1932.
Liu, C.-H., Kuo, S.-Y., Lee, D., Lin, C.-S., Weng, J.-H., and Yuan, S.-Y. Obstaclc-avoiding rectilinear steiner tree construction: A steiner-point-base algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(7):1050-106) 2012.
Shi, L., Zhang, G., Zhen, H., Fan, J., and Yan, Understand- ing and generalizing contrastive learning from the inverse optimal transport perspective. International conference machine learning, 2023a.
Liu, G.-H., Vahdat, A., Huang, D.-A., Theodorou, E. A., Nie, W., and Anandkumar, A. 12sb: image-to-image schrödinger bridge. In Proceedings of the 40th Inter- national Conference on Machine Learning, 1CML'23. JMLR.org, 2023.
Shi, L., Fan, J., and Yan, J. Ot-clip: Understanding and generalizing clip via optimal transport. In Forty-first International Conference on Machine Learning, 2024a.
Liu, J., Pui, C.W.,, Wang, F., and Young, E. F. Cugr: 3d global routing with proba- bilistic resource model. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Shi, L.,, Shen, Z.,, and Yan, J. bounle- optimal transport for advanced clustering and classification. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 38, pp. 14982-14990 2024b.
soailledrroutabiitt---eee
Liu, R., Ding, S., Sui, J., X., Bu, D., et al. Neuralsteiner: Learning steiner tree for werffoowaaooiiin global routing in chip design. In The Thirty- Annual Conference on Neural Information Processing Systems, 2024.
Shi, L., Zhen, H., Zhang, G., and Yan. J. Relative entropic optimal transport: a (prior-awarg, matching perspective to (unbalanced) classification. Advances in Neural Infor- mation Processing Systems, 36, 2024c.
10

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Shi, L., Li, Y., Zeng, K., Tu, Y., and Yan, Optimal flow transport and its entropic regularization: GPU-friendll matrix iterative algorithm for flow balance satisfaction. In The Thirteenth International Conference on Learning Representations, 2025a.
Wong, Y.-C. and Chu, C. A scalable and accurate rectilinear steiner minimal tree algorithm. In 2008 IEEE Interna- tional Symposium VLSI Design, Automation and Test (VLSI-DAT), PP. 29-34. IEEE, 2008.
Yan, J., Liu, X., Shi, L., Li, C., and Zha, H. Improving maximum likelihood estimation of temporal point process via discriminative and adversarial learning. In IJCAI, pp. 2948 2954, 2018.
Shi, L.., Shi, Z., and Yan, J. SelKD: Selective knowledge distillation via optimal transport perspective. In The Thir- teenth International Conference on Learning Representa- tions, 2025b.
Shi, Y., De Bortoli, V., Campbell, A., and Doucet, A. Dif- fusion schrödinger bridge matching. Advances in Neu- ral Information Processing Systems, 58:6218-62222. 2023b.
Shi, Y., Xue, K., Lei, S., and Qian, C. Macro placement by vire-mask-guided black-box optimization. NeurIPS, 2023c.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference machine learning, pp. 2256-2265. PMLR, 2015.
Somnath, V. R., Pariset, M., Hsieh, Y.-P., Martinez, M. R., Krause, A., and Bunne, C. Aligned diffusion schrödinger bridges. In Uncertainty in Artificial Intelligence, pp. 1985-1995. PMLR, 2023.
Song, J., Meng, C., and Ermon, S. Denoising diffuusin implicit models. In International Conference on Learning Representations, 2021a.
Song. Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poole, B. Score- based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021b.
Song, Y. Dhariwal, P., Chen, M., and Sutskever, Consis- tency models. In ICML, pp. 32211-32252, 2023.
Tang, Z., Hang, T., Gu, S., Chen, D., and Guo, B. Sim- plified diffusion schr\." odinger bridge. arXiv preprint arXiv:2403. 14623, 2024.
Villani, C. et al. Optimal transport: old and new, volume 338. Springer, 2009.
Vincent, A connection between score matching and de- noising autoencoders. Neural computation, 23(7):1661- 1674, 2011.

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
A. Implementation Details
A.I. Connection between SGMs and Simpiflied Diffusion Schrödinger Bridges
We incorporate the simpiflied diffusion schrödinger Bridge (Tang ct al., 2024) as the backbone of our generator in RoBtre In this section, we will take an insight into the connection between generative models (especially SGMs) and DSB pave the way for the tailored gradient search brought into DSB.
In earlier studies (Schrödinger, 1932; Léonard, 2013), it has been demonstrated that the optimal solution to the Schrödinger Bridge problem can be characterized by the following stochastic differential equation (SDE):
dX;- = (f + (t) V log e (X,, dt + g(t)dWW e: Xo ~ Pdata:
(15)
dX, (f (t) V log v [ , t))dt g dWt XT Perior:
where W; is Wiener process and We its time reversal. v & E C (10, T), Rd4) are time-varying energy potentials that constrained by the interconnected PDEs:
ht - Va V2 ff f- TT(( V2 v)
0e
= - V= (vfff + (rg v2 $).
öt
(16)
S.L. (xx 0) 0)
Pdatt:
(x, (x, T) = Pprior
More generally, we can achieve the distribution of SB at time by:
Pt tx,(((t)
(17)
et al., 2015; Song et al., 2021a; Song & Ermon, 2019) connect two densities through a dual process: forward process that transitions the data distribution, Pdata. toward a prior distribution Pprior and a reverse process, typically guided by neural networks, that converts the prior back to the data distribution. These two processes can be modeled as Markov chains. Given an initial data distribution Pdota and a target prior distribution Pprior, the forward process Pk+ 1|A (T++1 (xk) is designed to transition from Po = Pdato step-by-step ipproximation of Pprior- This process generates sequence To:N from the (N+1) intermediate steps. This trajectory's joint probability distribution is then formally defined as:
Score-based Generative Models (SGMs) (Ho et al., 2020;
N --1
p(ZO.N) = (o(o II
P1+1je A=
(18)
Through the backward process, the joint density can also be reformulated as a time-reversed distribution:
N-1
p(No.N) (NN
II
(19)
however, directly computing PæJK+ 1 (zx) (x++1) is typically challenging. SGM utilizes simplified approach that regard the forward process as a gradual adding of Gaussian noise:
P1+1IR [Tx) = (( + (x 17.
(20)
follows that for a sufficiently extensive N, the distribution PN will converge to Gaussian distribution, which we set as Pprior. Moreover, the temporal inversion in Equation 19 can be analytically approximated (Anderson, 1982; Hyvärinen & Dayan, 2005; Vincent, 2011) 1) as Subsequently, SGM employs neural networks s0 k + 1) to approximate the score term v Pk+1 (I*+1), thus the reverse process can be effectively modeled. By sampling z, Pprior. followed by iteratively applying ancestral sampling vua IA ~ PaIE++1 1 (2)1), culminating in the estimation of xn Pdata- While the diffusion and denoising processes modeled in SGM (Song & Ermon, 2019) can also be formulated as continuous-time Markov chains. The forward process can be represented as a continuous-time SDE:
dx, ((, + v 2dB
(21)
12

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Table Summary of the test dataset. We respectively show scale size, verticallorizontal capacity, number of nets, and aver- age/maximum number of pins for each net.
CASE
IBM01
IBM02
IBM03
IBM04
IBM05
ADA03
ADA04
SIZE
64 x 64
80 x 64
80 64
96 64
128 x 64
774 779
774 x 779
CAP.(V/H)
24/28
44/68
40/60
40/46
84/126
62/62
62/62
NETS
11507
18429
21621
26163
27777
466295
515304
AVG.PINS
4.31
4.88
4.10
3.86
5.25
4.02
3.71
MAX.PINS
42
134
55
46
17
3713
3974
SGM
X Diffusion Process
XT
X
Denoising Process
(xo Gaussian noise)
(Gaussian noise - xx
Forward Process
(xo >x1)
X
X1
DSB
X
X
Backward Process (Xo - xx1
Figure 3. Similarities and differences between SGM and DSB. In SGMs, the marginal distribution zo is gradually transformed into an approximate standard Gaussian distribution øT by introducing niose through SDE. During the inference (denoising) phase, the SDE is then used to recover the original distribution from the approximated Gaussian distribution. In contrast, DSB learns a conditional probability density,
enabling direct transition between the two maginal distributions zo æ1, during infereneing. Regardless of whether SGMs or DSB, the inferencing at timestamp It always depends on the preceding æx-1 (or in DSB) or the original distribution zo (or v in DSB).
Upon close inspection, (t) log (X,, t). Notably, SGMs may be regarded as particular instantiation of DSB when the non-linear drift terms are set to zero (i.e. (6X,,, t) = C). For Variance Preserving (VP) (Ho et al., 2020) and Variance Exploding (VE) (Song & Ermon, 2019) noise schedule in SGMs, f(X,,t) = - 04 X, where Or E R and the denoising model is essentially sloving Equation 15 using learnable network.
observe that Equation 21 and Equation 15 differ only by the additional non-linear drift term
More general, other dynamic generative models, c.g., Flow Matching (FM) (Lipman et al., 2023), I'BB (Liu al., 2023). Bridge-TTS (Chen et al., 2023), can be encapsulated within the framework of Equation 15 by selecting appropriate functions for f(X,,t) t) and d (X,,,)). In addition, as depicted in FIG. 3, both DSB and other SGMs, during their inference phase, exhibit actions that can be categorized as predicting the next distribution #A-1 (or 3&+1 in DSB) based the current distribution Fy. which only relies on and is independent of g". This means that the derivation (Equation 22) still works in DSB. This unification of dynamic generative models suggests the possibility more profound linkage between DSB, SGM and other dynamic generative models, which suggests the rationality to bring the commonly used gradient search scheme in SGM into DSB.
13

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
symmetrical schedule y
0.010
0.008
%
0.054
0.002
0.020
0.0
0.2
Figure 4. Linear schedule for "M.
A.2. Experimental protocols
A.2.1. DATASETS AND HARDWARE FOR EXPERIMENTS
Real-world Datasets ISPDO7 (Nam et al., 2007) and ISPD98 (Alpert, 1998) are employed in this work. In line with (Du et al., 2023), we construct the expert training datasets with low overflow using nthurouter (Chang et al., 2008) to route on parts of ISPD07 benchmarks, including bigblue4, newblue4, newblue5, newblue6 and newblue7. Each case has about 60k samples. Thus the training datasets have a total of nearly 300K samples. We initialize the capacity given by the benchmarks and sequentially route the nets using the results of (Chang et al., 2008). Each time the capacity is updated, a condition image, consisting of the current capacity and the positions of pins be routed in the next net, is generated. Meanwhile, a ground-truth route image is generated and saved correspondingly. By clipping them to the same scale 64 64 (if possible) randomly. For the tested cases in Tab. 2, choose newbluel, newblue2, bigbluel and bigblue2 from ISPD07, outside the training sets, with total 10k samples. Summary of tested cases in ISPD98 are shown in Tab. 7. We follow the same processing steps introduced in (Du et al., 2023) to have the tested ISPD98 cases prepared.
Training of the backbone of DSB is conducted on a machine with an Intel Xeon Platinum 8480+ CPU, 8 NVIDIA H800 GPUs, and 2.0TB RAM. All experiments in this work are conducted on machine with an Intel Xeon Platinum 8480+ CPU, NVIDIA RTX 4090 GPUs, and 460GB RAM.
A.3. DSBRouter Network Architecture
1. BACKBONE
We use the uvit_b architecture, based on the ViT structure (Dosovitskiy et al., 2021), as the backbone for our model. The input to our model an image of size batch sizex3x64x64. The first channel represents the pin map, the second channel represents the horizontal congestion heatmap, and the third channel represents the vertical congestion heatmap. The final output is also a three-channel image, where the second and third channels remain unchanged, and the first channel contains the predicted map that reveals the locations of all the pins in the predicted route. After being input into the model, the image is first divided into non-overlapping 4x4 patches, resulting in (64/4)x(64/4) patches in total. Each patch is then mapped to a 51 512-dimensional embedding vector. These encoded vectors are subsequently fed into a Transformer layer (13 layers) to learn and capture spatial and contextual information between patches. Finally, the vector is resized to match the original input size for image output.
A.3.2. NOISE SCHEDULER
Noise scheduler determines how the data between the two distributions is transformed, which is equivalent the noise addition method used in SGM. In the DSB framework, both the prior and posterior distributions represent meaningful data distributions, rather than the standard Gaussian distribution. Therefore, the noise intensity cannot monotonically change in either the forward or reverse process. Consequently, in DSB, we adopt the same approach as in (Tang et al., 2024), where the noise scale "t undergoes a symmetric linear variation: 7 increases first and then decreases linearly, with the magnitude of increase and decrease being the same, as depicted in Fig. 4
14

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
A.3.3. MOEL PARAMETERS
We use fixed learning rate of (r 0.001 and a batch size of 256. During each epoch, we repeat the training process for each batch 4 times.
A.4. Baselines
The baselines referred in Tab. 3 are introduced follows:
1) GeoSteiner (Juhl al., 2018): the optimal RSMT construction solver.
2) Labyrinth (Kastner et al., 2002): A classical routing algorithm that explores how the concept of pattern routing can be utilized to guide the router toward a solution that minimizes interconnect delay while preserving the routability of the circuit.
3) FLUTE (Wong& & Chu, 2008): A fast and accurate RSMT construction method using a look-up table. It is important to note that this approach can achieve the optimal solution for nets with up to 9 degrees.
4) Eege Shifting (Chu & Wong, 2005): fast, practical RSMT-based algorithm that leverages specialized lookup table for small nets and refined recursive splitting approach for larger nets.
5) HubRouter (Du et al., 2023): A global router for RST construction based on reinforcement learning. The hub is generated using a diffusion model, followed by reinforcement learning for RST construction.
6) NeuralSteiner (Liu et al., 2024): A state-of-the-art two-stage global router. The candidate points are predicted using an RCCA-enhanced CNN, and routing is performed using an RST construction algorithm based on greedy strategy.
A.5. Proof of Proposition 3.1
Proof. The density p[xx|><+1> g*) can be derived by:
p(x++1, Xk.
p(x++1 + Xk. xk,g")
p(x++1: g*)
p(g" X1++ (p(x++1)
p(g" |x+1 X Sx)p((x XX++ (p(X)-1)
p(g 10++))((00+11)
p(g" 11411. (((x Xx+1)
(22)
p(g xx+1)
as p(g" (xx+1) is not depend on Xs. thus it can be regarded as a constant. Now we can obtain (x xx+1,g")) x
p(g*(xx+1)
A.6. Algorithms
Algorithm extends the route output by model at timestamp by expanding routes with poor connectivity to incorporate potential steiner points, thereby generating routes with lower OF. After obtaining the Steiner Map M,, we have a greedy disjoint-set based RSMT construct method derive an OF-minimium RST given M, and The proposed method detailed in algorithm 3. The training process and inferencing process are detailed as follows:
B. Additional Results
B.1. Route Generation Results
Examples of the initial pins, generated routing results by DSB and real routes are depicted in 5.
B.2. Relative Error on Part of ISPD98 cases
To judge the improvement of gaining on the optimal wirelength rather than the absolute value, we further compare the relative error in Tab. 8, where the relative error is computed as (WL- LB)/LB LB. Here, LB denotes the theoretical lower bound. As shown the table, the WL promotion DSBRouter can hit the lowest on the cases of ibm01 and ibm04. However, as the scale increases, the realtive error of DSBRouter also increases dramatically, which leaves improvement space for DSBRouter.
15

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Algorithm 3 RSMT Construct
1: Input: Steiner Map My Routing result S);
2: Output: OF-minimium RST S
3: Initialize disjoint-set U1 given $
4: if Ven(Ui-finde
then
5:
6: end if
7: Initialize disjoint-set U2 by assigning pin E Mÿ to themselves;
8: Construct edges set (i,e) e) E E;i E e E M2 where pin i and pin are always vertically or horizontally two nearest points;
9: Initialize Si:
while len(U2.find) f 1 do
11: Edge (i,c) argminE;
OF S S (i,e);
12:
Update U2:
end while
15: Return S/
Algorithm 4 Training of DSB
1: Input: Number of training iterations iters; training steps (inference steps) steps; repeat times Primesi batch size be;
noise scheduler N; Target distribution pr;
2: Output: Model Parameters 0:
3: Initialize model parameters 0;
4: for iter to iters do
5: Sample batch C P, where [x| be;
6: for 0 ryimes do
7: for 8 = 0 to sleps do
Apply nosise adding to x, = Nxx s); 9: Obtain target XN from py;
8:
10: Descend the stochastic gradient loss of 5;
end for
end for
13:
end for
14: Return Model Parameters 0.
Table 8. Relative error on ISPD98. The routing results of (Juhl et al., 2018) are treated as the theoretical lower bound. Optimal results are bold.
MODEL
IRM01
IRM02
IBM03
IBM04
IBM05
ADA03
ADA04
LOWER BOUND
60142
165863
145678
162734
409709
9330748
8865643
LABYRINTH
0.262
0.213
0.286
0.203
0.026
FLUTE+RES
0.023
0.017
0.007
0.027
0.007
0.009
0.002
HR- VAE
0.075
0.024
0.064
0.04
0.098 1 0.022
0.105
0.033
0.061 .L 0.007
HR-DPM
0.5 + 0.026
0.149 = 0.014
0.156 + 0.017
0.128
0.010
0.161 + 0.013
HR-GAN
0.022 + 0.002
0.010 = 0.001
0.009 + 0.001
0.002 0.009
0.005 1 0.001
0.001
0.001
STEINER
0.026
0.027
0.016
0.024
0.014
0.013
0.015
(OUROUTER(OURS)
0.021
0.049
0.049
0.007
0.026
3.15
2.73
16

---

DSBRouter: End-to-end Global Routing via Diffusion Schrüdinger Bridge
Algorithm 5 Sampling Routes with evaluation-based guidance
Input: Initial distribution psi inference steps (training steps) stpes; Model parameters 0; batch size be; noise scheduler
N:
2: Output: Generated routing distribution Xy:
3: Initialize Xv = 0;
4: Obtain size size of psi
5: for size > do
6: for s
steps do
7:
if 0 then
8:
X X,;
9:
X,+2 X
10:
end if
11:
Obtain routing result x, (0(xx(Xx+1))
12:
Obtain Expected routes S1 given x, through algorithm 1;
13:
Compute Vx..1 (Ex, x, 1 (1(xx (7(xx+1)) - (fr(x++1)):
14:
Obtain Vx.., log p(g"" (x+1) through equation 14;
((g'(x,+1)
15:
Obatin refined routing result pa (x, x.+1.g") through proposition I;
16:
Apply noise adding to X₃ = N(x.s) s);
8 * steps then X,+1 X.: end if
19:
20: end for
21: XN <- N Ux;;
22: end for
23: Return XN.
Figure 5. Initial pins (first line), Generated routing results by DSB (sccond line), and the real routes (third line). All were randomly sampled in 'small-4', 'small', 'large-4", and 'large'.
17


Reviews:
[{"review_id": "C6vtgkA7tF", "reviewer": "Reviewer_HZXX", "summary": "This paper introduces DSBRouter, an end-to-end neural global routing solver based on the Diffusion Schrödinger Bridge (DSB) model. Traditional learning-based approaches to global routing (GR) often require post-processing heuristics or reinforcement learning to enforce connectivity, leading to inefficiencies. In contrast, DSBRouter directly learns a bi-directional mapping between initial pins and final routing solutions, ensuring connectivity without the need for a second-stage correction. DSBRouter leverages a novel evaluation-based guidance mechanism to optimize routing outputs based on overflow minimization and connectivity constraints. Extensive experiments show that DSBRouter achieves SOTA.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for thoroughly evaluating our paper and providing valuable and constructive feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.\n\n> **Weakness: Efficiency is a big concern for the proposed method. (I would like to thank the authors' honesty for reporting this problem.) Could you go into details on how to improve the efficiency of the proposed method.**\n\nThanks for your valuable comment. The DSB in our proposed DSBRouter, like the standard [DDPM](https://proceedings.neurips.cc/paper/2020/hash/4c5bcfec8584af0d967f1ab10179ca4b-Abstract.html) and [SGM](https://proceedings.neurips.cc/paper/2019/hash/3001ef257407d5a371a96dcd947c7d93-Abstract.html?ref=https://githubhelp.com), is based on the diffusion and denoising processes, and therefore, efficiency concerns are also present. To address the efficiency issues, we consider the following two approaches:\n\n1) Adopt the techniques of the [Consistency Model](https://openreview.net/forum?id=FmqFfMTNnv) to reduce the sampling steps.\n\n2) Recomputing the optimization objective every few steps during the inference process, instead of at each step, which simplifies the computational of evaluation-based guidance.\n\nWe are working hard on implementing the above two strategies and the experiments which take days to finish. We will add the results in our later rebuttal and final version.\n\n> **Suggestion: The formulae are way-too crowded in page 5 and 6. I think it might be better to consolidate them into simpler forms.**\n\nThanks for your insightful comment. We have revised the paper. The modified sections will be presented in our final version.\n\n> **Question: While I understand the constraint of page limits, the solution to faster inference in \"limitations\" is somehow vague.**\n\nThanks for your comment. We have revised the statement in the 'limitations' section regarding the difficulty in achieving accelerated inference as follows: \"Due to the nonmonotonically noise injection strategy and meaningful $p_r, p_s$ in the DSB-based sampling process, accelerated sampling techniques such as DDIM in DPM cannot be directly applied.\"\n\nThe reasons why acceleration techniques similar to [DDIM](https://arxiv.org/abs/2010.02502) are difficult to implement in DSB are: In the diffusion process of DDIM, it is assumed that the noise $\\epsilon_t = \\sqrt{1-\\bar{a}_t}\\bar{z}_t$ intensity added at each time step monotonically increases as following:\n$$\n\\begin{equation*}\nx_t=\\sqrt{\\bar{a}_t}x_0 + \\sqrt{1-\\bar{a}_t}\\bar{z}_t \\quad \\bar{z}_t \\sim \\mathcal{N}(0,\\mathbf{I}), \\tag{1}\n\\end{equation*}\n$$\nwhere $\\bar{a}_t$ is a parameter that decreases with the increase of time $t$ and after $T$ steps of noise addition, $x_T$ will converge to a Gaussian distribution $\\mathcal{N}(x_T,\\sqrt{\\bar{a}_T}x_0,(1-\\bar{a}_T)\\mathbf{I})$. During the denoising (sampling) process of DDIM, the neural network predicts the noise $\\epsilon_t$ and DDIM have the following hypothesis:\n\n$$\n\\begin{equation*}\nP(x_{t-1}|x_t,x_0) \\sim \\mathcal{N}(kx_0+mx_t,\\sigma^2), \\tag{2}\n\\end{equation*}\n$$\n\nHowever, in DSB, since both $p_s$ ($x_0$) and $p_r$ ($x_T$) represent meaningful data distributions, the noise intensity cannot monotonically change during either the forward or backward processes. Thus, a symmetric noise scheduling scheme $\\gamma_t$, as shown in Appendix A.2.1, is used. Additionally, supposing that the backbone of DSBRouter also predicts noise $\\gamma_t$, predict this nonmonotonically changing target is intuitively more difficult, and since we employ IPF iteration to optimize DSB, if we were to sample using this predicted noise, the model’s training would become harder to converge. Besides, in the transition of $p_s \\mapsto p_r$ (or $p_r \\mapsto p_s$) in DSB, there is no hypothesis in equation (2). Therefore, techniques like DDIM for accelerated sampling can not directly be used to implement in the sampling process of DSB. Besides, the [DSB method](https://arxiv.org/abs/2403.14623) we follow did not use acclearated samping techniques, indicating that the use of acceleration sampling techniques in DSB still needs theoretical and practical verification.", "claims_and_evidence": "Claim: The proposed DSBRouter achieves SOTA performance. \nEvidence: Table 2 & 3", "methods_and_evaluation_criteria": "Methodology is okay. Benchmarks are canonical ones (ISPD07/98).", "theoretical_claims": "I briefly check the proof, but I could not ensure each and every detail is 100% correct.", "experimental_designs_or_analyses": "I think the experimental designs are not problematic.", "relation_to_broader_scientific_literature": "Unlike previous routing works, this paper is the first to introduce Diffusion Schrodinger Bridge to routing.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\nNovelty. This is the first to introduce DSB to routing.\n\nWeaknesses:\n\nEfficiency is a big concern for the proposed method. (I would like to thank the authors' honesty for reporting this problem.)", "other_comments_or_suggestions": "The formulae are way-too crowded in page 5 and 6. I think it might be better to consolidate them into simpler forms.", "questions_for_authors": "While I understand the constraint of page limits, the solution to faster inference in \"limitations\" is somehow vague. Could you go into details on how to improve the efficiency of the proposed method.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "juJaHE80Y7", "reviewer": "Reviewer_qcjE", "summary": "This paper introduces DSBRouter, a novel global routing (GR) solver leveraging the Diffusion Schrödinger Bridge (DSB) model. The authors aim to address the challenge of ensuring routing connectivity in network prediction results, a persistent issue in learning-based GR methods. DSBRouter learns both forward and backward mappings between initial pins and routing results, and incorporates an evaluation-based sampling scheme to enhance routing predictions. The results demonstrate state-of-the-art performance in overflow reduction on public benchmarks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for thoroughly evaluating our paper and providing insightful and valuable feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.\n\n> **Question 1: The paper acknowledges that DSBRouter has a longer generation time. What specific strategies are the authors considering for future work to address this limitation, and what is the potential for these strategies to significantly improve the runtime ?**\n\nThanks for your valuable comment. The DSB in our proposed DSBRouter, like the standard [DDPM](https://proceedings.neurips.cc/paper/2020/hash/4c5bcfec8584af0d967f1ab10179ca4b-Abstract.html) and [SGM](https://proceedings.neurips.cc/paper/2019/hash/3001ef257407d5a371a96dcd947c7d93-Abstract.html?ref=https://githubhelp.com), is based on the diffusion and denoising processes, and therefore, efficiency concerns are also present. To address the efficiency issues, we consider the following two approaches:\n\n1) adopt the techniques of the [Consistency Model](https://openreview.net/forum?id=FmqFfMTNnv) to reduce the sampling steps.\n\n2) Recomputing the optimization objective every few steps during the inference process, instead of at each step, which simplifies the computational of evaluation-based guidance.\n\nWhile we are still implementing the two improvements, we estimate that they could reduce DSBRouter’s runtime by 60%-70%. Based on the 'Ablation Study' in Table 5, we believe runtime is closely tied to the number of inference steps. With a well-trained consistency model, we expect to compute the final route using only 1/5 of the original inference steps. Additionally, Strategy 2) reduces the complexity of optimizing the computational target, further cutting the runtime by ~60%. Final results will be included in our later rebuttal and final version.\n\n> **Question 2: The training data is generated using NthuRoute. How might the choice of training data generation method affect the generalizability of DSBRouter to different routing scenarios or design styles?**\n\nThanks for your insightful comment. Regarding your question, we have the following conclusions:\n\n**Conclusion 1**: *The bias of the supervised training set towards specific metrics (OF and WL) does indeed affect the routing generalization performance of DSBRouter.*\n\nIn the paper, the optimization objective of DSBRouter focuses on optimizing the OF metric. Therefore, we use the [Nthurouter](https://ieeexplore.ieee.org/document/4681595/) results on the datasets of [ISPD07](https://www.ispd.cc/contests/07/contest.html) including bigblue4, newblue4, newblue5, newblue6, and newblue7 as the supervised training set, as Nthurouter achieves SOTA performance on OF for these datasets compared to other methods proposed in the same year. The dataset newblue3, which has the highest number of pins, was excluded because its routing results performed poorly in terms of OF metrics. On the other hand, [Hubrouter](https://proceedings.neurips.cc/paper_files/paper/2023/hash/f7f98663c516fceb582354ee2d9d274d-Abstract-Conference.html) focuses on optimizing the WL metric and uses routing results from [NCTU-GR](https://ieeexplore.ieee.org/abstract/document/5703167), which are more tailored to optimizing the WL metric, as its supervised training set. The experimental results show that Hubrouter achieves SOTA performance on WL but lags behind on OF. To verify Conclusion 1, we replicated Hubrouter's training set and trained DSBRouter-NCTU using this set. We report the routing results of DSBRouter trained with two different training sets (other settings remain the same) on the ibm01 and ibm05 dataset in Table 1:\n\nTable 1. Comparision of DSBRouter-NTHU and DSBROUTER-NCTU on two different routing scenarios.\n| |ibm01-wirelength|ibm01-overflow|ibm05-wirelength|ibm05-overflow|\n| :-: | :-: | :-: | :-: | :-: |\n|DSBRouter-NTHU|61435|1430|420464|0|\n|DSBRouter-NCTU|86776|10256|1312353|115|\n\nTo address the current issue of DSBRouter's insufficient generalization, we have recently attempted to improve the optimization objective proposed in Section 3.3 of the paper with a hyperparameter $\\tau$. Where $\\mathbb{S}(\\mathcal{P}(\\bar{\\mathbf{x}_{k}}))$ turns to $\\tau * E^o + (1-\\tau) * E^w$. The goal is to enable DSBRouter to optimize a balance between OF and WL during inference. Due to space constraints, we only report the performance of DSBRouter on the ISPD98 cases in Table 2 for the cases where \\($\\tau = 0.3$ and $\\tau = 0$\\). (Experiments show that different datasets exhibit varying sensitivities to the hyperparameters $\\tau$.) We will report the full results in future work.\n\nTable 2. Routing Results of DSBRouter on ISPD98 with modified objective.\n| |ibm01-wl/of |ibm02-wl/of|ibm03-wl/of|ibm04-wl/of|\n| :-: | :-: | :-: | :-: | :-: |\n|$\\tau=0.3$|65665/1479|213588/0 | 165930/0|176945/0|\n|$\\tau=0$|65632/1390|208405/0|165168/0|175869/0|", "claims_and_evidence": "The primary claim that DSBRouter achieves state-of-the-art (SOTA) performance in overflow reduction is generally supported by the evidence provided.", "methods_and_evaluation_criteria": "The proposed DSBRouter method is well-motivated. The use of the Diffusion Schrödinger Bridge model is novel in the context of global routing. The evaluation criteria is comprehensive.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "- Ablation Study: The ablation study is designed to assess the contribution of the EG and NN modules.  The experimental setup is clear, and the results provide some insight into the importance of these components. However, as mentioned earlier, a more detailed analysis would be beneficial.   \n\n- Influence of Inferencing Steps: The experiments on the influence of inferencing steps are well-designed.  They systematically vary the number of steps and analyze the impact on performance metrics.   \n\n- Comparison with Baselines: The comparison with baseline methods is generally sound. The authors include both classical and ML-based routers in their comparison, providing a comprehensive evaluation of DSBRouter's performance.", "relation_to_broader_scientific_literature": "- Diffusion Models and Schrödinger Bridges: The paper builds upon the literature on diffusion models and Schrödinger Bridge models.  It extends these techniques to the problem of global routing. The authors also highlight the connection between SGMs and DSB.    \n\n- Global Routing Methods: The paper thoroughly reviews traditional and learning-based approaches to global routing.  It identifies the limitations of existing methods, such as the lack of connectivity guarantees and the reliance on post-processing.  DSBRouter is presented as a solution that addresses these limitations by providing an end-to-end approach that ensures connectivity.    \n\n- Objective Guidance: The use of objective guidance in the inference phase is inspired by techniques from score-based generative models.  The authors adapt these techniques to the DSB framework to improve the quality of the generated routes.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "No.", "questions_for_authors": "The paper acknowledges that DSBRouter has a longer generation time. What specific strategies are the authors considering for future work to address this limitation, and what is the potential for these strategies to significantly improve the runtime?\n\nThe training data is generated using NthuRoute. How might the choice of training data generation method affect the generalizability of DSBRouter to different routing scenarios or design styles?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yZrSSPI8fh", "reviewer": "Reviewer_4dzK", "summary": "DSBRouter is an end-to-end neural global routing solver based on the Diffusion Schrödinger Bridge (DSB) model, which learns the forward and backward mapping between initial pins and routing results. It achieves state-of-the-art performance in overflow reduction on ISPD98 and parts of ISPD07, with some cases achieving zero overflow without requiring post-processing.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Weakness 1: This work should collect a large batch of routing results as training data, where traditional global routers do not need this process. According to Table 2 and 4, the method is not very efficient.**\n\nThanks for your valuable comment. Though traditional global routers indeed do not rely on large datasets for training, we argue that they still exhibit the following issues:\n1) **Escalating Complexity and Longer Runtime**\nAs process nodes continue to shrink and chip sizes grow, traditional methods often demand higher computational resources and longer execution time. Furthermore, these methods rely on continuous updates and refinements from human experts.\n2) **Heavy Dependence on Manually Crafted Heuristics**\nTraditional routing methods heavily depend on heuristics that are manually specified or tuned, their applicability is limited when the design environment changes.\n3) **Prone to Local Optima and Complex Multi-Objective Trade-Offs**\nWhen dealing with highly complex objectives—such as congestion, timing, power, wirelength, IR drop, and other factors—conventional methods struggle to balance all of these goals simultaneously. \n\nBy contrast, ML-based methods like DSBRouter yield routing solutions in a feasible runtime, matching or even surpassing traditional routers. They also adapt across diverse routing scenarios and need no expert updates to routing rules.\n\nAnd we admit that DSBRouter currently faces challenges from relatively longer running time. Several improvements is being considered to address the efficiency of DSBRouter:\n1) adopt the techniques of the [Consistency Model](https://openreview.net/forum?id=FmqFfMTNnv) to reduce the sampling steps.\n2) Recomputing the optimization objective every few steps during the inference process, which reduces the computation of evaluation-based guidance.\n\nAlthough we are still in the process of implementing the aforementioned two improvements, we can estimate that after these enhancements, the runtime of DSBRouter could be reduced by 60%-70%. Once the experiments are finished. The results will be added in our later rebuttal and final version.\n\n> **Suggestion 1: According to Fig. 5, the DSB-generated routes should also modified by regulations. which means it is not a pure end-to-end method.**\n\nWe believe the misunderstanding arises from unclear explanation of Figure 5. The first row shows randomly selected initial pins from our supervised dataset. The second row presents the corresponding results generated by DSBRouter, based on the first-row inputs. The third row shows the ground-truth routing results from the dataset, not DSBRouter's outputs.\n\nWe also emphasize that DSBRouter is an end-to-end global router. In ML-based methods, if the entire process from input to output is learned and optimized by a single model without losing information, it is considered end-to-end. DSBRouter uses a single model, incorporating evaluation-based guidance in the inference process with no intermediate outputs, making it an end-to-end global router.\n\n> **Suggestion 2, 3 and 4: Typo: Section 4.1, Metircs->Metrics; Figure 1, one left-bottom pin is not easy to read; In table 1, what does the label \"△∗\" mean?**\n\n$\\triangle*$ means PRNet is only scalable for one-shot generation, but not scalable for post-processing. We have add the footnode in our revised paper. The modified sections will be presented in our final version.\n\n> **Question 1: DGR: Differentiable Global Router, should be discussed.**\n\nThanks for your valuable comment. We noticed this work during our survey, but since their [GitHub repository](https://github.com/search?q=DGR%3A%20Differentiable%20Global%20Router&type=repositories) seems to be private and lacks code to reproduce the results, we did not use it as a baseline. If they release their implementation, we will conduct comparative experiments.\n\n> **Question 2: In Table 3, Why not report the mean and variance?**\n\nFor the routing results of GeoSteiner, FLUTE, ES, and NeuralSteiner, we used the experiments from [NeuralSteiner](https://proceedings.neurips.cc/paper_files/paper/2024/hash/e6617714485265b9380a5315bf3ba98f-Abstract-Conference.html). For DSBRouter, we repeated the experiments three times with no observed variance, due to the neural network's determinism and the lack of post-processing in DSBRouter. The variance in HubRouter's results is due to the inherent uncertainty in its RL-based post-processing.\n\n> **Question 3: Why the size of figures in the training set is fixed to 64 × 64, where the testing set sizes are different.**\n\nWe believe the misunderstanding is due to the \"Size\" in Table 7. The \"Size\" in Table 7 refers to the original grid size of the benchmark, not the size of the images. We applied the same clipping operation to the benchmark in the test set as we did with the training set (mentationed in Appendix A.2.1), ensuring that the size of each initial pin image and its image of routing result ground truth is 64x64.", "claims_and_evidence": "- This is the first work to introduce the DSB technique to the global routing problem to the best of my knowledge.\n\n- This paper introduces instance-wise objective scores, enabling optimization while ensuring general feasibility.\n\n- This paper claims it does not need post-processing. However, from Figure 2, there are refining steps in the inference process.", "methods_and_evaluation_criteria": "- The method is built on the Diffusion Schr ̈odinger Bridge, which can incorporate constraints into the diffusion process.\n\n\n- The evaluation criteria (Wirelength, overflow, running time) is a general evaluation metric for routing tasks.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "- The evaluation is reasonable. It would be better if the authors could report the mean and standard deviation.", "relation_to_broader_scientific_literature": "This work builds on prior global routing methods and diffusion-based models by introducing DSBRouter, which leverages the Diffusion Schrödinger Bridge to ensure connectivity without post-processing. Unlike traditional approaches, it achieves state-of-the-art overflow reduction and incorporates constraints directly into the routing process.", "essential_references_not_discussed": "[1] DGR: Differentiable Global Router, DAC 2024.", "other_strengths_and_weaknesses": "- This work should collect a large batch of routing results as training data, where traditional global routers do not need this process. According to Table 2 and 4, the method is not very efficient.", "other_comments_or_suggestions": "- In table 1, what does the label \"△∗\" mean?\n- According to Fig. 5, the DSB-generated routes should also modified by regulations. which means it is not a pure end-to-end method.\n- Typo: Section 4.1, Metircs->Metrics.\n- Figure 1, one left-bottom pin is not easy to read.", "questions_for_authors": "- In Table 3, Why not report the mean and variance?\n\n- Why the size of figures in the training set is fixed to 64 × 64, where the testing set sizes are different.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposed DSBRouter, an end-to-end neural global routing solver using Diffusion Schrödinger Bridge (DSB). The method shows good performance in real-world problems and all reviewers are positive.
Decision: Accept (poster)