Bucket width, duplicate work, and local lookahead

Bee Rosa Davis · September 2026 · Local reproducible benchmark report

192 primary graph configurations; 43,956 validation samples; 9,504 calibration samples. Three synthetic seeds, held-out sources, balanced timing order, complete distance checks.

Ratios compare arms measured in the same rounds. Selected widths are trained on source 0. They are not oracles. Graph admission and executed scouting work are separate quantities.

Core solve times

Paired speed ratios by graph family
arm fourary mean_degree mean_map mean_ring original_mean selected_grid std_binary
family n
clustered 1000 0.3239 0.4251 0.2748 0.2545 0.3274 0.2466 0.3439
2000 0.7910 0.8316 0.5350 0.5144 0.6152 0.5260 0.8216
5000 2.6389 1.9700 1.5105 1.3952 1.7998 1.4218 2.6914
10000 7.4358 4.7415 3.9806 3.8908 6.6988 3.9476 7.2590
dense 1000 0.6676 0.8620 0.8492 0.8734 4.8212 0.6373 0.7722
2000 2.0144 2.9310 3.1926 3.3063 22.8754 2.5620 2.3776
5000 7.9821 13.8568 16.6253 16.9907 146.6585 13.5200 9.3033
grid 1000 0.1112 0.1236 0.1032 0.1019 0.1014 NaN 0.1012
2000 0.2242 0.2324 0.1924 0.1869 0.1744 NaN 0.2126
5000 0.6067 0.5460 0.4755 0.4438 0.4152 NaN 0.5633
10000 1.2854 0.9830 0.8724 0.8144 0.7732 NaN 1.1894
roadlike 1000 0.1178 0.1481 0.1257 0.1252 0.1266 NaN 0.1078
2000 0.2409 0.2736 0.2301 0.2238 0.2178 NaN 0.2184
5000 0.6172 0.6411 0.5451 0.5236 0.5074 NaN 0.5820
sparse 1000 0.1933 0.1548 0.1292 0.1195 0.1234 0.1161 0.1785
2000 0.4150 0.2979 0.2385 0.2264 0.2291 0.2307 0.3945
5000 1.1032 0.6979 0.5920 0.5712 0.5432 0.5716 1.0473
10000 2.4975 1.4289 1.3389 1.2770 1.2136 1.1795 2.3782

Gate mechanisms

The fixed gate is live on sparse graphs, saturated on grids, and dead on the dense, clustered, and road-like source-zero instances. NEVER is the relevant no-lookahead comparator. High/high uses AND; the logical complement uses OR.

family n m class arm admitted pushes pops scouts scout_scans comparisons
sparse 1000 4571 live never 0 1397 1397 0 0 23131
sparse 1000 4571 live always 4571 1695 1695 634 2965 30145
sparse 1000 4571 live degree4 568 1445 1445 135 348 24297
sparse 1000 4571 live high_high 1787 1623 1623 294 1950 28321
sparse 1000 4571 live complement 4003 1698 1698 563 2853 30204
sparse 1000 4571 live random_exact 568 1494 1494 143 645 25470
sparse 1000 4571 live adaptive 261 1414 1414 63 130 23509
dense 1000 99482 dead never 0 3812 3812 0 0 79677
dense 1000 99482 dead always 99482 4940 4940 803 79782 107762
dense 1000 99482 dead degree4 0 3812 3812 0 0 79677
dense 1000 99482 dead high_high 99482 4940 4940 803 79782 107762
dense 1000 99482 dead complement 99482 4940 4940 803 79782 107762
dense 1000 99482 dead random_exact 0 3812 3812 0 0 79677
dense 1000 99482 dead adaptive 0 3812 3812 0 0 79677
grid 1000 3870 saturated never 0 1241 1241 0 0 11902
grid 1000 3870 saturated always 3870 1360 1360 621 2404 14903
grid 1000 3870 saturated degree4 3870 1360 1360 621 2404 14903
grid 1000 3870 saturated high_high 0 1241 1241 0 0 11902
grid 1000 3870 saturated complement 0 1241 1241 0 0 11902
grid 1000 3870 saturated random_exact 3870 1360 1360 621 2404 14903
grid 1000 3870 saturated adaptive 252 1262 1262 58 174 12327
clustered 1000 25061 dead never 0 2412 2412 0 0 39306
clustered 1000 25061 dead always 25061 3230 3230 661 16590 60829
clustered 1000 25061 dead degree4 0 2412 2412 0 0 39306
clustered 1000 25061 dead high_high 25061 3230 3230 661 16590 60829
clustered 1000 25061 dead complement 25061 3230 3230 661 16590 60829
clustered 1000 25061 dead random_exact 0 2412 2412 0 0 39306
clustered 1000 25061 dead adaptive 0 2412 2412 0 0 39306
roadlike 1000 6000 dead never 0 1404 1404 0 0 13825
roadlike 1000 6000 dead always 6000 1741 1741 568 3408 20603
roadlike 1000 6000 dead degree4 0 1404 1404 0 0 13825
roadlike 1000 6000 dead high_high 6000 1741 1741 568 3408 20603
roadlike 1000 6000 dead complement 6000 1741 1741 568 3408 20603
roadlike 1000 6000 dead random_exact 0 1404 1404 0 0 13825
roadlike 1000 6000 dead adaptive 0 1404 1404 0 0 13825
sparse 2000 9049 live never 0 2697 2697 0 0 49332
sparse 2000 9049 live always 9049 3264 3264 1201 5440 63710
sparse 2000 9049 live degree4 1212 2796 2796 277 670 52069
sparse 2000 9049 live high_high 3381 3156 3156 544 3532 60778
sparse 2000 9049 live complement 7837 3202 3202 1028 5047 62242
sparse 2000 9049 live random_exact 1212 2937 2937 323 1446 55603
sparse 2000 9049 live adaptive 563 2744 2744 141 288 50692
dense 2000 399506 dead never 0 8555 8555 0 0 198795
dense 2000 399506 dead always 399506 11286 11286 1592 318144 275201
dense 2000 399506 dead degree4 0 8555 8555 0 0 198795
dense 2000 399506 dead high_high 399506 11286 11286 1592 318144 275201
dense 2000 399506 dead complement 399506 11286 11286 1592 318144 275201
dense 2000 399506 dead random_exact 0 8555 8555 0 0 198795
dense 2000 399506 dead adaptive 0 8555 8555 0 0 198795
grid 2000 7820 saturated never 0 2506 2506 0 0 26954
grid 2000 7820 saturated always 7820 2761 2761 1244 4867 33692
grid 2000 7820 saturated degree4 7820 2761 2761 1244 4867 33692
grid 2000 7820 saturated high_high 0 2506 2506 0 0 26954
grid 2000 7820 saturated complement 0 2506 2506 0 0 26954
grid 2000 7820 saturated random_exact 7820 2761 2761 1244 4867 33692
grid 2000 7820 saturated adaptive 352 2526 2526 82 245 27528
clustered 2000 51918 dead never 0 5247 5247 0 0 100376
clustered 2000 51918 dead always 51918 6660 6660 1485 38669 138722
clustered 2000 51918 dead degree4 0 5247 5247 0 0 100376
clustered 2000 51918 dead high_high 51918 6660 6660 1485 38669 138722
clustered 2000 51918 dead complement 51918 6660 6660 1485 38669 138722
clustered 2000 51918 dead random_exact 0 5247 5247 0 0 100376
clustered 2000 51918 dead adaptive 0 5247 5247 0 0 100376
roadlike 2000 12000 dead never 0 2790 2790 0 0 30634
roadlike 2000 12000 dead always 12000 3545 3545 1169 7014 46090
roadlike 2000 12000 dead degree4 0 2790 2790 0 0 30634
roadlike 2000 12000 dead high_high 12000 3545 3545 1169 7014 46090
roadlike 2000 12000 dead complement 12000 3545 3545 1169 7014 46090
roadlike 2000 12000 dead random_exact 0 2790 2790 0 0 30634
roadlike 2000 12000 dead adaptive 0 2790 2790 0 0 30634
sparse 5000 22746 live never 0 6879 6879 0 0 144514
sparse 5000 22746 live always 22746 8326 8326 3064 13851 186140
sparse 5000 22746 live degree4 3070 7210 7210 702 1778 153897
sparse 5000 22746 live high_high 8466 8026 8026 1357 8817 176857
sparse 5000 22746 live complement 19676 8276 8276 2689 13225 184424
sparse 5000 22746 live random_exact 3070 7482 7482 813 3815 161039
sparse 5000 22746 live adaptive 1463 7035 7035 375 783 148964
dense 5000 2499352 dead never 0 24020 24020 0 0 633974
dense 5000 2499352 dead always 2499352 31686 31686 3631 1815871 864484
dense 5000 2499352 dead degree4 0 24020 24020 0 0 633974
dense 5000 2499352 dead high_high 2499352 31686 31686 3631 1815871 864484
dense 5000 2499352 dead complement 2499352 31686 31686 3631 1815871 864484
dense 5000 2499352 dead random_exact 0 24020 24020 0 0 633974
dense 5000 2499352 dead adaptive 0 24020 24020 0 0 633974
grid 5000 19700 saturated never 0 6320 6320 0 0 74282
grid 5000 19700 saturated always 19700 6983 6983 3164 12465 92508
grid 5000 19700 saturated degree4 19700 6983 6983 3164 12465 92508
grid 5000 19700 saturated high_high 0 6320 6320 0 0 74282
grid 5000 19700 saturated complement 0 6320 6320 0 0 74282
grid 5000 19700 saturated random_exact 19700 6983 6983 3164 12465 92508
grid 5000 19700 saturated adaptive 592 6360 6360 134 400 75154
clustered 5000 142318 dead never 0 15349 15349 0 0 353297
clustered 5000 142318 dead always 142318 18825 18825 3710 106228 447668
clustered 5000 142318 dead degree4 0 15349 15349 0 0 353297
clustered 5000 142318 dead high_high 142318 18825 18825 3710 106228 447668
clustered 5000 142318 dead complement 142318 18825 18825 3710 106228 447668
clustered 5000 142318 dead random_exact 0 15349 15349 0 0 353297
clustered 5000 142318 dead adaptive 0 15349 15349 0 0 353297
roadlike 5000 30000 dead never 0 7001 7001 0 0 86902
roadlike 5000 30000 dead always 30000 8793 8793 2917 17502 126474
roadlike 5000 30000 dead degree4 0 7001 7001 0 0 86902
roadlike 5000 30000 dead high_high 30000 8793 8793 2917 17502 126474
roadlike 5000 30000 dead complement 30000 8793 8793 2917 17502 126474
roadlike 5000 30000 dead random_exact 0 7001 7001 0 0 86902
roadlike 5000 30000 dead adaptive 0 7001 7001 0 0 86902
sparse 10000 45188 live never 0 13603 13603 0 0 311994
sparse 10000 45188 live always 45188 16343 16343 6032 27422 395922
sparse 10000 45188 live degree4 6150 14195 14195 1431 3553 330090
sparse 10000 45188 live high_high 16524 15700 15700 2692 17399 374997
sparse 10000 45188 live complement 39038 16270 16270 5269 26021 393461
sparse 10000 45188 live random_exact 6150 14681 14681 1564 6938 344120
sparse 10000 45188 live adaptive 2806 13861 13861 736 1450 319841
dense 10000 9998123 dead never 0 51130 51130 0 0 1463240
dense 10000 9998123 dead always 9998123 65879 65879 5987 5987828 1933899
dense 10000 9998123 dead degree4 0 51130 51130 0 0 1463240
dense 10000 9998123 dead high_high 9998123 65879 65879 5987 5987828 1933899
dense 10000 9998123 dead complement 9998123 65879 65879 5987 5987828 1933899
dense 10000 9998123 dead random_exact 0 51130 51130 0 0 1463240
dense 10000 9998123 dead adaptive 0 51130 51130 0 0 1463240
grid 10000 39600 saturated never 0 12688 12688 0 0 167649
grid 10000 39600 saturated always 39600 14031 14031 6320 25029 206488
grid 10000 39600 saturated degree4 39600 14031 14031 6320 25029 206488
grid 10000 39600 saturated high_high 0 12688 12688 0 0 167649
grid 10000 39600 saturated complement 0 12688 12688 0 0 167649
grid 10000 39600 saturated random_exact 39600 14031 14031 6320 25029 206488
grid 10000 39600 saturated adaptive 792 12736 12736 171 513 168855
clustered 10000 324486 dead never 0 34037 34037 0 0 858309
clustered 10000 324486 dead always 324486 39885 39885 7669 249954 1048571
clustered 10000 324486 dead degree4 0 34037 34037 0 0 858309
clustered 10000 324486 dead high_high 324486 39885 39885 7669 249954 1048571
clustered 10000 324486 dead complement 324486 39885 39885 7669 249954 1048571
clustered 10000 324486 dead random_exact 0 34037 34037 0 0 858309
clustered 10000 324486 dead adaptive 0 34037 34037 0 0 858309
roadlike 10000 60000 dead never 0 13926 13926 0 0 186756
roadlike 10000 60000 dead always 60000 17888 17888 5872 35232 277123
roadlike 10000 60000 dead degree4 0 13926 13926 0 0 186756
roadlike 10000 60000 dead high_high 60000 17888 17888 5872 35232 277123
roadlike 10000 60000 dead complement 60000 17888 17888 5872 35232 277123
roadlike 10000 60000 dead random_exact 0 13926 13926 0 0 186756
roadlike 10000 60000 dead adaptive 0 13926 13926 0 0 186756

Real roads and scale

arm binary caliber degree4 fourary max_maxdegree mean_degree mean_map mean_ring radix selected_grid std_binary
panel family n
roads BAY 321270 58.065 43.639 69.644 59.668 35.448 43.951 41.309 36.514 78.503 35.018 54.789
COL 435666 79.692 60.832 95.290 79.453 50.522 62.256 55.993 48.915 107.236 49.116 77.751
NY 264346 53.192 42.605 64.959 54.715 29.682 35.869 34.145 31.288 66.924 29.717 51.622
scale sparse_fast 10000 2.964 2.621 3.483 2.964 1.813 1.725 1.814 1.623 NaN NaN 2.846
100000 51.626 45.899 62.355 51.150 27.392 27.289 28.410 27.621 NaN NaN 50.674
1000000 830.528 779.672 1006.562 801.001 447.286 450.580 449.358 445.235 NaN NaN 796.943

Layout exclusion

Both sources of layout case 29 (BFS, n=100000, seed 2026) are excluded from the reported layout summary following reported synchronization interference. Raw measurements remain intact. BFS retains two seeds; other layouts retain three.

median_ms
family n
bfs 5000 0.563
100000 25.681
destination 5000 0.730
100000 29.913
random 5000 0.705
100000 29.317
rcm 5000 0.587
100000 27.329
weight 5000 0.556
100000 24.353

Reproduction

Paper · Protocol · Run manifest · Paired differences and IQRs

Timings exclude loading and most preparation. One machine, three synthetic seeds, and descriptive uncertainty do not establish universal performance. The report is generated by render_results.py.