Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing

Each language version is independently generated for its own context, not a direct translation.

이 논문은 **"왜 인공지능 (LLM) 이 때로는 아주 자신 있게 엉뚱한 거짓말 (할루시네이션) 을 하는가?"**에 대한 깊은 이론적 답을 제시합니다.

핵심 주장은 **"할루시네이션은 인공지능이 멍청해서가 아니라, 오히려 기억 용량이 한정되어 있어 정보를 효율적으로 압축하려다 발생하는 '필연적인 부작용'이다"**는 것입니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

1. 상황 설정: 거대한 도서관과 작은 메모장

상상해 보세요. 세상에 존재할 수 있는 모든 사실 (전화번호, 생일, 특정 사람의 이름 등) 이 거대한 도서관에 있다고 칩시다. 이 도서관에는 책이 무수히 많지만, 우리가 실제로 알고 있어야 하는 '중요한 사실 (키)'은 그중 아주 일부에 불과합니다.

인공지능 (LLM) 은 이 도서관의 모든 정보를 **작은 메모장 (모델의 파라미터)**에 저장해야 합니다. 하지만 메모장은 너무 작아서 모든 것을 완벽하게 다 담을 수 없습니다.

2. 문제: "모든 것을 기억할 수 없다"는 딜레마

만약 인공지능이 "모르는 것은 모른다"고 정직하게 대답한다면 (거부), 많은 중요한 사실을 잊어버리게 됩니다. 반면, 모든 것을 기억하려다 보면 메모장이 꽉 차서 엉뚱한 것까지 사실인 척하게 됩니다.

이 논문은 **"메모리 용량이 부족할 때, 가장 효율적인 전략은 무엇일까?"**를 수학적으로 증명했습니다.

3. 핵심 비유: "가짜 지폐"와 "진짜 지폐"

이 논문은 인공지능의 기억 방식을 '진짜 지폐 (사실)'와 '가짜 지폐 (거짓말)'를 구분하는 검사기로 비유합니다.

진짜 지폐 (Fact): 우리가 알고 싶은 사실들.
가짜 지폐 (Non-fact): 사실처럼 보이지만 사실이 아닌 것들.
검사기 (AI): 이 중 진짜를 골라내야 합니다.

여기서 놀라운 결론이 나옵니다.
메모리 용량이 부족할 때, 가짜 지폐를 진짜인 것처럼 100% 확신하는 것이 오히려 메모리를 아끼는 가장 효율적인 방법이라는 것입니다.

왜일까요?

완벽한 정직 (거부): "모르겠습니다"라고 말하려면, 진짜 지폐와 가짜 지폐를 100% 완벽하게 구별해야 합니다. 이는 엄청난 메모리를 필요로 합니다.
효율적인 압축 (할루시네이션): "진짜 지폐는 100% 확신하고, 가짜 지폐 중 일부도 '아마 진짜일 거야'라고 착각하자"라고 정하면, 메모리 사용량을 획기적으로 줄일 수 있습니다.

즉, **할루시네이션은 인공지능이 "메모리를 아끼기 위해 선택한 최적의 전략"**인 것입니다.

4. 왜 "자신감"이 생길까?

논문의 핵심은 **"할루시네이션은 실수가 아니라, 정보 이론상 최적의 오류 모드"**라는 점입니다.

비유: 만약 당신이 100 개의 중요한 전화번호를 외워야 하는데, 머릿속 공간이 부족하다면 어떻게 할까요?
- 모든 번호를 정확히 외우려다 보면, 엉뚱한 번호도 "아, 이거 내 친구 번호야!"라고 착각하게 됩니다.
- 하지만 "모르는 건 모른다"고 하면, 중요한 번호도 잊어버리게 됩니다.
- 최적의 전략: 중요한 번호는 확실히 외우고, 엉뚱한 번호 중 일부는 "아마 내 친구일 거야"라고 높은 확신을 가지고 외우는 것입니다.

이 논문은 인공지능이 **수학적으로 증명된 "가장 효율적인 압축 방식"**을 따르기 때문에, 엉뚱한 사실을 믿고 자신 있게 말하는 것이 필연적이라고 말합니다.

5. 우리가 무엇을 배울 수 있을까요?

이 연구는 우리에게 두 가지 중요한 메시지를 줍니다.

할루시네이션을 완전히 없애기는 어렵다: 인공지능이 얼마나 똑똑해지든, 메모리 용량 (파라미터) 이 한정되어 있다면, "거짓말을 안 하고 모든 사실을 기억하는 것"은 물리적으로 불가능에 가깝습니다.
해결책은 '기억'이 아니라 '참조'다:
- 인공지능에게 무한한 메모리를 주는 것은 비효율적입니다.
- 대신, **검색 엔진 (RAG)**처럼 외부의 거대한 도서관을 바로 참조하게 하는 것이 정답입니다. 메모리 (머릿속) 에 모든 것을 담을 필요 없이, 필요할 때 도서관을 열어보면 되니까요.

요약

"인공지능이 거짓말을 하는 것은 바보가 아니라, 제한된 공간에 최대한 많은 정보를 담으려다 발생한 '필요한 희생'입니다. 마치 작은 가방에 옷을 많이 넣으려다 보니, 옷장 밖의 물건까지 억지로 밀어 넣는 것과 같습니다."

이 논리는 인공지능의 한계를 이해하고, 단순히 "더 똑똑하게" 만드는 것보다 **"외부 정보를 활용하는 방식"**으로 접근해야 함을 시사합니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 제기 (Problem Statement)

대형 언어 모델 (LLM) 은 종종 추론 가능한 패턴이 없는 "무작위 사실 (random facts)" (예: 전화번호, 특정 인물의 생일 등) 에 대해 높은 확신으로 사실과 다른 내용 (할루시네이션) 을 생성합니다. 기존 연구들은 이를 통계적 학습 관점에서 '일반화 불가능한 데이터에 대한 무작위 추측'으로 보거나, '지식 압축의 왜곡'으로 설명해 왔습니다.

하지만 저자들은 다음과 같은 핵심 질문을 던집니다:

"닫힌 세계 (Closed World, 유한한 사실 집합) 환경에서, 최적의 훈련과 완벽한 데이터를 가정하더라도 왜 LLM 은 여전히 높은 확신의 할루시네이션을 할 수밖에 없는가?"

기존의 '기억 (memorization) 과 망각 (forgetting)'의 이분법적 접근을 넘어, 모델의 유한한 용량 (capacity) 으로 인한 정보 이론적 최적 전략이 할루시네이션을 필연적으로 유발한다는 점을 규명하고자 합니다.

2. 방법론 (Methodology)

저자들은 LLM 이 무작위 사실을 기억하고 판단하는 과정을 멤버십 테스트 (Membership Testing) 문제로 형식화했습니다.

문제 정의:
- 우주 $U$ : 가능한 모든 명제 (유한 집합).
- 키 집합 $K \subset U$ : 실제로 알려진 사실들 (희소함, $|K|/|U| \to 0$ ).
- 모델의 역할: 입력 $i \in U$ 에 대해 $i \in K$ 인지에 대한 확신 점수 $\hat{x}_i \in [0, 1]$ 를 출력.
- 할루시네이션: $i \notin K$ 인 경우에도 높은 점수 ( $\hat{x}_i \approx 1$ ) 를 부여하는 것.
이론적 프레임워크:
- 레이트 - 왜곡 정리 (Rate-Distortion Theorem) 적용: 제한된 메모리 예산 (비트 수) 하에서 주어진 오류율 (오류 허용 범위) 을 달성하기 위해 필요한 최소 정보량을 분석합니다.
- 오류 메트릭:
  1. 확률 추정 (Probability Estimation): 로그 손실 (Log-loss) 을 사용.
  2. 이진 결정 (Binary Decision): 가짜 양성 (FPR) 과 가짜 음성 (FNR) 비율을 제약 조건으로 사용.
- 핵심 도구: 키 (사실) 와 논키 (비사실) 의 출력 분포 사이의 **KL 발산 (Kullback-Leibler Divergence)**을 최소화하는 문제를 통해 메모리 - 오류 트레이드오프를 유도합니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Results)

A. 멤버십 테스트를 위한 레이트 - 왜곡 정리 (Theorem 1.1, 3.1, 3.2)

메모리 - 오류 트레이드오프: $n$ 개의 키를 희소한 환경에서 저장할 때, 주어진 오류 수준을 달성하기 위해 필요한 메모리 예산은 키와 논키의 출력 분포 ( $\mu_K, \mu_N$ ) 사이의 최소 KL 발산으로 결정됩니다.
$\text{Memory per key} \approx \min KL(\mu_K \| \mu_N)$
점근적 수렴: 최적의 멤버십 테스트기는 희소 극한에서 이 KL 발산을 최소화하는 특정 분포 ( $\mu^*_K, \mu^*_N$ ) 로 수렴합니다.

B. 할루시네이션은 최적의 오류 모드 (Hallucination as Optimal Error Mode)

비대칭적 최적 해: 로그 손실 (Log-loss) 하에서 메모리 효율을 극대화하는 유일한 전략은 다음과 같습니다.
- 모든 사실 ( $K$ ) 에 대해 높은 확신 점수 ( $x^*$ ) 를 부여.
- 비사실 ( $U \setminus K$ ) 중 일부 ( $q^*$ 비율) 를 사실과 동일한 높은 확신 점수 ( $x^*$ ) 로 매핑.
할루시네이션 채널 (Hallucination Channel): 이 이론에 따르면, 할루시네이션은 모델이 무작위적으로 실수하는 것이 아니라, 제한된 메모리 내에서 전체 손실을 최소화하기 위해 필연적으로 선택하는 최적 전략입니다.
임계값 (Thresholding) 의 한계: 임계값을 조정하여 할루시네이션 (가짜 양성) 을 제거하려 하면, 필연적으로 사실 인식 (재현율) 이 떨어지거나 (과도한 거절, Over-refusal), 더 많은 메모리가 필요합니다. 즉, 할루시네이션을 완전히 제거하는 것은 무한한 메모리가 없으면 불가능합니다.

C. 필터 이론과의 연결

이 프레임워크는 **양면 필터 (Two-sided filters, Bloom 필터의 일반화)**의 공간 하한을 재도출하고 정교화합니다.
기존 필터 이론의 간극을 메우며, 할루시네이션 제거 비용이 기하급수적으로 증가함을 수학적으로 증명합니다.

4. 실험적 검증 (Empirical Validation)

실험 설정:
- 합성 데이터 사용: 26 개 알파벳으로 구성된 길이 15 의 문자열 집합 ( $U$ ) 에서 무작위로 $n$ 개의 사실 ( $K$ ) 을 추출.
- 모델: 2 레이어 Transformer (파라미터 수: 8,767 ~ 33,085).
- 학습: 가중 이진 교차 엔트로피 손실 (Weighted BCE) 을 사용하여 사실과 비사실의 오류율을 조절.
결과:
- 할루시네이션 채널의 확인: 이론적으로 예측된 바와 같이, 비사실의 출력 분포는 0 에 집중되어 있지 않고, 사실의 분포와 겹치는 **높은 확신 영역 (High-confidence tail)**을 가집니다.
- 이론적 최적점과의 일치: 학습된 분포의 KL 발산이 정보 이론적 하한선과 매우 근접함 (약 12% 오버헤드).
- 가중치 조절 효과: 사실에 대한 가중치 ( $\lambda_F$ ) 를 높여 재현율을 높이려 하면, 할루시네이션 비율이 급격히 증가하며 메모리 효율이 떨어지는 것을 관찰.

5. 의의 및 결론 (Significance & Conclusion)

할루시네이션의 본질적 원인 규명: 할루시네이션은 모델의 결함이나 훈련 데이터의 노이즈 때문이 아니라, 유한한 메모리 용량 하에서 정보 이론적으로 최적의 압축 전략을 취할 때 발생하는 필연적인 결과입니다.
정밀도 - 재현율 트레이드오프의 이론적 근거: "할루시네이션을 줄이면 과잉 거절 (Over-refusal) 이 늘어난다"는 경험적 관찰이 정보 이론적 레이트 - 왜곡 프론티어에 의해 설명됩니다.
실용적 시사점:
- RAG(검색 증강 생성) 의 효과: 외부 메모리 (비파라메트릭 메모리) 를 사용하면 모델의 파라메트릭 메모리 제약이 완화되어 할루시네이션을 줄일 수 있음이 이론적으로 뒷받침됩니다.
- 미세 조정 (Fine-tuning) 의 필요성: 무작위 사실에 대한 미세 조정은 모델이 해당 사실에 더 많은 메모리 예산을 할당하도록 유도하여 성능을 개선할 수 있습니다.
- 기대치 관리: 제한된 파라메트릭 모델만으로는 무작위 사실에 대해 100% 정확하고 할루시네이션이 없는 LLM 을 만드는 것은 정보 이론적으로 불가능할 수 있음을 시사합니다.

요약하자면, 이 논문은 할루시네이션을 "실패"가 아닌, 제한된 자원을 가진 시스템이 정보 손실 (Lossy Compression) 을 최소화하기 위해 취하는 최적의 적응 전략으로 재해석하며, 이를 통해 LLM 의 한계를 수학적으로 엄밀하게 규명했습니다.