An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization

기술적 요약: 조합 최적화에서 신경 및 휴리스틱 솔저를 비교하기 위한 분할 효율성 임계값

문제 제기
본 논문은 운영 연구 및 그린 AI 에서 널리 제기되는 비판, 즉 신경망 기반 조합 최적화 (CO) 솔저가 GPU 훈련에 따른 막대한 에너지 비용으로 인해 전통적인 CPU 기반 메타휴리스틱보다 본질적으로 에너지 효율이 낮다는 비판을 다룹니다. 저자들은 이 비판이 결함이 있는 추론 단계에 의존한다고 주장합니다. 이는 훈련의 대규모 고정 선제 비용을 영구적인 불합격 사유로 잘못 취급하여, 신경 솔저는 매우 작고 분할 가능한 인스턴스당 추론 비용을 발생시키는 반면, 메타휴리스틱은 해결된 모든 인스턴스에 대해 일정한 한계 비용을 발생시킨다는 사실을 무시합니다. 본 논문은 이러한 두 가지 비용 프로파일 (고정 대 한계) 을 스칼라로서 비교 가능하지 않으며, 특정 배포 볼륨에 걸쳐 비교되어야 한다고 제시합니다.

방법론: 분할 효율성 임계값 (AET)
이 비교를 공식화하기 위해, 본 논문은 세 가지 핵심 구성 요소로 정의된 정량적 프레임워크인 **분할 효율성 임계값 (AET)**을 도입합니다:

1. AET 의 정의: AET 는 신경 솔저 ($M$) 의 누적 에너지 (또는 탄소) 가 기준 휴리스틱 솔저 ($B$) 의 것과 같아지는 배포 볼륨 ($N$) 입니다. 이는 다음과 같이 계산됩니다:
   $$AET = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   이 계산은 품질 - 실행 가능성 제약을 따릅니다: 신경 솔저의 기대 최적성 갭이 사용자 정의 허용 오차 $\delta$만큼 기준의 갭을 초과하지 않아야 합니다. 이 제약은 "빠르지만 부정확한" 솔저가 임계값을 인위적으로 낮추는 것을 방지합니다.

   • $E_{train}(M)$에는 최종 수렴 모델뿐만 아니라 모든 하이퍼파라미터 탐색, 실패한 실행, 프로토타입의 누적 비용이 포함됩니다.
   • $E_{inst}^{NN}$는 단일 인스턴스 벽 시간 대신 배치 처리량 ($\tau_{NN}$) 을 기반으로 계산된 인스턴스당 추론 에너지로, GPU 실행의 병렬 특성을 반영합니다.

2. 수명 주기 회계 (내재 탄소): 이 프레임워크는 운영 에너지 회계를 하드웨어 제조에서 발생하는 내재 탄소를 포함하도록 확장합니다. 이 비용은 구성 가능한 하드웨어 수명 (기본값 5 년) 에 걸쳐 선형적으로 분할되며, 신경 가속기와 기준 CPU 모두에 대칭적으로 적용됩니다. 이는 비교가 전체 수명 주기 영향을 고려하도록 보장하며, 고투과율 GPU 가 효율적으로 활용될 경우 CPU 보다 인스턴스당 내재 부담이 낮을 수 있음을 지적합니다.

3. 점근적 구조적 논증: 본 논문은 (명제 1) 을 증명하여, 신경 솔저의 인스턴스당 에너지가 기준보다 엄격하게 낮을 경우 ($E_{inst}^{NN} < E_{inst}^{base}$), $N \to \infty$로 갈수록 그들의 누적 에너지 비율이 1 보다 엄격하게 낮은 상수로 수렴함을 보여줍니다. 특히, 이 한계는 훈련 비용, 데이터센터 오버헤드 (PUE), 또는 지역 탄소 강도에 무관하며, 이러한 요인이 양쪽에 대칭적으로 적용되는 한 성립합니다.

실험적 구체화 및 결과
이 프레임워크는 19 개의 문제 변형에 걸쳐 $n=20$명의 고객을 대상으로 한 다중 태스크 차량 경로 문제 (MTVRP) 환경에서 구체화되었습니다.

• 기준: PyVRP 에 구현된 하이브리드 유전 탐색 (HGS).
• 신경 솔저: 5 개의 시드에서 단일 GPU 를 통해 훈련된 학습된 정책.
• 주요 지표:
  • 인스턴스당 비율: 신경 솔저는 단일 스레드 HGS 기준 (1.32 Wh) 에 비해 인스턴스당 약 0.41 Wh를 소비하여 인스턴스당 약 2.4 배의 효율성 향상을 보입니다.
  • 훈련 비용: 중앙값 훈련 에너지는 121.5 Wh였습니다.
  • 교차점 (AET): 측정된 교차점은 약 $1.58 \times 10^5$개의 배포된 인스턴스에서 발생합니다. 이 볼륨 이상에서 신경 솔저는 총 누적 에너지 측면에서 더 에너지 효율적이 됩니다.
  • 민감도: 저자들은 배치 크기, 품질 허용 오차, 기준 스레드, 하드웨어 티어, 훈련 시드 등 5 축 민감도 표면을 분석합니다. 하드웨어 티어와 품질 허용 오차가 AET 값을 크게 이동시키지만, 비율의 구조적 수렴은 견고하게 유지됨을 발견합니다.

주요 기여

1. AET 의 공식화: 명시적 솔루션 품질 제약 하에서 신경 솔저의 손익분기점을 정량화하는 지표로, 논쟁을 수사적 수준에서 정량적 수준으로 이동시킵니다.
2. 수명 주기 교정: 운영 회계 방법론에 도전하며 내재 탄소를 대칭적으로 분할하여 포함합니다.
3. 점근적 증명: 훈련 비용이나 그리드 강도에 대한 교정 논쟁과 무관하게, 정성적 판단 (신경 솔저는 규모에서 승리함) 이 구조적으로 타당함을 수학적으로 증명합니다.
4. 개방형 계측: 에너지 추적 및 민감도 분석을 재현하기 위한 측정 프로토콜 및 스크립트 공개.

의의 및 주장
본 논문은 질문을 재구성함으로써 신경 CO 솔저에 대한 "에너지 효율성" 반박을 해결한다고 주장합니다. 이는 훈련이 비싸다는 전제에 대해서는 옳지만, 방법이 순효율성이 없다는 결론에 대해서는 틀렸다고 주장합니다.

• 정세 의존성: 신경 솔저는 AET 미만에서만 효율성이 낮습니다. AET 이상에서는 휴리스틱의 한계 비용이 무한히 누적되는 반면, 신경 솔저의 고정 비용은 완전히 분할됩니다.
• 구조적 우위: 본 논문은 직렬 휴리스틱 탐색에 비해 배치화된 신경 추론의 구조적 우위가 더 큰 문제 크기 ($n=50, 100$) 에서 효율성 격차가 크게 벌어질 것임을 시사합니다. 이는 휴리스틱 탐색 시간이 초선형적으로 확장되는 반면 신경 처리량은 상대적으로 안정적으로 유지되기 때문입니다.
• 겸손함: 저자들은 현재 결과가 $n=20$에서의 "예시적 구성"이라고 명시적으로 밝힙니다. 인스턴스당 비율 (0.41) 이 적당하며, 민감도 표면과 더 큰 문제 크기에 대한 완전한 실증 검증을 향후 작업으로 남겨두었다고 인정합니다. 본 논문은 신경 솔저가 보편적으로 우월하다고 주장하는 것이 아니라, 그들이 환경적으로 선호되는 선택이 되는 시기와 조건을 결정할 수 있는 프레임워크를 제공합니다.