acceptodds
Under review as a conference paper at ICLR 2027

Validity-Preserving Hierarchical RL for Joint Routing and Switch Placement in EDA

Abstract

Routing and switch placement are fundamental combinatorial optimization problems in chip design, requiring the joint optimization of routing topology and physical placement under strict structural, geometric and logical constraints. Existing approaches typically rely on carefully engineered heuristics that incorporate strong problem-specific biases to navigate the enormous space of possible designs. In this work, we introduce a hierarchical reinforcement learning framework for joint routing and switch placement at the level of logical communication routes. Starting from a minimal routing graph, our method progressively constructs increasingly expressive solutions through three coupled operations: switch expansion, switch placement, and route refinement. These operations preserve routing validity by construction, restricting exploration to feasible configurations where every communicating initiator-target pair has one assigned loop-free route. We explore the induced solution space using Gumbel Monte Carlo Tree Search, showing that neural-guided search substantially improves solution quality over non-learning optimization methods. Furthermore, pretraining across floorplans provides a strong initialization for fine-tuning on unseen instances. Our code will be made publicly available upon acceptance.

Primary area:
optimization
Keywords:
Reinforcement Learning, Combinatorial Optimization, Electronic Design Automation, Graphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_kpnrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a study on joint communication-route construction and intermediate-switch placement in a simplified, obstacle-aware interconnect model with fixed initiator and target locations. Its central contribution is a hierarchical graph construction that alternates switch expansion, placement on an extended Hanan grid, and route refinement. The construction process is formulated as a deterministic, sequential MDP whose state records the current route graph, switch positions, construction phase, and queues of switches and communication routes awaiting processing. Depending on the phase, the agent selects a switch to expand, assigns valid Hanan-grid positions to the affected switches, or chooses one of four local routing alternatives for each affected communication pair. Once the placement and refinement queues are emptied, the graph again represents a feasible routing configuration, and the process repeats until the prescribed switch budget is reached. The restricted construction space retains at least one globally optimal solution under their model.

A neural network jointly encodes the current route graph and the floorplan, including blockage geometry and legal switch locations. Its policy heads assign probabilities to the admissible expansion, placement, and route-refinement actions, while its value network estimates the return associated with the current state. Gumbel MCTS uses these action probabilities and value estimates to guide its simulations and improve action selection, using an upper-tail quantile-based search value and per-floorplan PopArt normalization. The terminal objective combines distinct physical-connection wirelength with one half of the summed communication-route lengths. Evaluation uses 24 synthetic training floorplans and four held-out transfer instances. The reported best-found objectives on the training instances favor Gumbel MCTS over the evaluated heuristic, random-search, genetic-algorithm, and PPO-EWMA baselines. Three-run fine-tuning experiments suggest benefits from pretraining, although Gumbel MCTS does not uniformly outperform PPO-EWMA on the held-out instances. The study does not model component footprints, detailed physical-design rules, congestion, or bandwidth constraints.

Critical strengths
  1. A structured construction for a coupled optimization problem. The route-node representation and local expansion/refinement operations provide a concrete way to optimize intermediate-switch placement and shared communication routes together. Preserving assigned-route validity after each completed cycle removes the need to recover routing connectivity from arbitrary candidate graphs. The distinction between route-specific assignments and shared physical connections is also consequential to the objective. The main technical contribution is this construction and its representational properties.

  2. Initial evidence for learned search and transferable initialization. The experiments compare multiple optimization paradigms on the same stated objective and use a common stated GPU/wall-clock budget for the four iterative methods. The separate held-out fine-tuning experiment compares pretrained and randomly initialized models over three runs and reports wall-time curves and variability. These are useful elements of the evaluation, even though the breadth and statistical support remain limited. The explicit limitations discussion and detailed solution visualizations help delimit and inspect what has been demonstrated.

Critical weaknesses

Critical Weaknesses

  1. The evidence is insufficient to establish a robust advantage or isolate the contribution of Gumbel MCTS. Appendix C.3 explicitly states that only one pretrained model is trained for each learning method, while Table 1 reports best-found objectives on the 24 training instances without variability across independent repetitions of the complete training/search procedure. These results are informative for the reported runs, but do not establish the stability of the algorithm ranking. Figure 5 and Tables 7-8 appropriately report mean ± one standard deviation over three independent fine-tuning runs, thereby quantifying variability conditional on the selected initialization. However, Appendix C.3 states that only one pretrained checkpoint is trained for each learning. Consequently, the results do not quantify variability across independently pretrained checkpoints. The authors should either repeat pretraining with multiple seeds or limit their robustness claims to the variability of fine-tuning from the particular checkpoint used. With only three runs, showing the individual-run results would also improve transparency. The comparison between Gumbel MCTS and PPO-EWMA should use explicitly matched computational budgets. Matching the number of PPO rollouts to the number of MCTS simulations is not sufficient, because these operations may have different costs. Please report best-so-far objective versus wall-clock time, the number of complete trajectories, environment transitions, network evaluations, MCTS simulations, and PPO updates, as well as the heuristic runtime. As an additional control, evaluate a fixed PPO policy through repeated stochastic rollouts under the same measured budget as Gumbel MCTS and retain the best solution. Ablations using mean versus upper-tail value estimates, conventional MCTS, and different MCTS budgets would clarify whether the gains come from tree search itself, its value estimator, or simply additional computation.

  2. The scope of validation is too narrow to establish broader generalization or practical relevance. Table 1 concerns the training instances, while transfer is evaluated on only four held-out synthetic floorplans. The switch budgets range from 2 to 5, and the instances contain 18-25 required communication pairs. A broader held-out evaluation, a reproducible instance-generation procedure, and scaling experiments are needed to establish how the method behaves across different communication structures and geometric difficulty. Reporting training-instance optimization results is legitimate, but those results should not be presented as evidence of unseen-instance generalization. The simplified abstraction is clearly acknowledged; nevertheless, its relationship to a realizable communication network remains unvalidated. Optimizing and evaluating the stated objective is appropriate, but an improvement in that objective alone does not establish improvements in chip area, congestion, timing, or bandwidth. Appendix D usefully separates wirelength and route length; additional analyses such as maximum route length or route stretch, sensitivity to the objective weight, and a modest experiment with a relevant physical or capacity constraint would better characterize the trade-offs. These measures should be chosen to match the intended application, they should not be replaced by fixed floorplan area or Appendix D's input free-space percentage, neither of which measures the quality of an optimized placement in this model.

Secondary Concerns:

  1. The provenance and physical scope of the dataset should be clarified. The paper states that the experiments use synthetic floorplans, but it does not sufficiently describe how initiator and target locations, communication pairs, blockage geometries, circuit or communication topologies, and switch budgets are generated. It is also unclear whether the instances are intended to represent abstract NoC/interconnect problems or physical circuits from a particular technology. Because component dimensions, shapes, pin locations, and technology-specific constraints are ignored, the authors should explicitly state whether all components are modeled as zero-size points, whether component variants are supported, and how these assumptions limit the applicability of the method to physical EDA. A specific PDK is not necessarily required for this abstract study, but the intended problem scope and relationship between the synthetic instances and real design scenarios should be made explicit.

  2. If accurately characterized, the following related work should be cited and discussed: Wang et al., "Exploring Search for FPGA Placement using RL", in RLC 2025 Workshop on Practical Insights into RL for Real Systems (RL4RS), 2025, available at https://openreview.net/pdf?id=nvge2HodpL. This paper explores the use of the Gumbel MCTS algorithm for FPGA placement. Although it addresses a different problem than the one studied here, both works fall within the broader area of RL for chip placement and, in particular, both employ the Gumbel MCTS technique. Prior work in this area should therefore be properly cited and discussed.

  3. The novelty discussion relative to Cheng and Yan (2021), Chen et al. (2022), and Geng et al. (2024) should be sharpened. In particular, the proposed route-node construction and intermediate-switch topology/placement decisions should be distinguished from prior joint placement-and-routing learning and prior RL/tree-search formulations. The current brief description of Cheng and Yan understates its explicit joint-learning formulation.

  4. The global-optimality guarantee in Proposition 4.8 is central to the contribution, but the induction in Appendix A.3 is difficult to follow as written. Lemma A.5 supplies a common-subpath property for a selected globally optimal routing configuration, the proof does not establish that this property, or another sufficient contractibility invariant, survives the successive contractions. It is not preserved by arbitrary contractions in a general route family: the switch sequences (a,b)(a,b), (a,c,d)(a,c,d), and (b,d)(b,d) satisfy the property, but contraction of a,ba,b yields (s)(s), (s,c,d)(s,c,d), and (s,d)(s,d), which do not. Please supply the missing invariant or a contraction-selection argument guaranteeing that the construction can be completed.

  5. The broad claim of "consistently outperforming direct policy optimization" requires further qualification, since Tables 7-8 show lower final mean objectives for pretrained PPO on two of the four held-out instances. The benefit of pretraining should be separated from the ranking of the two algorithms.

  6. Section 5 says the value function is trained toward the top 25% of observed returns. Appendix B describes eight quantile outputs, quantile Huber training, interpolated targets, and use of the two largest predicted quantiles for the scalar search value. Training a quantile predictor and using an upper-tail summary at search time should be distinguished from discarding all but the top 25% of observed training returns. The main text description should be aligned with the actual loss and target construction.

  7. The formal representation has one route node per communication use of an edge, whereas the neural implementation describes route-bundle nodes that can represent shared segments. The mapping between them, and how route-specific decisions are preserved, would benefit from a short explicit explanation.

  8. Section 5's final implementation details pointer names Appendix C, although the architecture and learning hyperparameters are in Appendix B.

  9. Reference "Yunqi Shi, Ke Xue, Song Lei, and Chao Qian. Macro placement by wire-mask-guided black-box optimization. Advances in Neural Information Processing Systems, 2023." requires an author name correction: Lei Song, not Song Lei.

  10. It is recommended to protect words with capitalized letters in the LaTeX bibliography items with braces, otherwise they are not rendered properly. For example {RePlAce}, {Gumbel}, {Steiner}, {HubRouter}, {NeuralSteiner}, {REST}, {PopArt}, {NoC}, {VLSI}, and {NP}. The authors should check for other missing capitalized letters, for example in journal or conference titles.

  11. It is also recommended to add volume, issue, pages/article number, and DOI or stable URL where the required style permits and the fields can be verified. The current entries are generally identifiable, but sparse. For example, volume, issue and page numbers are expected for journal articles.

Questions for authors
  1. How were the 28 synthetic floorplans generated, and what real design setting are they intended to represent? Please specify the distributions or procedures used for component locations, communication topologies, blockage geometries, and switch budgets, clarify whether component variants, dimensions, shapes, or technology-specific constraints are outside the intended scope of the current framework, and how the four held-out instances were selected.

  2. Can you provide a complete proof of Proposition 4.8? In particular, what invariant guarantees that the successive contractions in Appendix A.3 can always be continued until a single-switch configuration is obtained?

  3. In Appendix E, are the reported and visualized solutions terminal solutions after reaching the maximum switch budget, or are they the best intermediate solutions found during optimization?

  4. How many complete trajectories, environment transitions, neural-network evaluations, MCTS simulations, PPO updates, and genetic-algorithm generations are performed during the 48-hour experiments?

  5. Can you provide best-objective-versus-wall-clock-time curves for all iterative methods, together with the measured runtime of the heuristic baseline?

  6. Can you evaluate a frozen PPO-EWMA policy using repeated stochastic rollouts under a computational budget matched to Gumbel MCTS, retaining the best solution found? Please define the matching budget using measured computational cost rather than simply equating PPO rollouts with MCTS simulations.

  7. How much of the observed improvement is due to tree search, upper-tail value estimation, and the specific Gumbel MCTS procedure? Please provide ablations using mean-value search, conventional MCTS, and different numbers of MCTS simulations.

  8. Since only one pretrained checkpoint is produced for each learning algorithm, how sensitive are the transfer results to the pretraining seed? Could you report results from independently pretrained checkpoints, or limit the transfer claims to fine-tuning variability conditional on the selected checkpoint?

  9. What is the exact mapping between the formal route-node representation in Definition 4.1 and the route-bundle representation used by the neural-network implementation?

  10. Why was lambda = 1/2 selected in the objective? How sensitive are the results to this weight, and how do the individual wirelength and route-length components change across methods?

  11. Given the simplified point-based physical model, which claims are intended to generalize beyond this abstract setting, and which omitted constraints are expected to be most important in future extensions?

5 comments

Weaknesses:

W1, Q4, Q5, Q6, Q7 and Q8.

Appendix C.3 explicitly states that only one pretrained model is trained for each learning method, while Table 1 reports best-found objectives on the 24 training instances without variability across independent repetitions of the complete training/search procedure. These results are informative for the reported runs, but do not establish the stability of the algorithm ranking.

The pretraining run is very costly (running on 6 L40S for 48 hours), so we report only one seed due to computational constraints. The clear gap in performance across the 24 floorplans between the different methods is too large to be solely attributed to seed randomness.

With only three runs, showing the individual-run results would also improve transparency.

For transparency, we report here the individual runs for the four held-out floorplans.

InstanceMethodInitializationRun 1Run 2Run 3
1PPO-EWMAPretrained15.83015.81015.815
1PPO-EWMAScratch15.81015.81015.810
1Gumbel MCTSPretrained15.81015.81015.810
1Gumbel MCTSScratch15.81015.81015.810
2PPO-EWMAPretrained13.93313.93313.933
2PPO-EWMAScratch13.93313.93313.933
2Gumbel MCTSPretrained13.96813.97813.968
2Gumbel MCTSScratch13.96813.96814.523
3PPO-EWMAPretrained13.34713.34713.347
3PPO-EWMAScratch14.78213.77813.778
3Gumbel MCTSPretrained13.40313.43313.417
3Gumbel MCTSScratch13.42213.39313.927
4PPO-EWMAPretrained14.88214.76814.768
4PPO-EWMAScratch15.42814.72914.882
4Gumbel MCTSPretrained14.21714.21714.217
4Gumbel MCTSScratch14.33714.33714.583

The comparison between Gumbel MCTS and PPO-EWMA should use explicitly matched computational budgets. Matching the number of PPO rollouts to the number of MCTS simulations is not sufficient, because these operations may have different costs.

We already match the computational budget. As stated in the paper, lines 408-410: “All methods except Heuristic are run for 48 hours on the 24 pretraining floorplans. Heuristic is instead run once as a deterministic constructive procedure”.

Please report best-so-far objective versus wall-clock time, the number of complete trajectories, environment transitions, network evaluations, MCTS simulations, and PPO updates, as well as the heuristic runtime.

We can provide best-so-far objective versus wall-clock time curves if necessary. However, as we have a total of 28 floorplans and 4 methods needing a curve, this would add an additional 27 pages of figures in the Appendix, where we already have 27 pages of visualizations. Rather, we will make the Weight&Biases run public upon acceptance of the paper, which already contains those curves.

About the rest, for the experiments on the pretraining dataset, we estimate approximately 3.50 million complete trajectories for MCTS, 185 million for PPO, 1.36 billion for random search, and 1.18 billion for genetic search. The corresponding environment-transition counts are at most 141 billion for MCTS, and exactly 9.22 billion, 66.2 billion, and 50.3 billion for PPO, random search, and genetic search, respectively. The number for MCTS is based on 800 simulations per decision, as tree reuse allows us to keep part of the simulations done during the previous search. Collection/search network evaluations are estimated at most 141 billion for MCTS under the same upper-bound approximation and 9.40 billion for PPO; random and genetic search require no learned-network evaluations. PPO and MCTS perform approximately 377,000 and 71,700 optimizer updates, respectively.

We report here the runtime for the heuristic:

InstanceRuntime (s)
1750.354
2676.305
3606.266
4948.047
5962.715
61214.116
7983.439
81009.230
91061.287
101034.839
11558.902
12644.146
13481.251
14603.034
15220.294
16165.932
17233.674
181194.117
19943.917
20121.232
21574.726
22342.139
23581.730
24185.933

As an additional control, evaluate a fixed PPO policy through repeated stochastic rollouts under the same measured budget as Gumbel MCTS and retain the best solution.

In our experiments, PPO and MCTS are already trained using the same machine and for the same duration.

Ablations using mean versus upper-tail value estimates, conventional MCTS, and different MCTS budgets would clarify whether the gains come from tree search itself, its value estimator, or simply additional computation.

In the following table, we compare Gumbel MCTS with and without the risk-seeking value estimator, for a single seed run in 24h on a single RTX6000PRO, with 2048 trajectories per collection, which is a weaker setup compared to our paper’s pretraining experiments (which used 6 L40S during 48h) due to time and computational constraints.

InstanceScalar MCTSRisk-seeking MCTS
111.68911.486
211.22411.508
315.93315.043
49.91510.563
514.20414.218
610.95710.571
78.8988.254
810.78510.319
911.20811.218
1014.15313.366
1113.53714.012
1213.38013.551
1313.28713.648
1413.34613.645
1514.13414.148
1615.24815.269
1715.23915.239
1814.33514.886
1914.49215.322
2015.81715.726
2112.97113.106
2213.47813.903
2312.78513.070
2415.29715.277

Risk-seeking value estimation doesn’t strongly affect the performance. Please also note that those values are not final, and that more than 24 h is required for the algorithm to converge.

We also provide a comparison between learned Gumbel MCTS and non-learned MCTS, where the prior actions are selected uniformly, and the values are estimated using 800 random rollouts per decision, on the fourth held-out floorplan. We use a single seed for the non-learned version, run on a single L40S for 24 h.

MethodWirelengthRoutelengthObjective
Non-learned MCTS11.87930.16826.963
Gumbel MCTS, pretrained3.907 ± 0.00020.620 ± 0.00014.217 ± 0.000
Gumbel MCTS, scratch2.852 ± 0.00923.134 ± 0.21514.419 ± 0.116

We finally provide an evaluation of Gumbel MCTS using the pretrained checkpoint with a varying number of simulations, on instance 18, which is the largest floorplan of our pretraining set. Mean and standard deviation are computed over 1024 trajectories.

Simulations/moveTrajectoriesMean objectiveStdBest objectiveMedianRuntime (s)
0102414.6221080.48539114.17890214.504927111.766
8102414.5434600.35053814.18424114.454237144.862
32102414.5582150.33529614.16674114.476794228.776
128102414.5878100.45670214.16364314.479611378.389
400102414.5404540.28491014.15928314.460787669.971
800102414.4971720.21866114.15928314.443811996.678
1600102414.4714420.26318514.15928114.4186141543.999
3200102414.4617240.38240514.15274214.3933842819.967

W2, W3, and Q1.

A broader held-out evaluation

Each held-out floorplan is costly, as it requires four additional experiments (one for both PPO-EWMA and Gumbel MCTS, for both pretrained initialization and fine-tuning). We believe four held-out floorplans to be enough to demonstrate that a pretrained initialization speeds up convergence.

a reproducible instance-generation procedure

Each instance consists of two components: (i) a communication graph describing the initiators and targets, their positions on the floorplan, and the required initiator-to-target communications; and (ii) a rectangular floorplan containing rectangular obstacles (blockages).

To generate diverse instances, we vary three main parameters:

  • Floorplan coverage: the fraction of free space remaining after placing rectangular obstacles, allowing us to generate floorplans with different levels of geometric obstruction. Number of initiators and targets: controlling the number of communicating components.

  • Connectivity percentage: the proportion of possible initiator-to-target communications included in the graph. A connectivity of 100% corresponds to full connectivity, where every initiator communicates with every target.

  • Blockages are positioned with varying sizes and aspect ratios to create diverse spatial layouts and routing constraints. Initiators and targets are placed at different locations across the floorplan, outside blockage interiors. Required communications are then selected as a subset of the possible initiator–target pairs, according to the desired connectivity percentage. We will clarify this generation procedure in the revised manuscript.

scaling experiments are needed to establish how the method behaves across different communication structures and geometric difficulty

Scaling to larger instances is difficult due to our limited computational availability. We evaluated our method to the best we could under our limited computing availability.

The simplified abstraction is clearly acknowledged; nevertheless, its relationship to a realizable communication network remains unvalidated.

For a discussion about the simplified abstraction, please refer to the answer to Reviewer bg2t.

Reporting training-instance optimization results is legitimate, but those results should not be presented as evidence of unseen-instance generalization.

We do not claim that our method generalizes to unseen floorplans in zero-shot. Our fine-tuning experiments show that a pretrained checkpoint provides a useful initialization for unseen floorplans.

These measures should be chosen to match the intended application, they should not be replaced by fixed floorplan area or Appendix D's input free-space percentage, neither of which measures the quality of an optimized placement in this model.

The input free-space percentage is specific to the floorplan instance and is not modified by our algorithm. It is only a characteristic of the problem instance.

W4. Gumbel MCTS is just a modern variant of MCTS and is not related to our core contribution, which is the hierarchical space construction. We will add a citation to the paper in the related work, along with all the other RL for EDA works already cited.

W5. Due to space constraints, we briefly discussed these citations. Besides, as clarified in Cheng et al. (2022), Cheng and Yan (2021) use a heuristic rip-up-and-reroute algorithm to provide routing feedback to the placement policy. Their codebase does not contain any RL method for routing eithertoo. In contrast, our method directly includes routing decisions in the learned search process, alongside switch placement and topology decisions.

Chen et al. (2022) also use reinforcement learning and MCTS but for global routing, at the wire level, while we represent each route explicitly. Moreover, our hierarchical switch-expansion and route-refinement operations are designed to preserve the validity of these routes throughout the construction, while they predict Steiner points on a fixed regular grid, not using the Hanan grid.

Finally, Geng et al. (2024) combine reinforcement learning and MCTS for macro placement, not routing. We also stress that RL-based search is not our core contribution.

W6 and Q2. We thank the reviewers for identifying the gap in Proposition 4.8. We agree there is a gap in the argument. We will promote Lemma A.5 to a standalone proposition and replace Proposition 4.8 with two complementary theoretical results.

1. Exact characterization of the hierarchical search space. We establish the following exact characterization:

A set of simple communication routes is expressible through switch expansions and route refinements if and only if its switches admit a sequence of pairwise contractions reducing them to a single switch, such that no contracted communication route contains the same switch twice at any step of the sequence.

2. Optimality coverage for (ℓ1\ell_1)-embeddable switch networks.

We further establish that our hierarchical search space contains a globally optimal solution whenever an optimum exists whose switch-network shortest-path metric is isometrically embeddable into ℓ1\ell_1. This sufficient condition covers a broad family of networks, including trees, forests, cycles, cactus graphs, four-vertex diamond graphs, weighted outerplanar graphs, and, more generally, K2,3K_{2,3}-minor-free graphs.

Moreover, since every metric on at most four points is ℓ1\ell_1-embeddable (MET4=CUT4\mathrm{MET}_4=\mathrm{CUT}_4), we obtain the following corollary:

For every instance with Smax⁡≤4S_{\max}\leq 4, our hierarchical search space contains a globally optimal solution, independently of the floorplan geometry, obstacles, and communication topology.

W7. Gumbel MCTS outperforms or is equivalent to PPO on all of the pretraining floorplans, not fine-tuning. Fine-tuning experiments last only 24h, not 48h like the pretraining experiment, and MCTS takes longer than PPO to fully converge.

W8. This is just a minor textual shortcut, that is not substantial to the understanding of the method.

W9 and Q9. Conceptually, it is the same. It is simply that the architecture aggregates the embeddings of all route nodes before message passing, in order to save compute. We will clarify that in the paper.

W10, W11, W12 and W13. We will correct this.

Questions:

Q3. It corresponds to the best solutions after reaching the final number of switch expansions. Please note that switches can be discarded, so some solutions may not have the maximum amount of switches.

Q10. Lambda = ½ is arbitrary. As discussed in the paper, lines 152-154: “The wirelength encourages compact and shared wires, while the route length discourages long communication paths between individual initiator-target pairs”, and lambda controls which component is favored.

The wirelength and route length of all found solutions are already provided in Appendix D.

Reviewer_bg2tOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a reinforcement learning framework for joint routing and switch placement in on-chip communication networks. Starting from a valid network with one switch, the method adds switches through expansion, placement, and route refinement. The construction preserves routing validity, and the authors show that its search space contains at least one global optimum under assumptions. A learned policy and value network guide tree search for exploration and exploitation. Experiments on synthetic floorplans show better solution quality than heuristic and genetic algorithm baselines.

Critical strengths
  1. The method is well designed. The hierarchical construction allows switch placement and routing to be optimized together while keeping the assigned communication paths valid. The theoretical results help explain the properties of this construction.
  2. The paper is clearly written and easy to follow. The figures and step-by-step description make the main ideas understandable.
Critical weaknesses
  1. The experiments cover only small synthetic floorplans, with 18–25 communication pairs and 2–5 switches. No real chip designs are evaluated. This makes it hard to judge whether the method remains effective at larger scales or offers useful improvements in practice.
  2. The practical motivation needs more explanation. The introduction explains that routing and switch placement affect each other, but it does not clearly identify the main challenges in the network-on-chip (NoC) application or explain how the simplified model captures them. As a result, the practical value of solving this particular formulation is difficult to assess.
Questions for authors
  1. My background is in ASIC placement and routing rather than NoC design. In the ASIC flows I am familiar with, large problem sizes and costly downstream evaluation are major challenges. What are the main challenges in the on-chip communication network setting studied here, and how do they differ from those in ASIC routing?
  2. How do the benchmark sizes compare with practical NoC designs?
3 comments

Weaknesses:

W1. Our instances are inspired by an internal NoC topology-generation tool. Unfortunately, publicly available hardware designs are scarce, especially for NoCs. As the search space grows exponentially with the number of switches and communication routes, and due to computational constraints, we could not evaluate our method on larger industrial-scale instances. However, our experiments on small-scale floorplans are still representative of some real applications.

W2. Conventional placement and routing starts from a fixed netlist, whereas our goal is to generate the NoC topology itself. This means jointly deciding where to place switches, how to connect them, and how to route communications through the network. Also, routing in our case refers to packet routing through the network, not physical wire routing through the metal layers of the chip.

Unlike other IP blocks that can be reused as fixed hard macros, a NoC must be adapted to each system-on-chip (SoC). Its topology depends on the positions of the IP blocks it connects and the available space between them. Therefore, NoC topology generation is a system-level problem that must be solved again for each new design. Existing approaches often rely on heuristics that sequentially construct the placement and routes to reduce the search space. However, early decisions can constrain later ones, and their impact on the final wirelength and communication latency is difficult to estimate. This motivates our joint approach.

Our simplified model captures the tradeoff between the implementation cost and performance through our objective, where wirelength approximates the implementation cost and route length approximates communication latency / performance. We will clarify this in the paper.

Questions:

Q1. As discussed in our response to Weakness 2, the main difference is that we address NoC topology generation rather than the placement and routing of a fixed netlist. The main challenge is the large search space resulting from jointly deciding switch positions, connectivity, and communication routes. These decisions strongly depend on one another, and it is difficult for sequential heuristics to anticipate the impact of early choices. Another important distinction is that routing in our setting refers to communication paths through the switch network, i.e., packet routing rather than physical wire routing through the chip's metal layers.

Q2. Our benchmarks contain around ten initiators and targets, which is comparable in order of magnitude to small-sized NoCs. The largest industrial NoCs can have up to around a hundred initiators and targets. We will clarify this in the paper.

Thank you for your response. However, I remain unconvinced that the simplified problem and small-scale experiments present sufficient challenges. Therefore, I will maintain my current score.

We thank the reviewer for their follow-up. We respectfully disagree that our problem instances do not present sufficient challenges. Unlike conventional ASIC routing, our problem jointly optimizes NoC topology, switch placement, and logical communication routes. Even a relatively small instance with 4 switches, 20 communication pairs, and 500 candidate positions yields a search space of around 104710^{47} configurations. This inherent combinatorial difficulty is reflected in our experiments, where MCTS substantially outperforms the genetic algorithm on most instances, under equal computational budgets.

Furthermore, while our physical model is simplified, the underlying optimization problem is directly relevant to industrial NoC synthesis. For example, the commercial Arteris FlexGen tool [1] also optimizes NoC topology with a focus on wirelength and latency. We emphasize that our problem instances are already representative of practical industrial applications. While larger-scale experiments would provide further empirical evidence, their scale is currently limited by our computational resources. We nevertheless believe that the scientific merit of our method should be distinguished from its industrial-scale validation.

[1] https://www.arteris.com/products/non-coherent-interconnect-ip/flexgen/

Reviewer_SqYmOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies joint switch placement and routing for multiple communication pairs under a simplified obstacle-aware rectilinear model. The proposed construction uses route nodes to represent individual communication assignments and alternates switch expansion, placement on an extended Hanan grid, and local route refinement. The paper establishes validity preservation after each completed construction cycle and claims that the restricted hierarchical search space retains a globally optimal solution. A graph policy and value network guide Gumbel MCTS. Experiments on 24 synthetic training floorplans compare against a constructive heuristic, random search, a genetic algorithm, and PPO-EWMA; four held-out floorplans evaluate whether pretraining accelerates subsequent optimization.

Critical strengths
  1. A useful construction for jointly optimizing topology, placement, and assigned routes. The route-node representation makes per-communication assignments explicit, and the expansion–refinement operations preserve one assigned simple path per communication pair after each completed cycle. Proposition 4.6 is supported by a clear local argument. The Hanan-grid discretization also provides a principled finite placement space under the stated model. These are meaningful structural contributions: they allow learning and search to operate over feasible assigned routings while jointly changing the intermediate infrastructure.

  2. Consistent optimization gains on the evaluated training instances and useful transfer evidence. In Table 1, Gumbel MCTS is no worse than any listed baseline on every floorplan; it improves over PPO-EWMA on 19 instances and ties on five. The held-out experiments also show that pretraining improves early optimization. The transfer protocol appropriately reinitializes instance-specific identifier embeddings and PopArt output state, as well as optimizer and replay state, and reports three independent fine-tuning runs. These results support the usefulness of the complete learned-search approach within the evaluated setting.

Critical weaknesses
  1. The proof of global-optimum coverage is incomplete. In Appendix A.3, page 15, lines 784–797, Lemma A.5 justifies selecting a contractible pair in the initial optimal configuration. The argument then repeats this step without establishing that the common-subpath property survives contraction. For example, the switch sequences ((a,b)), ((a,c)), and ((b,d,c)) satisfy that property, but contracting the permitted pair (a,b) into (s) produces ((s,c)) and ((s,d,c)), which do not. Moreover, the intermediate contracted configurations are not shown to remain globally optimal, so Lemma A.5 cannot simply be reapplied to them. This identifies a missing induction argument, rather than disproving Proposition 4.8: a different contraction order might succeed. Nevertheless, a structural lemma or a justified contraction-selection rule is necessary to establish one of the paper’s central contributions.

  2. The added value of learned tree search is not clearly validated. The PPO comparison is described as isolating explicit search, but the methods also differ in scalar versus risk-seeking quantile value estimation and in data collection and replay procedures (Appendices B.1–B.3). Likewise, uniform random search does not isolate learned guidance from tree-search allocation. The empirical reference point is also narrow: Table 1 reports best-of-budget results on 24 training floorplans with 2–5 switches and 18–25 communication pairs, using one pretraining run per learning algorithm. The four held-out floorplans omit the non-learning baselines. Although Appendix C.3 provides equal hardware and wall-time budgets for the four iterative methods, the heuristic’s runtime and an optimality-gap reference are not reported. Consequently, the source, robustness, and practical magnitude of the advantage remain insufficiently established even within the proposed simplified model.

Questions for authors
  1. What invariant or contraction-selection rule guarantees that the construction in Appendix A.3 can continue to a single switch? In particular, how does the proof handle the loss of the common-subpath property illustrated above?

  2. Can you provide a controlled comparison that separates tree search from the different value estimator and training procedure? A non-learned-prior MCTS control would additionally clarify how much of the gain depends on learned guidance.

  3. How do the heuristic and genetic algorithm perform on the four held-out floorplans, and what is the heuristic’s wall time? An exact solution or certified lower bound on a tractable subset would also help determine whether the reported improvements represent a substantial reduction in the remaining optimization gap.

3 comments

Weaknesses:

W1 and Q1. We thank the reviewers for identifying the gap in Proposition 4.8. We agree there is a gap in the argument. We will promote Lemma A.5 to a standalone proposition and replace Proposition 4.8 with two complementary theoretical results.

1. Exact characterization of the hierarchical search space. We establish the following exact characterization:

A set of simple communication routes is expressible through switch expansions and route refinements if and only if its switches admit a sequence of pairwise contractions reducing them to a single switch, such that no contracted communication route contains the same switch twice at any step of the sequence.

2. Optimality coverage for (ℓ1\ell_1)-embeddable switch networks.

We further establish that our hierarchical search space contains a globally optimal solution whenever an optimum exists whose switch-network shortest-path metric is isometrically embeddable into ℓ1\ell_1. This sufficient condition covers a broad family of networks, including trees, forests, cycles, cactus graphs, four-vertex diamond graphs, weighted outerplanar graphs, and, more generally, K2,3K_{2,3}-minor-free graphs.

Moreover, since every metric on at most four points is ℓ1\ell_1-embeddable (MET4=CUT4\mathrm{MET}_4=\mathrm{CUT}_4), we obtain the following corollary:

For every instance with Smax⁡≤4S_{\max}\leq 4, our hierarchical search space contains a globally optimal solution, independently of the floorplan geometry, obstacles, and communication topology.

W2 and Q3.

The PPO comparison is described as isolating explicit search, but the methods also differ in scalar versus risk-seeking quantile value estimation and in data collection and replay procedures (Appendices B.1–B.3).

See Question 2.

Likewise, uniform random search does not isolate learned guidance from tree-search allocation.

We agree that random search does not isolate the contribution of tree search, but that it isolates the benefits of learning, and that PPO isolates the benefits of explicit search. We already wrote in lines 403-404, “Random Search (Karnopp, 1963), [...], isolating the benefit of learned guidance”, and in lines 405-407, “ Finally, PPO-EWMA (Hilton et al., 2022) [...], isolating the contribution of explicit search”.

The empirical reference point is also narrow: Table 1 reports best-of-budget results on 24 training floorplans with 2–5 switches and 18–25 communication pairs, using one pretraining run per learning algorithm.

The pretraining run is very costly (running on 6 L40S for 48 hours), so we report only one seed due to computational constraints. The clear gap in performance across the 24 floorplans between the different methods is too large to be solely attributed to seed randomness.

The four held-out floorplans omit the non-learning baselines.

Our objective with the transfer experiments is to investigate whether a pretrained checkpoint can substantially speed up convergence, so we did not report non-learning baselines. We report here the best value of the objective found by the three non-learning baselines on the fourth held-out floorplan, using a single seed, along with the results for PPO-EWMA and Gumbel MCTS from the paper:

MethodWirelengthRoutelengthObjective
Heuristic3.60023.76115.480
Genetic search5.75928.41619.967
Random search11.63731.26627.271
PPO-EWMA, pretrained3.048 ± 0.12623.554 ± 0.13914.825 ± 0.057
PPO-EWMA, scratch3.079 ± 0.19824.000 ± 0.30415.078 ± 0.349
Gumbel MCTS, pretrained3.907 ± 0.00020.620 ± 0.00014.217 ± 0.000
Gumbel MCTS, scratch2.852 ± 0.00923.134 ± 0.21514.419 ± 0.116

We will add the remaining seeds and floorplans in the camera-ready version.

the heuristic’s runtime and an optimality-gap reference are not reported

We report here the runtime for our heuristic baseline:

InstanceRuntime (s)
1750.354
2676.305
3606.266
4948.047
5962.715
61214.116
7983.439
81009.230
91061.287
101034.839
11558.902
12644.146
13481.251
14603.034
15220.294
16165.932
17233.674
181194.117
19943.917
20121.232
21574.726
22342.139
23581.730
24185.933

We additionally used Scipy’s MILP solver to compute the optimality gap on the smaller floorplans in our pretraining dataset (floorplans 20, 17, 15, and 24) with an upper time limit of 24 h. We provide here the found optima:

InstanceOptimumMCTS best solutionGap (%)
2015.72615.7260.000
1715.23915.2390.000
1514.13414.1340.000
2415.27715.2770.000

The other larger instances are too large and not feasible.

Questions:

Q2. In the following table, we compare Gumbel MCTS with and without the risk-seeking value estimator, for a single seed run in 24 h on a single RTX6000PRO, with 2048 trajectories per collection, which is a weaker setup compared to our paper’s pretraining experiments (which used 6 L40S during 48 h) due to time and computational constraints.

InstanceScalar MCTSRisk-seeking MCTS
111.68911.486
211.22411.508
315.93315.043
49.91510.563
514.20414.218
610.95710.571
78.8988.254
810.78510.319
911.20811.218
1014.15313.366
1113.53714.012
1213.38013.551
1313.28713.648
1413.34613.645
1514.13414.148
1615.24815.269
1715.23915.239
1814.33514.886
1914.49215.322
2015.81715.726
2112.97113.106
2213.47813.903
2312.78513.070
2415.29715.277
Risk-seeking value estimation doesn’t strongly affect the performance. Please also note that those values are not final, and that more than 24 h is required for the algorithm to converge.

We additionally provide a comparison between learned Gumbel MCTS and non-learned MCTS, where the prior actions are selected uniformly, and the values are estimated using 800 random rollouts per decision, on the fourth held-out floorplan. We use a single seed for the non-learned version, run on a single L40S for 24 h.

MethodWirelengthRoutelengthObjective
Non-learned MCTS11.87930.16826.963
Gumbel MCTS, pretrained3.907 ± 0.00020.620 ± 0.00014.217 ± 0.000
Gumbel MCTS, scratch2.852 ± 0.00923.134 ± 0.21514.419 ± 0.116

Thank you again for your time and constructive feedback. As the discussion period is coming to a close, we would like to follow up. We hope our answers addressed the concerns appropriately. If so, we kindly ask the reviewer for potential reconsideration of the score. We would also be happy to clarify any remaining concerns.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.