Predicting the Reality Gap of Ising Solvers from Disorder Chaos

Many hard discrete optimization problems, such as maximum cut, graph partitioning and coordination over networks, are solved by recasting them as an Ising model. In that model each binary decision becomes a "spin", each pairwise cost becomes a "coupling" between two spins, and the best solution is the lowest-energy configuration, called the ground state. These solvers are almost always judged on pristine synthetic instances such as the Gset graphs. In any deployment, though, the couplings are measurements: link latencies, trust ratings, channel gains. They carry error. Statistical physicists have long known that spin glasses are chaotic in their couplings. A tiny random change to the couplings rearranges the ground state in large, fractal-shaped clusters of spins. Nobody has turned this fact into a quantitative account of what an optimizer loses when it trusts the simulated instance.

This proposal makes that connection and tests it. The main question is not whether the solution changes, because disorder chaos guarantees it will. The question is how much objective value is lost, and whether a scaling law from spin-glass theory predicts that loss before deployment. If it does, the same law yields two practical results. The first is a noise floor below which differences between benchmarked solvers are meaningless. The second is a principled way to stop annealing early, at a temperature matched to measurement error, so the solver returns solutions that hedge against the error.

Core Claim

Disorder chaos in spin glasses shows that perturbing couplings by relative strength $\Delta J$ defines a chaos length $\ell_c \propto \Delta J^{-1/\xi}$. The measured exponents are about 1.0 in 2D, 1.3 in 3D and 0.5 in mean-field. Beyond $\ell_c$, the old and new ground states are essentially unrelated. That paper measures configuration overlap, not cost.

We make a claim about cost, using a standard droplet-picture argument. Take a system of $N$ spins in dimension $d$. Suppose the nominal ground state is wrong on roughly independent clusters of linear size $\ell_c$. Each such cluster costs of order $\ell_c^{\theta}$ in energy, where $\theta$ is the stiffness exponent that sets how excitation energy grows with cluster size. The excess energy per spin of the nominal solution, evaluated on the true couplings, should then scale as

$$ r(\Delta J) \;=\; \frac{H_{\text{true}}(\sigma_{\text{nom}}) - H_{\text{true}}(\sigma^*_{\text{true}})}{N} \;\propto\; \ell_c^{\,\theta-d} \;\propto\; \Delta J^{(d-\theta)/\xi}. $$

Here $\sigma_{\text{nom}}$ is the ground state of the simulated instance, $\sigma^*_{\text{true}}$ is the ground state of the perturbed instance, and $H_{\text{true}}$ is the energy under the perturbed couplings. The file does not report values of $\theta$, so we will estimate it on the same instances rather than import it.

The claim is falsifiable in three ways. First, per-spin regret should follow a power law in $\Delta J$ whose exponent is predicted from independently measured $\xi$ and $\theta$. Second, the configuration overlap can fall toward zero while the regret stays small, because the energy landscape is highly degenerate. A Spin-Glass Model for Semi-Supervised Community Detection identifies exactly this degeneracy for modularity: exponentially many different partitions reach nearly the same energy. Third, stopping the annealing at a finite temperature $T^*$ should lower true regret. At that temperature the thermal fluctuations are comparable to the droplet energy at scale $\ell_c$, so the returned configuration averages over clusters the measurement noise cannot resolve anyway.

Research Program

The first part is measurement. We take instances where the ground state can be computed or tightly bracketed: 2D and 3D Edwards-Anderson lattices (grids of spins with random couplings, the setting used in the chaos paper) and Gset graphs, which are sparse random graphs and should behave like the mean-field case. For each instance we draw many perturbed coupling sets at several values of $\Delta J$ and record overlap and regret. We also record the gap between the best and worst of a panel of solvers. The panel covers simulated annealing, the spiking-neuron annealer NeuroSA from ON-OFF neuromorphic ISING machines using Fowler-Nordheim annealers run in its emulated form, and the relax-optimize-sample graph neural network ROS from ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems. The goal is to test whether $\xi$ and $\theta$, fitted on held-out instances, predict the regret curve on new ones.

The second part turns the prediction into an evaluation rule. For a given uncertainty $\Delta J$, the predicted $r(\Delta J)$ is a noise floor. Two solvers whose nominal energies differ by less than this floor cannot be ranked for deployment. We test this by checking whether solver rankings on clean Gset survive perturbation whenever their nominal gaps sit below the floor.

The third part is the remedy. We choose the stopping temperature $T^*$ from the predicted droplet energy at $\ell_c$, and we return a configuration obtained by majority vote over samples drawn at $T^*$. For ROS, the matching move is to stop sharpening its continuous probability relaxation at a matching entropy. Its expectation-consistency result, which says the expected cost of sampled discrete cuts equals the continuous objective, makes this finite-entropy hedge well defined.

Both NeuroSA and ROS supply methods here, not motivation. Both were validated only on static instances, and both would inherit any coupling-chaos penalty. The distributed Glauber-dynamics work in Simulation-based Distributed Coordination Maximization over Networks motivates a later extension to stale neighbor states, but that is out of scope here.

Baselines

The naive reference point is to trust the simulator. We take the best-known nominal solution for each instance and score it on the true couplings. This is how every Gset result in the file is reported. NeuroSA reports solution distributions "within 99%" of the best known Gset cuts, and ROS reports matching or beating ANYCSP and BQP while running about 15 times faster than Mirror Descent at 10,000 nodes. Neither paper reports a result under perturbed couplings, and we found no reported result on Lacuna for any Ising solver's true-instance regret under coupling noise. The naive baseline is therefore computed by us with those solvers.

The strongest competitor is sample-average robust optimization. It draws $K$ perturbed coupling sets from the assumed noise model and solves the averaged instance. Equivalently, it scores candidate solutions by their mean energy across the draws. It is a strong competitor because it attacks the same problem directly, with no physics theory required. For fairness it gets the same noise model, the same annealer, and the same total number of spin updates as our temperature-matched method. Its $K$ and schedule are tuned with the same budget of validation instances that we use to fit $\xi$ and $\theta$.

The oracle upper bound re-solves on the true couplings. This is unavailable in deployment, but it anchors the regret at zero.

The ablation that isolates the key ingredient keeps our finite-temperature majority-vote procedure but sets $T^*$ in one of two other ways: by grid search on validation instances, or by a fixed fraction of the initial temperature. Beating the naive baseline requires a statistically significant reduction in true regret at matched compute. Beating sample-average optimization requires equal or lower regret at lower compute, or lower regret at equal compute. If we only match it, the contribution narrows to the predictive law and the evaluation floor, and we will report it that way.

Why not just…?

Why not just re-solve on fresh measurements at deployment? When fresh couplings can be measured and the solve fits in time, re-solving wins, and the oracle baseline says so. The problem is that measurements stay noisy at deployment. The chaos result says that a re-solved ground state of a still-noisy instance carries the same scale of error. Re-solving moves the gap without closing it. The measurement experiment quantifies this directly.

Why not just use sample-average robust optimization and skip the physics? This is the real threat, and it may match the remedy on regret. Our answer is that it cannot tell you ahead of time how much is lost, or which benchmark differences are meaningless. The scaling law does that without solving the perturbed instances at all. The head-to-head comparison at matched spin-update budgets settles whether the temperature rule adds anything beyond the diagnostic.

Why not just take the consensus of many independent annealing runs at zero temperature? Consensus over near-ground states hedges against degeneracy, but not against coupling error. Every run sees the same wrong couplings, so all of them agree on the same wrong clusters. The ablation with $T^*$ set to zero and $K$ repeated runs tests exactly this. If it matches $T^*$, the temperature-matching idea is refuted.

Proposed Experiments and Decisive Checks

The first experiment tests the scaling law. On 2D lattices up to $L=60$ and 3D lattices up to $L=10$, matching the sizes solved in the chaos paper, and on Gset graphs, we fit $\xi$ from overlap decay and $\theta$ from the energies of forced excitations on half the instances. We then predict the regret exponent $(d-\theta)/\xi$ on the other half. The check is decisive: if the measured and predicted exponents disagree beyond bootstrap error in all three geometries, the core claim fails. If they agree, the overlap-versus-regret decoupling should also appear, with overlap near zero while per-spin regret stays well below $\Delta J$.

The second experiment tests the evaluation rule. We compute Kendall rank correlation between solver rankings on clean and perturbed Gset, stratified by whether nominal gaps fall above or below the predicted floor. The prediction is that rank correlation stays high above the floor and falls to chance below it.

The third experiment compares remedies. Our temperature-matched method, sample-average optimization, zero-temperature consensus, the naive baseline and the oracle are compared on true-instance regret at matched compute.

The fourth experiment is the real-world check. A pristine simulator cannot supply real, non-Gaussian coupling error, so we use the Bitcoin-OTC signed trust network that ROS partitions. If its rating timestamps permit, we build the nominal instance from earlier ratings and treat later ratings as the realized couplings. The Karate Club and Dolphin networks from Eaton and Mansbach serve as small cases where exact solutions are available.

This is where the theory is most likely to break. Real rating drift is correlated and bursty, not independent, and the file notes that Eaton and Mansbach's noise was synthetic and uniform. We will report whether an effective $\Delta J$, fitted from the empirical drift, still predicts regret. A failure here would itself be informative: it would show that independent-noise chaos theory understates the reality gap for structured drift.