기술 요약: 차이점 탐지는 구조적 이해가 아니다

문제 정의

대규모 언어 모델(LLM)은 다양한 추론 작업에서 인상적인 성능을 보여주었으나, 그래프 도메인에서의 진정한 구조적 추론 능력은 여전히 불분명하다. 유효한 구조적 추론의 근본적인 요구 사항은 **치환 불변성(permutation invariance)**이다. 즉, 노드의 레이블이나 순서에 관계없이 두 그래프가 구조적으로 동일(동형)하다는 것을 인식하는 능력이다.

본 논문은 LLM이 진정으로 그래프 동형성을 이해하고 있는지, 아니면 높은 정확도가 직렬화된 표현(serialized representations)의 표면적 패턴을 이용한 결과인지 조사한다. 만약 LLM이 동일한 그래프가 노드 레이블이 치환되어 제시되었을 때 일관된 판단을 유지하지 못한다면, 이는 모델이 추상적 위상(topology)을 추론하는 것이 아니라 직렬화의 차이를 탐지하고 있음을 시사한다.

방법론

본 연구는 세 가지 널리 사용되는 LLM(GPT-4o-mini(OpenAI), Gemini 2.5 Flash(Google), Llama 3.3 70B Instruct(Together AI via))을 평가하기 위해 2단계 실험 설계를 채택하였다.

실험 설정

1. 직렬화 형식(Serialization Formats): 형식 민감도를 테스트하기 위해 그래프를 세 가지 표준 형식으로 제시하였다:
   • 에지 리스트(Edge List): 단순 노드 쌍.
   • 에지 인덱스(Edge Index): 소스-타겟 열 벡터.
   • 인접 행렬(Adjacency Matrix): 이진 연결 행렬.
2. 프롬프팅 전략:
   • 제로샷(Zero-shot): 추론 가이드가 없는 최소한의 작업 지침.
   • 지시형(Instructed): 그래프 동형성에 대한 명시적 정의 및 추론 단계 포함.
3. 실험 1: 비동형성 탐지(Non-Isomorphism Detection):
   • 모델들을 네 가지 난이도 카테고리에 걸친 400개의 비동형 그래프 쌍에 대해 테스트하였다:
     • 카테고리 1: 노드 수가 다름.
     • 카테고리 2: 에지 수가 다름.
     • 카테고리 3: 노드 및 에지 수가 모두 다름.
     • 카테고리 4: 1-Weisfeiler-Lehman(1-WL) 테스트로는 구별할 수 없으나(노드/에지 수 및 차수 시퀀스가 동일함), 복잡한 구조적 특성으로 인해 비동형인 그래프.
4. 실험 2: 치환 불변성(Permutation Invariance):
   • 모델들을 노드 레이블이 무작위로 치환된 400개의 동형 그래프 쌍에 대해 테스트하였다.
   • 목표는 레이블 변화에도 불구하고 모델이 이 쌍들을 동형으로 올바르게 식별하는지 확인하는 것이다.

주요 결과

표준 탐지에서의 높은 정확도 (실험 1)

첫 번째 실험에서 세 모델 모두 대부분의 카테고리와 형식에서 완벽에 가까운 정확도(96–100%)를 달却했다. 특히, 그래프 신경망(GNN)이 일반적으로 어려움을 겪는 카테고리 4에서도 우수한 성능을 보였다.

• Gemini는 모든 조건에서 100% 정확도를 유지했다.
• OpenAI와 Llama는 특정 조건에서 미세한 하락을 보였다 (예: OpenAI는 지시형 프롬프팅 시 카테고리 4에서 88.0%로 하락; Llama는 제로샷 카테고리 2에서 96.0%로 하락).

치환 불변성의 실패 (실험 2)

두 번째 실험에서 모델들은 동형 그래프의 노드 레이블이 치환되었을 때 성능이 붕괴되었다:

• OpenAI: 정확도가 0.0%에서 18.0% 사이였다.
• Gemini: 정확도가 0.0%에서 0.2% 사이였다.
• Llama: 정확도가 2.0%에서 39.2% 사이였다.
• 관찰 사항: 성능이 직렬화 형식에 따라 크게 달라졌는데, 이는 모델이 위상이 아닌 입력 패턴(예: 특정 노드 인덱스의 공통 발생 등)에 의존함을 시사한다. 치환 불변성을 명시적으로 상기시키는 "지시형(Instructed)" 프롬프팅조차 견고한 추론을 이끌어내는 데 실패했다.

주요 기여

본 논문은 세 가지 주요 기여를 한다:

1. 평가 프로토콜: LLM 기반 그래프 추론에서 치환 불변성을 테스트하기 위한 간단한 프로토콜을 도입하였다.
2. 경험적 증거: LLM이 그래프 동형성 탐지에서 높은 정확도를 달성하지만, 다양한 프롬프팅 전략과 직렬화 형식에 걸쳐 임의의 노드 재레이블링에 취약함을 입증하였다.
3. 방법론적 주장: LLM의 그래프 구조 작업 능력을 평가할 때, 높은 정확도만으로는 구조적 이해를 증명할 수 없으므로 불변성 기반 평가가 정확도 지표를 보완해야 한다고 주장한다.

의의 및 주장

본 논문은 LLM의 그래프 추론 벤치마크 성공이 **환상(illusory)**이라고 결론짓는다. 모델은 진정한 위상적 추론을 수행하기보다 직렬화된 표현의 패턴(예: 특정 노드 레이블 관례나 위치 편향)을 이용하는 것으로 보인다.

• 실무자를 위한 시사점: 노드 재레이블링에 대한 견고성이 요구되는 구조 중심의 그래프 추론 작업에 LLM을 신뢰해서는 안 된다.
• 향후 방향: 저자들은 풍부한 위상적 특성을 포착할 수 있는 치환 불변적 직렬화 방법의 개발에 집중할 것을 제안한다. 또한, 표준 벤치마킹에 불변성 기반 평가를 포함할 것을 권고한다.
• 한계점: 본 연구는 세 가지 특정 LLM과 세 가지 직렬화 방법에 국한된다. 저자들은 이러한 실패의 기계적 원인(근본적인 기호 추론의 한계인지, 아니면 사전 학습된 통계적 패턴 때문인지)이 향후 연구를 위한 열린 과제로 남아 있다고 언급했다. 또한, 토큰화 선택 및 특정 그래프 구조적 특성(예: girth, 대칭성)과 같은 요소들이 체계적으로 제거(ablated)되지 않았음을 인정하였다.