🤖 machine learning

Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers

본 논문은 조합 최적화 문제를 위한 재사용 가능하고 제약 조건을 인지하는 솔버를 생성하도록 강화 학습을 통해 코드 LLM 을 학습시키는 것이 해의 품질과 계산 효율성 측면에서 기존 추론 시간 탐색 방법보다 훨씬 우수한 성능을 보임을 입증한다.

원저자: Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

게시일 2026-05-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

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

"추론 시간 검색을 넘어: 강화 학습이 재사용 가능한 솔버를 합성한다"라는 논문에 대한 설명을 간단한 언어와 창의적인 비유로 제시합니다.

핵심 아이디어: "매번 추측하기"에서 "매뉴얼 작성하기"로

매우 똑똑하지만 약간 혼란스러운 조수 (대형 언어 모델, LLM) 가 있다고 상상해 보세요. 여러분이 어려운 퍼즐을 줄 때마다, 이 조수는 처음부터 다시 시작하여 추측하고, 확인하고, 다시 추측하는 방식으로 해결하려 합니다. 때로는 정답을 맞추기도 하지만, 종종 막히거나 어리석은 실수를 범합니다. 이것이 오늘날 대부분의 AI 가 문제를 해결하는 방식입니다: 질문할 때마다 매번 추론합니다.

이 논문은 다른 질문을 던집니다: 만약 AI 가 퍼즐을 매번 푸는 대신, 누구나 사용할 수 있는 완벽한 지침서 (솔버) 를 작성하는 법을 배운다면 어떨까요?

연구자들은 AI 가 "추측하는 조수"가 되는 것을 멈추고 "컴파일러"처럼 행동하도록 훈련할 수 있는지 확인하고자 했습니다. 새로운 고객마다 작업을 수행하는 대신, AI 는 규칙을 한 번 배운 후 재사용 가능한 프로그램을 작성하고, 그 프로그램이 향후 수천 개의 문제를 즉시 해결할 수 있게 됩니다.

테스트: "기만적인" 퍼즐 상자

이를 테스트하기 위해 연구자들은 **상호의존적 선택 (Synergistic Dependency Selection, SDS)**이라고 불리는 특정 유형의 퍼즐을 만들었습니다.

비유: 무게 제한이 있는 배낭을 가진 보물찾기를 상상해 보세요. 여러분은 가치가 있는 아이템을 고르고 싶습니다. 하지만 함정이 있습니다. 어떤 아이템은 함께 선택했을 때만 가치가 있습니다 (상호작용), 그리고 어떤 아이템은 둘 다 선택하면 서로 상쇄됩니다 (갈등). 또한, 어떤 아이템은 특정 다른 아이템을 먼저 선택해야만 합니다 (선행 조건).
함정: 이 퍼즐은 "기만적"으로 설계되었습니다. 단순하고 탐욕스러운 전략 (예: "가장 무거운 아이템부터 고르자") 은 작동하는 것처럼 보이지만, 실제로는 막다른 길로 이끕니다. 직관적이고 쉬운 경로가 실제로는 벽으로 이어지는 미로와 같습니다.

"기반" AI 의 문제점

연구자들은 먼저 표준적인 미훈련 AI 모델을 사용하여 이러한 퍼즐을 해결해 보았습니다. 그들은 AI 가 각 퍼즐마다 64 번 시도하게 하고 (이 방법을 "Best-of-64"라고 함) 가장 좋은 답변을 선택했습니다.

결과: 64 번 시도함에도 불구하고, AI 는 달성할 수 있었던 가치의 약 **71%**만 얻었습니다 (28.7% 의 격차).
이유: AI 는 논리를 "환각"하고 있었습니다. AI 는 좋은 전략의 이름 (예: "시뮬레이션 어닐링", 이는 "상자를 흔들어 최상의 배열을 찾는 것"이라는 fancy 한 표현) 을 알고 있었지만, 그 전략에 대한 코드를 작성할 때 치명적인 논리 오류를 범했습니다. 마치 케이크 레시피를 아는 요리사가 오븐을 켜는 것을 잊거나, 더 나쁘게는 케이크를 냉동실에 넣는 것과 같습니다.

해결책: AI 에게 자신의 논리를 "수정"하도록 가르치기

연구자들은 이후 **강화 학습 (Reinforcement Learning, RL)**이라는 기법을 사용했습니다. 이는 단순히 "잘했어!" 또는 "나빠!"라고 말하는 것이 아니라 구체적인 피드백을 주는 엄격한 코치와 같습니다:

"실행 가능성 게이트": 코치는 말합니다. "만약 당신의 코드가 규칙을 위반하면 (예: 서로 충돌하는 두 개의 아이템을 선택하는 경우), 점수가 아무리 좋아도 점수 0 점을 받습니다." 이는 AI 가 높은 점수를 얻는 것보다 규칙을 따르는 것을 우선시하도록 강제합니다.
"게으름 방지" 페널티: 코치는 AI 가 쉬운 길 (예: 복잡한 상호작용을 무시하고 아이템을 무게순으로 정렬하는 것) 을 택하려 하면 처벌합니다.
"발판": 그들은 AI 에게 구체적인 사고 템플릿을 제공했습니다. "문제를 분해하고, 전략을 추측하고, 자신의 추측을 비판한 후 코드를 작성하라."

결과: 재사용 가능한 "솔버" 탄생

이 훈련 후 AI 는 단순히 추측을 잘하게 된 것이 아니라, 근본적으로 작동 방식을 바꾸었습니다.

"컴파일러" 효과: AI 는 "시뮬레이션 어닐링" 전략을 올바르게 구현한 단일 재사용 가능 코드 (솔버) 를 작성하는 법을 배웠습니다.
마법: **99.8%**의 경우, AI 는 이 올바른 패턴을 따르는 코드를 작성했습니다. 미훈련 AI 가 계속 저지르던 논리 오류를 수정한 것입니다.
성능: 새로운 "영웅" 솔버는 이론상 가능한 최선의 답변과 5% 이내의 점수를 달성했습니다.
비용: 이것이 가장 흥미로운 부분입니다.
- 이전 방식 (퍼즐당 64 번 추측) 은 새로운 퍼즐마다 많은 컴퓨터 시간을 소모했습니다.
- 새로운 방식 (솔버를 한 번 작성) 은 컴퓨터가 무거운 작업을 한 번만 수행하면 된다는 것을 의미했습니다. 그 후 솔버는 수천 개의 퍼즐을 즉시 실행할 수 있었습니다.
- 수학: 새로운 방법은 기존 "추측" 방식 대비 퍼즐당 컴퓨터 시간 기준으로 91 배 더 저렴했습니다.

작동하지 않은 것 ("부정적" 교훈)

논문은 특수 훈련 기법을 제거하면 어떤 일이 일어나는지 또한 테스트했습니다:

규칙 없음: AI 에게 제약 조건을 엄격히 따르는 규칙 없이 창의적으로 시도하도록만 하면, 실수를 반복하게 됩니다.
부드러운 규칙: "점수가 높다면 규칙을 조금 깨도 괜찮다"고 AI 에게 말하면 실패합니다. AI 는 규칙을 존중하도록 배우기 위해 단단한 "정지" 신호가 필요합니다.
프롬프트만: 지시사항에 "똑똑해져라"라고만 말하고 보상 시스템으로 훈련하지 않으면 여전히 실패합니다. 지시사항은 단지 지도일 뿐이며, 훈련은 실제로 차를 운전하는 차량입니다.

결론

이 논문은 AI 모델을 "즉석 추측자"가 아닌 "프로그래머"로 훈련시킬 수 있음을 증명합니다. 엄격한 규칙을 갖춘 강화 학습을 통해 AI 는 개별적으로 해결하는 데 고군분투하는 대신, 어려운 문제의 전체 계열을 올바르게 해결하는 재사용 가능한 도구를 합성할 수 있습니다.

이는 매일 여러분을 위해 수학 문제를 풀어주는 사람을 고용하는 것 (비싸고 느림) 과 그 사람에게 문제를 영원히 풀어줄 계산기를 만들도록 가르치는 것 (싸고 빠름) 의 차이와 같습니다. 연구자들은 올바른 훈련을 통해 AI 가 그 계산기를 만들 수 있음을 보여주었습니다.

기술 요약: 추론 시간 검색을 넘어

1. 문제 제기

현재의 대규모 언어 모델 (LLM) 은 일반적으로 조합 최적화를 추론 시간 절차로 취급하며, 각 문제 인스턴스를 샘플링, 검색 또는 반복적인 프롬프팅을 통해 개별적으로 해결합니다. 이 패러다임은 모든 새로운 쿼리에 대해 추론의 '한계 비용'을 발생시킵니다. 저자들은 강화 학습 (RL) 이 이러한 추론 비용을 모델의 가중치 안으로 이동시켜, 인스턴스별 솔루션을 생성하는 대신 전체 문제 군에 대한 재사용 가능한 솔버를 합성할 수 있는지 조사합니다.

본 연구는 2 차 배낭 문제의 통제된 강한 NP-난제 변형인 **상호 의존적 선택 (Synergistic Dependency Selection, SDS)**에 초점을 맞춥니다. SDS 는 다음과 같은 '기만적'인 최적화 지형으로 설계되었습니다:

국소 신호가 전역 최적성과 모순됨: 2 차 상호작용 항이 선형 가중치를 지배하여 탐욕적 휴리스틱이 실패하게 만듭니다.
엄격한 실현 가능성 제약: 솔루션은 카디널리티, 우선순위, 상호 배제, 그룹 제한을 모두 만족해야 합니다.
템플릿 검색 대 실행화: 기본 모델은 종종 적절한 솔버의 구문(예: 시뮬레이션 어닐링) 을 검색할 수 있지만, 자주 실행 가능한 논리를 올바르게 구현하지 못합니다 (예: 수용 규칙의 오용).

본 논문은 세 가지 핵심 연구 질문에 답합니다:

역량 한계벽: 동일한 프롬프팅 하에서 Best-of-N 과 같은 광범위한 테스트 시간 샘플링이 기만적 지형에서 RL 훈련 정책의 성능을 회복시킬 수 있는지, 아니면 기본 모델이 한계에 부딪히는지 여부.
의미적 복구: RL 이 성공할 때, 단순히 올바른 솔루션의 빈도를 높이는 것만인지, 아니면 단순 샘플링이 회복할 수 없는 실행 가능한 알고리즘 논리를 복구하는 것인지.
상각된 솔버 합성: 훈련 시간 최적화가 추론을 경량화되고 재사용 가능한 프로그램으로 정제하여 반복적인 인스턴스별 검색보다 우수한 성능을 낼 수 있는지.

2. 방법론

저자들은 Qwen2.5-Coder-14B-Instruct 모델을 기반으로 **GRPO(Group Relative Policy Optimization)**를 사용하여 미세 조정된 정책인 Hero를 제안합니다. 이 접근법은 실현 가능성 우선 레시피의 효과를 격리하기 위해 일반적인 안정화 요소 (예: KL 페널티, 오라클 고정) 를 제거한 의도적으로 간소화된 방식입니다.

주요 구성 요소:

구조화된 시스템 프롬프트: 프롬프트는 '분해 - 가설 설정 - 비판' 추론 루프를 강제합니다. 이는 모델이 탐욕적 휴리스틱을 피하고 탐색과 활용을 균형 있게 조화시키는 검색 전략을 설계하도록 명시적으로 경고합니다.
계층적 보상 설계: 복합 보상 $r(o)$ $r (o)$ 는 raw 최적성보다 구조적 준수를 우선시합니다:
- 형식 및 실행 ( $R_{exec}$ ): 유효한 Python 구문, 스키마 준수, 그래프 이론적 구조를 보장합니다. 특히, 2 차 상호작용을 무시하는 선형 탐욕적 휴리스틱을 사용하는 사전 훈련된 모델의 경향을 억제하기 위한 비-게으름 정렬 페널티를 포함합니다.
- 실현 가능성 게이트 최적성 ( $R_{nom}$ ): 주요 최적화 신호는 엄격하게 게이트됩니다. 솔루션이 하드 제약 (카디널리티, 우선순위 등) 중 하나라도 위반하면, 목적 함수 점수와 관계없이 보상은 0 이 됩니다. 이는 정책이 목적 함수 최적화 전에 제약 조건 준수를 우선시하도록 강제합니다.
훈련 환경: 모델은 12 개의 NVIDIA GH200 GPU 에서 90 개의 글로벌 스텝 동안 훈련되며, 전체 프롬프트 수준 에포크의 약 4.5% 만 관찰하지만 23,040 개의 추론 흔적을 생성합니다.

3. 주요 기여

본 논문의 기여는 알고리즘적이기보다 경험적이며 기계론적입니다:

역량 한계벽의 식별: 동일한 프롬프팅 하에서 기본 모델의 Best-of-64 샘플링은 가상 최선 솔버 (VBS) 에 비해 28.7% 의 격차에서 포화됩니다. 표면적으로 적합한 솔버 템플릿을 검색함에도 불구하고 (예: 고유 기본 코드의 21.9% 가 시뮬레이션 어닐링과 유사함), 기본 모델은 이를 올바르게 실행하지 못합니다.
의미적 복구의 입증: RL 훈련된 정책 (Hero) 은 실현 가능한 출력의 **99.8%**에서 제약 인식형 시뮬레이션 어닐링 템플릿으로 수렴합니다. 이는 기본 모델 샘플에 만연한 '전역 최선 버그'를 복구합니다. 이 버그는 수용 논리가 현재 상태가 아닌 실행 중인 전역 최선과 이웃을 비교하는 오류입니다. 이 수정은 진정한 어닐링 행동을 가능하게 합니다.
상각된 솔버 합성의 검증:
- 성능: Hero 는 VBS 에 대해 5.0% 의 격차를 달성하여 기본 모델과 지역 검색 (10.0% 격차) 과 같은 고전적 휴리스틱을 크게 능가합니다.
- 효율성: Hero 는 Best-of-64 평가의 누적 비용에 비해 후생성 실행/검색 비용이 91 배 더 저렴합니다.
- 재사용성: '한 번 컴파일' 평가는 시드당 생성된 단일 동결 솔버가 전체 테스트 세트에서 변경 없이 재사용될 때 매우 경쟁력 있음 (97.87% 통과율, 4.34% 격차) 을 보여주며, 모델이 인스턴스별 생성기가 아닌 재사용 가능한 아티팩트를 합성함을 입증합니다.

4. 결과 및 제거 실험

주요 성능: Hero 는 97.8% 의 통과율과 VBS 대비 5.0% 의 격차를 달성합니다. 배포 시 강력한 독점 모델을 사용하는 갱신된 ShinkaEvolve 베이스라인을 능가하며, 실행 속도는 6.3 배 빠르면서도 CP-SAT(1.0% 격차) 의 성능에 근접합니다.
제거 실험:
- 구조적 발판: 구조적 보상 (비-게으름 정렬 및 그래프 구조 검사) 을 제거하면 모델이 취약한 탐욕적 휴리스틱으로 회귀하여 성능이 34.7% 격차로 붕괴됩니다.
- 실현 가능성 게이트: 하드 실현 가능성 게이트를 소프트 페널티로 대체하면 성능이 크게 저하됩니다 (97.8% 대비 57.4% 통과율). 이는 무효 솔루션으로의 모드 붕괴를 방지하기 위해 하드 게이트가 필수적임을 확인시켜 줍니다.
- 오라클/다양성: 오라클 고정이나 다양성 페널티를 추가하면 성능이 저하되어, 이 영역에서 밀도 있는 결과 형성보다 희소하고 실현 가능성 우선 피드백이 더 효과적임을 시사합니다.
일반화:
- 파괴적 망각 부재: 모델은 일반적인 코딩 능력을 유지합니다 (HumanEval Pass@1: 80.9% vs 기본 82.3%).
- 교차 도메인: 동일한 레시피를 Job Shop Scheduling(JSSP) 에 적용하면 긍정적 결과 (99.3% 통과율, 6.12% 격차) 를 보이지만, 저자들은 이는 도메인 무관한 견고성의 증명보다는 전이의 더 좁은 증거라고 지적합니다.

5. 중요성 및 주장

본 논문은 RL 이 코드 LLM 을 인스턴스별 검색 regime 에서 재사용 가능한 솔버 합성 regime 으로 이동시킬 수 있음을 입증한다고 주장합니다. 그 중요성은 RL 이 단순히 기존 솔루션을 찾는 효율성을 높이는 '분포 sharpener'가 아니라, 단순 샘플링이 신뢰할 수 있게 회복할 수 없는 실행 가능한 논리 (예: 메트로폴리스 수용 규칙 수정) 를 복구하는 기능적 컴파일러로 작용한다는 발견에 있습니다.

저자들은 이 성공이 보편적인 레시피가 아니라 엄격하고 실현 가능성 우선인 발판에 의존한다고 강조합니다. 이 방법은 하드 실현 가능성 게이트 및 구조적 페널티와 같은 특정 설계 선택에 의존하며, 보상 정규화에 민감합니다. 이 연구는 복잡하고 기만적인 최적화 지형에서 솔버를 구축하는 데 필요한 '추론'이 모델의 가중치로 정제되어, 반복적인 추론 시간 검색보다 훨씬 효율적인 배포 가능한 아티팩트를 생성할 수 있음을 시사합니다.