기술 요약: EvoOptiGraph

문제 정의

자연어 의사결정 문제를 정식 수학적 최적화 모델(특히 혼합 정수 선형 계획법, MILP)로 자동 변환하는 것은 대규모 언어 모델(LLM)에게 여전히 큰 도전 과제입니다. 기존의 접근 방식은 다음과 같은 두 가지 주요 한계에 직면해 있습니다:

1. 훈련 데이터의 구조적 다양성 부족: 기존 벤치마크(예: NL4Opt, MAMO)는 매우 좁은 범위의 유효한 최적화 정식화만을 다룹니다. 데이터 합성 파이프라인은 주로 매개변수 섭동(perturbation)을 가하는 고정된 템플릿에 의존하며, 이는 견고한 일반화를 위해 필요한 광범위한 구조적 다양성을 생성하는 데 실패합니다.
2. 정적인 훈련 파이프라인: 대부분의 훈련 설정은 모델 훈련 전에 구축된 고정된 데이터셋을 사용합니다. 이러한 디커플링(decoupling)은 시스템이 모델이 실패하는 특정 구조적 영역을 식별하고, 해당 약점을 타겟팅하는 새로운 인스턴스를 생성하는 것을 방지합니다.

방법론: EvoOptiGraph

저자들은 명시적인 구조적 표현을 통해 데이터 생성과 모델 훈련을 결합하는 약점 기반 공진화(co-evolution) 프레임워크인 EvoOptiGraph를 제안합니다. 이 프레임워크는 세 가지 핵심 구성 요소로 이루어진 폐쇄 루프로 작동합니다:

1. 그래프 기반 구조적 표현

각 MILP는 속성이 부여된 이분 그래프(attributed bipartite graph) $G = (V, E, A)$로 표현됩니다:

• 노드: 결정 변수당 하나의 노드($V_{var}$)와 제약 조건 및 전용 목적 함수 노드당 하나의 노드($V_{con}$)가 존재합니다.
• 에지: 계수가 0이 아닌 변수와 제약 조건/목적 함수를 연결하며, 에지의 가중치는 계수 값을 저장합니다.
• 속성: 노드는 변수 범위, 유형(정수/연속/이진), 제약 조건의 부호(sense), 우변 값(RHS)과 같은 메타데이터를 저장합니다.
  이 표현 방식은 솔버 코드(예: Gurobi)로의 결정론적 컴파일을 가능하게 하며, 유효성을 보존하는 유전 연산을 지원합니다.

2. 그래프 진화를 통한 제어 가능한 데이터 생성

텍스트나 매개변수를 섭동시키는 대신, EvoOptiGraph는 유전 연산자를 사용하여 그래프 공간에서 최적화 인스턴스를 직접 진화시킵니다:

• 교차(Crossover): 부모 인스턴스 간에 호환 가능한 서브그래프를 교환합니다(예: 생산 스케줄링 제약 조건과 배낭 문제 제약 조건을 결합). 구조적 다양성을 높이기 위해 클래스 간 교차(cross-class crossover)가 허용됩니다.
• 변이(Mutation): 세 가지 수준에서 작동합니다:
  • 매개변수(Parameter): 계수, 범위 및 RHS 값을 섭동시킵니다.
  • 구조(Structural): 선형성을 유지하면서 변수 또는 제약 조건을 삽입, 삭제 또는 수정합니다.
  • 규모(Scale): 문제의 크기를 변경합니다(예: 공급/수요 노드 확장).
• 적합도 함수(Fitness Function): 후보군은 다음을 기준으로 점수가 매겨집니다:
  • 난이도(Difficulty): 솔버 통계(해 탐색 시간, 분기 한정 노드 수)로부터 도출됩니다.
  • 다양성(Diversity): 현재 모집단에 대한 그래프 편집 거리(GED)로 측정됩니다.
  • 약점 정렬(Weakness Alignment): 인스턴스의 구조적 특징과 모델의 현재 약점 벡터 사이의 코사인 유사도입니다.

3. 2단계 모델 훈련 및 공진화 루프

훈련 과정은 모델 피팅과 데이터 진화를 번갈아 수행합니다:

1. 웜업(SFT): 기본 LLM은 전문가 시드 생성기에서 생성된 검증된 인스턴스 집단에 대해 지도 미세 조정(Supervised Fine-Tuning)됩니다.
2. 약점 분석: 현재 모델은 홀드아웃 검증 세트에서 평가됩니다. XGBoost 분류기가 그래프 유래 구조적 특징을 기반으로 실패를 예측합니다. 오류 사례에 대해 SHAP 값이 계산되어, 모델 실패와 가장 밀접하게 연관된 구조적 특성을 강조하는 약점 벡터($w$)를 생성합니다.
3. 약점 기반 강화 학습(RLVR): 진화적 생성기는 구조적 특징이 약점 벡터($\tilde{f}_{weak}$)와 일치하는 인스턴스 쪽으로 편향됩니다. 그 후, **검증 가능한 보상을 사용하는 강화 학습(RLVR)**을 사용하여 모델을 업데이트합니다.
   • 보상(Rewards): 코드 실행 가능성, 해의 타당성, 실제 목적 함수와의 근접성(상대 오차 10% 이내), 그리고 정확한 정답 여부에 기반한 다단계 합산 방식입니다.
   • 최적화: Group Relative Policy Optimization (GRPO)가 사용되어, SFT 참조 모델에 대한 KL 발산 규제를 유지하면서 보상 극대화를 균형 있게 수행합니다.

주요 기여

1. 폐쇄 루프 공진화 프레임워크: 데이터 합성에서 모델 최적화를 분리하는 기존 방식과 달리, EvoOptiGraph는 그래프 수준의 약점 분석을 통해 이들을 연결함으로써 훈련 분포가 모델의 진화하는 실패 모드에 동적으로 적응할 수 있도록 합니다.
2. 제어 가능한 그래프 기반 생성기: 이 프레임워크는 속성이 부여된 이분 그래프 상에서 직접 교차와 변이를 수행하여, 단순한 매개변수 섭동을 넘어 구조적 수준의 진화를 가능하게 합니다. 이는 체계적인 구조적 다양성 탐색을 지원합니다.
3. 검증 가능한 피드백을 통한 약점 기반 적응: 시스템은 그래프 특징을 사용하여 구조적 오류 패턴을 진단하고, 해당 실패를 구체적으로 겨냥하는 새로운 인스턴스를 진화시키며, 솔버 기반의 검증 가능한 보상을 통해 모델을 최적화합니다.

실험 결과

본 프레임워크는 6개의 공개 벤치마크(NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR, IndustryOR)에서 평가되었습니다.

• 성능: EvoOptiGraph(8B 파라미터 백본 사용)는 매크로 평균 **Pass@1 정확도 78.1%**를 달성하였으며, 이는 더 큰 규모의 범용 모델(예: GPT-4o, DeepSeek-V3) 및 에이전트 방식(예: OptiMUS, Chain-of-Experts), 전문 미세 조정 베이스라인(예: ORLM, LLMOPT)을 능가하는 수치입니다.
• 데이터 다양성: EvoOptiGraph가 생성한 인스턴스는 원래 문제 유형과 **66.93%**의 구조적 유사성을 보였으며, 이는 텍스트 기반의 OptMATH가 달성한 **93.04%**의 유사성보다 현저히 낮았습니다(이는 더 높은 다양성을 의미함).
• 절제 연구(Ablation Studies): 공진화 루프를 제거했을 때(SFT 전용 또는 RL 전용), 각각 9.6%와 14.7%의 성능 저하가 발생하여 초기 지도 학습 기반의 접지(grounding)와 적응형 약점 기반 생성이 모두 필수적임을 확인했습니다.
• 일반화: 모델은 특히 ComplexOR 및 MAMO-Complex와 같이 구조적으로 까다로운 데이터셋에서 강력한 일반화 능력을 보여주었으며, 이는 타겟팅된 데이터 진화가 단순히 모델 규모를 키우는 것보다 효과적임을 시사합니다.

의의 및 주장

본 논문은 타겟팅된 데이터-모델 공진화가 최적화 모델링 작업에서 LLM을 개선하는 효과적인 전략임을 주장합니다. MILP를 그래프로 표현하고 이를 데이터 생성과 실패 진단 모두에 활용함으로써, EvoOptiGraph는 모델의 특정 사각지대를 해결하기 위해 훈련 분포를 지속적으로 업데이트하는 자기 개선 루프를 구축합니다.

저자들은 본 방식이 단순한 모델 규모 확장이나 정적 데이터셋에 의존하는 것보다 구조적 데이터 진화가 더 나은 결과를 낼 수 있음을 입증한다고 강조합니다. 이 프레임서은 유효한 최적화 정식화의 가설 공간과 실제 모델의 능력 사이의 간극을 성공적으로 메우며, 보다 적응적인 훈련 파이프라인을 향한 경로를 제시합니다.

인정된 한계점:

• 현재 프레임워크는 MILP에 국한되어 있으며, 사용 가능한 시드 생성기의 범위에 제한이 있습니다.
• 대규모 인스턴스에 대해서는 검증 비용이 많이 들 수 있습니다.
• 약점 벡터는 오류에 대한 인과적 설명이라기보다는 실용적인 우선순위 지정 신호 역할을 합니다.