기술 요약: PathWise

문제 정의

자동 휴리스틱 설계 (AHD) 는 조합 최적화 문제 (COP) 에 대한 휴리스틱 알고리즘을 자동으로 생성하여 수동으로 설계된 전문가 의존도를 낮추는 것을 목표로 합니다. 최근 대규모 언어 모델 (LLM) 이 진화적 탐색 과정에 통합되면서 AHD 를 가능하게 했지만, 기존 프레임워크는 상당한 한계를 겪고 있습니다. 집단 기반 방법은 고정된 진화 규칙과 정적 프롬프트 템플릿에 의존하여 단시안적인 휴리스틱 생성, 중복 평가, 그리고 조기 수렴을 초래합니다. 몬테카를로 트리 탐색 (MCTS) 을 사용하는 것과 같은 트리 기반 방법은 검색 공간의 의미적 이해보다는 성능 통계에 의해 주도되는 계층적 구조를 부과합니다. 결정적으로, 현재 접근 방식은 휴리스틱이 어떻게 유도되는지, 편집이 세대를 거쳐 어떻게 전파되는지, 또는 수정이 성공하거나 실패하는 이유에 대한 상태 유지적 (stateful) 의미 표현이 부족합니다. 이로 인해 LLM 호출의 비효율적인 사용과 과거 결정을 효과적으로 계승하지 못하는 문제가 발생합니다.

방법론

저자들은 PathWise(자기 진화 LLM 을 통한 자동 휴리스틱 설계를 위한 세계 모델을 활용한 계획) 를 제안합니다. 이는 휴리스틱 생성을 함의 그래프 (entailment graph) 상의 순차적 의사결정 과정으로 형식화하는 새로운 다중 에이전트 추론 프레임워크입니다. 이 그래프는 검색 궤적의 컴팩트한 상태 유지 메모리 역할을 합니다.

핵심 구성 요소

1. 함의 그래프 ($G = (V, E)$):

   • 표준 진화 트리나 집단과 달리, 함의 그래프는 유도 이력을 인코딩합니다.
   • 노드 ($v$): 휴리스틱 코드 ($h$), 자연어 유도 근거 ($\kappa$), 알고리즘적 설명 ($d$), 성능 지표 ($P(h; D)$), 그리고 부모 메타데이터 ($PM$) 를 포함하는 튜플을 나타냅니다.
   • 간선 ($E$): 부모 집합을 자식 노드에 연결하며, 부모로부터 자식을 유도하는 데 사용된 구체적인 근거를 인코딩합니다.
   • 이 구조는 시스템을 단계들을 고립된 샘플링 사건으로 취급하는 대신, 유도 이력에 기반하여 미래 의사결정을 조건화할 수 있게 합니다.

2. 다중 에이전트 시스템:
   이 프레임워크는 두 가지 시간 규모 (외부 집단 업데이트 및 내부 함의 단계) 에 걸쳐 계획, 실행, 성찰의 조정된 사이클을 통해 작동합니다:

   • 정책 에이전트 ($\pi_p$): 고수준 계획자 역할을 합니다. 현재 상태 (함의 그래프의 프론티어) 를 관찰하고, 선택된 부모 노드 집합 ($S$) 과 자연어 유도 근거 ($\kappa$) 로 정의된 행동을 제안합니다. 이를 통해 정책은 고정된 템플릿에 의존하는 대신 동적으로 새로운 연산자 유형을 발명할 수 있습니다.
   • 세계 모델 에이전트 ($\pi_{wm}$): 저수준 실행자 역할을 합니다. 정책의 고수준 행동을 선택된 부모와 지시에 조건부로 실행 가능한 휴리스틱 코드 (롤아웃) 로 변환합니다.
   • 비평가 에이전트:
     • 정책 비평가 ($\pi_{p\_critic}$): 정책 행동 (부모 선택 및 지시) 의 결과를 분석하여 미래 진화 전략을 안내하는 라우팅된 성찰을 제공합니다.
     • 세계 모델 비평가 ($\pi_{wm\_critic}$): 최상위 및 최하위 성능을 보이는 휴리스틱 롤아웃을 비교하여 코드 합성 품질에 대한 피드백을 제공하며, 세계 모델이 알고리즘 구조와 효율성을 정제하도록 안내합니다.

3. 탐색 과정:

   • 외부 루프: 루트 노드의 집단을 유지합니다.
   • 내부 루프: 현재 집단을 기반으로 함의 그래프를 점진적으로 구축합니다. 각 단계에서 시스템은 여러 행동과 롤아웃을 샘플링하고, 가장 좋은 결과 노드를 선택하여 그래프를 업데이트합니다.
   • 다양성 메커니즘: 낮은 다양성 출력을 방지하기 위해 PathWise 는 프롬프트 수준의 다양성(탐색적 구문으로 프롬프트를 교란) 과 상태 셔플링(위치 편향을 완화하기 위해 노드 순서를 무작위화) 을 사용합니다.

주요 기여

1. 하이브리드 그래프 - 집단 형식화: 저자들은 유도 근거와 성능 이력을 인코딩하는 함의 그래프를 도입하여 정책과 세계 모델 상호작용을 위한 공유 상태로 활용하는 형식화를 제시합니다.
2. 조정된 다중 에이전트 프레임워크: 정책 에이전트가 진화 전략을 통제하고, 세계 모델이 코드 생성을 실행하며, 비평가 에이전트가 라우팅된 성찰을 제공하는 시스템으로, LLM 파라미터를 업데이트하지 않고도 상태 인식형 자기 진화 휴리스틱 생성을 가능하게 합니다.
3. 프롬프트 수준의 다양성: 부모 선택과 휴리스틱 롤아웃의 다양성을 보장하여 함의 그래프 상에서 더 넓은 탐색을 가능하게 하는 메커니즘입니다.
4. 실증적 검증: PathWise 가 더 적은 평가로 더 강력한 휴리스틱을 발견하고, 더 빠른 수렴을 달성하며, 다양한 COP 에 걸쳐 더 큰 문제 크기로 효과적으로 확장됨을 보여주는 광범위한 실험 결과입니다.

실험 결과

PathWise 는 Traveling Salesman Problem (TSP), Knapsack Problem (KP), Capacitated Vehicle Routing Problem (CVRP), Multiple Knapsack Problem (MKP), Orienteering Problem (OP), Bin Packing Problem (BPP) 을 포함한 여러 NP-하드 COP 에 대해 평가되었습니다. 이 프레임워크는 단계별 구성 (Step-by-Step Construction), 개미 집단 최적화 (ACO), 그리고 유도된 지역 탐색 (GLS) 의 세 가지 검색 패러다임에서 테스트되었습니다.

• 성능: PathWise 는 최신 LLM 기반 AHD 베이스라인 (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) 과 수동으로 설계된 휴리스틱을 일관되게 능가했습니다. 도메인 내 및 도메인 외 테스트 세트 모두에서 더 낮은 최적성 격차를 달성했습니다.
• 효율성: PathWise 는 더 나은 휴리스틱으로 더 빠르게 수렴했습니다. 여러 실험에서 PathWise 는 베이스라인이 1000 회 평가를 허용받은 반면, 단 500 회 평가만으로 우수한 성능을 달성했습니다.
• 확장성: 이 방법은 더 큰 문제 크기 (예: $N=200$인 TSP, $N=500$인 KP) 와 다양한 추론 수준을 가진 다른 LLM 백본 (GPT-4o-mini, GPT-5-nano) 에 대해 강력한 일반화 능력을 보여주었습니다.
• 절대 연구: 비평가 에이전트나 다양성 메커니즘을 제거하면 성능이 크게 저하되어, 상태 인식형 피드백과 탐색의 필요성을 확인했습니다.

중요성과 주장

이 논문은 PathWise 가 "시행착오 진화"에서 "추론을 통한 상태 인식 계획"으로의 전환을 나타낸다고 주장합니다. 휴리스틱 발견을 함의 그래프 상의 순차적 의사결정 과정으로 취급함으로써, 시스템은 과거 결정을 계승하고 세대 간 유도 정보를 재사용하거나 회피할 수 있습니다.

저자들은 PathWise 가 LLM 파라미터를 업데이트하지 않는다는 점에서 학습이 필요 없는 (training-free) 방식임을 강조합니다. 대신 자연어 성찰을 통해 강화된 LLM 의 사전 학습 지식을 활용합니다. 그 중요성은 검색 과정의 구조화된 메모리를 제공함으로써 기존 AHD 방법의 단시안성을 극복하고, 중복 평가를 줄이며 복잡한 조합 문제에 대한 고품질 휴리스틱의 더 효과적인 발견을 가능하게 한다는 데 있습니다. 이 연구는 유도 이력에 대한 구조화된 추론이 LLM 기반 자동 알고리즘 설계를 확장하는 데 필수적인 요소임을 시사합니다.