기술 요약: 조합 최적화(Combinatorial Optimization)를 위한 오픈 웨이트 LLM의 행동 및 표현

문제 정의

조합 최적화(Combinatorial Optimization, CO)는 알고리즘 개발 및 선택 과정에서 전문가 중심의 수동적인 프로세스에 크게 의존하고 있습니다. 머신러닝(ML)이 이 분야에 통합되기 시작했으나, 대규모 언어 모델(LLM)의 내부 표현 능력이 조합 최적화 문제 구조를 어떻게 파악하고 있는지에 대한 연구는 여전히 미개척 영역으로 남아 있습니다. 기존 연구들은 주로 LLM의 기능적 성능(예: 휴리스틱 또는 코드 생성)을 평가하는 데 집중할 뿐, 내부 표현이 문제 인스턴스나 알고리즘 동작에 관한 유의미한 정보를 포착하고 있는지에 대해서는 조사하지 않았습니다.

본 연구는 관찰 가능한 역량과 잠재적 이해 사이의 간극을 다룹니다. 본 연구는 동결된(frozen) 오픈 웨이트 LLM이 조합 최적화 문제(COP)의 구조적 및 수치적 정보를 인코딩하고 있으며, 이를 다운스트림 작업에 활용할 수 있는지 조사합니다. 특히, 본 연구는 직접적인 프롬프팅을 통해 명시적으로 회복(explicitly recovered) 가능한 정보와, 생성을 통해 접근할 수는 없더라도 은닉층(hidden layers) 내에 암묵적으로 인코딩(implicitly encoded) 되어 있는 정보 사이를 구분합니다.

방법론

저자들은 네 가지 벤치마크 문제인 빈 패킹(Bin Packing, BPP), 그래프 채색(Graph Coloring, GCP), 잡숍 스케줄링(Jobshop Scheduling, JSP), 배낭 문제(Knapsack Problem, KP)에 대해 **직접 질의(Direct Querying)**와 프로빙(Probing) 분석을 결합한 통합 실험 프레임워크를 제안합니다.

1. 실험 설정

• 모델: Llama instruct 제품군(3B, 8B, 70B)과 gpt-oss 추론 제품군(20B, 120B)을 포함하여 3B에서 120B 파라미터에 이르는 5개의 오픈 웨이트 LLM.
• 데이터: 문제 유형, 특징 복잡도 및 알고리즘 포트폴리오 전반에 걸친 커버리지를 보존하기 위해 기존 인스턴스 공간 분석(ISA) 연구의 층화된 5% 서브셋 사용.
• 표현 방식: 인스턴스는 세 가지 형식(표준 텍스트, 코드 형태인 MiniZinc, 자연어)으로 제시됨.
• 제약 조건: 모델의 고유한 표현을 평가하기 위해 특정 태스크를 위한 파인튜닝을 수행하지 않고, 모델을 "오프더쉘프(off-the-shelf)" 상태로 사용함.

2. 직접 질의 (명시적 회복)

모델에 특정 인스턴스 특징(예: 노드 수, 그래프 밀도, 평균 가중치)을 입력 텍스트로부터 직접 추출하도록 프롬프트를 제공했습니다.

• 프롬프트 변형:
  • 표준(Standard): JSON 형식의 수치 값을 직접 요청.
  • 생각의 사슬(Chain-of-Thought, CoT): 추론 과정(reasoning trace)을 거친 후 값을 요청.
  • 네이티브 추론(Native Reasoning, gpt-oss): Harmony 인터페이스를 통해 모델의 내부 추론 채널 활용.
• 평가: 예측된 값은 수작업으로 제작된 추출기를 통해 계산된 실제값(ground-truth)과 비교되었으며, 평균 절대 오차(MAE) 및 예측값이 실제값의 1% 이내에 드는 비율 등의 지표를 사용함.

3. 프로빙 (암묵적 디코더 가능성)

잠재적 표현을 평가하기 위해 저자들은 모델의 최종 레이어에서 추출된 은닉층 활성화 값(hidden-layer activations)을 추출했습니다.

• 풀링(Pooling): 평균(mean), 최대값(max), 마지막 토큰(last-token) 전략을 사용하여 활성화 값을 풀링함.
• 프로브(Probes): 추출된 벡터로부터 인스턴스 특징(회귀) 또는 최적의 알고리즘(분류)을 예측하도록 감독 학습된 모델(Ridge 회귀, MLP, LightGBM)을 훈련시킴.
• 목표: 생성 출력과는 독립적으로, 특징 정보가 잠재 공간에서 선형적 또는 비선형적으로 디코딩 가능한지 결정함.

4. 알고리즘 선택

프로빙 프레임워크를 인스턴스별 알고리즘 선택 작업으로 확장했습니다. LLM 유래 임베딩을 분류기의 입력으로 사용하여 포트폴리오 내 최적의 알고리즘을 예측하였으며, 그 성능을 수작업 및 ISA 기반 특징들을 사용한 베이스라인과 비교하였습니다.

주요 기여

1. 통합 프레임워크: 명시적 특징 추출(질의)과 잠재 표현 분석(프로빙)을 함께 평가하는 방법론을 도입함.
2. 규모 및 추론 분석: 5개의 모델(3B–120B)에 걸쳐 프레임워크를 검증하고, 생각의 사슬(CoT) 프롬프팅의 영향을 분석하여 모델 규모에 따른 의존성을 밝힘.
3. 신호의 분리: 명시적 검색과 잠재적 인코딩이 서로 다른 속성임을 보여주는 첫 대규모 증거를 제시함. 즉, 모델이 올바른 값을 생성하지 못하더라도 은닉 상태에는 해당 정보가 인코딩되어 있을 수 있음.
4. 대리 기술자(Surrogate Descriptors): LLM 은닉층 표현이 알고리즘 선택을 위한 효과적인 대리 기술자로 기능할 수 있음을 입증하였으며, 전통적인 수작업 특징과 유사한 예측력을 달성함.
5. 재현성: 연구의 발전을 위해 데이터셋, 코드 및 프롬프트를 공개함.

주요 결과

직접 질의 성능

• 특징 복잡도: 모델은 단순하고 직접 추출 가능한 특징(예: 개수)은 안정적으로 회복하지만, 구조적 계산이나 집계가 필요한 특징(예: 평균, 비율)에서는 크게 어려움을 겪음.
• 모델 규모: 낮은 복잡도의 특징에 대해서는 규모가 커질수록 성능이 향상되지만, 높은 복잡도의 특징에 대해서는 한계 효용이 체감됨.
• 생각의 사슬(CoT): CoT의 효과는 비단조적(non-monotonic)이며 규모에 따라 달라짐. 작은 모델(3B)에서는 성능을 저하시키고, 중간 규모 모델(8B)에서는 선택적인 이점을 제공하며, 대규모 모델(70B)에서는 일관되게 성능을 향상시킴. 그러나 CoT는 항상 계산 비용을 증가시킴.
• 실패 모드: 추론 중심 모델(gpt-oss)은 계산이 불확실할 때 자주 null을 반환하는 "교정된 절제(calibrated abstention)"를 보이는 반 반면, Llama 모델은 틀렸지만 그럴듯해 보이는 숫자를 내놓는 "과잉 확신적 환각(over-confident hallucinations)"을 보이는 경 경향이 있음.

프로빙 및 잠재 인코딩

• 잠재 vs 명시: 명시적 회복과 잠재적 디코딩 사이에는 일관된 격차가 존재함. 프로빙은 특히 복잡한 특징에 대해 직접 질의보다 더 높은 정확도를 달encing하는데, 이는 관련 정보가 은닉 상태에는 존재하지만 생성 과정을 통해서는 접근할 수 없음을 나타냄.
• 표현의 견고성: 잠재 표현의 예측 신호는 입력 표현(표준 vs 자연어 vs 코드 형태) 및 풀링 전략의 변화에 대해 견고함.

알고리즘 선택

• 예측 패리티(Predictive Parity): LLM 유래 임베딩은 5개 모델 모두에서 전통적인 수작업 및 ISA 기반 특징들과 대등한 수준의 알고리즘 선택 예측 정확도를 달성함.
• 분류기 의존성: 성능에 더 큰 영향을 미치는 것은 표현의 출처(LLM vs 수작업)보다 다운스트림 분류기(예: LightGBM vs Logistic Regression)의 선택이었음.
• 체계적 우위 부재: ISA 기반 특징이 LLM 유래 표현보다 체계적으로 우수하다거나 그 반대의 경우에 대한 강력한 증거는 발견되지 않음.

의의 및 주장

본 논문은 LLM이 명시적 추론 능력과 내부 표현 사이에 **기능적 비대칭성(functional asymmetry)**을 가지고 있다고 주장합니다. LLM이 아직 정밀한 수작업 특징 추출기를 대체할 만큼 신뢰할 수 있는 도구는 아니며(높은 계산 비용과 구조적 계산의 불확실성 때문), 그럼에도 불구하고 그들의 잠재 표현은 알고리즘 성능을 예측하는 데 충분한 통계적 규칙성을 포함하고 있는 효과적인 대리 기술자(surrogate descriptors) 역할을 할 수 있습니다.

저자들은 LLM 유래 표현이 다음과 같은 시나리오에서 가장 가치 있다고 주장합니다:

1. 수작업 특징 엔지니어링을 설계하기 어렵거나 비용이 너무 많이 드는 경우.
2. 인스턴스가 이질적이거나 비표준적인 형식으로 들어오는 경우.
3. 특정 특징 엔지니어링이 가능해지기 전, 문제 불가지론적(problem-agnostic)인 인스턴스 기술자가 필요한 경우.

본 연구는 LLM이 현재 결정론적인 방식으로 특징을 "계산"하여 정밀한 최적화 파이프라인에 적용하기에는 부족하지만, 내부 상태는 알고리즘 성능을 매우 잘 예측하는 신호를 인코딩하고 있으며, 이를 통해 수동적인 특징 설계 없이도 원시 인스턴스 데이터와 알고리즘 선택 사이의 간극을 메울 수 있다고 결론짓습니다.