AlgoSkill: 인간과 유사한 기술을 활용하여 알고리즘 설계 학습

AlgoSkill: Learning to Design Algorithms by Scheduling Human-Like Skills

자연어 문제 설명에서 알고리즘을 설계하려면 문제 구조를 파악하고, 제약 조건을 이해하며, 적절한 패러다임을 선택하고, 정확성을 검증하고, 복잡도를 개선해야 합니다. 기존의 대규모 언어 모델(LLM) 방법은 종종 직접적인 생성 또는 일반적인 자체 개선에 의존하여 이러한 단계를 암묵적으로 처리합니다. 본 논문에서는 알고리즘 설계를 추상화, 제약 조건 분석, 상태 설계, 자료 구조 선택, 증명 검사, 반례 구성 및 복잡도 개선을 포함하는 유형화된 알고리즘 기술 라이브러리를 사용한 순차적 의사 결정 문제로 모델링하는 AlgoSkill을 제안합니다. 학습된 스케줄러는 현재 설계 상태에서 기술을 제안하고, 몬테카를로 트리 탐색(MCTS) 컨트롤러는 컴파일, 테스트, 스트레스 테스트 및 복잡도 분석으로부터 얻은 검증 피드백을 사용하여 기술 시퀀스를 탐색합니다. 경쟁 프로그래밍 및 조합 최적화 벤치마크에 대한 실험 결과, AlgoSkill은 직접적인 LLM 생성 방식, 체인 오브 소트(chain-of-thought) 프롬프트, 자체 개선 방식, 그리고 유형화되지 않은 기술을 사용한 MCTS 방식보다 성능이 우수함을 보여줍니다. 분석 결과, 유형화된 기술, 검증 기반 수정 및 탐색 기반 스케줄링 각각이 성능 향상에 기여하는 것으로 나타났습니다. 이러한 결과는 자동 알고리즘 설계가 단일 코드 생성보다는 검증 지향적인 기술 스케줄링으로 간주되어야 함을 뒷받침합니다.

Designing an algorithm from a natural-language problem statement requires identifying the problem structure, reading constraints, choosing a suitable paradigm, checking correctness, and refining complexity. Existing large language model (LLM) methods often rely on direct generation or generic self-refinement, leaving these steps implicit. We propose AlgoSkill, which models algorithm design as sequential decision-making over a typed library of algorithmic skills, including abstraction, constraint analysis, state design, data-structure selection, proof checking, counterexample construction, and complexity refinement. A learned scheduler proposes skills from the current design state, while a Monte Carlo Tree Search (MCTS) controller explores skill sequences using verification feedback from compilation, testing, stress testing, and complexity analysis. Experiments on competitive programming and combinatorial optimization benchmarks show that AlgoSkill improves over direct LLM generation, chain-of-thought prompting, self-refinement, and MCTS without typed skills. Ablations show that typed skills, verification-based repair, and search-based scheduling each contribute to performance. These results support treating automatic algorithm design as verification-guided skill scheduling rather than one-shot code generation.