기술 요약: ALGOBENCH

문제 정의

HumanEval 및 LiveCodeBench와 같은 기존의 코드 생성 대규모 언어 모델(LLM) 벤치마크는 높은 통과율을 보이지만, 이것이 반드시 진정한 알고리즘 추론 능력을 반영하는 것은 아닙니다. 주요 한계점은 **데이터 오염(Data Contamination)**입니다. 확립된 문제 문구, 해설, 그리고 참조 솔루션들이 공개된 학습 코퍼스에 널리 퍼져 있습니다. 결과적으로, 모델들은 제약 조건으로부터 알고리즘을 도출하기보다는 암기된 솔루션 패턴을 회상함으로써 높은 점수를 얻을 수 있습니다. 최근의 벤치마크들(예: LiveCodeBench, ProBench, HLCE)은 더 새롭거나 어려운 문제를 사용하여 이를 완화하려고 시도하지만, 이들은 여전히 정적(static)입니다. 일단 출시되면, 해당 문제 문구와 모델이 생성한 솔루션은 필연적으로 학습 데이터에 포함되어, 미래의 모델들이 향상된 추론이 아닌 노출을 통해 개선될 수 있게 합니다. 따라서 모델이 알고리즘 전략을 적응하도록 강제하며, 단순히 소스 솔루션을 암기하는 것만으로는 불충분한, 동적으로 생성된 문제를 갖춘 벤치마크가 필요합니다.

방법론

핵심 프레임워크: ALGOBENCH

저자들은 알려진 경쟁 프로그래밍 소스로부터 새로운 알고리즘 문제를 자동으로 구축하는 프레임워크인 ALGOBENCH를 제안합니다. 핵심 철학은 **제약 조건 이동 변환(Constraint-shifting transformation)**으로, 원본 참조 알고리즘이 실패하도록 소스 문제를 수정하여 새로운 알고리즘 접근 방식이나 다른 점근적 복잡도(asymptotic complexity)를 요구하게 만드는 것입니다.

1. 변환 연산자 (Transformation Operators)
프레임워크는 소스 문제($q$)로부터 변형 문제($q'$)를 생성하기 위해 10가지 규칙 기반 변환 연산자를 사용합니다. 여기에는 다음이 포함됩니다:

• 제약 조건 스케일링 (Constraint Scaling, CS): 입력 범위 증가 (예: $N \le 2000 \to N \le 2 \times 10^5$).
• 정적-동적 전환 (Static-to-Dynamic, SD): 정적 문제를 동적 문제로 변환 (예: 업데이트 연산 추가).
• 목표 섭동 (Objective Perturbation, OP): 최적화 목표 변경.
• 그리디 트랩 주입 (Greedy-Trap Injection, GT): 그리디 휴리스틱을 무효화하는 제약 조건을 도입하여 동적 계획법(DP)을 요구함.
• 기타 연산자로는 제약 조건 결합(Constraint Coupling), 엣지 케이스 확장(Edge-Case Expansion), 출력 요구사항 변경(Output Requirement Change), 그리고 더 넓은 범위의 변환인 현실 세계 래핑(Real-World Wrapping) 및 그래프 구조 변경(Graph-Structure Change) 등이 있습니다.

2. 품질 게이트 (Quality Gates)
유효성을 보장하고 사소한 문제(triviality)를 방지하기 위해, 생성된 문제는 네 가지 자동화된 게이트를 통과해야 합니다:

• 게이트 1 (기존 솔루션 거부): 원본 참조 솔루션($a^*$)이 새로운 문제에서 실패해야 함 (WA, TLE 또는 MLE 발생).
• 게이트 2 (새로운 솔루션 검증): 새로운 참조 솔루션($\hat{a}^*$)이 작은 입력에 대한 브루트 포스 오라클(brute-force oracle)에 의해 검증되어야 함.
• 게이트 3 (비 패러프레이즈): 생성된 문구가 소스와 충분히 달라야 함 (TextSim $< \tau_{text}$).
• 게이트 4 (복잡도 인증): 새로운 솔루션이 목표 시간 및 공간 복잡도를 충족해야 함.

3. 결정론적 복잡도 검증기 (Deterministic Complexity Verifier)
3단계 검증기는 제출된 솔루션을 평가하여 기능적 정확성과 알고리즘 최적성을 구분합니다:

• 레이어 1 (정적 AST 분석): 루프 중첩, 재귀, 데이터 구조를 기반으로 시간/공간 복잡도를 추정하기 위해 코드를 파싱합니다.
• 레이어 2 (알고리즘 태그 검증): 기대되는 알고리즘(예: 세그먼트 트리를 위한 lazy propagation)의 구조적 증거를 확인하고 금지된 알고리즘의 부재를 확인합니다.
• 레이어 3 (교정된 런타임 스케일링): 증가하는 입력 크기에 대해 솔루션을 실행하여 런타임 모델 $T(n) = cn^\alpha (\log n)^\gamma$에 적합시킵니다. 적합된 지수가 목표보다 0.15를 초과하는 경우 솔루션에 페널티를 부여합니다.

평가 지표

표준적인 pass@k 외에도, ALGOBENCH는 복잡도를 고려한 지표를 도입합니다:

• OPTT/OPTS: 정답이면서 동시에 목표 시간/공간 복잡도를 충족하는 제출 비율.
• TRAPRATE: 소스 알고리즘을 구조적으로 재사용하는 잘못된 제출의 비율 (기존 솔루션 트랩을 나타냄).
• GAPT (효율성 격차): 적합된 런타임 지수와 목표 지수 사이의 격차를 측정합니다.
• CONSENS: 제약 조건의 규모가 커짐에 따라 성능 저하를 측정합니다.
• $\Delta_{gen}$: 소스 문제와 생성된 변형 문제 간의 성능 저하를 나타냅니다.

주요 기여

1. 프레임워크: 추적 가능하면서도 알고리즘적으로 구별되는 문제를 생성하는 자동 파이프라인인 ALGOBENCH를 소개합니다.
2. 변환 및 검증: 기존 솔루션을 거부하고 새로운 복잡도를 요구하는 문제를 생성하기 위한 10가지 변환 연산자와 4단계 품질 관리 시스템을 설계했습니다.
3. 벤치마크 데이터셋: 300개의 소스 문제(Codeforces, AtCoder, Kattis, LeetCode Hard)로부터 유도된 598개의 승인된 변형 문제(주 실험에는 420개 사용)를 메타데이터, 참조 솔루션, 브루트 포스 오라클과 함께 구축했습니다.
4. 지표: 점근적 적합성만을 평가하는 지표(OPTT, OPTS, TRAPRATE, GAPT, CONSENS)를 제안했습니다.
5. 실증적 결과: 6가지 프롬프팅 전략에 대해 7개의 LLM을 평가하여, 생성된 변형 문제에서 성능이 크게 저하되며 많은 "정답" 솔루션들이 복잡도 요구사항을 충족하지 못함을 입증했습니다.

실험 결과

성능 저하 및 적응

• 일반화 격차 (Generalization Gap): 모델들은 소스 문제에서 ALGOBENCH 변형 문제로 이동할 때 급격한 성능 저하를 보입니다. 오래된 모델들은 소스 문제에서의 평균 85.1% pass@1에서 변형 문제에서는 **53.6%**로 떨어졌습니다. 최신 프런티어 모델(GPT-5.4, Claude Opus 4.5)조차 33.3% 하락했습니다.
• 복잡도 불일치 (Complexity Mismatch): pass@k와 OPTT 사이에 상당한 격차가 존재합니다. 예를 들어, GPT-4o는 72.7%의 pass@5를 달성했지만 OPTT는 63.6%에 그쳤으며, 이는 많은 통과된 솔루션들이 하위 최적(suboptimal) 알고리즘을 사용했음을 나타냅니다.
• 검색 위험 (Retrieval Risks): 소스 문제를 컨텍스트로 사용하는 검색 증강 생성(RAG)은 종종 TRAPRATE를 증가시켰습니다. Gemini 2.5 Flash의 경우, RAG를 사용했을 때 트랩 비율이 3.6%에서 30.0%로 증가했는데, 이는 검색이 모델을 (이제는 유효하지 않은) 원래의 솔루션에 고착시킨다는 것을 시사합니다.

오류 분석

400개의 실패한 제출에 대한 분석 결과, 실패는 구현 수준보다는 주로 알고리즘적인 것으로 나타났습니다:

• 기존 솔루션 트랩 (42.3%): 모델이 소스 알고리즘을 구현하여 공개 예제는 통과하지만 숨겨진 트랩 테스트에서 실패함.
• 속도 미달 (21.8%): 모델이 올바른 접근 방식을 식별했으나 필요한 최적화(예: $O(N^2)$에서 $O(N \log N)$으로의 전환 실패)를 놓침.
• 구현 버그: 실패 원인의 **9.0%**만을 차지함.

민감도 및 오염

• 제약 조건 민감도: 입력 범위가 증가함에 따라(예: $N=10K \to 50K$) 성능이 급격히 저하되었으며, 이는 이차 시간 복잡도($O(N^2)$) 솔루션이 시간 초과를 일으키는 지점과 일치합니다.
• 오염 효과: 모델들은 2024년 문제보다 오래된 소스 문제(2020년)에서 유의미하게 더 나은 성능을 보였는데, 이는 암기 현상을 시사합니다. 그러나 ALGOBENCH 변형 문제의 경우, 소스 문제의 출판 연도와 관계없이 일관되게 어려웠으므로 이 격차는 좁혀졌습니다.

의의 및 주장

본 논문은 ALGOBENCH가 표준 코드 벤치마크와는 구별되는 능력을 평가한다고 주장합니다: 즉, 암기된 템플릿에 의존하는 것이 아니라 새로운 제약 조건에 알고리즘적 추론을 적응시키는 능력입니다.

• 기능적 정확성을 넘어: 본 벤치마크는 높은 통과율이 점근적 적합성을 보장하지 않는다는 것을 보여줍니다. 많은 모델이 기능적으로는 정확하지만 알고리즘적으로는 비효율적인 솔루션을 생성합니다.
• 암혹성에 대한 견고성: 소스 솔루션이 실패하는 문제를 자동으로 생성함으로써, ALGOBENCH는 훈련 데이터 오염의 위험을 완화하고 진정한 알고리즘 추론에 대한 더 신뢰할 수 있는 척도를 제공합니다.
• 진단적 가치: 본 프레임적으로는 전통적인 벤치마크에서는 가려져 있던 특정 실패 모드(예: Greedy에서 DP로의 전환 실패, 또는 동적 업데이트 처리 실패)를 식별할 수 있습니다.

저자들은 현재의 LLM이 익숙한 템플릿이 불충분할 때 어려움을 겪는다고 결론지으며, 알고리즘 추론의 미래 발전에는 패턴 매칭이 아닌 진정한 적응을 요구하는 벤치마크가 필요하다고 강조합니다.