대규모 언어 모델 (LLMs)은 현재 해결할 수 없는 문제들을 어떻게 해결할 수 있을까요? 반복적인 샘플링 (Repeated sampling)은 테스트 시간 연산 (test-time compute)을 확장하지만, GPU 비용은 시도 횟수에 따라 선형적으로 증가합니다. 반면, 검증 가능한 보상 (verifiable rewards)을 사용하는 강화학습 (RL)은 샘플 다양성을 희생하면서 단일 시도 정확도를 향상시킵니다. 두 전략 모두 기본 정책 (base policy)이 정답을 생성할 확률이 거의 제로에 가까울 때는 결국 실패합니다. 즉, 샘플링을 아무리 많이 하거나 그래디언트 신호 (gradient signal)를 주더라도 탐색 공간 (search space)이 너무 크면 극복할 수 없습니다.

우리는 다른 접근 방식을 취합니다. 더 많이 샘플링하는 대신, 문제를 구현 후 재조합할 수 있는 작고 독립적으로 해결 가능한 하위 함수 (sub-functions)들로 분해하여 작업을 더 쉽게 만듭니다. 기성 모델들은 이러한 모듈형 생성 (modular generation)을 위해 학습되지 않았기 때문에, 우리는 계층적 코드 구조를 분해하고 구현하는 법을 명시적으로 학습하는 RL 알고리즘인 DecompRL을 소개합니다. $n$개의 모듈에 대해 $k$개의 구현체를 재조합하면 최대 $k^{n}$개의 후보 솔루션을 얻을 수 있으며, 이를 통해 병목 현상을 GPU 추론 (GPU inference)에서 저렴한 CPU 평가 (CPU evaluation)로 전환하고 GPU 토큰 비용을 약 50배 절감합니다. LiveCodeBench 및 CodeContests (Qwen2.57B, Code World Model~32B)에서 DecompRL은 문제당 $10^5$ 토큰을 초과하는 지점에서 표준 및 다양성 최적화 RL 베이스라인을 능가하며, 표준 생성 방식으로는 도달할 수 없는 문제들을 해결합니다.