Measuring the Overlap Gap at Finite Size: A Stability Test for Learned Combinatorial Solvers

Theory says that for many random optimization problems, such as finding a large independent set in a random graph, good solutions are scattered in isolated islands. Any "stable" algorithm, meaning one whose output changes only a little when the input graph changes a little, cannot jump between those islands, so it is stuck at a performance ceiling. This geometric fact is called the Overlap Gap Property (OGP): two near-optimal solutions are either very similar or nearly unrelated, and there is a forbidden middle range of similarity. It has been used to argue that graph neural networks (GNNs) cannot beat simple greedy rules on these problems. Every such argument is asymptotic, though. It assumes graphs of infinite size and, often, infinite degree. Nobody has measured whether the islands exist at the sizes people actually run, whether learned solvers are in fact stable, or whether the solvers that do better than greedy are exactly the unstable ones.

We propose to turn the proof device behind OGP into a measurement. OGP proofs interpolate between two correlated random instances and track how an algorithm's output drifts along the way. We will run that interpolation numerically on graphs with 10^2 to 10^5 nodes and degree 3 to 50. For each solver we will record two things: how far its output moves per unit of input change, and whether its high-quality outputs ever cross the forbidden overlap band. The claim to be tested is concrete. At finite size, a solver's measured stability should predict its performance ceiling better than its architecture or parameter count does. Interventions that break stability should raise the ceiling, and interventions that only add capacity should not.

Core Claim

Barriers for the performance of graph neural networks (GNN) in discrete random structures proves several results. An $R$-layer GNN is an $R$-local algorithm, meaning each node's output depends only on its $R$-hop neighborhood. Such algorithms hit a 1/2-optimality wall for maximum independent set on random $d$-regular graphs as $d \to \infty$, and they are capped below message passing for hypergraph MaxCut. The same paper flags fixed small $d$ and finite $n$ as open, and it reports no experiments. The broader stability results in Low-Degree Hardness of Random Optimization Problems and Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics supply the mechanism we reuse. Stable algorithms cannot cross an empty overlap band.

Our claim is that this mechanism can be checked directly, at finite size, by measuring stability and overlap trajectories. We call this the jump test. If the theory's mechanism is operative at practical scales, we expect the following. Solvers that exceed the greedy reference on random $d$-regular graphs should show large discontinuous jumps in output overlap along the interpolation path. Solvers below that reference should drift smoothly. The boundary should sharpen as $d$ grows. If instead learned solvers beat greedy while remaining measurably stable, then the asymptotic barrier says little about practice at those sizes. That would also be a useful, publishable outcome.

Research Program

The core object is an interpolation path between two random instances. Start from a random $d$-regular graph $G_0$. Produce $G_t$ by applying degree-preserving edge switches to a fraction $t \in [0,1]$ of edges, so that $G_1$ is an independent sample. For an algorithm $A$ that returns a vertex set, we measure the overlap trajectory

$$ q_A(t) = \frac{|A(G_0) \cap A(G_t)|}{|A(G_0)|}, $$

which runs from 1 at $t=0$ to roughly the overlap of two independent outputs at $t=1$. We summarize stability by the largest overlap drop caused by a single edge switch, $J_A = \max_t |q_A(t) - q_A(t + 1/m)|$, where $m$ is the number of edges. A stable algorithm has $J_A$ near zero.

In parallel, we estimate the solution geometry itself. We collect many near-optimal independent sets per graph, using reduction-based exact search on small $n$ and long Tabu runs on larger $n$. We then histogram their pairwise overlaps to see whether a forbidden band appears, and at which $(n, d)$. Combining the two gives the jump test. It asks whether a solver's high-value outputs have trajectories that skip over the empirically empty band. If they do, the solver is evading the barrier the way the theory says only unstable algorithms can.

The interdisciplinary step is deliberately narrow. We do not borrow an analogy from statistical physics. We transplant one specific operation, the correlated-instance interpolation, into the evaluation pipeline. This answers the "why does the mechanism transfer" gap that Read, Grep, and Synthesize: Diagnosing Cross-Domain Seed Exposure for LLM Research Ideation identified. That paper found that targeted cross-domain retrieval tied with random seeds (47% win rate) and that borrowed mechanisms were often abandoned in the final method. Here the borrowed mechanism is the measurement itself, so it cannot be dropped later.

Two further studies sharpen the interpretation. The first is a negative control based on Some easy optimization problems have the overlap-gap property. That paper proves that shortest path on sparse $G(n,q)$ with $q=\Theta(\log n)$ has OGP, yet is solved by degree-$O(\log n)$ polynomial estimators with good, not ultra-high, success probability. It contains no experiments. We will implement low-degree and message-passing estimators for that problem and measure their overlap histograms, $J_A$, and per-instance success rates. This tells us whether an empirical overlap gap alone over-predicts hardness, which the theory says it should. In that case, success-probability profiles, not just averages, must be part of the diagnostic.

The second study revisits the "Zero-Trap" reported in Binarizing Physics-Inspired GNNs for Combinatorial Optimization. There, continuous physics-inspired GNNs (GNNs trained without labels to minimize a relaxed quadratic binary objective) collapse to all-zero outputs at $d \ge 20$. The paper's remedies are temperature annealing, straight-through hard binarization, and a fuzzy-logic relaxation. We do not presume the collapse is OGP-related. The all-zero point is plausibly just a degenerate fixed point of the relaxed loss. We test this by measuring $J_A$ for each remedy and asking whether recovered performance tracks lost stability.

Baselines

The naive reference point is minimum-degree greedy for independent set and random-assignment-plus-greedy-flips for MaxCut. Per Barriers for the performance of graph neural networks (GNN) in discrete random structures, greedy already reaches the asymptotic local-algorithm ceiling, so any learned solver must beat it at matched $(n,d)$ to be interesting. We run it on every instance, with no tuning.

The strongest classical competitor is Tabu Search. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization reports that it "consistently achieved approximation ratios near 1.0" on MaxCut, frequently beating S2V-DQN and ECO-DQN. The same paper's SoftTabu ablation, a linear model over two features ("Marginal Gain" and "Time Since Flip"), matched ECO-DQN. It is therefore the right test of whether a GNN contributes anything beyond flip bookkeeping. Tabu Search and SoftTabu are both included. Each gets the same wall-clock budget per instance as the learned solvers, and its tenure parameter is tuned on held-out graphs from the same generator with the same tuning budget we give learned models.

The strongest learned competitors for independent set are two hybrid methods. The first is GCN with guided tree search from Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search, which solved 62.5% of BUAA-MC instances versus 25% for ReduMIS. The second is DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization, a discrete diffusion solver that reports a 0.21% optimality gap on SATLIB independent set against 0.63% for the previous neural solver. These are the strongest competitors precisely because tree search and stochastic denoising look unstable by design. Our theory predicts they should be the ones that pass the jump test.

For physics-inspired GNNs, we use the binarized variant. It reports a MaxCut cut value of 9699.70 at $N=1000$, $d=50$, where the continuous baseline scores 0.00 (Binarizing Physics-Inspired GNNs for Combinatorial Optimization). For random $d$-regular independent set density specifically, we found no reported result on Lacuna; that paper reports the fuzzy variant's advantage only qualitatively. All learned models are trained on the same generator with the same GPU budget and evaluated on identical seeds.

The key ablation isolates stability rather than architecture. We take one fixed GNN backbone and toggle exactly one ingredient at a time: deterministic thresholding versus stochastic rounding, tree search off versus on, and depth $R$ swept from 2 to beyond $\log n$. Capacity is held fixed throughout. Beating the baselines in our sense has two parts. A solver must exceed greedy's independent set density at fixed $(n,d)$ by a margin larger than the across-seed spread. And that margin must be explained by $J_A$ (high rank correlation across solvers and ablations) better than it is explained by parameter count or depth.

Why not just…?

Why not just run another leaderboard of GNNs versus greedy? That comparison exists. Angelini and Ricci-Tersenghi found greedy beats physics-inspired GNNs, as discussed in Barriers for the performance of graph neural networks (GNN) in discrete random structures. Leaderboards tell you who wins but not why. A tuned solver could lose for optimization reasons unrelated to OGP. Our stability ablation separates "fails because it is stable" from "fails because it is badly trained." A leaderboard cannot make that distinction.

Why not just use Tabu Search and call the problem solved? For random MaxCut at the sizes in MaxCut-Bench, Tabu may well be near-optimal, and we expect it to be the hardest baseline. But Tabu is itself an interesting case. It is a local method that reaches near-optimal values. If OGP holds at those sizes, its trajectories must show jumps, which its memory-driven escape moves could provide. Measuring Tabu's $J_A$ is part of the study, not a distraction from it. If Tabu turns out smooth and near-optimal, that is direct evidence that the finite-size overlap gap is absent, which itself settles the theory's practical reach.

Why not just explain the Zero-Trap as a loss-scaling artifact? This is a real threat, and it may well be correct. Temperature annealing changes the optimization schedule without obviously destabilizing the final map. So if annealing recovers performance as fully as hard binarization, with low $J_A$, then the collapse is an optimization artifact and not an OGP effect. We will report that outcome as such.

Why not just bound the network's Lipschitz constant analytically? Analytic bounds on deep networks are loose, and they ignore the rounding and search steps where instability actually enters. The edge-switch interpolation matches the definition used in the hardness proofs. It also applies identically to neural, classical, and hybrid solvers.

Proposed Experiments

We will use the $d$-regular generator from Binarizing Physics-Inspired GNNs for Combinatorial Optimization at $N \in \{10^2, 10^3, 10^4\}$ and $d \in \{3,5,10,20,50\}$, extended to $10^5$ for greedy and Tabu. MaxCut-Bench instances (Erdős–Rényi, Sherrington–Kirkpatrick spin glasses, GSet) from A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization serve as the MaxCut arm. Shortest path on $G(n,q)$ is the easy-OGP control. SATLIB independent set is a structured transfer check against DIFUSCO's reported number.

The metrics are four. We report independent set density or cut value relative to the best found. We report the stability statistic $J_A$ and the full trajectory $q_A(t)$. We report pairwise-overlap histograms of near-optimal solutions. And we report per-instance success rates, since Some easy optimization problems have the overlap-gap property shows that moderate success can coexist with OGP.

Three outcomes are decisive. The first is whether a forbidden overlap band is visible at finite size, and its width as a function of $(n,d)$. This directly addresses the open finite-$d$ question. The second is whether, across all solvers and ablations, exceeding greedy is accompanied by large $J_A$ and band-crossing trajectories. A stable solver that beats greedy with a clear margin at $d \ge 20$ would falsify the claim that the barrier is operative at those sizes. The third is whether the shortest-path control shows a band yet admits stable estimators with good success rates. That outcome would confirm that the overlap histogram alone is an insufficient hardness signal and that the jump test must be paired with success-probability profiles.