AI가 최적해가 유일한지 판단할 수 있을까? 정확한 답을 요구하는 소규모 Kaggle 벤치마크

이 글은 Kaggle Benchmarking Challenge에 제출하는 내용입니다.

내가 벤치마킹한 내용

솔버(solver)나 AI 모델이 "최적의 해답(optimal solution)"을 반환할 때, 그것이 유일한 해답인지 여부를 알려주는 경우는 드뭅니다. 이 점이 중요합니다. 만약 여러 개의 동등하게 좋은 해답들이 존재한다면, 데이터에 작은 변화만으로도 매우 다른 "최적" 답변으로 이동할 수 있습니다. 저는 언어 모델(language models)이 이러한 차이를 감지하는지 알고 싶었기 때문에, 이 벤치마크는 하나의 질문을 던집니다. 모델이 최적이 유일한지 여부를 판단할 수 있으며, 그렇지 않다면 몇 개의 최적 해답이 존재하는지를 알 수 있는가?

작동 방식:

• 다섯 가지 종류의 87개 소규모 최적화 문제로 구성되어 있습니다: 부분집합 선택(subset selection), QUBO, 할당(assignment), 배낭(knapsack) 및 장난감 포트폴리오 선택(toy portfolio selection). (변수는 16~20개의 이진 변수; 할당은 8x8 또는 9x9.)
• 각 문제는 모두 완전 열거(enumerate exhaustively)할 수 있을 만큼 작기 때문에, 정답(ground truth)은 정확합니다. 즉, 최적 값과 최적 해답의 정확한 개수를 알고 있습니다. 모델에게는 이 개수가 절대 알려지지 않습니다.
• 인스턴스는 최적해의 개수별로 균형을 이루고 있습니다: 1개, 2개, 3개부터 5개, 6개부터 10개, 11개부터 50개, 그리고 50개가 넘는 경우(장난감 포트폴리오 계열은 50개를 초과하는 인스턴스가 없습니다).
• 모델은 자유 형식의 텍스트로 답변하며 마지막에 하나의 JSON 라인을 붙입니다: solution, objective, unique, number of optima. 채점자는 모델이 제시한 개수를 신뢰하는 대신 반환된 해답의 목적 함수(objective)를 재계산합니다.
• 세 가지 항목을 점수화합니다: 해답이 최적인지 여부, 유일성/비유일성 주장이 맞는지 여부, 그리고 개수가 정확한지 여부입니다.

Kaggle 과제인 uniqueness_of_optimum은 29개의 고정된 인스턴트(문제 유형 및 개수 구간별로 하나씩)를 사용합니다. 모든 세 가지 검사 항목이 통과할 경우에만 점수가 1점을 받으며, 리더보드 값은 29개 답변 중 1점을 받은 비율입니다.

테스트한 모델

• Kaggle 리더보드에서: Gemini 3.7 Flash와 gpt-oss-120b가 각각 29개 인스턴스 보드에 대해 한 번씩 실행되었습니다.
• 리더보드 외부에서는 동일한 생성기 및 채점기를 사용하여, Gemini 3.7 Flash는 모든 87개 인스턴스에 대해 두 가지 프롬프트(일반적인 프롬프트와 모델에게 명시적으로 다른 해답을 찾도록 요청하는 프롬프트)로 테스트되었고, GPT-6.1-sol은 Flash가 가장 어렵다고 판단한 10개 인스턴스에서 테스트되었습니다.

저는 가용성, 예산, 대비를 고려하여 이 모델들을 선택했습니다: 빠르고 일반적인 모델, 작고 오픈 웨이트(open-weight) 모델, 그리고 가장 어려운 경우에 더 강력한 모델입니다. 이것은 전체 분야의 순위가 아니라 작은 라인업일 뿐입니다.

주요 발견 사항 (Findings)

1. 리더보드. Gemini 3.7 Flash는 0.90점(29개 중 26개)을 기록했고, gpt-oss-120b는 0.55점(29개 중 16개)을 기록했습니다. 29개 인스턴스와 각각 한 번의 실행만으로는 불확실성이 크지만 (대략 플러스 마이너스 0.06과 0.09), 그 차이는 이 노이즈보다 큽니다 (Fisher exact test, p = 0.007).
2. 개수를 세는 것이 알아차리는 것보다 어렵다. 87개 인스턴스 전체 실행에서 Gemini 3.7 Flash는 일반적인 프롬프트 사용 시 답변의 70%에서 정확한 최적해 개수를 얻었고, 명시적인 프롬프트 사용 시에는 75%였습니다. 최적해 개수가 늘어날수록 정확도는 떨어졌습니다: 일반적인 프롬프트 사용 시 최적해가 유일할 때는 100%였지만, 50개 이상의 최적해가 있을 때는 42%에 그쳤습니다.
3. 개수가 틀릴 때, 보통 너무 낮다. 잘못된 개수 48개 중 43개가 실제 값보다 적었습니다. 인스턴스 수준에서 보면, 25개는 순수하게 과소평가(undercount)되었고 1개는 순수하게 과대평가(overcount)되었습니다. 예시: 72개 대신 15개, 65개 대신 9개, 2,411개 대신 298개. 모델은 마치 그것이 정확한 개수인 것처럼 하한선(lower bound)과 같은 것을 보고합니다.
4. 더 강력한 모델이 어려운 경우에 훨씬 더 잘했다. Flash가 실패했던 10개 인스턴스에서 (일반적인 프롬프트 사용 시 10개 중 0개, 명시적인 프롬프트 사용 시 10개 중 1개 정확), GPT-6.1-sol은 2,411개의 최적 순열을 포함하여 모두 10개 인스턴스에서 정확했습니다. 제가 내부적으로 추론했는지 아니면 도구를 사용했는지는 알 수 없습니다. 이 벤치마크는 방법이 아니라 답변 자체를 측정합니다.

모델에게 명시적으로 확인하도록 요청하는 것은 분명히 도움이 되지 않았습니다. 명시적인 프롬프트가 8개 사례에서는 더 좋았고 4개 사례에서는 더 나빴는데, 이는 노이즈 범위 내에 있습니다 (정확한 McNemar test, p = 0.39).
6. 답변이 반복 가능하지 않습니다. 소규모 반복 테스트(15가지 과제, 동일 프롬프트, 두 번 실행)에서 주장된 개수가 30개 사례 중 8개 사례에서 실행별로 달랐습니다. 이전에 진행했던 Flash 실행에서는 동일한 29개의 리더보드 사례가 29개 중 22개에서 정확한 개수를 보여주었으며, 리더보드에서 완전히 올바른 답변은 29개 중 26개였습니다. 따라서 실행 간 변동성이 상당하며 저는 이를 별도의 측정치로 취급합니다.
7. 저를 놀라게 한 점. 모델들이 유일성을 주장하는 경우가 너무 많을 것이라고 예상했습니다. 제가 전체 답변을 유지했던 실행에서는 비유일 최적해를 유일하다고 부르는 경우가 드물었습니다 (두 파일럿 실행에서 0건, Flash의 가장 어려운 사례 10개 중 1건). 실패는 더 조용합니다: 정확한 개수로 제시된 그럴듯한 하한선입니다.

제가 다음에 측정할 것들: 간격을 두고 여러 번의 실행을 진행하는 것, 동일 모델의 사고 과정(thinking) 대 비사고 과정(non-thinking), 도구 접근성, 규모를 허용하는 카운트 지표(예를 들어 두 배 이내의 오차 범위), 그리고 실제 문제 크기입니다.

한계점. 벤치마크가 작고 대부분의 모델은 한 번만 실행됩니다. 첫 번째 전체 Flash 실행의 원본 로그는 노트북 세션이 재시작되면서 손실되었기 때문에, 저는 결정론적 생성기와 출력된 오류 목록으로부터 사례별 개수와 오류를 재구성했으며, 이로부터 얻은 카운트 기반 결과만을 보고합니다. 10개의 '어려운' 사례는 Flash가 실패했기 때문에 선택되었으므로, GPT-6.1-sol의 10개 중 10개라는 결과는 GPT-6.1-sol에게 어려운 사례에 대해서는 아무것도 말해주지 않습니다. 정확한 개수는 수천 개의 최적해가 있을 때 엄격한 지표입니다. 이 장난감 포트폴리오 문제는 작은 정수 데이터를 사용합니다. 더 많은 최적해를 가진 사례 역시 세기 어렵기 때문에, 저는 문제의 어떤 단일 속성이 오류의 원인이라고 주장하지 않습니다.

저의 벤치마크

• 벤치마크: [https://www.kaggle.com/benchmarks/dimitarkretski/uniqueness-of-optimum]
• 태스크: [https://www.kaggle.com/benchmarks/tasks/dimitarkretski/uniqueness-of-optimum]
• 인스턴스와 정답이 포함된 데이터셋: [https://www.kaggle.com/datasets/dimitarkretski/uniqueness-bench-large]
• 생성기 및 스코어링 코드가 포함된 노트북: [https://www.kaggle.com/code/dimitarkretski/new-benchmark-task-97935]

이 질문은 제가 QUBO 문제의 근사 최적해 퇴화(degeneracy)에 대해 수행한 작업에서 나왔지만, 이 벤치마크는 해당 작업을 사용하거나 검증하지 않습니다.
저는 코드, 분석 및 초안 작성을 위해 AI 어시스턴트를 사용했습니다. 수치는 원본 결과 파일과 Kaggle 리더보드에서 가져왔습니다.