https://arxiv.org/abs/2401.11817
Hallucination is Inevitable: An Innate Limitation of Large Language Models
Hallucination has been widely recognized to be a significant drawback for large language models (LLMs). There have been many works that attempt to reduce the extent of hallucination. These efforts have mostly been empirical so far, which cannot answer the
arxiv.org
안녕하세요~ 이번에는 LLM의 할루시네이션 불가피성을 증명한 논문 시리즈를 가져왔습니다.
LLM의 환각은 모델이 그럴듯하지만 사실과 다르거나 무의미한 정보를 생성하는 심각한 단점으로 널리 인식되고 있습니다. 저는 그동안 이걸 “당연하다!”고 여겼고, 글에서도 당연한 문제라고 다뤘는데요.
최근에는 연구자들이 이 문제를 수학적 구조적 한계, 계산 가능성과 학습이론에 근거한 형식적 증명, 통계적 학습 과정과 사회적 평가 체계로 설명하는 논문들을 내놓고 있습니다. 말 그대로 엔지니어스러운 접근이죠.
제가 소개할 논문은 세 편인데, 오늘은 그 첫 번째,
`Hallucination is Inevitable: An Innate Limitation of LLMs` 입니다.
Inevitable .. 타노스가 생각나요. 🍆
1. 논문에서 제기한 기존 방법론, 혹은 현실의 문제점
기존 연구들은 LLM 환각의 원인을 데이터 수집, 학습, 추론 단계에서 찾아왔습니다.
- 현실의 문제: LLM이 생성하는 환각은 안전성과 신뢰성의 핵심 문제.
- 기존 시도들:
- 데이터/학습 관점: 노이즈, 편향, 노후 데이터 제거
- 추론 관점: 샘플링 랜덤성, 컨텍스트 부족, softmax 병목 등
- 대응책:
- 팩트 중심 벤치마크/지표 (TruthfulQA, HaluEval 등)
- Retrieval 기반 지식 보강 (RAG, knowledge graph)
- Chain-of-Thought, Verification prompting
→ 근데 이런건 제가 맨날 말하던거처럼 그저 경험적인 연구이고, "환각이 완전히 제거될 수 있는지", 이 근본적인 질문에는 답할 수가 없었습니다.
→ 모든 가능한 입력을 경험적으로 나열하고 테스트하는건 불가능하기에 과학적이지 않았죠. 그리고 현실 세계에서 llm의 사실적 또는논리적 오류인 환각을 형식적으로 정의하는 것은 ~ 정확성을 형식화하는 것만큼 어려워요.
2. 따라서 이 논문이 주장하는 내용
이 논문의 핵심은 단순합니다.
LLM에서 환각을 완전히 제거하는 것은 불가능하다.
구체적으로 저자들은 계산 가능한 LLM과 계산 가능한 실제 함수(ground truth function) 사이의 불일치를 환각으로 정의하는 형식적 세계(formal world)를 설정합니다.
3. 계산 가능한 실제 함수(ground truth function)란..
우리 고등학교 때 배운 확률과 통계에서 '확률 함수' 느낌으로다가 이해하면 됩니다.
- 확률 함수는 현실 세계의 사건을 숫자로 매핑해주는 함수였죠,
- f(빨간공 나오는 경우)
여기서 말하는 ground truth function f도 마찬가지입니다.
- 현실 세계의 사건(질문)에 대해 항상 정답을 반환하는 함수.
- f(한국의 수도는?) =
LLM도 결국 입력(prompt) → 출력(text)을 매핑하는 모델이니까 함수로 볼 수 있습니다.
- 그런데, 현실의 LLM은 확률 분포에서 샘플링하므로, 사실상 확률 변수처럼 동작하는 함수입니다.
- 논문에서는 단순화를 위해 LLM을 계산 가능한(computable) 함수로 모델링했습니다. 즉, 언제든 실행하면 결과를 줄 수 있는 함수로 간주한 것이죠.
4. 그 방법론/실험에 대해서:
4-1. Formal World 정의
- 현실에서 “참/거짓”을 형식화하기 어렵기 때문에, 논문은 형식 세계를 설정합니다.
- 이 세계에서 환각은 단순히 h(s) ≠ 일 때 발생합니다.
4-2. Diagonalization Argument (대각선 논법)
- 칸토어의 대각선 논법을 활용합니다.
- 모든 LLM의 상태(state)를 나열 → 각 입력에 대한 출력값 테이블 생성.
- 대각선을 따라 출력을 뒤집으면, 모든 LLM이 틀리는 새로운 f를 만들 수 있음.
- 따라서 어떤 LLM도 항상 정답을 맞출 수는 없다는 것이 증명됩니다.
4-3. 이론적 결과 (Theorem 1, 2, 3)
- Theorem 1: 모든 계산 가능한 LLM 집합은 반드시 환각을 일으키는 입력이 존재한다.
- Theorem 2: 환각은 단발성이 아니라 무한히 많은 입력에서도 발생한다.
- Theorem 3: 일반적으로, 모든 계산 가능한 LLM은 어떤 ground truth function에 대해 무조건 환각을 일으킨다.
→ 결론: 환각은 단순한 구현상의 결함이 아니라 LLM의 구조적 한계라는 것
5. 실험 결과
이론적 증명 외에도, 실제로 환각이 뚜렷하게 나타나는 문제군을 실험으로 보여줍니다.
- Combinatorial Listing Problem
- 알파벳 두 글자로 만들 수 있는 모든 길이 nn 문자열 나열
- 계산량이 2^n에 비례 → 다항시간 LLM은 끝까지 산출 불가능 → 오류 발생
- Subset Sum Problem (NP-complete)
- 부분합이 목표값 를 만족하는지 판정
- LLM은 모든 경우를 계산할 수 없어 추측 → 환각 자꾸 나옴
- Boolean Satisfiability (SAT, NP-complete)
- 논리식이 참이 되는 변수 조합 존재 여부 판정
- 일정 규모 이상 문제에서는 오답 출력
- Presburger Arithmetic
- 덧셈과 순서(<)만 포함하는 논리 체계
- 계산 복잡도가 초지수적(super-exponential) → 현실적 자원 한계 → 환각 다발
6. 한계점
- 계산 가능성 관점 한정
- 실제 데이터 품질, 확률적 추론에서 오는 환각은 다루지 않았고
- 결정론적 ground truth function 가정
- 현실 세계의 불확실성, 다중 정답 상황은 반영 불가
- 실험적 검증의 한계
- 일부 수학적/논리적 문제로만 환각을 관찰했을 뿐, 다양한 도메인에 대한 폭넓은 검증은 부족
7. 마무리
네, 모 .. 얘도 뭐랄까 .. 귀납법으로 증명을 시도한 느낌이라 막 속시원하거나, "와! 이래서 환각이!" 이런 기분이 드는 글은 아니었어요.
그래두 제가 검색한 범위 내에서는, “Hallucination is Inevitable: An Innate Limitation of LLMs” 이 논문이 거의 처음으로
- 환각을 형식적으로 정의하고
- 계산 가능성 이론 / 학습이론을 활용하여 “환각을 완전히 제거하는 것은 불가능하다”는 주장을 수학적으로 제시한 논문으로 보입니다.
그래서 다음글에서 만납시다.