🤖 AI

Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs

본 논문은 NP-하드 최적화 문제에 대해 대규모 언어 모델을 훈련시키기 위해 검증 가능한 보상을 활용한 품질 인식 강화 학습 (RLVR) 을 사용하는 포괄적인 프레임워크인 OPT-BENCH 를 소개하며, 기존 모델 및 이진 보상 접근법과 비교하여 다양한 추론 작업에서 해결책의 품질과 일반화 성능이 크게 향상되었음을 보여줍니다.

원저자: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

게시일 2026-05-12

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

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

매우 똑똑한 로봇 비서 (대규모 언어 모델, 또는 LLM) 가 있다고 상상해 보세요. 이 로봇은 "이 수학 문제가 올바르게 풀렸는가?" 또는 "이 단어를 올바르게 철자했는가?"와 같은 질문에 답하는 데 탁월합니다. 오랫동안 우리는 정답일 때 "잘했다!"라고 말하고 오답일 때 "다시 시도해라"라고 말하며 이러한 로봇들을 훈련시켜 왔습니다. 이는 오직 하나의 정답만 있는 객관식 시험을 채점하는 것과 같습니다.

하지만 과제가 단순히 정답을 맞추는 것이 아니라, 가장 최상의 답을 찾는 것이라면 어떨까요?

이것이 FORGE 논문이 다루는 문제입니다. 이는 로봇에게 식료품점으로 가는 어떤 경로를 찾는 것뿐만 아니라, 수백만 개의 다른 유효한 경로들이 있더라도 가장 짧고 빠른 경로를 찾도록 요구하는 것과 같습니다.

다음은 그들이 이를 수행한 방법에 대한 간단한 설명입니다:

1. 문제: "충분히 좋은 것" 대 "최고의 것"

당신이 여행 가방을 싸고 있다고 상상해 보세요.

구식 방법 (이진 보상): 로봇에게 가방을 싸게 하라고 요청합니다. 만약 모든 물건이 가방에 들어간다면 "성공!"이라고 말합니다. 만약 물건이 넘쳐나면 "실패"라고 말합니다. 로봇은 가방에 물건이 들어가기만 하면 된다고 배우며, 가방의 절반이 비어 있거나 깨지기 쉬운 물건 위에 무거운 물건을 싣더라도 상관없습니다.
FORGE 방식 (품질 인식 보상): 로봇에게 "성공은 좋지만, 같은 공간에 더 많은 물건을 넣거나 더 가볍게 배치할 수 있다면 더 큰 보상을 받는다"고 말합니다. 로봇은 완벽해질 때까지 계속 개선하려고 노력하는 법을 배웁니다.

이 논문은 현재의 AI 모델들이 "유효한" 해결책 (작동하는 경로) 을 찾는 데는 뛰어나지만, "최적의" 해결책 (절대적으로 가장 좋은 경로) 을 찾는 데는 매우 서툴다고 주장합니다. 이는 물류, 일정 조정, 네트워크 설계와 같은 실제 세계의 문제들에 큰 영향을 미치며, 이러한 문제들은 NP-하드 문제 (완벽하게 해결하는 것이 극도로 어려운 수학 문제) 로 알려져 있습니다.

2. 해결책: "Forge" 공장

저자들은 이러한 로봇들을 더 나은 최적화 전문가로 훈련시키기 위해 FORGE-ENGINE이라는 공장을 구축했습니다. 이는 AI 의 뇌를 위한 체육관과 같지만, 역기를 드는 대신 복잡한 퍼즐을 푸는 곳입니다.

이 공장에는 세 가지 주요 기계가 있습니다:

생성기 (The Generator): 이 기계는 수백만 개의 연습 퍼즐을 생성합니다. 5 조각 퍼즐처럼 쉬운 것부터 1,000 조각 퍼즐처럼 어려운 것까지 다양한 난이도로 만들 수 있습니다.
검증기 (The Validator): 이는 엄격한 심판입니다. 로봇의 해결책이 실제로 규칙을 따르는지 확인합니다 (예: "모든 도시를 정확히 한 번씩 방문했는가?").
휴리스틱 솔버 (비밀 무기): 이것이 가장 중요한 부분입니다. 거의 완벽하게 퍼즐을 해결하는 초고속 전통적인 컴퓨터 프로그램입니다. 이는 "골드 스탠다드"나 코치 역할을 합니다.
- 비유: 로봇이 시험을 치르는 학생이라고 상상해 보세요. 검증기는 답이 올바르게 쓰였는지 확인합니다. 휴리스틱 솔버는 정답지를 가진 선생님입니다. 로봇이 만점의 80% 를 얻었다면, 선생님은 단순히 "틀렸다"고 말하지 않습니다. 대신 "80% 를 맞췄어. 90% 까지 맞춰봐"라고 말합니다. 이는 로봇에게 단순한 "합격/불합격" 대신 연속적인 점수를 제공합니다.

3. 훈련 방법: "산을 오르기"

로봇을 즉시 1,000 조각 퍼즐에 던져 넣을 수는 없습니다. 혼란을 느껴 포기할 것이기 때문입니다. 따라서 이 논문은 커리큘럼 학습 전략을 사용합니다:

쉬운 단계: 로봇이 규칙을 배우기 위해 작고 간단한 퍼즐을 풉니다.
중간 단계: 퍼즐이 더 커집니다. 로봇은 미리 계획을 세우는 법을 배웁니다.
어려운 단계: 로봇이 거대하고 복잡한 퍼즐에 도전합니다.
재플레이 트릭: 저자들은 앞만 보고 진행하면 (쉬움 → 어려움) 로봇이 쉬운 방법을 잊어버린다는 것을 발견했습니다. 따라서 그들은 로봇이 주기적으로 쉬운 단계와 중간 단계를 재플레이하도록 만들었습니다. 이는 어려운 것을 배우는 동안에도 기술을 날카롭게 유지시킵니다.

4. 결과: 더 똑똑한 뇌

그들은 새로운 로봇 (FORGE) 을 10 가지 유형의 어려운 퍼즐 (배송 트럭을 위한 최단 경로 계획이나 충돌 없는 회의 일정 조정 등) 에서 테스트했습니다.

점수: 로봇은 단순히 어떤 해결책을 찾은 것이 아니라, 훌륭한 해결책을 찾았습니다. 유명한 GPT-4o 모델을 압도적인 차이로 능가했습니다. GPT-4o 는 약 62% 의 확률로 유효한 해결책을 찾은 반면, FORGE 는 93% 의 확률로 찾았습니다. 더 중요하게는 FORGE 의 해결책이 "완벽한" 답에 훨씬 더 가까웠습니다.
보너스 효과: 이것이 가장 멋진 부분입니다. 그들이 로봇을 이러한 어려운 최적화 퍼즐로 훈련시켰을 때, 로봇은 퍼즐만 더 잘하게 된 것이 아니라 다른 모든 것도 더 잘하게 되었습니다.
- 수학 실력이 향상되었습니다.
- 논리력이 향상되었습니다.
- 지시를 따르는 능력이 향상되었습니다.
- 비유: 체스 선수를 그랜드마스터로 훈련시키는 것과 같습니다. 그 과정에서 그들은 체스뿐만 아니라 일상생활에서의 전략, 인내심, 계획 수립 능력도 향상됩니다. 이 논문은 "최적화" (가장 좋은 해결책을 찾는 것) 를 배우는 것이 AI 에게 깊이 생각하고 답을 다듬는 보편적인 기술을 가르쳐 주며, 이는 모든 종류의 작업에 도움이 된다고 제안합니다.

요약

이 논문은 AI 를 훈련시키는 새로운 방법인 FORGE를 소개합니다. 단순히 AI 에게 "올바른" 답을 얻는 법을 가르치는 대신, 해결책의 질에 대한 지속적인 점수를 제공함으로써 가장 좋은 가능한 답을 찾도록 가르칩니다. 이는 AI 를 현재의 최상위 모델들보다 어려운 수학 퍼즐을 더 잘 해결할 뿐만 아니라, 일반적인 추론, 논리, 지시 따르기에서도 더 똑똑해지는 마스터 최적화 전문가로 변모시킵니다.

기술 요약: FORGE-ENGINE

문제 정의

강화 학습과 검증 가능한 보상 (RLVR) 을 통해 대규모 언어 모델 (LLM) 이 추론 벤치마크 (수학, 코딩, 논리) 에서 상당한 성과를 거두었음에도 불구하고, 기존 평가 패러다임은 **최적성 (optimality)**보다는 **정확성 (correctness, 실현 가능성)**에만 집중한다는 치명적인 한계를 안고 있습니다. 물류나 자원 할당과 같은 많은 실제 시나리오에서는 단순히 "유효한" 해법만으로는 부족하며, 목적 함수를 최대화하거나 최소화하는 해법을 찾는 것이 목표입니다. 현재 벤치마크는 대부분 이진 보상 (통과/실패) 에 의존하는데, 이는 모델을 최적 해법으로 이끄는 데 필요한 밀집된 연속적 피드백을 제공하지 못합니다. 더 나아가 기존 NP-하드 벤치마크는 최적의 정답 값을 생성하는 메커니즘이 부재하여 세밀한 보상 계산을 불가능하게 만들고, 훈련을 비효율적인 이진 피드백 루프로 되돌리게 합니다.

방법론: FORGE-ENGINE

저자들은 Quality-Aware RLVR을 사용하여 NP-하드 최적화 문제에서 LLM 을 훈련하고 평가하기 위한 포괄적인 프레임워크인 FORGE-ENGINE을 제안합니다. 이 프레임워크는 세 가지 핵심 구성 요소로 이루어져 있습니다:

1. 데이터 구축 파이프라인

이 프레임워크는 그래프 클러스터링, 자원 스케줄링, 그래프 분할, 부분집합 선택, 경로 계획 등 5 가지 범주에 걸친 10 가지 서로 다른 NP-하드 작업 전반에 걸쳐 훈련 데이터를 생성하기 위해 확장 가능한 4 단계 파이프라인을 사용합니다.

제어 가능한 생성기: 실현 가능한 해법의 존재를 보장하는 "설계 기반 구축 (construction-by-design)" 접근 방식을 사용하여 난이도 (쉬움, 중간, 어려움) 가 단계별로 구분된 무한한 인스턴스를 생성합니다.
규칙 기반 검증기: 인간 라벨링 없이 절대적인 정확성을 보장하기 위해 제약 조건 충족을 자동으로 검증하고 목적 함수 값을 계산합니다.
휴리스틱 솔버: 각 인스턴스에 대해 준최적 기준선을 계산하는 작업별 휴리스틱 알고리즘 (예: TSP 를 위한 2-opt 가 적용된 멀티-스타트 최단 이웃) 을 사용하는 것이 핵심 혁신입니다. 이러한 기준선은 보상 계산을 위한 정답 (ground truth) 역할을 합니다.
커리큘럼 보정: 점진적 학습을 촉진하기 위해 목표 성공률 (예: 쉬움: 70-90%, 어려움: 10-40%) 을 달성할 수 있도록 난이도 수준을 경험적으로 보정합니다.

2. FORGE-BENCH

훈련 중에는 볼 수 없도록 설계된 1,000 개의 고복잡도 인스턴스 (작업당 100 개) 로 구성된 엄격한 평가 벤치마크입니다. 이전 연구들과 달리, 이 벤치마크는 두 가지 상호 보완적인 지표를 사용하여 모델을 평가합니다:

성공률 (SR): 모델이 모든 제약 조건을 만족하는 유효한 해법을 생성한 인스턴스의 비율.
품질 비율 (QR): 휴리스틱 기준선에 대한 해법의 품질을 측정하는 연속적 지표 (예: 최소화 문제의 경우 $QR = \text{휴리스틱} / \text{모델}$ ). 이는 단순히 실현 가능한 해법과 준최적 해법을 구분합니다.

3. 품질 인식 RLVR 프레임워크

훈련 전략은 휴리스틱 기준선에서 파생된 세밀한 연속 보상으로 희소한 이진 신호를 대체합니다.

보상 함수: 계층적 보상 시스템이 세 가지 차원에서 출력을 평가합니다:
1. 형식 보상 ( $R_{format}$ ): 구조화된 추론 (예: <thought> 태그) 을 보장합니다.
2. 실현 가능성 보상 ( $R_{feasibility}$ ): 제약 조건 위반 시 페널티 (예: -1.5) 를 부과하고 유효한 해법의 경우 최적성 점수를 통과시킵니다.
3. 최적성 보상 ( $R_{optimal}$ ): 모델의 목적 함수 값과 휴리스틱 기준선의 비율에 기반한 연속 점수로, 최적화를 위한 밀집 피드백을 제공합니다.
다단계 커리큘럼 재생: "콜드 스타트" 문제와 파기적 망각을 완화하기 위해 훈련은 (쉬움 $\to$ 중간 $\to$ 어려움) 의 순환 전략을 사용하여 난이도 수준을 여러 번 반복하며, 기초 기술을 강화하면서 점진적으로 복잡한 최적화 문제를 해결합니다.

주요 결과

실험은 3 단계에 걸쳐 총 15,000 개의 예제 (15K) 로 훈련된 Qwen2.5-7B-Instruct-1M에서 수행되었습니다.

도메인 내 성능: 결과 모델인 FORGE는 FORGE-BENCH 에서 93.1% 의 성공률과 46.6% 의 품질 비율을 달성했습니다. 이는 GPT-4o(성공률 62.1%, 품질 비율 36.2%) 를 크게 능가하며, 기본 모델의 성능 (성공률 29.6%, 품질 비율 14.6%) 을 훨씬 상회합니다.
도메인 외 (OOD) 일반화: FORGE-ENGINE 훈련은 다양한 추론 작업으로 이전되어 다음과 같은 향상을 가져왔습니다:
- 지시 따르기: +6.1%
- 지식 추론: +4.1%
- 수학: +2.2%
- 논리: +1.2%
어블레이션 연구:
- 보상 설계: 품질 인식 보상은 이진 보상 대비 해법 품질을 28.8% 향상시켜 보상 해킹을 방지하고 모델을 진정한 최적성으로 이끕니다.
- 커리큘럼 전략: 다단계 커리큘럼 재생은 선형 단일 통과 전략보다 우수한 성능을 발휘하여 성능 한계를 돌파하고 정체성을 방지합니다.
- 작업 다양성 대 양: 다양한 10 개 작업으로 훈련하는 것이 더 적은 작업에 더 많은 데이터로 훈련하는 것보다 일반화 성능이 더 뛰어났으며, 이는 다양한 문제 구조에 노출되는 것이 추론 능력의 주요 동인임을 시사합니다.
- RLVR 대 SFT: 최적 해법에 대한 지도 미세 조정 (SFT) 은 도메인 내 성능을 향상시켰으나, 도메인 외 성능이 파기적으로 저하됨 (-12.0 점) 을 보였습니다. 반면, RLVR 은 견고하고 이전 가능한 제약 조건 충족 전략을 육성했습니다.

의의 및 주장

본 논문은 휴리스틱 솔버를 통합하여 세밀한 최적성 보상을 제공함으로써 NP-하드 최적화 문제에 RLVR 을 성공적으로 적용한 최초의 포괄적인 프레임워크인 FORGE-ENGINE을 주장합니다.

저자들은 이 연구가 LLM 추론에서 실현 가능성과 최적성 사이의 격차를 해소한다고 주장합니다. 이진 정확성을 넘어선 이 프레임워크는 모델이 반복적 최적화 탐색에 참여할 수 있게 합니다. 특히, 이 논문은 최적화 훈련이 생성 및 자기 정제 능력을 갖춘 이전 가능한 "최적화 마인드셋"을 육성하여 특정 최적화 작업을 넘어 더 넓은 추론 능력을 향상시킨다는 경험적 증거를 제시합니다. 연구 결과에 따르면 RLVR 을 확장하기 위해서는 단순한 데이터 양보다 작업 다양성과 품질 인식 보상이 더 중요한 요소입니다.

이 연구는 최적화 기반 추론과 LLM 을 통합하기 위한 기초적인 단계로 제시되며, 복잡한 추론에 대한 향후 연구를 위한 확장 가능한 인프라와 벤치마크를 제공합니다.