차이점을 탐지하는 것이 구조를 이해하는 것은 아니다: 대규모 언어 모델(LLMs)의 그래프 동형성(Graph Isomorphism) 판단 실패

대규모 언어 모델 (LLMs)은 다양한 추론 작업에서 인상적인 성능을 보여주었으나, 그래프에서의 구조적 추론 (structural reasoning) 능력은 여전히 불분명합니다. 본 연구에서는 LLM이 그래프 이론 (graph theory)의 근본적인 문제인 그래프 동형성 (graph isomorphism)을 진정으로 이해할 수 있는지 조사합니다. LLM은 동형성 탐지에서 거의 완벽에 가까운 정확도를 달성하지만, 우리는 이러한 성능이 환상임을 보여줍니다. 동일한 그래프를 노드 레이블 (node labels)이 치환된 상태로 제시했을 때, LLM은 이들의 동형성을 식별하는 데 실패합니다. 이러한 발견은 LLM이 추상적인 그래프 구조에 대해 추론하기보다는 패턴을 이용한다는 것을 시사합니다. 치환 불변성 (permutation invariance)은 유효한 구조적 추론을 위한 근본적인 요구 사항이므로, 이러한 결과는 그래프 추론 벤치마크에서의 성공이 진정한 위상학적 이해 (topological understanding)의 증거로 해석되어서는 안 된다는 것을 나타냅니다.