Your Optimizer Found a Good Answer — Is It the Only One?

Dimitar Kretski — Mon, 21 Sep 2026 04:51:28 +0000

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

ScalePredict update: 291 views, 29 testers this week. Predict cloud runtime in 2 min link + feedback!".

Dimitar Kretski — Sat, 14 Mar 2026 08:03:14 +0000

Share your benchmark + real run kretski1@gmail.com,https://github.com/Kretski/ScalePredict
@vast_ai

DEV Community: Dimitar Kretski

Your Optimizer Found a Good Answer — Is It the Only One?

ScalePredict update: 291 views, 29 testers this week. Predict cloud runtime in 2 min link + feedback!".