🔍 연구의 필요성

LLM의 발전으로 코드 생성이 활발해졌지만, 알고리즘 문제에서는 정답을 내는 것과 시간 제한 안에서 정답을 내는 것이 전혀 다른 문제입니다. 경쟁 프로그래밍, 코딩 인터뷰, 벤치마크 대부분은 time limit을 명시하고 있으며, 작은 입력에서는 통과하더라도 효율성이 중요한 영역에 들어가면 실패하는 코드가 흔합니다. 그 결과 최근 연구들은 코드의 정답 여부뿐만 아니라 실행 효율성까지 함께 평가하는 방향으로 나아가고 있습니다.

이러한 평가를 위해서는 알고리즘적 병목을 드러내는 효율성 테스트 케이스(efficiency test cases) 가 필요합니다. 그런데 효율성 테스트 케이스를 만든다는 것은 단순히 입력을 크게 만든다는 의미가 아닙니다. Worst 케이스는 종종 입력의 구조에 달려 있습니다. 역정렬된 배열은 pivot에 민감한 quicksort를 무너뜨리고, path-shaped 트리는 재귀 깊이를 극대화하여 연산량을 폭증시킵니다. 즉 효율성 테스트 케이스는 (i) 입력 제약을 만족하면서 (ii) 비효율적 풀이가 느려지는 구조라는 두 조건을 동시에 만족해야 합니다.

기존 효율성 지향 테스트 생성기들은 이 두 조건 중 일부만 다룹니다. 입력 크기를 키워 runtime threshold를 넘기는 데 집중하거나, 프로그램의 실행으로부터 병목 조건을 추론해 fuzzing으로 입력을 찾는 식입니다. 두 방향 모두 reference implementation의 실행 행위에서 비효율을 추적하기 때문에, "이 코드를 무엇이 느리게 하는가" 는 답해도 "이 문제를 알고리즘적으로 무엇이 어렵게 하는가" 는 답하지 못합니다.

우리는 이 공백을 메우기 위해 STAB을 제시합니다. STAB은 reference implementation이나 실행 피드백 없이 자연어 문제 명세만으로 효율성 테스트 케이스를 생성하며, "유효한 입력 경계를 얼마나 크게 잡을 수 있는가"와 "그 경계 안에서 어떤 구조가 알고리즘을 느리게 하는가"를 분리해서 해결합니다.

✨ STAB이란?

STAB (Specification-driven Testing for Algorithmic Bottlenecks)은 자연어 문제 명세만을 입력으로 받아, 알고리즘적 병목을 노출하는 효율성 테스트 케이스를 생성하는 specification-driven 파이프라인입니다. 출력은 원시 입력 문자열이 아니라 Python generator 함수이며, 실행 시 구체적 입력을 출력합니다. Generator 표현은 입력이 크고 구조적일 때 더 짧고, 구성 논리가 드러나며, 동일한 채점 환경에서 반복 실행 가능하다는 장점을 가집니다.

STAB은 직접 프롬프팅이 한 번에 풀어야 했던 두 과제를 명시적으로 분리합니다.

1. Constraint Saturator (입력 경계를 최대로 키우기)

<aside> 📌

• 정규식 기반 파서로 명세에 등장하는 constraint(범위, 연쇄 부등식, 곱 제약, 문자열 길이 등)를 normalized record로 추출
• 변수 간 dependency graph를 만들어 독립 변수와 종속 변수 그룹을 분리
• 변수 종류에 따라 두 가지 path로 최대 크기 할당을 도출:
  • Rule-based saturation: 독립 변수는 추출된 상한으로 직접 포화
  • CP-SAT 최적화: 곱 제약, 연쇄 부등식, 집계 제약에 묶인 종속 변수들은 함께 해석해 유효성을 깨지 않는 최대 크기 할당 도출 </aside>

2. Adversarial Scenario Injector (적대적 구조 원리 주입하기)

<aside> 📌

• 13개 알고리즘 시나리오, 51개 구현체를 포함한 curated catalog 구축 (Sorting, Hashing, Tree traversal, Graph shortest path, String matching, BST/segment, DP/recursion, Number theory, Binary search, Two pointers, Bitmasks, Combinatorics, Geometry). 각 구현체에는 vulnerability class(Structural / Numerical / Size Only)와 adversarial construction principle이 매핑됨
• 문제 명세에 매칭되는 시나리오 후보 검색은 Keyword Match를 우선하고, 매칭이 실패하면 KNN으로:
  • Keyword Match: 알고리즘, 자료구조 이름이나 task-level cue("non-decreasing", "range query")로 명세에서 직접 매칭
  • KNN retrieval: train split 문제들을 임베딩해 시나리오별 centroid를 구성하고, 들어온 문제 명세를 cosine similarity로 상위 2개 시나리오를 선택 </aside>

3. Generator Synthesis (구조화된 명세로 generator 합성하기)

<aside> 📌

• 문제 명세, resolved boundary, 선택된 construction principles를 structured generation specification으로 인코딩
• LLM은 제약 만족과 adversarial 입력 설계를 동시에 추론하지 않고, 이미 검증된 경계 안에 선택된 구조를 배치하는 역할만 수행 </aside>

평가 지표 (Metric)

<aside> 📌

• ASR (Algorithmic Slowdown Rate): 정답 코드의 runtime을 CodeContests 테스트 스위트의 최대치 이상으로 끌어올린 생성 테스트 케이스의 비율. Python/Java/C++ 각각에 대해 DOMjudge 환경에서 CPU time을 기준으로 측정합니다. </aside>