🤖 machine learning

Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

이 논문은 메모리 효율적인 Mamba 백본과 훈련 중 로컬 서치(local search)에 의해 유도되는 디커플링된 배치형 직접 선호 최적화(Direct Preference Optimization) 파이프라인을 결합하여, TSP 및 CVRP 작업에서 우수한 성능과 하드웨어 활용도를 달성하는 효율적인 신경 조합 최적화 프레임워크인 ECO를 소개한다.

원저자: Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

게시일 2026-07-21

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

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

당신이 수천 명의 손님을 위한 거대한 연회를 준비하려는 숙련된 셰프라고 상상해 보십시오. 당신에게는 식재료 목록(노드)과 일련의 규칙이 있습니다: 모든 식재료를 정확히 한 번씩 방문해야 하며, 카트가 담을 수 있는 양만큼만 운반해야 하고, 가능한 한 빨리 주방으로 모든 것을 가져와야 합니다. 이것이 바로 **조합 최적화(Combinatorial Optimization)**의 세계입니다. 수십 년 동안 인간은 이 퍼즐을 풀기 위해 정교하게 손으로 만든 레시피(알고리즘)를 사용해 왔지만, 이는 느리고 새로운 연회가 열릴 때마다 인간 전문가가 매번 미세하게 조정해 주어야 했습니다.

최근 과학자들은 컴퓨터가 스스로 레시피를 학습하도록 가르치기 시작했습니다. 이 신경망을 수천 개의 사례를 지켜보며 다음 최선의 움직임을 추측하려고 노력하는 열정적인 견습생이라고 생각하십시오. 하지만 함정이 있습니다. 이 견습생들을 교육하는 데는 엄청난 비용이 듭니다. 이는 마치 견습생에게 요리 한 접시를 만들고, 맛을 보고, 버린 다음, 단 하나의 새로운 기술을 배우기 위해 이 과정을 수백만 번 반복하라고 요구하는 것과 같습니다. 이 과정은 너무 느리고 메모리를 많이 소모하여, 견습생이 실력을 갖추기도 전에 컴퓨터가 과부하로 멈춰버리곤 합니다. 연구자들의 큰 질문은 이것이었습니다: 우리는 이 AI 셰프들이 더 똑똑하면서도, 훨씬 더 빠르고 낭비 없이 배울 수 있도록 가르칠 수 있을까?

이 논문은 ECO(Efficient Combinatorial Optimization)라는 새로운 프레임워크를 소개하며 그 답이 "예"라고 말합니다. 저자들은 품질을 떨어뜨리지 않으면서 속도를 높이기 위한 두 가지 마법 같은 기술을 제안합니다. 첫째, 그들은 학습 스타일을 바꿉니다. 견습생이 요리하고, 맛보고, 하나의 요리마다 혼란스러운 루프 속에서 배우는 대신, ECO는 견습생이 한 번에 한 묶음의 요리를 만들고, 서로 비교한 뒤, 가장 좋은 것들로부터 한꺼번에 배우도록 합니다. 그들은 이를 "배치 선호 최적화(Batched Preference Optimization)"라고 부릅니다. 이는 선생님이 학생에게 열 개의 에세이를 보여주며, "이것이 제일 좋고 저것은 제일 나쁘다. 차이가 보이니? 이 차이를 보고 배워라"라고 말하는 것과 같습니다. 하나하나 채점하고 학생이 다시 쓰기를 기다렸다가 다음 것을 채점하는 방식과는 다릅니다.

둘째, 그들은 견습생의 두뇌를 업그레이드합니다. 대부분의 AI 모델은 "트랜스포머(Transformer)" 구조를 사용하는데, 이는 특정 페이지 사이의 연결 고리를 찾기 위해 서가의 모든 책을 읽어야 하는 사서와 같습니다. 만약 서가가 너무 길어지면(수천 개의 식재료), 사서는 압도되어 메모리가 부족해집니다. ECO는 이 대신 맘바(Mamba) 백본을 사용합니다. 맘바를 효율적인 스캐너라고 상상해 보십시오. 맘바는 서가를 매끄럽고 연속적인 흐름으로 읽으며, 필요한 것만을 기억하며 따라갑니다. 이를 통해 시스템은 컴퓨터가 멈추지 않고도 거대한 연회(수천 개의 노드)를 처리할 수 있습니다.

저자들은 이 기술을 두 가지 고전적인 문제인 외판원 문제(여러 도시를 방문하는 가장 짧은 경로 찾기)와 차량 경로 결정 문제(제한된 트럭 공간 내에서 여러 고객에게 패키지를 배달하기)에 대해 테스트했습니다. 그 결과 ECO는 믿기지 않을 정도로 빠르다는 것을 발견했습니다. 5,000개의 도시가 있는 문제에서 ECO는 테스트 세트를 단 2.5분 만에 해결한 반면, 다른 신경망 방식은 훨씬 오래 걸렸고 전통적인 정확한 해법(exact solvers)은 몇 시간이 걸렸습니다. 결정적으로, 저자들은 ECO가 최종 테스트 중에 "지역 탐색(local search, 빠른 수정)"을 사용하여 속임수를 쓰는 것이 아니라, AI가 훈련 과정에서 스스로 기술을 배웠음을 보여줍니다.

이 논문은 이 새로운 "배치형" 학습 스타일과 효율적인 맘바 두뇌를 결합함으로써, 이전보다 훨씬 더 빠르고 거대하고 복잡한 경로 문제를 해결하도록 AI를 훈련할 수 있음을 시사합니다. 결과는 ECO가 특히 문제가 매우 커질 때 기존의 최선인 AI 방법들과 경쟁할 수 있거나 오히려 더 나은 성능을 보인다는 것을 보여줍니다. 다만, 저자들은 "두뇌(인코더)"는 더 효율적이 되었지만, 다음 움직임을 선택하는 최종 단계는 여전히 상당한 작업량을 요구하기 때문에 전체 과정이 완벽하게 선형적이지는 않다는 점을 주의 깊게 언급하고 있습니다. 하지만 이는 과거의 방식들에 비해 엄청난 개선입니다.

기술 요약: 신경 조합 최적화의 효율성 재고: Mamba를 이용한 배치 선호도 최적화

1. 문제 정의

신경 조합 최적화(Neural Combinatorial Optimization, NCO)는 초기 포인터 네트워크(Pointer Networks)에서 트랜스포머 기반 아키텍처(예: AM, POMO) 및 생성적 흐름 네트워크(Generative Flow Networks)로 진화해 왔습니다. 이러한 방법들은 솔루션 품질을 개선했지만, 특히 **확장성(scalability)**과 학습 수렴 속도 측면에서 심각한 효율성 병목 현상에 직면해 있습니다.

본 논문은 기존 NCO 작업에서 발생하는 두 가지 주요 비효율성의 원인을 식별합니다:

학습 패러다임: 전통적인 온라인 강화 학습(Reinforcement Learning, RL)은 궤적 생성(rollout)과 파라미터 업데이트를 밀접하게 결합합니다. 이러한 "샘플링 후 업데이트" 루프는 GPU 병렬성을 충분히 활용하지 못하며, 모든 최적화 단계가 매번 새로운 자기회귀적 생성에 의존하게 만들어 수렴 속도를 늦추고 하드웨어 비용을 높입니다.
신경망 아키텍처: 최첨단 NCO 모델은 트랜스포머 아키텍처에 크게 의존합니다. FlashAttention과 같은 최적화에도 불구하고, 근본적인 토큰 간 상호작용은 시퀀스 길이에 대해 이차적( $O(N^2)$ )입니다. 이는 긴 라우팅 인스턴스(예: 수천 개의 노드를 가진 TSP)에서 메모리 폭발과 지연 문제를 야기하여, 대규모 문제에 대한 NCO의 실질적인 배포를 제한합니다.

본 연구가 다루는 핵심 질문은 다음과 같습니다: 솔루션 품질을 희생하지 않으면서 어떻게 NCO의 효율성을 개선할 수 있는가?

2. 방법론: ECO 프레임워크

저자들은 궤적 생성과 그래디언트 업데이트를 분리하고, 트랜스포머 백본을 Mamba 기반 아키텍처로 대체하는 효율성 중심의 프레임워크인 ECO를 제안합니다.

A. 배치 선호도 최적화 패러다임

ECO는 엄격한 온라인 RL에서 "배치 또는 업데이트 시 오프라인" 패러다임으로 전환하는 2단계 학습 워크플로우를 도입합니다.

1단계: 지도 학습 웜업 (Supervised Warm-up, SFT): 고품질의 사전 계산된 솔루션(LKH-3 또는 휴리스틱에 의해 생성됨)에 대한 행동 복제(Behavior Cloning)를 통해 정책을 초기화합니다. 이는 라우팅 제약 조건과 국소 최적성에 대한 기본적인 이해를 제공합니다.
2단계: 반복적 직접 선호도 최적화 (Iterative Direct Preference Optimization, DPO): PPO에서와 같이 별도의 가치 함수(Critic)를 학습하는 대신, ECO는 쌍체 선호도(pairwise preferences)로부터 정책을 직접 최적화하기 위해 DPO를 사용합니다.
- 워크플로우: 현재 정책이 일련의 후보 솔루션을 생성합니다. 투어 길이(tour length)를 기준으로 선호 쌍(승자/패자)을 구성합니다.
- 참조 모델 (Reference Model): KL 발산(KL divergence)을 억제하여 반복적인 개선을 안정화하기 위해 참조 모델( $\pi_{ref}$ )을 일정 주기( $T$ 스텝마다)로 업데이트합니다.
- LS 증강 부트스트래핑 (LS-Augmented Bootstrapping): 정책이 개선됨에 따라 보상 마진이 좁아져 발생하는 그래디언트 소실(vanishing gradients)을 방지하기 위해, 훈련 중에 모델이 생성한 솔루션에 경량 로컬 서치(Local Search, LS) 연산자(예: 2-opt, 3-opt)를 적용합니다. 정제된 솔루션이 "승자"가 되고, 가공되지 않은 출력이 "패자"가 됩니다. 결정적으로, 로컬 서치는 추론 시에는 절대 사용되지 않으며, 오직 신경 정책으로 증류될 더 강력한 훈련 신호를 구축하는 데만 사용됩니다.

B. 혼합 Mamba 기반 아키텍처

트랜스포머의 이차적 메모리 스케일링 문제를 해결하기 위해, ECO는 맞춤형 Mamba(State Space Model) 아키텍처를 채택합니다.

재귀적 Mamba 인코더 (Recurrent Mamba Encoder): 노드 시퀀스를 처리하기 위해 적층된 Mamba 레이어(S6 설정)를 사용합니다. 트랜스포머와 달리, Mamba는 선형 메모리 시퀀스 모델링을 사용합니다. Mamba의 비순열 치환 불변성(non-permutation-equivariant) 특성을 처리하기 위해, 인코딩 전 입력을 정규화(예: Morton/Z-order 코드로 정렬)합니다.
S4 디코더: 훈련 중에는 병렬 교사 강제(teacher-forced) 계산을 수행하고, 추론 중에는 효율적인 재귀적 상태 업데이트를 수행하는 S4 스타일의 레이어를 사용합니다.
자기회귀적 스코어링 (Autoregressive Scoring): 프레임워크는 표준적인 자기회귀적 후보 스코어링(포인터 스타일의 호환성 스코어링) 단계를 유지합니다. 저자들은 인코더와 재귀적 상태 업데이트는 선형이 되지만, 현재 상태를 모든 가능한 후보와 비교해야 하므로 최악의 경우 액션 스코어링은 여전히 이차적( $O(N^2)$ )임을 명시적으로 언급합니다. 그러나 이 아키텍처는 인코더 메모리 압박과 재귀적 상태 비용을 크게 줄여줍니다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 설명합니다:

최초의 Mamba 기반 NCO 솔버: 저자들은 Mamba에 기반한 최초의 NCO 솔버를 소개하며, Mamba가 인코더 메모리 스케일링과 재귀적 디코딩 상태 비용을 줄이지만 단순한 자기회귀적 후보 스코어링은 여전히 이차적임을 보여주는 복잡도 분해를 제공합니다.
효율성 중심 프레임워크: 맞춤형 Mamba 아키텍처, 2단계 배치 선호도 최적화 파이프라인(SFT + Iterative DPO), 그리고 훈련을 안정화하고 선호도 마진을 증폭하기 위한 로컬 서치 가이드 부트스트래핑의 새로운 통합을 제시합니다.
포괄적인 경험적 분석: TSP 및 CVRP에 대한 광범-한 사례 연구를 통해, ECO가 대규모 인스턴스에서 상당한 효율성 이득을 얻으면서도 신경 기반 성능에서 최고 수준이거나 경쟁력 있는 성능을 달성함을 입증합니다. 분석에는 복잡도 분해, 순열 민감도 테스트, 각 설계 구성 요소에 대한 절제 실험(ablation studies)이 포함됩니다.

4. 실험 결과

실험은 단일 NVIDIA A800 GPU를 사용하여 TSP ( $N \in \{200, 500, 1000, 5000\}$ ) 및 CVRP ( $N \in \{100, 200, 500, 1000\}$ )에 대해 수행되었습니다.

솔루션 품질: ECO는 대부분의 규모에서 신경 기반 베이스라인(AM, POMO, LEHD, CNF, GFlowNet-HBG)과 대등하거나 더 나은 결과를 달성했습니다.
- TSP5000에서 ECO는 **5.49%**의 격차를 달성한 반면, 트랜스포머 기반 베이스라인(AM, POMO)은 70-89%를 초과하는 심각한 성능 저하를 겪었습니다.
- CVRP1000에서 ECO는 **2.87%**의 격차를 달성하여 다른 신경망 방법들을 능가하거나 대등한 성능을 보였습니다.
확장성 및 메모리:
- 메모리: 트랜스포머 베이스라인은 이차적 어텐션 메모리로 인해 80GB GPU에서 $N \approx 7000$ 부근에서 OOM(Out-Of-Memory) 오류를 발생시킵니다. ECO는 선형에 가까운 메모리 성장을 유지하며 $N=10,000$ 에서도 제한 범위 내(약 40GB)에 머뭅로 있습니다.
- 처리량 (Throughput): ECO는 긴 시퀀스에 대해 트랜스포머보다 훨씬 높은 추론 처리량을 유지합니다. 이는 메모리 제한에 걸리지 않고 더 큰 배치 크기를 활용할 수 있기 때문입니다.
학습 효율성:
- ECO는 표준 온라인 베이스라인보다 훨씬 빠르게 수렴합니다.
- 동일한 Mamba 백본을 사용하는 DPO와 PPO를 비교했을 때, ECO는 대등한 품질(TSP1000에서 4.84% vs 4.88% 격차)을 달성하면서도 훈련 시간을 34.5시간에서 10.2시간으로 단축했습니다.
구성 요소 분석:
- LS 부트스트래핑: LS 가이드를 제거하면 TSP1000 격차가 4.84%에서 9.55%로 증가하여, LS가 신경 정책으로 증류될 더 강력한 훈련 신호를 제공함을 확인했습니다.
- SFT 웜업: SFT 없이 훈련하면 불안정성과 발산이 발생하며, 이는 유능한 초기 정책의 필요성을 확인시켜 줍니다.
- 아키텍처: 동일한 DPO 목적 함수 하에서 Mamba를 트랜스포머로 교체하면 격차가 커지고(5.47% vs 4.84%) 훈련 시간이 증가하여, 아키텍처의 이점이 최적화 목적 함수와 독립적임을 입증합니다.

5. 의의 및 주장

본 논문은 ECO가 솔루션 품질에 치중되어 간과되었던 "효율성" 격차를 해결함으로써, 확장 가능하고 실용적인 신경 라우팅 솔버를 향한 중요한 진전임을 주장합니다.

선형성에 대한 완곡한 주장: 저자들은 ECO가 전체 구성적 추론을 선형으로 만드는 것은 아니라고 명시합니다. 이점은 구체적입니다: 인코더 메모리 스케일링과 재귀적 상태 비용을 줄이고, 스캔 커널(scan kernels)과 배치 업데이트를 통해 하드웨어 활용도를 높이는 것입니다. 최종 액션 스코어링 단계는 여전히 이차적입니다.
훈련 vs 추론: 핵심 발견은 로컬 서치가 엄격하게 훈련 시의 메커니즘이라는 점입니다. ECO가 절제된 버전보다 우수한 성능을 보이는 것은 추론 시의 후처리가 아니라, LS 가이드 신호로부터 학습된 개선된 네트워크 파라미터 덕분입니다.
하드웨어 인식: 본 연구는 하드웨어 인식 아키텍처(Mamba)와 효율적인 훈련 패러다임(Batched DPO)을 결합함으로써, 전통적인 어텐션 기반 모델이 메모리 제약으로 실패하는 지점에서 NCO 모델이 소비자급 또는 단일 GPU 하드웨어에서도 수천 개의 노드로 확장될 수 있음을 보여줍니다.

결론적으로, ECO는 선형 메모리 백본과 안정적인 배치 선호도 학습 파이프라인을 통합함으로써, 경쟁력 있는 솔루션 품질을 달성하는 동시에 훨씬 나은 메모리 및 처리량 프로필을 제공하는 확장 가능한 신경 라우팅의 강력한 방향을 제시합니다.