← All projectsGitHub
Algorithmic chip-design loops

How much of an open-source chip design search can cheap fidelity rungs and proof prediction save, with a guarantee?

research/verified-dse

Milestones 1 to 3 done: on 10 designs x 60 ABC pass sequences, the generic-gate score does not rank like routed SKY130 area x delay (tau-b median -0.04), and liberty mapping mis-ranks too when the clock is tight (tau 0.59); at equal wall-clock a one-shot cheap-rung screen does not beat random or hill-climbing search on the cached table; successive halving across rungs does not beat random routed search on mean regret either (plain halving from the generic-gate rung is worst; a 6-point routed pilot to pick the start rung fixes most of that, H3), a 10-point routed pilot plus a conformal bound on the mapped rung keeps the routed optimum 0.99 of the time (nominal 0.90) at 42 to 57% of the routed runs, but on the generic-gate rung coverage fails (0.65 against 0.80, H4 refuted there); proof-success prediction (H5): pooled AUC 0.96 to 0.998 across 15 designs is just design size (an oracle knowing only each design's success rate scores the same), and inside the one design with variation it is 0.65 to 0.78, so H5 is not supported; milestone 6 proves that halving's routed regret is at most the sum of the cut rungs' largest ranking inversions (vacuous for the generic-gate rung, loose for the mapped ones); milestone 7a adds a distribution-free pilot quantile of pair inversions (16-point pilots hold the nominal 0.8 coverage in all 60 group-rung cells, median 0.32 of the maximum), whose summed bound is under 0.1 on 9 of 10 groups for the mapped rungs at a relaxed clock but is violated by realised halving regret in 1 of 40 cells, so it is a heuristic, not a guarantee

20 tests

What it found

An open research programme; milestone 1 is measured. Over 10 small designs, 60 ABC pass sequences each and two clock targets (1,200 runs through Yosys, ABC and OpenROAD on SKY130 HD), the generic-gate rung's Kendall tau-b against routed (global-route plus timing repair) area × period is below 0.7 on all 9 designs where it is defined (median −0.04), and its pick costs a median 13.5% of routed area × period. The liberty-mapped rung is no better than 0.59 median tau at a tight clock (median regret 10.5%) but nearly exact at a relaxed one (0% regret), because timing repair reorders designs. Routed points cost about 8× a generic point here, so there is little to save on designs this small. Limits: one corner and utilisation, global-route estimates, ten small designs. Milestone 2 replays search on the cached table at equal wall-clock: screening the pool at the generic-gate or mapped rung and verifying the top points does not beat random or hill-climbing search (45 s: regret 1.08% and 1.27% against 0.94% and 0.61%), and loses badly at smaller budgets. Hypotheses H2 to H5 (multi-fidelity wins, coverage, proof prediction) are not yet run. Milestone 3 replays successive halving across the four rungs: starting from the generic-gate rung it is the worst strategy (about 10% mean routed regret at the tight clock at 45 s against 0.94% for random search); starting at the mapped rung wins on most designs at a relaxed clock but loses heavily on two; a 6-point routed pilot that picks the start rung recovers the designs plain halving loses (H3), so there is no multi-fidelity gain at equal wall-clock on this 50-point pool yet. Milestone 4 (H4) replays conformal shortlists: a routed pilot of 10 to 16 points calibrates a one-sided bound on routed area × delay from a cheap rung. On the mapped rung the routed optimum is kept 0.99 of the time at nominal 0.90 (0.90–0.92 at 0.80) while routing 42–57% of the pool, against 0.53–0.65 for random search with equal routed runs; on the generic-gate rung coverage is 0.65 at nominal 0.80, no better than random search, so H4 is refuted there. Limits: 20 groups from 10 small designs, one corner. H5 (milestone 5): across 752 Yosys SAT-miter proofs of ABC rewrites on 15 designs, proof time is set by design size (multiplier median 0.01 s at 4 bits, 11 s at 8, over 10 s at 9–10) and never by a rewrite failing; leave-one-design-out AUC is high pooled (0.96–0.998) only because it reads design size, and within the 8-bit multiplier it is 0.65–0.78 against 0.81 for the rule “the rewrite shrinks the netlist”. One solver, one timeout. Milestone 6 (theory): define a rung’s inversion as the largest log-factor by which it ranks a truly worse candidate at or ahead of a better one; halving’s routed regret is then at most the sum of the cut rungs’ inversions (proved; holds on all 40 table cells). It is vacuous for the generic-gate rung (inversion above 0.3 on 8 of 10 groups) and loose for the mapped rungs (bound 0.23–0.35 against about 0 realised); a 10-point pilot sees a median 52–67% of the inversion but cannot certify it. The probabilistic version is open.

Research log

Ongoing: each run adds a batch and an entry, newest first. Source: LOG.md.

2026-10-31 · Milestone 45: does the rank displacement rho/k grow with pool size? (exploratory; no predictions were written before the script ran)

2026-10-30 · Milestone 44: how far do the rungs displace the pool optimum, and is a rank assumption on it enough for zero regret? (exploratory; no predictions were written before the script ran)

2026-10-30 · Milestone 43: no quantile of the per-candidate excess g bounds halving regret in general (a counterexample; theory, no flow run)

2026-10-30 · Milestone 42: does a quantile of g computed inside a 16-point pilot bound halving regret? (exploratory; no predictions were written before the script ran)

2026-10-30 · Milestone 41: does a quantile of the per-candidate excess g_x^(k) bound halving regret? (predictions fixed before the script ran)

### Outcome (experiments/theory/quantile_g.py, about 3 s, quantile_g_results.txt; 40 cells x 200 tie-breaks)

2026-10-29 · Milestone 40: can a fixed multiplier turn the 16-point pilot estimate of iota^(k) into a bound? (negative; exploratory, no predictions written before the script ran)

2026-10-29 · Paper sync: section 6 item 4 now cites milestones 36 and 38 (documentation only; no experiment)

2026-10-28 · Milestone 39: an optimum-anchored halving bound (theorem plus check; exploratory, no predictions written before the script ran)

2026-10-28 · Milestone 38: can a 16-point pilot estimate iota^(k)? (negative; no predictions were written before this run, so read it as exploratory)

2026-10-28 · Milestone 37: a regret bound that improves with the survivor count k (theorem; predictions fixed before the script ran)

### Outcome (experiments/theory/kth.py about 10 s, kth_results.txt; no flow run)

2026-10-28 · Milestone 36: coverage of the with-replacement (independent-pairs) pilot quantile on the cached tables (predictions fixed before the script ran)

### Outcome (experiments/theory/with_replacement.py about 12 s, with_replacement_results.txt; no flow run)

2026-10-28 · Milestone 35: is the disjoint-pair pilot quantile (QUANTILE.md) actually proved? (hypothesis fixed before the script ran; theory item 4 of the paper's list)

### Outcome (experiments/theory/disjoint_results.txt)

2026-10-28 · Milestone 34: median, worst-design and tail regret for every arm, budget and design set (descriptive; predictions fixed before the script ran)

### Outcome (experiments/tail_risk/: tail.py about 15 s, results.txt, summary.json; no flow run)

2026-10-28 · Milestone 33: does the R2 score matter once the first cut is harsh (eta = 3)? (predictions fixed before the script ran)

### Outcome (experiments/r2_harsh_cut/: replay.py 12 s, results.txt, summary.json; no flow run)

2026-10-28 · Milestone 32: does ranking the R2 rung on mapped area alone beat area x period on the 12 held-out designs? (predictions fixed before the script ran)

### Outcome (experiments/r2_area_arm/: replay.py 9 s, results.txt, summary.json; 24 cells)

2026-10-27 · Milestone 31: which factor of the area-delay product does R2 get wrong on fanao96? (post hoc: the script was written after milestone 30's data existed; no flow run, no tuning)

### Outcome (experiments/fanao_mech/results.txt)

2026-10-27 · Milestone 30: does repair-driven inversion (milestone 28) show up, with statistics, on high-fanout designs whose sequences give many distinct mappings? (predictions fixed before any flow output exists)

### Outcome (experiments/fanout_rich/: run.py about 40 min on 4 cores, results.jsonl 240 runs, 200 ok and 40 failed in ABC (10 per cell), analyse.py -> outcomes.txt, replay.py -> results.txt; Yosys 0.33, OpenROAD 26Q2 from the nixpkgs cache, as before; baseline no-wire periods 3.60 and 2.07 ns)

2026-10-27 · Milestone 29: are the held-out wins of "cut on R2 gently" over random R4 significant when the ten unseen and hostile designs are pooled? (post hoc: the script ran once before this entry was written; comparisons and tests were fixed in the script's header, not tuned afterwards)

### Outcome (experiments/heldout_signif/: results.txt, summary.json)

2026-10-27 · Paper: milestones 24 to 28 folded into the results (no new experiment)

2026-10-27 · Milestone 28: does R2 fail, and does the pilot gate then pay, on designs built to be wiring-dominated? (predictions fixed before any flow output exists)

### Outcome (experiments/hostile/: run.py about 100 min on 4 cores, results.jsonl 600 runs of which 520 ok and 80 failed in ABC, replay.py 13 s, results.txt; designs xbar, gf2mat, bcastmix, cmp128, rotmix in designs/, all five kept; baseline no-wire periods 1.10, 1.35, 6.52, 1.51, 2.42 ns)

2026-10-27 · Milestone 27: does the pilot-gate picture (milestone 16) hold on five designs from families it never saw? (predictions fixed before the flow output was opened)

### Outcome (experiments/unseen/: run.py about 35 min on 4 cores, results.jsonl 600 runs of which 502 ok and 98 failed in ABC (about the same share as earlier tables), replay.py about 1 min, results.txt, summary.json)

2026-10-27 · Milestone 26: do the halving and never-cut strategies of milestone 13 keep their ranking on the ss table, and does an eta chosen at tt transfer? (predictions fixed before reading any output; the script was started first and its output not opened)

### Outcome (experiments/corner_replay/: replay.py about 100 s, results.txt, summary.json; no flow run; the tt half reproduces eta_floor/results.txt line for line, a check on the swap)

2026-10-27 · Milestone 25: does the rung-bias picture of the five larger designs survive a second operating point (65% placement utilisation)? (planned before running)

### Outcome (experiments/util65/: run.py about 85 min on 4 cores, results.jsonl, results.txt, summary.json)

2026-10-27 · Milestone 24: does the rung bias survive a second corner (SKY130 HD ss_100C_1v60)? (planned before the analysis; the flow was started first)

### Outcome (experiments/corner_ss/: results.jsonl 1,200 runs of which 1,004 ok and 196 failed, the same count as at tt; compare.py, results.txt, summary.json; flow about 40 min on 4 cores)

2026-10-26 · README sync after milestones 20 to 23 (no experiment)

2026-10-26 · Milestone 23: does BOHB's model (a TPE density ratio over R2 features) beat "never cut on R2" (f3)? (planned before running)

### Outcome (experiments/mf_tpe/: tpe.py about 20 min, results.txt, summary.json; no flow run)

2026-10-26 · Milestone 22: does a Gaussian-process BO baseline (expected improvement) beat "never cut on R2" (f3)? (planned before running)

### Outcome (experiments/mf_gp/: gp.py about 940 s, results.txt, summary.json; no flow run)

2026-10-26 · Paper and artefact sync after milestones 17 to 21

2026-10-26 · Milestone 21: does an exploration term rescue the learned surrogate of milestone 20? (post hoc: script run once before this entry was written)

2026-10-26 · Milestone 20: does a learned multi-fidelity surrogate beat "never cut on R2" (f3) at equal budget? (planned before running)

### Outcome (experiments/mf_surrogate/: surrogate.py about 150 s, results.txt, summary.json; no flow run)

2026-10-26 · Milestone 19: does a score learned on other designs beat the hand-made R2 and R3 scores? (held out by design)

2026-10-26 · Milestone 18: is it R2's area or R2's period that mis-ranks, and where is the room? (diagnostic on the committed tables)

### Outcome (experiments/r2_components/: components.py, results.txt, summary.json; no flow run, 40 cells, full pools of about 50 points)

2026-10-26 · Milestone 17: does a bigger pilot or a held-out threshold make the R2-to-R3 gate beat "never cut on R2"? (planned before running)

### Outcome (experiments/pilot_sweep/: sweep.py about 90 s, results.txt, summary.json; no flow run)

2026-10-26 · Milestone 16: can a cheap pilot statistic tell when cutting on R2 rank is safe? (planned before running)

### Outcome (experiments/pilot_gate/: gate.py about 50 s, results.txt, summary.json; no flow run)

2026-10-26 · Milestone 15: does the larger-design finding hold on a non-arithmetic family? (planned before running)

### Outcome (experiments/nonarith/: run.py about 35 min on 4 cores, analyse.py, sweep.py about 100 s, perdesign.py, results.txt, perdesign.txt; 600 flow runs, 96 rejected as in milestone 9)

2026-10-25 · Milestone 14: is gentle-cut halving better than random R4 under a paired test, and does a per-family fold change the held-out choice? (planned before running)

### Outcome (experiments/signif/: test.py about 75 s, results.txt, summary.json; no flow run)

2026-10-25 · Milestone 13: does a gentler cut than eta = 1.5, or filtering on R3 only, remove the halving floor? (experiments/eta_floor/)

### Outcome

2026-10-25 · Milestone 12: is eta = 2 for halving from R2 a real gain once eta is chosen on other designs? (planned before running)

### Outcome (experiments/eta_sweep/: sweep.py about 30 s, results.txt, summary.json; no flow run)

2026-10-25 · Milestone 11: can a two-arm hedge remove the bias floor of successive halving from R2? (planned before running)

### Outcome (experiments/hedge/: replay.py about 60 s, results.txt, summary.json; no flow run)

2026-10-25 · Milestone 10b: an independent rerun with predictions on record (conformal shortlist and pilot bound, larger designs)

2026-10-25 · Milestone 10: does the conformal shortlist (H4) survive the larger designs?

2026-10-25 · Milestone 9: five larger designs, and does the routed rung get expensive enough for H2? (planned before running)

### Outcome (experiments/large/: run.py about 50 min on 4 cores, analyse.py, results.txt, halving_replay.py 20 s, halving_results.txt; 600 runs, 96 rejected by ABC/OpenROAD, pools of 50 to 52)

2026-10-25 · Milestone 8: Hyperband across the four rungs at equal wall-clock (planned before running)

### Outcome (experiments/hyperband/: replay.py about 30 s, results.txt, summary.json; the SH-from-R2 and random columns reproduce milestone 3's numbers exactly, a check on the shared cost model)

2026-10-25 · Milestone 7d: paper draft and a one-command reproduction (planned before running)

### Outcome

2026-10-25 · Milestone 7c: does the top-vs-all bound survive smaller pilots, and does the hypergeometric fact explain when? (planned before running)

### Outcome (experiments/theory/: sweep.py about 3 s, sweep_results.txt, sweep_summary.json)

2026-10-25 · Milestone 7b: pilot-by-pilot coverage of a halving bound, random pairs versus the pilot's best few (planned before running)

### Outcome (experiments/theory/: topk.py under 1 s, topk_results.txt, topk_summary.json, 1 new test)

2026-10-25 · Milestone 7a: a distribution-free pilot quantile of pair inversions, and how much of the halving bound it keeps (planned before running)

### Outcome (experiments/theory/: QUANTILE.md, quantile.py about 7 s, quantile_results.txt, 3 new tests)

2026-10-24 · Milestone 6: a regret bound for successive halving from the largest rung inversion (theory), planned before running

### Outcome (experiments/theory/: BOUND.md proof, bound.py about 10 s, src/verified_dse/bound.py with 4 new tests)

2026-10-24 · Milestone 5: is equivalence-proof success predictable from cheap features (H5), planned before running

### Outcome (experiments/proof_success/: proof_run.py about 2.8 min + 5.7 min on 4 cores, analyse.py seconds; 752 proofs, 15 designs)

2026-10-24 · Milestone 4: conformal shortlist (H4), planned before running

### Outcome (experiments/conformal/, 20 design x clock groups, 200 tie-breaks or pilots per group; replay.py runs in about 35 s, deterministic)

2026-10-24 · Milestone 3: successive halving across rungs, plain versus pilot-calibrated (H2, H3), planned before running

### Outcome (experiments/halving/, 10 designs, 400 paired seeds per cell, one core; replay.py runs in about 50 s)

2026-10-24 · Milestone 2: search baselines at equal wall-clock budget on the cached table (planned before running)

### Outcome (experiments/search_baselines/, 10 designs, 400 paired seeds per cell, one core; replay.py runs in about 75 s)

2026-10-24 · Milestone 1: rung-bias benchmark (H1), planned before running

### Outcome (same day, experiments/rung_bias/)

2026-10-24 · Programme opened: proposal written

Paper, code and results

More in Algorithmic chip-design loops

All 42 Algorithmic chip-design loops projects →

Other research topics

Proper scoring & elicitation28Effort & peer prediction9Verification games & slashing19Detection & tolerances14Markets as routers13Prediction-market design9Paying contributors8Decentralised training systems23Digital twins & sim-to-real164LLM chip design loops40Robot manufacturing loops53Ambient AI assistant46Self-replicating manufacturing34Simulation-first design64Engineered clothing45Task-specific AI accelerators40Algorithmic chip-design loops42Open-source purpose-built robots44The software-engineering loop43Adversarial human imitation41Open-source residential construction41Autonomous multi-angle capture34Sensing, imaging and 3D31Energy supply and dense energy storage39Robot societies among people31Agentic co-design of low-cost robots27Laundry-hanging robots25Machine learning on qualitative data23Robots on the building site27Civilizations & group psychology1History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.