환각은 언제 발생하는가? 경로 재사용 및 경로 압축의 진화에 대한 그래프 관점

When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression

대규모 언어 모델(LLM)에서 발생하는 추론 환각은 종종 유창하지만 근거가 부족하고 주어진 맥락이나 기본적인 사실 지식을 위반하는 결론으로 나타납니다. 이러한 실패는 널리 관찰되지만, 디코더 전용 트랜스포머가 이러한 환각을 어떻게 생성하는지에 대한 메커니즘은 아직 제대로 이해되지 못하고 있습니다. 우리는 다음 토큰 예측을 기본 그래프에서의 그래프 탐색 과정으로 모델링합니다. 여기서 개체는 노드에 해당하고, 학습된 변환은 엣지를 형성합니다. 이러한 관점에서, 문맥적 추론은 샘플링된 서브그래프(내재적 추론)에서의 제약된 탐색이며, 문맥이 없는 쿼리는 기본 그래프에 저장된 구조(외재적 추론)에 의존합니다. 우리는 추론 환각이 두 가지 근본적인 메커니즘으로 인해 발생한다고 보입니다. 첫째, extbf{경로 재사용}은 초기 훈련 단계에서 저장된 지식이 문맥적 제약을 압도하는 현상입니다. 둘째, extbf{경로 압축}은 자주 사용되는 다단계 경로가 후기 훈련 단계에서 더 짧은 연결(단축 엣지)로 붕괴되는 현상입니다. 이러한 두 가지 메커니즘은 LLM에서 발생하는 추론 환각에 대한 통합적인 설명을 제공하며, 이는 다양한 하위 작업 애플리케이션에서 관찰되는 잘 알려진 현상과 관련되어 있습니다.

Reasoning hallucinations in large language models (LLMs) often appear as fluent yet unsupported conclusions that violate either the given context or underlying factual knowledge. Although such failures are widely observed, the mechanisms by which decoder-only Transformers produce them remain poorly understood. We model next-token prediction as a graph search process over an underlying graph, where entities correspond to nodes and learned transitions form edges. From this perspective, contextual reasoning is a constrained search over a sampled subgraph (intrinsic reasoning), while context-free queries rely on memorized structures in the underlying graph (extrinsic reasoning). We show that reasoning hallucinations arise from two fundamental mechanisms: \textbf{Path Reuse}, where memorized knowledge overrides contextual constraints during early training, and \textbf{Path Compression}, where frequently traversed multi-step paths collapse into shortcut edges in later training. Together, these mechanisms provide a unified explanation for reasoning hallucinations in LLMs and connected to well-known behaviors observed in downstream applications.