🤖 machine learning

DecompRL: Solving Harder Problems by Learning Modular Code Generation

이 논문은 대규모 언어 모델이 작업을 모듈형 하위 함수로 분해하는 법을 학습함으로써 이전에 해결 불가능했던 코딩 문제들을 해결할 수 있게 하고, 이를 통해 탐색 공간을 기하급적으로 확장하며 GPU 추론 비용을 크게 절감할 수 있게 하는 강화 학습 알고리즘인 DecompRL을 소개한다.

원저자: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

게시일 2026-07-03

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 문제: "원샷(One-Shot)"의 병목 현상

당신이 매우 어려운 퍼즐을 풀려고 노력하고 있다고 상상해 보세요. 당신에게는 그 퍼즐을 대신 풀어줄 수 있는 아주 똑똑한 로봇(대규모 언어 모델, LLM)이 있습니다.

현재 이 로봇에게 어려운 퍼즐을 풀게 하는 표준적인 방법은, 로봇에게 계속해서 반복해서 시도하라고 요청하는 것입니다.

기존 방식: 당신은 로봇에게 "전체 솔루션을 작성해 줘"라고 요청합니다. 만약 실패하면, 다시 요청합니다. 또 실패하면, 또 다시 요청합니다.
문제점: 로봇에게 매번 처음부터 다시 전체 솔루션을 쓰라고 요청할 때마다 많은 비용과 시간(GPU 연산 능력)이 소모됩니다. 만약 퍼즐이 정말 어렵다면, 로봇은 단 하나를 맞히기 위해 수백만 번을 시도해야 할지도 모릅니다. 이것은 마치 당신이 괜찮은 오믈렛 하나를 만드는 법을 확인하고 싶을 때마다, 마스터 셰프를 고용해 매번 처음부터 10가지 코스 요리를 전부 만들게 하는 것과 같습니다. 너무 비효적입니다.

새로운 아이디어: "레고(Lego)" 접근 방식 (DecompRL)

이 논문의 저자들은 로봇에게 한 번에 전체 성을 쌓으라고 요구하는 대신, 성을 조각조각 나누어 쌓도록 가르쳐야 한다는 점을 깨달았습니다.

복잡한 코딩 문제를 거대한 레고 성을 만드는 것에 비유해 봅시다.

표준 방식: 로봇은 한 번에 전체 성을 지으려고 시도합니다. 만약 지붕을 잘못 만들면, 전체가 실패하게 됩니다.
DecompRL 방식: 로봇은 성을 작고 독립적인 부분들로 나누는 법을 배웁니다: "여기는 벽", "여기는 문", "여기는 창문".

로봇이 이러한 작은 부품들을 만드는 법을 배우고 나면, 마법 같은 일이 일어납니다: 바로 **재조합(Recombination)**입니다.

예를 들어, 로봇이 "벽"의 서로 다른 버전 5개, "문"의 서로 다른 버전 5개, "창문"의 서로 다른 버전 5개를 만들었다고 가정해 봅시다.
5개의 완전한 성을 만드는 것은 비용이 많이 들지만, 이 부품들을 서로 섞고 조합할 수는 있습니다. 당신은 벽 1번, 문 3번, 창문 5번을 가져와서 새로운 성을 만들 수 있습니다. 그다음엔 벽 2번, 문 1번, 창문 4번을 조합할 수도 있죠.
단 15개의 작은 부품만 있으면, 당신은 125개의 서로 다른 성(5 x 5 x 5)을 만들어낼 수 있습니다.

작동 원리: 두 단계의 댄스

이 논문은 로봇에게 이러한 "레고" 접근 방식을 가르치는 새로운 훈련 방법인 DecompRL을 소개합니다. 이 방식은 두 가지 특화된 역할(정책)을 사용합니다:

설계자 (Decomposition Policy): 이 로봇의 부분은 어려운 문제를 보고 이렇게 말합니다. "좋아, 이 문제를 풀려면 정렬 함수, 수학 함수, 그리고 출력 함수가 필요해." 즉, 큰 문제를 작고 관리 가능한 작업들로 나눕니다.
제작자 (Implementation Policy): 이 부분의 로봇은 그 작은 작업들 각각에 대한 코드를 작성합니다.

마법의 기술:
시스템은 "설계자의 계획"에 대한 수많은 버전과 "제작자의 코드"에 대한 수많은 버전을 생성합니다. 그런 다음, 저렴한 컴퓨터(CPU)를 사용하여 이 모든 조합을 섞고 맞춥니다.

비용의 전환: 코드를 쓰는 것은 비쌉니다 (높은 급여를 받는 설계자를 고용하는 것과 같습니다). 하지만 코드가 제대로 작동하는지 확인하는 것은 저렴합니다 (단순한 품질 검사와 같습니다).
결과: "전체" 솔루션을 생성하는 대신 "부분"들을 섞고 조합함으로써, 시스템은 단 몇 개의 솔루션을 생성하는 비용으로 수천 개의 잠재적인 솔루션을 테스트할 수 있습니다. 이는 병목 현상을 비싼 "두뇌 연산(GPU)"에서 저렴한 "검증 연산(CPU)"으로 옮겨줍니다.

이것이 왜 중요한가

이 논문은 로봇이 보통 99.9%의 확률로 실패하는 매우 어려운 문제들에 대해 다음과 같이 보여줍니다:

표준 방식은 한계에 부딪힙니다. 로봇에게 전체 솔루션을 시도하라고 아무리 여러 번 요청해도, 로봇은 계속 실패할 뿐입니다.
DecompRL은 계속해서 발전합니다. 작은 부분들을 섞고 조합함으로써 수천 개의 조합을 테스트할 수 있기 때문에, "전체 솔루션" 방식으로는 결코 도달할 수 없었던 솔루션을 찾아냅니다.

주의점 (한계점)

이 논문은 단점도 솔직하게 밝히고 있습니다:

"포맷 세금(Format Tax)": 쉬운 문제의 경우, 문제를 나누는 것이 오히려 더 느리고 비효율적입니다. 이것은 샌드위치를 먹을 수 있는데도 빵과 고기를 따로 분리해서 먹으려고 하는 것과 같습니다. 로봇은 언제 문제를 나누어야 하는지를 알 수 있도록 특별히 훈련되어야 합니다.
훈련의 어려움: 로봇은 이를 자연스럽게 알지 못합니다. "설계자"와 "제작자" 역할을 학습하기 위해 특수한 강화 학습 과정을 통해 처음부터 다시 훈련되어야 합니다.

요약

DecompRL은 AI에게 한 번에 전체 답을 쓰려고 하지 말고, 작은 재사용 가능한 부품들로 이루어진 도구 상자를 만드는 법을 가르치는 새로운 방식입니다. 이러한 부품들을 섞고 조합함으로써, AI는 수많은 전체 답변을 생성하는 높은 비용을 지불하지 않고도 수백만 개의 가능성을 테스트할 수 있습니다. 이는 값비싼 "추측하고 확인하기(guess and check)" 게임을 저렴한 "섞고 맞추기(mix and match)" 게임으로 바꾸어 놓습니다.

기술 요약: DecompRL

문제 정의

대규모 언어 모델(LLM)은 기본 정책(base policy)이 정답을 생성할 확률이 거의 제로에 가까운 복잡한 문제를 해결하는 데 현재 어려움을 겪고 있습니다. 기존 전략들은 다음과 같은 상당한 병목 현상에 직면해 있습니다:

반복 샘플링 (pass@k): 테스트 시 컴퓨팅 자원(test-time compute)을 확장하는 데는 효과적이지만, GPU 비용이 시도 횟수에 따라 선형적으로 증가합니다. 성능 이득은 이러한 선형적 비용에 비해 로그 함수적으로 성장하는 경우가 많습니다.
표준 강화 학습 (RL): PPO나 GRPO와 같은 방법들은 단일 시도 정확도(pass@1)를 개선하지만, 종종 샘플 다양성을 감소시킵니다. 이는 높은 $k$ 값( $k \gg 100$ )으로 추론을 확장할 때 그 효과를 저해합니다.
핵심 한계점: 탐색 공간이 너무 넓을 경우, 늘어난 샘플링이나 그래디언트 신호 모두 기본 정책이 정답을 생성할 낮은 확률을 극복하지 못합니다.

방법론: DecompRL

저자들은 계층적 모듈형 생성을 활용하여, 계산의 병목을 비싼 GPU 추론에서 저렴한 CPU 평가로 전환하는 강화 학습 프레임워크인 DecompRL을 제안합니다.

1. 계층적 추론 (Hierarchical Inference)

DecompRL은 단일한 형태의 코드 솔루션을 생성하는 대신, 문제를 독립적으로 해결 가능한 하위 함수들의 계층 구조로 분해하도록 모델을 훈련합니다.

분해 정책 ( $\pi(D)$ ): 문제 $x$ 를 시그니처와 자연어 독스트링(docstring)으로 지정된 $n$ 개의 함수 집합( $D$ )으로 나눕니다.
구현 정책 ( $\pi(I|D)$ ): $D$ 내의 각 함수에 대해 $k$ 개의 독립적인 구현체를 생성합니다.
재결합 (Recombination): 각 함수에 대해 $k$ 개의 구현체를 생성함으로써, 시스템은 재결합을 통해 $k^n$ 개의 후보 솔루션을 만들어냅니다. 이를 통해 선형적인 추론 비용( $k \times n$ 토큰)만으로도 조합 폭발적인 잠재적 프로그램( $k^n$ )을 생성할 수 있습니다.

2. 강화 학습 목적 함수

DecompRL은 두 개의 정책이 관여하는 협력적 다중 에이전트 RL 문제로 계층적 추론을 취급합니다. 재결합 과정에서 발생하는 희소한 보상(sparse rewards)과 높은 분산을 처리하기 위해 저자들은 다음과 같은 특정 알고리즘적 적응을 도입했습니다:

LogMeanExp 목적 함수: 탐색(exploration)과 이용(exploitation)의 균형을 맞추기 위해, 저자들은 $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$ 로 정의된 소프트 목적 함수를 사용합니다. 이는 평균( $\beta \to \infty$ )과 최댓값( $\beta \to 0$ ) 사이를 보간하며, pass@k 목적 함수의 로그-균등 혼합(log-uniform mixture)을 근사합니다.
Leave-One-Out 베이스라인: 정책 그래디언트를 계산하기 위해, 저자들은 leave-one-out 베이스라인을 사용합니다. 특정 액션(분해 또는 구현)에 대해, 어드밴티지는 전체 보상 세트에 대한 다중 샘플 목적 함수와 해당 액션을 제외한 세트에서 계산된 목적 함수를 비교함으로써 산출됩니다. 이는 그래디언트 분산을 줄이고 편향을 방지합니다.
순차적 훈련 (Sequential Training): 분해 정책과 구현 정책은 공동(jointly)으로 훈련되는 대신 순차적으로(교대 단계로) 훈련됩니다. 이는 다중 에이전트 RL에서의 "움직이는 타겟(moving target)" 문제를 해결하여, 구현 정책이 특정 분해에 과적합되거나 그 반대의 경우가 발생하는 것을 방지합니다.

3. 계산의 전환

이 방법은 근본적으로 계산의 병목 지점을 전환합니다:

표준 RL: 전체 솔루션을 생성하기 위한 GPU 추론 비용이 지배적입니다.
DecompRL: 재결합된 솔루션을 평가하기 위한 CPU 실행 비용이 지배적입니다. 동일한 평가 예산(예: 512회 평가)에 대해 GPU 토큰 생성량이 약 50배 감소합니다.

주요 결과

실험은 LiveCodeBench 및 CodeContests에서 Qwen 2.5 7B, Llama 3.1 8B Instruct, Code World Model 32B를 대상으로 수행되었습니다.

어려운 문제에 대한 성능: DecompRL은 토큰 예산이 $10^5$ 를 초과할 때 표준 RL 베이스라인(GRPO, pass@k 훈련, SPO)보다 우수한 성능을 보입니다. 이는 표준 생성 방식으로는 도달할 수 없는 문제를 해결하며, LiveCodeBench의 "hard" 서브셋에서 최대 **35%의 해결률(solve rate)**을 달성합니다.
스케일링 동작: 표준 방식은 토큰 예산이 증가함에 따라 포화 상태에 도달하는 반면, DecompRL의 성공률은 계속해서 스케일링됩니다. 문제당 최대 3백만 개의 토큰을 사용할 때, 기존 방법들을 크게 압도합니다.
다양성 및 재결합: 이 방법은 다양한 솔루션을 생성합니다. 분석에 따르면 DecompRL로 훈련된 모델은 훈련이 진행됨에 따라 더 큰 분해(더 많은 함수)를 생성하는 법을 배우며, 이는 대규모 추론 예산에서의 높은 성공률과 상관관계가 있습니다.
효율성: 문제당 512회의 평가 시, DecompRL은 GPU 토큰 생성을 약 198k(표준)에서 4k로 줄여, 실제 소요 시간의 주도권을 CPU 실행(CPU 시간 99.6% vs GPU 시간 0.4%)으로 전환합니다.

의의 및 주장

논문은 DecompRL이 기본 정책의 성공률이 거의 제로인 "더 어려운" 문제들을 해결하기 위한 새로운 경로를 제공한다고 주장합니다:

콜드 스타트(Cold Start) 극복: 이는 표준적인 고(high)-pass@k 샘플링으로는 도달할 수 없는 태스크에서 정답 솔루션을 발견하는 탐색 도구로서 작용하며, 정책 증류(policy distillation) 파이프라인의 자연스러운 보완재가 됩니다.
효율적인 스케일링: 생성 비용과 평가 비용을 분리함으로써, GPU 풋프린트를 비례적으로 늘리지 않고도 저렴한 CPU 클러스터에서 탐색을 확장할 수 있게 합니다.
제어 축으로서의 모듈성: 결과적인 생성 파이프라인은 반복 샘플링이나 확장된 생각의 사슬(chain-of-thought) 방식에서는 가질 수 없는 해석 가능성과 제어 축을 제공합니다.
한계점: 저자들은 계층적 추론이 쉬운 문제나 낮은 토큰 예산에서는 단일(monolithic) 생성보다 성능이 떨어진다는 "포맷 세금(format tax)"을 언급했습니다. 또한 훈련 중에 "크기 붕괴(size collapse, 분해 크기가 줄어드는 현상)" 경향이 나타나는데, 이를 logmeanexp 목적 함수와 순차적 훈련을 통해 완화했다고 밝혔습니다.

저자들은 DecompRL을 표준 RL 후처리(강력한 시작 정책의 경우 여전히 샘플 효율성이 높음)를 대체하는 것이 아니라, 고품질 데이터를 발견하고 이전에는 해결 불가능했던 과제를 해결하기 위한 특화된 탐색 전략으로 포지셔닝하고 있습니다.