DEV Community: Dimitar Kretski

Can AI tell whether an optimum is unique? A small Kaggle benchmark with exact answers

Dimitar Kretski — Sat, 10 Oct 2026 09:58:51 +0000

This is a submission for the Kaggle Benchmarking Challenge

What I Benchmarked

When a solver or an AI model returns "the optimal solution", it rarely says whether it is the only one. That matters: if many equally good solutions exist, a small change in the data can silently move you to a very different "optimal" answer. I wanted to know whether language models notice this, so the benchmark asks one question: can a model tell whether an optimum is unique, and if it is not, how many optimal solutions there are?

How it works:

87 small optimization problems of five kinds: subset selection, QUBO, assignment, knapsack and a toy portfolio selection (16 to 20 binary variables; assignment 8x8 or 9x9).
Each problem is small enough to enumerate exhaustively, so the ground truth is exact: the optimal value and the exact number of optimal solutions. The model is never told the count.
Instances are balanced by number of optima: 1, 2, 3 to 5, 6 to 10, 11 to 50 and more than 50 (the toy portfolio family has no instance above 50).
The model answers in free text and ends with one JSON line: solution, objective, unique, number of optima. The scorer recomputes the objective of the returned solution instead of trusting the model's number.
Three things are scored: is the solution optimal, is the unique / not-unique claim right, and is the count exactly right.

The Kaggle task uniqueness_of_optimum uses a fixed board of 29 instances (one per problem type and count bin). An answer scores 1 only if all three checks pass, and the leaderboard value is the share of the 29 answers that score 1.

Models Tested

On the Kaggle leaderboard: Gemini 3.7 Flash and gpt-oss-120b, one run each on the 29-instance board.
Outside the leaderboard, with the same generator and scorer: Gemini 3.7 Flash on all 87 instances with two prompts (plain, and one that asks the model to look explicitly for other solutions), and GPT-6.1-sol on the 10 instances that Flash found hardest.

I picked them by availability, budget and contrast: a fast general model, a small open-weight model, and a stronger model on the hardest cases. This is a small lineup, not a ranking of the field.

Findings

Leaderboard. Gemini 3.7 Flash scored 0.90 (26 of 29) and gpt-oss-120b scored 0.55 (16 of 29). With 29 instances and one run each the uncertainty is large (roughly plus or minus 0.06 and 0.09), but the gap is bigger than that noise (Fisher exact test, p = 0.007).
Counting is harder than noticing. In the full run on 87 instances, Gemini 3.7 Flash got the exact number of optima right in 70% of answers with the plain prompt and 75% with the explicit prompt. Accuracy fell as the number of optima grew: with the plain prompt it was 100% when the optimum was unique and 42% with more than 50 optima.
When the count is wrong, it is usually too low. 43 of the 48 wrong counts were below the truth. At the level of instances, 25 had a net undercount and 1 a net overcount. Examples: 15 instead of 72, 9 instead of 65, 298 instead of 2,411. The model reports something like a lower bound as if it were the exact number.
A stronger model did much better on the hard cases. On the 10 instances where Flash failed (0 of 10 exact counts with the plain prompt, 1 of 10 with the explicit prompt), GPT-6.1-sol was exact on all 10, including 2,411 optimal permutations. I do not know whether it reasoned internally or used tools. The benchmark measures the answer, not the method.
Asking the model to check explicitly did not clearly help. The explicit prompt was better on 8 instances and worse on 4, which is within noise (exact McNemar test, p = 0.39).
Answers are not repeatable. In a small repeat test (15 tasks, same prompts, two runs) the claimed count differed between runs in 8 of 30 cases. The same 29 leaderboard instances gave exact counts in 22 of 29 in my earlier Flash run, against 26 of 29 fully correct answers on the leaderboard, so run-to-run variation is substantial and I treat these as separate measurements.
What surprised me. I expected models to claim uniqueness too often. In the runs where I kept the full answers, calling a non-unique optimum unique was rare (0 cases in the two pilot runs, 1 of 10 on the hardest instances for Flash). The failure is quieter: a plausible lower bound presented as an exact count.

What I would measure next: several runs per instance with intervals, thinking versus non-thinking versions of the same model, tool access, a count metric that tolerates scale (for example within a factor of two), and real-world problem sizes.

Limits. The benchmark is small and most models have one run. The raw logs of my first full Flash run were lost when the notebook session restarted, so I reconstructed its instance-level counts and errors from the deterministic generator and the printed error list, and I only report count-based results from it. The 10 "hard" instances were picked because Flash failed on them, so GPT-6.1-sol's 10 of 10 says nothing about instances that are hard for GPT-6.1-sol. Exact count is a strict metric when there are thousands of optima. The toy portfolio problem uses small integer data. Instances with more optima are also harder to count, so I do not claim that any single property of the problem causes the errors.

My Benchmark

Benchmark: https://www.kaggle.com/benchmarks/dimitarkretski/uniqueness-of-optimum
Task: https://www.kaggle.com/benchmarks/tasks/dimitarkretski/uniqueness-of-optimum
Dataset with instances and ground truth: https://www.kaggle.com/datasets/dimitarkretski/uniqueness-bench-large
Notebook with the generator and scoring code: https://www.kaggle.com/code/dimitarkretski/new-benchmark-task-97935

The question came out of my work on near-optimal solution degeneracy in QUBO problems, but this benchmark does not use or validate that work.
I used an AI assistant for code, analysis and drafting. The numbers come from the raw result files and from the Kaggle leaderboard.

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

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

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

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