A chip's clock speed is limited by its slowest chain of logic gates, the critical path. After synthesis, a netlist (the list of gates and their connections) is usually already close to meeting timing. Only a small set of gates, often shared by many failing paths, needs a different size or threshold voltage. This proposal treats that repair as refinement rather than creation. We use a diffusion model, a generator that learns to turn noise into samples by removing it step by step. Here the "noise" is random bit flips on each gate's discrete sizing choice. The key change from standard practice is that sampling does not start from pure noise. It starts from the synthesized netlist itself, and each gate is re-randomized by an amount set by how badly it bottlenecks timing. Gates with healthy slack stay nearly frozen. Shared bottleneck gates are strongly perturbed, and the model resolves them jointly.
In two sentences: we corrupt a netlist's discrete gate choices with a per-gate flip rate proportional to a bottleneck score from critical-path analysis, then train a graph denoiser to walk those gates back to a timing-clean assignment. Because the corruption is graded rather than uniform, the model can escape the starting netlist's local minimum where it matters without destroying the good structure everywhere else.
Core Claim
Three separate literatures each hold one piece of this. Bit-flip ("Bernoulli") diffusion beats Gaussian diffusion on discrete combinatorial problems. DIFUSCO shows this on graph problems such as the traveling salesman problem, but it always samples from uniform random bits and has never touched circuits. Warm starts make diffusion far cheaper to train. Information Theoretic Learning for Diffusion Models with Warm Start reports convergence in about 0.3M iterations versus up to 10M for a variational diffusion model. However, its theory is continuous-only, and it names discrete data as open. Bottleneck gate identification, formalized as a scoring heuristic in Relax-and-retime, tells us which gates matter.
Our claim is specific. A warm-started Bernoulli diffusion whose per-gate noise level is a monotone function of a bottleneck score fixes more timing per unit of area than three alternatives:
- the same diffusion with a uniform noise level;
- the same diffusion with a hard in/out mask, which is the "stitching" strategy of Masked Bernoulli Diffusion transplanted to circuits;
- a one-step predictor with the same network.
The graded schedule targets the "noise paradox" that the masked-diffusion paper describes. Too much noise erases the prior, and too little traps the model in the prior's errors. A single global noise level forces this trade-off on every gate at once. A per-gate level lets the model pay it only where it is useful.
Mechanism
Each gate $i$ receives a small binary code. One bit selects low versus high threshold voltage. A thermometer code of $m$ bits encodes drive strength, decoded as the number of ones, so every decoded size is legal and a single flip means roughly one size step. The warm-start state $x^{\text{init}}$ is the synthesized netlist's code.
We extract critical endpoints and their top paths with the bounded report_timing_endpoint(n, k) query of Timing-Driven Global Placement by Efficient Critical Path Extraction. On those paths we compute a bottleneck score $s_i \in [0,1]$ for each gate. The score combines the ingredients used in Relax-and-retime: the fraction of critical paths through the gate, the slack recoverable by changing it, and its fan-out to failing endpoints. We drop switching probability unless leakage or dynamic power is the objective.
Each bit of gate $i$ then gets its own flip probability, applied once to the warm start:
$$ \rho_i = \rho_{\max}\, g(s_i), \qquad q(\tilde{x}_i = 1 - x^{\text{init}}_i) = \rho_i . $$
Here $\rho_{\max} \le 0.5$ is the largest flip rate, reached for the worst bottleneck. The function $g$ is a monotone map from score to $[0,1]$, for example a clipped power $s_i^{\gamma}$ with shape parameter $\gamma$. The perturbed state $\tilde{x}$ is where reverse sampling begins.
A bit-flip chain that has run for $t$ steps with per-step flip rate $\beta$ has total flip probability $(1-(1-2\beta)^t)/2$. This relation comes from composing symmetric binary channels. We therefore map each $\rho_i$ to a per-gate "effective diffusion time" $t_i$. The denoiser is conditioned on this per-node time rather than on one global step. This is the discrete analogue of the controlled starting noise level in the continuous warm-start work. The difference is that our level varies across nodes and comes from timing.
The denoiser is the anisotropic, edge-gated graph network used by DIFUSCO. It runs on the gate-level timing graph with the following node features: current code, load capacitance, arrival time, required time, slack, and $t_i$. For designs too large for one GPU pass, we slice the graph along topological signal order, following the Order Preserving Partition of PreRoutGNN. Reverse steps predict each bit's clean posterior, as in DIFUSCO. At each step, gates whose effective time has already reached zero are clamped to their current value. Healthy logic is therefore never rewritten.
We draw several samples in parallel, and a static timing analyzer picks the best one. Sampling a set of candidates and selecting among them mirrors DIFUSCO's decoding and needs no gradients through the timer. The outer loop then re-extracts paths, recomputes scores and repeats two or three times. This addresses the risk that near-critical paths become critical after a fix, which the research file calls "slack ping-pong."
Where Training Data Comes From
This is the proposal's main risk, so we state it plainly. Clean targets $x_0$ are timing-repaired netlists produced by a conventional sizer on training designs. Training pairs could come from two sources.
The first is synthetic: corrupt $x_0$ with the graded kernel above, using scores computed on $x_0$'s own near-critical paths. The second is real: pair the actual synthesized netlist with its repaired version. Synthetic corruption is cheap and unlimited, but it may not resemble how real synthesis mis-sizes gates. We will train on each source alone and on a mixture. We will report the gap on held-out designs.
A large gap in favor of real pairs would mean the forward process is the wrong model of pre-repair netlists. That would itself be a finding about warm-start discrete diffusion. As with DIFUSCO, supervision comes from a classical solver. We accept that dependence, but we do test whether the model can exceed its teacher by reranking multiple samples.
Research Program
The work has four parts. The first is the per-node-time Bernoulli warm-start formulation and its training objective. We write down the forward kernel and its posterior for heterogeneous flip rates, and check that the reverse model matches it on toy chains. This fills the discrete gap left open by the continuous warm-start paper.
The second is the scoring and scheduling module. It connects bounded path extraction to per-gate noise, and we ablate the shape parameter $\gamma$ and the maximum rate $\rho_{\max}$.
The third is the denoiser and sampling loop with timing-based reranking, run in an open flow on open benchmark designs.
The fourth is the comparison study described below. Its central question is whether iterative joint denoising adds anything once bottleneck gates are known.
The reason to expect that it might is structural. When two gates share a failing path, upsizing either one may suffice. A model that predicts each gate's change independently tends to upsize both, wasting area, or neither. Iterative denoising conditions each step on the others' current choices and can pick one mode. DIFUSCO attributes its advantage on multi-solution problems to this kind of multimodality. Whether the effect holds on timing graphs is an empirical question.
Baselines
The naive reference point is the synthesized netlist with no sizing repair, timed by the same analyzer. Every result is reported relative to it. Any method must beat it on worst negative slack (WNS) and total negative slack (TNS) at bounded area growth to count at all.
The first conventional baseline is the open flow's built-in timing repair, the sizer used to produce training targets, run with its default and its most aggressive settings. Where a license is available, we will also run Synopsys IC Compiler II (ICC2). Beating it means better TNS at equal area on held-out designs, or equal TNS with less area and fewer changed gates.
The strongest existing learning method is Learning-driven Physically-aware Large-scale Circuit Gate Sizing. It predicts timing with a graph Transformer plus layout CNN, and optimizes discrete sizes by gradient descent through a straight-through estimator with Gumbel-Softmax sampling focused on critical paths. It reports a 16.29% TNS and 18.61% WNS improvement over ICC2, with a 6.64x speedup, on OpenCores designs in a TSMC 16nm process. Those numbers use a proprietary process and flow, so we cannot compare to them directly. We will reimplement the method on our designs with the same training split, the same analyzer for sign-off, and a matched GPU-hour tuning budget. It also starts from the synthesized netlist, so both methods share the warm start. We will count our method as beating it only if it wins on TNS at matched area across most held-out designs. We have found no reported result on Lacuna for this method, or any learned sizer, on the OpenROAD benchmark.
The discrete-diffusion baseline is cold-start DIFUSCO applied to the same bit encoding. It starts from uniform random bits and uses the same network and step budget. It isolates the value of the warm start.
Three ablations isolate the key ingredient. The first uses the same model with one global noise level tuned on validation data. The second uses a hard binary mask, with top-scoring gates fully noised and the rest clamped, as in Masked Bernoulli Diffusion. The third collapses the model to a single reverse step, a one-shot per-gate classifier with an identical network and training data. The graded schedule must beat the first two, and iteration must beat the third, for the core claim to stand.
Why not just…?
Why not just run a conventional sizer restricted to the bottleneck gates? This is the most serious threat. The score might do all the work, and a greedy or Lagrangian sizer confined to high-score gates might match the diffusion model. We will run exactly this with the same score and threshold. If it matches our method on TNS and area, the honest conclusion is that bottleneck-restricted search is the contribution and diffusion is unnecessary. The paper would then be rewritten around that result. We expect diffusion to help mainly on designs with dense path overlap, where greedy sizing oscillates. We will therefore report results stratified by the path-overlap fraction.
Why not just use gradient-based sizing with a straight-through estimator? Ye et al. already optimize discrete sizes well and beat ICC2. Their own discussion flags the mismatch between the relaxed training loss and slack after rounding. This mismatch is a bias of the straight-through estimator, not a proven failure. The reimplemented baseline above settles the question directly. We will also measure how often its rounded solution is worse than its relaxed prediction, which diffusion avoids by never leaving the discrete space.
Why not just predict each gate's change in one shot with a graph network? This is the one-step ablation. If it performs as well, the multimodality argument fails for timing graphs. Iterative sampling would then only cost runtime, and we would report that.
Why not start from random bits, as existing diffusion solvers do? A synthesized netlist is always available, and MaskRegulate shows in macro placement that refining a DREAMPlace layout beats building one from scratch. Its gains include an 18.35% WNS improvement on superblue1. The cold-start DIFUSCO baseline tests whether this carries over to discrete sizing, measuring both quality and the number of denoising steps needed.
Proposed Experiments
The primary setting is the 21-circuit OpenROAD benchmark used by PreRoutGNN, which includes aes128 and xtea at over 300,000 pins. We split it by design so that test circuits are never seen in training. The ISCAS89 and UltraSPARC T1 modules from Relax-and-retime serve as a small, fast development set and a second held-out check.
Metrics are WNS and TNS from the static timing analyzer after sizing and incremental legalization. We also report area and leakage change, number of gates modified, wall-clock runtime, and a "path wall" count: the number of paths within 5% of the critical delay, borrowed from Relax-and-retime. Every method is plotted as a TNS-versus-area curve by sweeping its budget knob, so no comparison rests on a single operating point.
Three checks are decisive. First, graded noise must beat both uniform noise and the hard mask at matched area on held-out designs. Second, the diffusion model must beat bottleneck-restricted conventional sizing, with the advantage concentrated on high path-overlap designs. Third, warm start must reach cold-start quality in far fewer denoising steps, or beat it at an equal step count.
Secondary checks cover two further questions. The first is the synthetic-versus-real training gap. The second is whether reranking several samples lets the model exceed the sizer that produced its targets. Failure on the first two decisive checks would falsify the core claim, and we would report it as such.
References
- DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
- Information Theoretic Learning for Diffusion Models with Warm Start
- Relax-and-retime: a methodology for energy-efficient recovery based design
- Binary Noise for Binary Tasks: Masked Bernoulli Diffusion for Unsupervised Anomaly Detection
- Timing-Driven Global Placement by Efficient Critical Path Extraction
- PreRoutGNN for Timing Prediction with Order Preserving Partition: Global Circuit Pre-training, Local Delay Learning and Attentional Cell Modeling
- Learning-Driven Physically Aware Large-Scale Circuit Gate Sizing
- Reinforcement Learning Policy as Macro Regulator Rather than Macro Placer