Update (10 Oct 2026): corrections to this post. Some claims below were stronger than what I can support, so here is what I changed in my own understanding.
- Portfolio example. The figures (1,998 near-optimal portfolios, no asset above 44%) came from a run whose script I did not preserve, so I cannot verify them. I rebuilt the experiment on real daily prices (20 large caps, K = 5, exhaustive C(20,5)). It reproduces the direction (higher risk aversion gives a larger and more diverse near-optimal set) but not the numbers: at lambda = 8 I get 684 portfolios and a maximum single-asset share of 67%. These values depend on the assets, the period and the band used for "near-optimal".
- MAX-CUT numbers. The simulated-annealing search reaches 96 to 99% of the best-known cuts (not 97 to 99%). The Entry-to-x* overlap across seven MQLib instances ranged from 0.08 to 0.125 (I could not reproduce the lower value of 0.06). x* is the best solution of a heavy search, not a proven optimum.
- Penalty check. Only one part is rigorous: if the penalty exceeds the largest total coefficient magnitude touching a variable, every single-flip local minimum satisfies the one-hot constraints. The ~1.25x figure is empirical, from one small synthetic family, and depends on coupling density (about 2.1x with ~12 couplings per variable). The 0% deviation across scales shows scale invariance, not that 1.25 is a general constant.
- Correlation check. The 1/sqrt(1 - rho) scaling is derived for equicorrelated, equal-variance assets with continuous weights and a fixed absolute tolerance. In my synthetic sweep the fitted exponent was about -0.83 rather than -0.5 (one possible reason is the tolerance definition, untested), and R^2 = 0.94 measures the quality of the fit, not agreement with -0.5. It has not been validated on real portfolios.
- Null baseline. As Ahmet pointed out in the comments, for K-of-N selection the baseline must preserve the constraint: for N = 20, K = 5 the mean overlap of random K-subsets is about 0.25, versus about 0.18 for unconstrained random spins. The LOW / INTERMEDIATE / HIGH labels are being recalibrated.
- Demo and licence. The numbers you type into the demo are processed on the Space server (no account or file upload needed). The auditor itself is not open source; the demo is CC BY-NC-ND. The concept note linked below is v1.1; the two pre-solve checks are in the newer version https://doi.org/10.5281/zenodo.22738805 A follow-up measurement in a different setting (whether language models can tell if an optimum is unique): https://dev.to/dimitar_kretski_329e6235e/can-ai-tell-whether-an-optimum-is-unique-a-small-kaggle-benchmark-with-exact-answers-5e27Your 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 (7)
"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.
I should qualify my earlier wording: I do not have a documented domain-specific case to substantiate that experience claim here. The restart-distance check is a diagnostic suggestion, not evidence of degeneracy by itself.
Your null calibration is the missing comparison. I would want the null to preserve the relevant constraints and problem size, since distant feasible solutions can be ordinary in a large search space. Comparing objective-matched solutions against that baseline would make the structural-distance result much easier to interpret than a raw distance alone.
Thanks for the clarification, and you're right about the null. For MAX-CUT and spin-glass instances every configuration is feasible, so an unconstrained random null is appropriate there. For K-of-N selection it is not: for N=20, K=5 random K-subsets give a mean overlap of about 0.25, versus about 0.18 for unconstrained random spins, so the built-in null underestimated the baseline. I rebuilt the portfolio experiment against a constraint-preserving null and the trend with risk aversion holds, but the absolute class thresholds do not carry over, and I'm recalibrating them.
Thanks for rerunning it against a constraint-preserving null. Keeping the trend while changing the absolute thresholds is exactly why the baseline needs to be visible beside the result. Otherwise the labels would look stable even though their interpretation changed.
For the recalibration, I would show the empirical null distribution and uncertainty around each boundary, rather than only its mean overlap. Holding out some feasible samples for the final comparison could also help separate a threshold fitted to this portfolio instance from one that transfers across different N and K settings.
Agreed on both points. I'll replace the fixed z cutoffs with quantiles of the empirical null (random K-subsets matched on N, K and near-optimal set size) and report bootstrap intervals around each boundary, since the null spread depends strongly on set size. For the hold-out, I plan to calibrate the boundaries on some (N, K) settings and test them on others, to see whether they transfer. I haven't run that yet. I'll post what I find, including if the boundaries turn out not to transfer.
Holding out entire N and K settings is a good test of whether those boundaries travel beyond the calibration regime. I would keep the near-optimal tolerance explicit too, since changing it changes the set being compared even when N and K remain fixed.
If transfer fails, reporting the empirical percentile within each matched null would still give an interpretable result without forcing universal labels. The bootstrap interval could then communicate uncertainty in that percentile rather than implying the same label boundary applies to every problem size.