Your Optimizer Found a Good Answer. Is It the Only One?
If you've ever used simulated annealing, QAOA, or a D-Wave solver to tackle a QUBO or Ising problem — portfolio selection, routing, scheduling, resource allocation — you've probably checked one thing at the end: how good is the answer?
Here's a question almost nobody checks: is that answer the only good one, or is it one of many equally-good configurations your solver happened to land on?
This isn't a philosophical distinction. It has a concrete failure mode attached to it.
The problem energy histograms can't see
Say your solver returns a portfolio allocation with 98% of the best-known objective value. Great — but that number tells you nothing about whether nine other, structurally completely different allocations would have scored just as well.
If they would have, your "optimal" answer is fragile. A small change tomorrow — an updated price, a shifted correlation, one different input — can flip the solver to a totally different "best" answer, and nobody will know why. It'll just look like the recommendation changed for no reason.
Energy histograms — the standard tool everyone already uses — report the distribution of objective values. They say nothing about whether the near-optimal solutions are structurally similar or structurally unrelated. Two samples can have nearly identical energy and be almost orthogonal as bit configurations.
A concrete example
Take a cardinality-constrained portfolio problem: 20 assets, pick 5, exhaustively enumerate all C(20,5) = 15,504 combinations (small enough to brute-force, so the ground truth is exact, not estimated).
At low risk-aversion (λ=0.5), the picture is what you'd hope for: one asset appears in 100% of near-optimal portfolios. The solver's answer is essentially unique.
At higher risk-aversion (λ=8.0), the picture flips: 1,998 structurally distinct portfolios land within a tight band of the best objective value, and no single asset appears in more than 44% of them. Same problem class, same solver — completely different reliability profile, invisible if you only look at the objective value.
Two numbers instead of one
The diagnostic I've been building (AZURO Landscape Auditor) reports two solver-agnostic quantities instead of just objective quality:
P(q) — pairwise overlap between independently-obtained near-optimal configurations. High overlap means the near-optimal region is a single sharp basin (reliable). Low overlap means it's fragmented across structurally different solutions (fragile), even when every one of them scores well.
Entry→x* gap — compares how self-consistent the solver is (does it agree with itself across runs?) against how close it actually sits to the reference optimum. These two numbers can diverge dramatically: across Gset/MQLib benchmarks, solvers hit 97–99% of the best-known cut while Entry→x* overlap sits at just 0.06–0.13 — the near-optimal configurations are nearly orthogonal to the reference solution despite excellent energy proximity. A solver monitoring only self-consistency would call this reliable. It isn't.
Catching it before you even solve
The more useful version of this question is: can you flag the risk before spending compute on a solve? Two mechanisms turned out to have closed-form, pre-solve answers:
Penalty calibration. For constraints encoded as QUBO penalty terms (one-hot, cardinality, etc.), there's a scale-invariant minimum penalty ratio: P* ≈ 1.25 × max coefficient magnitude in your objective. Validated across a 3× change in coefficient scale with 0% relative deviation — below this threshold, feasibility drops sharply; above it, it's reliable. Computable in milliseconds, no solve required.
Correlated-input degeneracy. For a cluster of correlated inputs (assets, resources, whatever your variables represent), the near-optimal spread grows as ~1/√(1−ρ) as pairwise correlation ρ→1 — derived directly from the risk Hessian's curvature, confirmed numerically (R²=0.94) against the theoretical exponent. The more correlated your inputs, the more arbitrary the "optimal" split between them becomes.
Worth saying plainly: a third candidate mechanism — whether topological/structural symmetry in the problem graph predicts degeneracy — was tested across three independent designs (degree-variance regression, degree-preserving edge rewiring, spectral analysis) and found not supported. It's reported anyway, because a diagnostic tool that only publishes the mechanisms that worked isn't one you should trust.
Try it yourself
Both pre-solve checks are live as a small interactive demo — no data upload needed, runs on numbers you enter directly:
🔗 huggingface.co/spaces/Kretski/azuro-landscape-auditor
Full methodology, validation data, and the closed-form derivations:
📄 DOI 10.5281/zenodo.21941962
Code for the demo app: github.com/Kretski/azuro-landscape-auditor
Curious whether this shows up in problems you're solving — happy to compare notes if you run it against something of your ow
Top comments (2)
"Is it the only one" is a better question than "how good is it" and the degeneracy framing generalises well past QUBO. Any solver that returns a single argmax hides whether the objective had one peak or a plateau, and a plateau means your answer is an artifact of the seed rather than a property of the problem.
The practical consequence you name — a structurally different allocation scoring the same — is exactly why reporting only the best objective value is misleading to whoever consumes the result downstream.
The cheapest diagnostic I have used elsewhere is restarting from several seeds and measuring the distance between the returned solutions rather than between their scores. Similar scores with distant configurations is the signature, and an energy histogram cannot show it because distance is the axis it does not have.
Thanks — that's a precise way to put it, and the restart-and-measure-distance-between-configs approach is a great low-overhead first pass. Where it can mislead is scale: raw distance between configurations doesn't tell you whether that gap is large relative to the null (i.e. would two solves on genuinely different problem instances land just as far apart by chance?) — that's the piece P(q) calibrates against a Monte Carlo null specifically. For a quick sanity check your method is exactly right though; I'd reach for the calibrated version only once the cheap check flags something worth taking seriously.
Curious what domain you've used it in — energy landscape shape shows up in some surprising places outside combinatorial optimization.