/Users/jehyunlee/Documents/내노트북/paper-curation/docs/papers/182_Can_language_models_falsify_evaluating_algorithmic_reasoning

Motivation

• Known: 기존 LM 벤치마크는 대부분 문제에 대한 solution을 생성하는 능력(정방향 생성)을 평가하며, LiveCodeBench 등에서 OpenAI o3-mini나 DeepSeek R1과 같은 모델이 알고리즘 문제를 상당히 높은 비율로 해결할 수 있음이 알려져 있다.
• Gap: 과학적 진보의 핵심인 hypothesis falsification, 즉 틀린 주장에 대한 counterexample을 창의적으로 찾아내는 역방향(inverse) 능력을 평가하는 벤치마크는 존재하지 않았으며, 이는 모델이 자기 자신의 코드 오류를 찾아 self-repair하는 능력과도 밀접히 연관되어 있으나 검증되지 않았다.
• Why: falsification 능력은 과학적 발견을 가속화하고 LM이 신뢰할 수 있는 reflective reasoning을 통해 self-improve하도록 만드는 데 핵심적이므로, 이를 측정하고 개선하는 것은 AI를 통한 연구 자동화 및 모델 신뢰성 향상에 매우 중요하다.
• Approach: 저자들은 Codeforces의 최신 대회에서 사람 전문가가 실제로 counterexample을 찾아낸 incorrect submission들을 자동으로 수집하여, 코드 실행을 통해 자동 검증 가능한 REFUTE 벤치마크를 구축했다.

Achievement

(Left) Distribution of Test Cases Passed by Incorrect Solutions: The median test

1. REFUTE 벤치마크 구축: 2024-2025년 Codeforces 대회에서 수집한 324개의 problem-incorrect solution 쌍으로 구성된, 동적으로 업데이트되는 오염(contamination)-free 벤치마크를 제시했다.
2. 자동 필터링 파이프라인: 무작위 탐색이 아닌 실제 추론을 요구하도록 샘플을 정제하는 자동화된 필터링 절차를 개발했다.
3. 핵심 실증 결과: OpenAI o3-mini (high), DeepSeek R1 등 code execution feedback과 ReAct agent, few-shot chain-of-thought를 사용한 최상위 모델들도 REFUTE에서 9% 미만의 counterexample 생성 성공률을 보인 반면, 동일 모델들은 처음부터 문제를 최대 48%까지 풀 수 있음을 보여, generation과 falsification 능력 간의 뚜렷한 비대칭성(generator-verifier gap)을 입증했다.

How

While standard benchmarks for algorithmic reasoning require models to generate

• Codeforces Division 대회에서 647개의 problem statement와 실제로 반례가 발견된 incorrect submission을 소싱
• 문제 설명(입력 제약 포함)과 틀린 solution을 LM에 제공, LM은 제약을 만족하는 입력을 생성하는 program을 작성해야 함
• 생성된 입력을 held-out correct solution과 incorrect solution의 출력 비교로 자동 검증
• few-shot prompting + chain of thought, 그리고 code execution feedback이 있는 ReAct agent scaffold 두 가지 설정으로 다섯 개 개발사의 최상위 모델(OpenAI o3-mini (high), DeepSeek R1 등)을 평가
• LiveCodeBench 기반 Elo rating과 비교하여 generation 능력 대비 falsification 능력의 격차 분석

Originality

• 기존 벤치마크가 대부분 solution generation을 평가하는 것과 달리, falsification/counterexample creation이라는 inverse capability를 평가하는 최초의 체계적 벤치마크를 제안
• 사람 전문가가 실제로 어렵게 찾아낸 반례만을 선별하여 무작위 탐색으로는 풀 수 없는 난이도를 확보한 점
• 동적 업데이트를 통한 contamination-free 설계(LiveCodeBench와 유사한 철학 적용)
• self-repair, self-improvement, scalable oversight 등 여러 연구 흐름과 falsification 능력을 연결하여 새로운 관점 제시

Limitation & Further Study

• 알고리즘 문제 solving이라는 formally verifiable한 좁은 도메인에 국한되어 있어, 일반적인 과학적 주장이나 수학적 명제에 대한 falsification으로 일반화되는지는 검증되지 않음
• 324개 샘플 규모가 상대적으로 작아 통계적 유의성 및 다양한 알고리즘 토픽별 세부 분석의 신뢰도에 제약이 있을 수 있음
• Codeforces 대회 문제에 특화되어 있어 실제 연구 논문이나 과학적 hypothesis에 대한 반례 생성 능력으로의 전이 가능성은 향후 연구로 남아 있음
• ReAct agent scaffold의 설계나 prompting 전략에 따라 성능이 달라질 수 있어, 더 정교한 agent 설계나 tool 사용이 결과를 개선할 여지가 있음

Evaluation

총평: LM의 self-verification 및 falsification 능력에 대한 근본적인 맹점을 명확한 실험으로 드러낸 시의적절하고 독창적인 연구로, 향후 reflective reasoning 및 self-improvement 연구에 중요한 초석이 될 것으로 평가된다.