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

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

1. 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).
2. 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.
3. 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.
4. 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.
5. 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).
6. 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.
7. 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.