Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC
Organizations: Independent Researcher.
Abstract
Optimizing transition probabilities on a fixed grap may leave substantial limitations on the efficiency of reversible Markov chain Monte Carlo (MCMC). We develop a framework for transition-support design that considers both allowed transitions and their stationary flows. For a fixed target distribution, observable, and node-flow budget, we derive a necessary and sufficient dual condition for support augmentation to strictly reduce the optimal value of the asymptotic variance, together with computable primal--dual certificates that establish improvements over every admissible original-support reweighting. We also construct a family in which adding a single edge reduces integrated autocorrelation time by an factor relative to optimal original-support weighting, demonstrating that structural limitations can impose arbitrarily large relative losses in estimation efficiency. To realize these gains, we investigate energy-informed edge selection and constrained stationary-flow optimization. Experiments on molecular and Ising state graphs distinguish the potential value of new transitions from the performance of kernels constructed on them: on identical augmented Ising supports, full weight optimization certifies strict improvements in 24/24 conditions, whereas degree-based Metropolis--Hastings weighting certifies none. Our results provide a principled approach to characterizing, certifying, and exploiting transition-support improvements in explicitly represented finite state spaces.
Figures & tables
| Question | Evidence and outer unit |
|---|---|
| Support value | Instancewise certificates; uniform-target separation family |
| Checkpoint transfer | 5 model seeds; 40 nested cells |
| Component transfer | 8 new components; 80 cells; same construction rule |
| Selection value | Common weighting; 5 molecular seeds and 12 Ising instances |
| Release attribution | 12 development Ising instances; matched free-set sizes |
| Factorial confirmation | 12 new Ising instances; selection release; 3 repeats |
| LEF-selected support | Capacity-selected support | ||||
|---|---|---|---|---|---|
| Cohort | Cells | Degree-MH | Optimized | Degree-MH | Optimized |
| Molecular development | 4 | 3 | 4 | 3 | 4 |
| Held-out checkpoints | 40 | 24 | 38 | 20 | 38 |
| Same-rule new components | 80 | 72 | 80 | 68 | 78 |
| Natural-support Ising | 24 | 0 | 24 | 0 | 23 |
| Group | Control | Ratio | 95% outer interval | Median |
|---|---|---|---|---|
| Molecular | Random | 58.795 | [25.040, 154.300] | 19.106 |
| Hamming | 62.691 | [26.506, 163.335] | 19.575 | |
| Energy-only | 62.922 | [26.541, 163.826] | 19.589 | |
| Capacity | 1.976 | [1.213, 4.308] | 1.005 | |
| Ising | Random | 1.141 | [1.100, 1.187] | 1.125 |
| Hamming | 1.139 | [1.092, 1.189] | 1.131 |
| Contrast | Ratio [95% CI] | Wins | |
|---|---|---|---|
| LEF: C/P | 1.045 [1.031,1.057] | 23/24 | .0029 |
| Cap: C/P | 1.039 [1.027,1.052] | 23/24 | .0020 |
| C: Cap/LEF | 1.035 [1.015,1.060] | 20/24 | .0107 |
| P: Cap/LEF | 1.041 [1.023,1.060] | 21/24 | .0088 |
| Energy | Magnetization | |||
|---|---|---|---|---|
| Comparator | 1024 | 2048 | 1024 | 2048 |
| Base degree-MH | 2.740 | 1.480 | 1.335 | 0.970 |
| Base full | 0.598 | 1.048 | 5.694 | 13.218 |
| Capacity combined 20% | 0.858 | 0.851 | 1.070 | 1.071 |
| LEF full | 0.695 | 0.779 | 4.804 | 7.723 |
| Independent | 0.206 | 0.136 | 0.034 | 0.022 |
Appendix figures & tables37 assets
Supplementary material from the paper’s appendix.
Appendix
| Seed | Base optimum | Direct LEF upper | Optimized LEF | Optimized capacity |
|---|---|---|---|---|
| 0 | [9.715350,9.715361] | 31.389932 | [5.738051,5.738057] | [7.116234,7.116239] |
| 1 | [548.221006,548.221611] | 123.999952 | [30.021484,30.021496] | [30.408813,30.408825] |
| 2 | [835.059575,835.060517] | 463.048736 | [84.269815,84.269962] | [89.560063,89.560233] |
| 3 | [420.761980,420.762137] | 72.409725 | [10.262866,10.262878] | [10.262866,10.262878] |
| Seed | Pairs | Poisson contrast | Rank-one gain | Degree-MH gain |
|---|---|---|---|---|
| 0 | 876 | 0.632 | 0.630 | 0.541 |
| 1 | 873 | 0.688 | 0.699 | 0.619 |
| 2 | 877 | 0.698 | 0.704 | 0.552 |
| 3 | 883 | 0.651 | 0.656 | 0.425 |
| Stage | Median | Query (s) | ||
|---|---|---|---|---|
| Degree | 12.645 | 0.101 | 0/24 | 0/24 |
| Endpoint | 7.487 | 0.114 | 0/24 | 0/24 |
| 10% | 6.299 | 0.120 | 0/24 | 0/24 |
| 20% | 2.689 | 0.137 | 0/24 | 0/24 |
| 40% | 1.131 | 0.177 | 9/24 | 5/24 |
| Hash 40% | 4.039 | 0.176 | 0/24 | 0/24 |
| Cohort | Control | Outer 95% interval | Cell median | Counts | |
|---|---|---|---|---|---|
| Molecular | Random ensemble | 58.795 | [25.040,154.300] | 19.106 | 38/0/0/2 |
| Maximum-Hamming | 62.691 | [26.506,163.335] | 19.575 | 38/0/0/2 | |
| Energy-only | 62.922 | [26.541,163.826] | 19.589 | 38/0/0/2 | |
| Capacity | 1.976 | [1.213,4.308] | 1.0046 | 25/2/8/5 | |
| Ising | Random ensemble | 1.1413 | [1.1003,1.1867] | 1.1250 | 24/0/0/0 |
| Maximum-Hamming | 1.1388 | [1.0918,1.1891] | 1.1306 | 23/1/0/0 |
| Cohort | Selector | Topology: | Time (s) | ||||
|---|---|---|---|---|---|---|---|
| Molecular | LEF | 38.002 | 3.660 | 1.342 | 40/40 | 24/35/38 of 40 | 0.170 |
| Capacity | 45.575 | 7.622 | 2.397 | 40/40 | 20/29/38 of 40 | 0.170 | |
| Ising | LEF | 14.568 | 9.124 | 3.466 | 24/24 | 0/0/24 of 24 | 0.471 |
| Capacity | 14.322 | 9.272 | 3.532 | 24/24 | 0/1/23 of 24 | 0.479 |
| Development: 24 cells | Fresh confirmation: 16 cells | Fresh certified | |||||
|---|---|---|---|---|---|---|---|
| Method | Certified | IACT | Time (s) | Certified | IACT | Time (s) | and cheaper |
| Degree-MH | 0/24 | 14.568 | 0.067 | 0/16 | 19.265 | 0.049 | 0/16 |
| Endpoint update | 0/24 | 9.124 | 0.472 | 0/16 | 12.107 | 0.505 | 0/16 |
| Adaptive 10% | 0/24 | 8.344 | 0.910 | 0/16 | 7.809 | 0.956 | 0/16 |
| Adaptive 20% | 6/24 | 4.826 | 1.471 | 5/16 | 5.264 | 1.508 | 5/16 |
| Adaptive 40% | 12/24 | 3.849 | 2.361 | 8/16 | 4.603 | 2.371 | 0/16 |
| Cohort | Adaptive 20% | Adaptive 40% | Hash 20% | Hash 40% | Full | |
|---|---|---|---|---|---|---|
| Development | 0.3 | 0/12 | 0/12 | 0/12 | 0/12 | 12/12 |
| 0.8 | 6/12 | 12/12 | 0/12 | 0/12 | 12/12 | |
| Fresh | 0.3 | 0/8 | 0/8 | 0/8 | 0/8 | 8/8 |
| 0.8 | 5/8 | 8/8 | 0/8 | 1/8 | 8/8 |
| Cost ledger | 20%: same support | 20%: with base kernel | 40%: same support |
|---|---|---|---|
| Sampling setup | 14/16 | 14/16 | 1/16 |
| Witness verification | 14/16 | 14/16 | 1/16 |
| Joint proof-and-kernel | 14/16 | 1/16 | 1/16 |
| Stage | Median IACT | Cumulative seconds | Certified | Certified and cheaper than full |
|---|---|---|---|---|
| endpoint | 9.124079 | 0.4729 | 0/24 | 0/24 |
| potential20 | 4.635916 | 1.4579 | 9/24 | 9/24 |
| dual20 | 8.307282 | 1.4814 | 1/24 | 1/24 |
| combined20 | 4.825849 | 1.4740 | 6/24 | 6/24 |
| hash20 | 7.677151 | 1.4938 | 0/24 | 0/24 |
| potential40 | 4.107867 | 2.2590 | 12/24 | 1/24 |
| Release | Control | Control/combined | Cell median | Combined wins/losses | Leave-one-instance-out |
|---|---|---|---|---|---|
| 20% | Potential | 0.965646 | 0.974851 | 1/23 | [0.962670, 0.969318] |
| 20% | Dual | 1.685595 | 1.702877 | 24/0 | [1.663885, 1.720480] |
| 20% | Hash | 1.598127 | 1.537450 | 24/0 | [1.581997, 1.619324] |
| 40% | Potential | 1.069301 | 1.047724 | 22/2 | [1.063218, 1.074180] |
| 40% | Dual | 1.801811 | 1.793052 | 24/0 | [1.751669, 1.848663] |
| 40% | Hash | 1.540321 | 1.503148 | 24/0 | [1.515505, 1.557621] |
| Stage | Current implementation |
|---|---|
| Candidate discovery | Scans pairs; heap selection costs at most with extra candidate storage. |
| Local selection | scores, sorting; degree preparation. |
| Poisson proposal | Dense factorization usually costs floating-point operations and memory; repeated across stages and candidate kernels. |
| Restricted weighting | current variables, conductances, and cone auxiliaries; full-graph conservation and target information remain active. |
| Release ordering | scoring and sorting using the full potential and node prices. |
| Witness checking | Budget and divergence sums require rational operations; bit lengths and current-repair tree construction add costs. |
| Comparison (numerator/denominator) | Geom. | 95% CI | Median | Wins | Outer wins / |
|---|---|---|---|---|---|
| LEF Combined / LEF Potential | 1.044824 | [1.031125,1.057476] | 1.047094 | 23/24 | 11/12 / .002930 |
| Cap Combined / Cap Potential | 1.038953 | [1.027005,1.052031] | 1.034746 | 23/24 | 12/12 / .001953 |
| Cap Combined / LEF Combined | 1.035469 | [1.015323,1.059798] | 1.025003 | 20/24 | 10/12 / .010742 |
| Cap Potential / LEF Potential | 1.041320 | [1.023294,1.060330] | 1.043512 | 21/24 | 10/12 / .008789 |
| Selector / rule | IACT | Setup (s) | Joint (s) | Cert. | Cert. + cheap |
|---|---|---|---|---|---|
| LEF / Combined 20% | 4.6374 | 1.5576 | 4.7954 | 7/24 | 6/24 |
| LEF / Potential 20% | 4.4372 | 1.4631 | 4.6586 | 7/24 | 6/24 |
| Capacity / Combined 20% | 4.9487 | 1.5330 | 4.7552 | 7/24 | 6/24 |
| Capacity / Potential 20% | 4.5384 | 1.5132 | 4.7368 | 7/24 | 7/24 |
| LEF / Combined 40% | 3.6861 | 2.3711 | 5.6773 | 9/24 | 0/24 |
| LEF / Potential 40% | 3.9225 | 2.2701 | 5.4193 | 9/24 | 2/24 |
| States | Method | Completed; budget-available | Setup seconds | Peak RSS (MiB) |
|---|---|---|---|---|
| 1024 | Base degree-MH | 5/5; 5/5 | 0.111 | 115.3 |
| 1024 | Base full | 5/5; 5/5 | 43.551 | 150.7 |
| 1024 | LEF degree-MH | 5/5; 5/5 | 0.459 | 102.1 |
| 1024 | LEF adaptive20 | 5/5; 5/5 | 16.069 | 149.1 |
| 1024 | Capacity adaptive20 | 5/5; 5/5 | 19.009 | 145.1 |
| 1024 | LEF full | 5/5; 5/5 | 32.127 | 150.7 |
| States | Start | Base degree | LEF degree | Base full | LEF full | Capacity20 | Independent |
|---|---|---|---|---|---|---|---|
| 1024 | all-plus | 2.437 (5/5) | 2.302 (5/5) | 0.599 (1/5) | 0.525 (0/5) | 0.737 (1/5) | 0.213 (0/5) |
| 1024 | all-minus | 2.224 (5/5) | 2.393 (5/5) | 0.586 (0/5) | 0.518 (0/5) | 1.171 (3/5) | 0.208 (0/5) |
| 1024 | uniform-state | 2.740 (5/5) | 2.789 (5/5) | 0.598 (1/5) | 0.695 (0/5) | 0.858 (2/5) | 0.206 (0/5) |
| 2048 | all-plus | 2.182 (5/5) | 2.016 (5/5) | 1.278 (4/5) | 0.993 (3/5) | 1.123 (4/5) | 0.135 (0/5) |
| 2048 | all-minus | 2.270 (5/5) | 2.572 (5/5) | 1.373 (3/5) | 1.019 (3/5) | 1.311 (3/5) | 0.140 (0/5) |
| 2048 | uniform-state | 1.480 (4/5) | 1.469 (3/5) | 1.048 (3/5) | 0.779 (2/5) | 0.851 (2/5) | 0.136 (0/5) |
| States | Start | Base degree | LEF degree | Base full | LEF full | Capacity20 | Independent |
|---|---|---|---|---|---|---|---|
| 1024 | all-plus | 1.175 (3/5) | 1.141 (3/5) | 4.837 (5/5) | 3.919 (5/5) | 0.822 (1/5) | 0.031 (0/5) |
| 1024 | all-minus | 1.066 (3/5) | 1.037 (2/5) | 4.741 (5/5) | 4.189 (5/5) | 1.040 (3/5) | 0.024 (0/5) |
| 1024 | uniform-state | 1.335 (5/5) | 1.487 (5/5) | 5.694 (5/5) | 4.804 (5/5) | 1.070 (3/5) | 0.034 (0/5) |
| 2048 | all-plus | 1.126 (3/5) | 1.132 (3/5) | 14.663 (5/5) | 8.088 (5/5) | 1.134 (3/5) | 0.024 (0/5) |
| 2048 | all-minus | 0.730 (0/5) | 0.755 (1/5) | 10.116 (5/5) | 7.165 (5/5) | 0.936 (2/5) | 0.021 (0/5) |
| 2048 | uniform-state | 0.970 (2/5) | 0.979 (2/5) | 13.218 (5/5) | 7.723 (5/5) | 1.071 (3/5) | 0.022 (0/5) |
| Method | 1024 | 2048 | 4096 |
|---|---|---|---|
| Base degree-MH | 5.570e-08 | 6.149e-08 | 7.698e-08 |
| Base full | 1.113e-08 | 4.121e-08 | – |
| LEF degree-MH | 6.278e-08 | 5.544e-08 | 8.627e-08 |
| LEF adaptive20 | 2.264e-08 | 3.919e-08 | – |
| Capacity adaptive20 | 1.678e-08 | 3.447e-08 | – |
| LEF full | 1.556e-08 | 3.477e-08 | – |
| States | Comparator | Ratio | Favorable | Outer 95% interval | Leave-one-seed-out |
|---|---|---|---|---|---|
| 1024 | Base degree-MH | 2.740 | 5/5 | [2.460, 3.090] | [2.611, 2.838] |
| 1024 | Base full | 0.598 | 1/5 | [0.475, 0.890] | [0.492, 0.636] |
| 1024 | LEF full | 0.695 | 0/5 | [0.598, 0.827] | [0.643, 0.738] |
| 1024 | Capacity adaptive20 | 0.858 | 2/5 | [0.597, 1.233] | [0.739, 0.966] |
| 1024 | Independent | 0.206 | 0/5 | [0.154, 0.258] | [0.191, 0.237] |
| 2048 | Base degree-MH | 1.480 | 4/5 | [1.033, 2.119] | [1.328, 1.712] |
| States | Candidate (s) | Local (s) | Full (s) | Peak MiB | Full certified | |||
|---|---|---|---|---|---|---|---|---|
| 64 | 0.0024 | 0.082 | 0.501 | 130.4 | 4.180 | 3.338 | 1.018 | 3/3 |
| 128 | 0.0323 | 0.205 | 1.229 | 159.3 | 5.566 | 4.264 | 1.295 | 3/3 |
| 256 | 0.0572 | 0.460 | 3.042 | 224.7 | 7.236 | 5.798 | 1.624 | 3/3 |
| 512 | 0.2036 | 1.245 | 8.983 | 391.7 | 8.143 | 7.044 | 1.775 | 3/3 |
| 1024 | 0.9604 | 4.246 | 25.701 | 823.9 | 9.823 | 8.786 | 2.246 | 2/3 |
| Cohort | Selector | Rational target | Real target | Minimum IACT margin | Minimum relative margin |
|---|---|---|---|---|---|
| Molecular | LEF | 38/40 | 38/40 | 0.00181536 | 0.1990% |
| Capacity | 38/40 | 38/40 | 0.00111776 | 0.1225% | |
| Ising | LEF | 24/24 | 24/24 | 0.10490894 | 1.1717% |
| Capacity | 23/24 | 23/24 | 0.00009853 | 0.005264% |
| component | QM9 index | candidates | minimum cell ratio | component geometric ratio |
|---|---|---|---|---|
| 1 | 21583 | 267 | 1.435 | 39.205 |
| 2 | 21593 | 374 | 2.896 | 309.173 |
| 3 | 21597 | 354 | 22.239 | |
| 4 | 21603 | 172 | 1.787 | |
| 5 | 21611 | 440 | ||
| 6 | 21634 | 1020 | 2.971 | 288.869 |
| cell | stored | 120-digit | rel. error | 120-digit base/LEF | |
|---|---|---|---|---|---|
| 22-off-c4 | |||||
| 22-off-c5 | |||||
| 22-on-c4 | |||||
| 22-on-c7 | |||||
| 23-off-c3 | |||||
| 23-off-c4 |
| base graph | seeds | cells | outer interval | geometric base/LEF |
|---|---|---|---|---|
| original star + peer-4NN | 5/5 | 35/40 | [17.230, 139.959] | 45.023 |
| Hamming-local matched | 5/5 | 36/40 | [12.243, 128.575] | 38.959 |
| hash-based matched | 5/5 | 40/40 | [70.195, 499575.981] | 5921.782 |
| energy | edges | bond order | wedges | triangles | |
|---|---|---|---|---|---|
| energy | 1.000 | 0.071 | 0.369 | 0.142 | 0.006 |
| edges | 0.071 | 1.000 | 0.010 | 0.553 | 0.050 |
| bond order | 0.369 | 0.010 | 1.000 | 0.096 | 0.001 |
| wedges | 0.142 | 0.553 | 0.096 | 1.000 | 0.012 |
| triangles | 0.006 | 0.050 | 0.001 | 0.012 | 1.000 |
| Base | Capacity | LEF | Greedy | Base/LEF [95%] | Capacity/LEF [95%] | |
|---|---|---|---|---|---|---|
| 6.5 | 46.753 | 31.682 | 25.406 | 19.492 | 2.095 [1.796,2.609] | 1.301 [1.210,1.457] |
| 19.5 | 15.665 | 13.054 | 10.808 | 9.096 | 1.404 [1.348,1.476] | 1.189 [1.150,1.249] |
| 45.5 | 6.289 | 5.751 | 5.135 | 4.322 | 1.200 [1.163,1.238] | 1.130 [1.120,1.139] |
| Family | Seed suffix | Base | Capacity | LEF | Ratio | Ratio | ||
|---|---|---|---|---|---|---|---|---|
| Ferro | 00 | 0.3 | 75.50 | 11.761 | 11.515 | 11.095 | 1.0379 | 0.9541 |
| Ferro | 00 | 0.8 | 3.52 | 68.458 | 53.792 | 62.090 | 0.8663 | 0.7461 |
| Ferro | 01 | 0.3 | 60.89 | 13.743 | 13.630 | 12.945 | 1.0529 | 0.8892 |
| Ferro | 01 | 0.8 | 3.91 | 32.421 | 31.277 | 30.630 | 1.0211 | 1.0604 |
| Ferro | 02 | 0.3 | 100.54 | 10.393 | 10.232 | 9.622 | 1.0633 | 0.9340 |
| Ferro | 02 | 0.8 | 4.06 | 74.433 | 61.123 | 63.032 | 0.9697 | 0.9532 |
| Selector | New benefit | Old loss | Net gain | Base-improved cells |
|---|---|---|---|---|
| LEF | 0.71434741 | 0.02117495 | 0.69317246 | 35/40 |
| Capacity | 0.65029703 | 0.02259880 | 0.62769823 | 35/40 |
| Mode | Method | Queries | Acc. ESJD | Net Ham. 2 | |
|---|---|---|---|---|---|
| QAP-off | QUBO | 226 | 2.125 | 2.125 | |
| QAP-off | unary | 204 | 7.438 | 14.906 | |
| QAP-off | pair Gibbs | 225 | 5.156 | 14.375 | |
| QAP-off | met. pair | 225 | 5.219 | 16.063 | |
| QAP-on | QUBO | 226 | 2.781 | 2.781 | |
| QAP-on | unary | 204 | 8.688 | 18.813 |
| Cell | MH gap | FMMC gap | Gap ratio | MH IACT | FMMC IACT | IACT ratio |
|---|---|---|---|---|---|---|
| seed 0 | 0.002458 | 0.011499 | 4.678 | 59.91 | 26.31 | 2.277 |
| seed 1 | 0.0000222 | 0.000147 | 6.657 | 3204.70 | 612.48 | 5.232 |
| seed 2 | 0.0000128 | 0.0000778 | 6.083 | 5105.65 | 4896.75 | 1.043 |
| seed 3 | 0.001153 | 0.003009 | 2.609 | 1061.90 | 434.99 | 2.441 |
| Selector | Mean gap | Gap range | Mean IACT | IACT range |
|---|---|---|---|---|
| Random | 1.004 | 1.000–1.017 | 1.862 | 0.994–4.301 |
| Maximum Hamming | 1.000 | 1.000–1.000 | 1.539 | 1.000–3.152 |
| Target-mass capacity | 17.821 | 1.883–33.184 | 24.171 | 1.233–47.861 |
| Slow eigenspace | 17.782 | 1.728–33.184 | 24.408 | 1.612–48.266 |
| Energy Poisson | 17.687 | 1.350–33.184 | 24.428 | 2.668–46.869 |
Markov Chain Monte Carlo
Markov Chain Monte Carlo uses Markov chains designed to have a target distribution as their stationary law, enabling sampling and statistical estimation.
See all 157 papers