Xu, Ziwei, Sanjay Jain, and Mohan Kankanhalli. "Hallucination is inevitable: An innate limitation of large language models." arXiv preprint arXiv:2401.11817 (2024).

Why Language Models Hallucinate

Adam Tauman Kalai* Ofir Nachum Santosh S. Vempala ${ }^{\dagger}$ Edwin Zhang<br>OpenAI OpenAI Georgia Tech OpenAI

2025년 9월 4일

Abstract

마치 어려운 시험 문제에 직면한 학생들처럼, 대규모 언어 모델(LLM)은 때때로 불확실할 때 추측하여, 불확실성을 인정하는 대신 **그럴듯하지만 틀린 진술(plausible yet incorrect statements)**을 생성한다. 이러한 **"환각(hallucinations)"**은 최신 시스템에서도 지속적으로 나타나며 신뢰를 저해한다. 우리는 언어 모델이 환각을 일으키는 이유가 학습 및 평가 절차가 불확실성을 인정하는 것보다 추측에 보상을 주기 때문이라고 주장하며, 현대 학습 파이프라인에서 환각이 발생하는 통계적 원인을 분석한다. 환각은 신비로운 현상이 아니다. 이는 단순히 이진 분류(binary classification)에서의 오류로 발생한다. 만약 틀린 진술이 사실과 구별될 수 없다면, 사전학습된 언어 모델에서 환각은 자연스러운 통계적 압력에 의해 발생할 것이다. 우리는 또한 대부분의 평가가 채점되는 방식 때문에 환각이 지속된다고 주장한다. 즉, 언어 모델은 "시험을 잘 보는" 모델로 최적화되어 있으며, 불확실할 때 추측하는 것이 시험 성능을 향상시키기 때문이다. 이러한 "불확실한 응답에 페널티를 주는" 관행은 사회-기술적 완화를 통해서만 해결될 수 있다. 즉, 추가적인 환각 평가를 도입하는 대신, 잘못 정렬되어 있지만 리더보드를 지배하는 기존 벤치마크의 채점 방식을 수정해야 한다. 이러한 변화는 이 분야를 더욱 신뢰할 수 있는 AI 시스템으로 이끌 수 있을 것이다.

1 Introduction

Language model은 지나치게 확신에 차 있고 그럴듯한 거짓 정보를 생성하는 것으로 알려져 있으며, 이는 모델의 유용성과 신뢰도를 떨어뜨린다. 이러한 오류 모드는 **"hallucination"**이라고 불리지만, 인간의 지각 경험과는 근본적으로 다르다. 상당한 발전에도 불구하고, hallucination은 여전히 이 분야의 고질적인 문제이며, 최신 모델(OpenAI, 2025a)에서도 나타난다. 다음 prompt를 고려해 보자:

What is Adam Tauman Kalai's birthday? If you know, just respond with DD-MM.

세 번의 시도에서, state-of-the-art 오픈소스 language model은 "03-07", "15-06", "01-01"이라는 세 가지 잘못된 날짜를 출력했다. 이는 응답을 요청할 때 알려진 경우에만 응답하도록 지시했음에도 발생한 것이다. (정확한 날짜는 가을에 해당한다.) Table 1은 이보다 더 정교한 hallucination의 예시를 보여준다.

Hallucination은 language model이 생성하는 오류 중 중요한 특별한 경우이며, 우리는 이를 계산 학습 이론(computational learning theory) (예: Kearns and Vazirani, 1994)을 사용하여 더 일반적으로 분석한다. 우리는 **일반적인 오류 집합 $\mathcal{E}$**와, **그럴듯한 문자열(plausible strings)의 임의의 부분집합 $\mathcal{X}=\mathcal{E} \cup \mathcal{V}$**를 고려한다. 여기서 다른 그럴듯한 문자열 $\mathcal{V}$는 유효(valid)하다고 정의한다. 그런 다음 이러한 오류의 통계적 특성을 분석하고,

ChatGPT: Adam Tauman Kalai의 Ph.D. 논문 (2002년 CMU에서 완성) 제목은 다음과 같습니다: (GPT-4o) "Boosting, Online Algorithms, and Other Topics in Machine Learning." DeepSeek: "Algebraic Methods in Interactive Machine Learning". . . 2005년 하버드 대학교에서. Llama: "Efficient Algorithms for Learning and Playing Games"... 2007년 MIT에서.

Table 1: "Adam Kalai의 박사 학위 논문 제목은 무엇이었습니까?"라는 질문에 대한 세 가지 인기 있는 language model의 응답 발췌. 3개 모델 모두 정확한 제목이나 연도를 생성하지 못했다 (Kalai, 2001).

관심 있는 오류 유형, 즉 그럴듯한 허위 정보(plausible falsehoods)인 hallucination에 결과를 적용한다. 우리의 형식론은 language model이 응답해야 하는 prompt의 개념도 포함한다.

언어의 분포는 **학습 예시(corpus of training examples)**로부터 초기 학습되는데, 이 학습 데이터는 필연적으로 오류와 불완전한 진실(half-truths)을 포함한다. 그러나 우리는 학습 데이터가 오류가 없더라도, language model 학습 중에 최적화되는 목표(objectives)가 오류를 생성하게 만든다는 것을 보여준다. 다양한 수준의 오류를 포함하는 현실적인 학습 데이터에서는 훨씬 더 높은 오류율을 예상할 수 있다. 따라서 우리의 오류 하한(lower bounds on errors)은 전통적인 계산 학습 이론(Kearns and Vazirani, 1994)에서와 같이 더 현실적인 설정에도 적용된다.

우리의 오류 분석은 일반적이지만 hallucination에 대한 구체적인 함의를 가진다. 이는 추론(reasoning) 및 검색-회수(search-and-retrieval) language model을 포함하여 광범위하게 적용되며, 이 분석은 다음 단어 예측(next-word prediction)이나 Transformer 기반 신경망의 속성에 의존하지 않는다. 이는 아래에 설명된 현대 학습 패러다임의 두 단계, 즉 pretraining과 post-training만을 고려한다. Hallucination의 경우, 분류 체계(Maynez et al., 2020, Ji et al., 2023)는 종종 **사용자의 prompt와 모순되는 내재적 hallucination(intrinsic hallucinations)**을 추가로 구별한다. 예를 들면 다음과 같다:

DEEPSEEK에 D가 몇 개 있습니까? 아는 경우, 설명 없이 숫자만 말해주세요. DeepSeek-V3는 10번의 독립적인 시도에서 "2" 또는 "3"을 반환했다. Meta AI와 Claude 3.7 Sonnet²도 유사하게 수행했으며, "6"과 "7"과 같은 큰 숫자도 답변에 포함되었다. 우리의 이론은 또한 **학습 데이터나 외부 현실과 모순되는 외재적 hallucination(extrinsic hallucinations)**에 대해서도 설명한다.

1.1 Errors caused by pretraining

사전학습(pretraining) 과정에서 기반 모델(base model)은 대규모 텍스트 코퍼스 내 언어의 분포를 학습한다. 우리는 오류 없는 학습 데이터를 사용하더라도, 사전학습 시 최소화되는 통계적 목적 함수가 오류를 생성하는 language model로 이어질 수 있음을 보여준다. 이를 증명하는 것은 간단하지 않다. 왜냐하면 "I don't know (IDK)"를 항상 출력하거나, 오류 없는 코퍼스를 단순히 암기하여 재생산하는 모델처럼 어떤 모델은 전혀 오류를 만들지 않을 수도 있기 때문이다. 우리의 분석은 사전학습 후 어떤 유형의 오류가 예상되는지를 설명한다.

이를 위해 우리는 이진 분류(binary classification)와의 연결점을 찾는다. "이것이 유효한 language model 출력인가?"와 같은 질문을 고려해보자. 유효한 출력을 생성하는 것은 이러한 Yes/No 질문에 답하는 것보다 어떤 면에서는 더 어렵다. 왜냐하면 생성은 각 후보 응답에 대해 "이것이 유효한가"라는 질문에 암묵적으로 답하는 것을 요구하기 때문이다. 공식적으로, 우리는 Is-It-Valid (IIV) 이진 분류 문제를 고려한다. 이 문제의 학습 세트는 다수의 응답으로 구성되며, 각 응답은 유효(+) 또는 오류(-)로 레이블링된다 (Fig. 1 참조). 이 supervised learning 문제에서, 학습 및 테스트 데이터는 유효한 예시(사전학습 데이터는 유효하다고 가정하므로 +로 레이블링됨)와 $\mathcal{E}$에서 추출된 균일하게 무작위적인 오류(-로 레이블링됨)가 50/50으로 혼합되어 있다. 그런 다음, 우리는 어떤 language model이든 IIV 분류기로 사용될 수 있음을 보여준다. 이는 다시 생성 오류(예: hallucination)와 IIV 오분류율(misclassification rate) 사이의 수학적 관계를 설정할 수 있게 한다:

$$\text { (generative error rate) } \gtrsim 2 \cdot \text { (IIV misclassification rate). }$$

Language model은 철자 오류와 같은 많은 유형의 오류를 피하며, 모든 오류가 hallucination은 아니다. **IIV 오분류에서 생성으로의 환원(reduction)**은 생성 오류의 통계적 본질을 밝혀준다. 이 분석은 사전학습이 오류에 직접적으로 어떻게 기여하는지를 보여준다. 또한, 이진 분류에서 오류에 기여하는 동일한 통계적 요인들이 language model 오류도 유발함을 보여준다. 수십 년간의 연구는 오분류 오류의 다면적인 본질을 밝혀왔다 (Domingos, 2012). Fig. 1 (오른쪽)은 이러한 요인들을 시각적으로 보여준다: 상단은 정확하게 분류된 분리 가능한 데이터; 중간은 원형 영역에 대한 선형 분리기의 불량한 모델; 하단은 간결한 패턴이 없는 경우이다. Section 3.3에서는 데이터에 패턴이 없는 경우의 인식론적 불확실성(epistemic uncertainty)을 포함한 여러 요인을 분석한다.

Figure 1: Is-It-Valid는 레이블링된 $\pm$ 예시(왼쪽)를 사용하여 유효한 생성을 식별하는 방법을 학습해야 한다. 분류기(점선)는 철자(상단)와 같은 특정 개념에서는 정확할 수 있지만, 불량한 모델(중간)이나 데이터에 패턴이 없을 때의 임의의 사실(하단)로 인해 오류가 자주 발생한다.

이러한 환원은 다양한 유형의 사실을 다룬 이전 연구들을 연결한다. 예를 들어, Kalai와 Vempala (2024)는 이전의 생일 hallucination 예시처럼 데이터에 학습 가능한 패턴이 없는 임의의 사실(arbitrary facts)의 특수한 경우를 고려했다. 우리는 IIV 환원이 이 경우를 어떻게 다루고, 사전학습 후 hallucination 비율이 학습 사실 중 한 번만 나타나는 사실의 비율 이상이어야 한다는 그들의 bound를 어떻게 복구하는지를 보여준다. 예를 들어, 생일 사실의 20%가 사전학습 데이터에 정확히 한 번만 나타난다면, 기반 모델은 생일 사실의 최소 20%에서 hallucination을 일으킬 것으로 예상된다. 실제로, 우리의 분석은 prompt와 IDK 응답을 포함하도록 그들의 결과를 강화하며, 이 둘은 hallucination의 필수 구성 요소이다.

1.2 Why hallucinations survive post-training

두 번째 단계인 post-training은 기본 모델을 정제하며, 주로 환각(hallucination)을 줄이는 것을 목표로 한다. 사전학습(pretraining) 분석에서는 오류를 더 일반적으로 다루었지만, post-training 분석에서는 정보를 생략하거나 IDK와 같은 불확실성을 표현하는 대신, 왜 과도하게 확신하는 환각이 생성되는지에 초점을 맞춘다. 우리는 post-training 이후에도 환각이 지속되는 현상에 대한 사회-기술적 설명을 제시하고, 이러한 환각을 억제하기 위한 방법을 논의한다.

비유적으로, 인간도 때때로 그럴듯한 정보를 지어내는 상황을 생각해보자. 학생들은 불확실할 때 객관식 시험에서 추측하고, 주관식 시험에서는 거의 확신이 없는 답을 그럴듯하게 제출하며 허세를 부리기도 한다. Language model도 유사한 시험으로 평가된다. 두 상황 모두에서, 정답에 1점을 주고 공란이나 IDK에는 점수를 주지 않는 이진 0-1 채점 방식에서는, 불확실할 때 추측하는 것이 기대 점수를 최대화한다. 허세는 종종 과도하게 확신하고 구체적이다. 예를 들어, 날짜에 대한 질문에 "가을 어느 때쯤"이 아니라 "9월 30일"이라고 답하는 식이다. 많은 language model 벤치마크는 정확도나 합격률과 같은 이진 측정 기준을 사용하여 표준화된 인간 시험을 모방한다. 따라서 이러한 벤치마크에 맞춰 모델을 최적화하는 것은 환각을 조장할 수 있다. 인간은 학교 밖에서, 즉 험난한 경험을 통해 불확실성을 표현하는 것의 가치를 배운다. 반면에 language model은 불확실성을 불이익으로 간주하는 시험으로 주로 평가된다. 따라서 그들은 항상 "시험 모드"에 있다. 간단히 말해, 대부분의 평가는 정렬되어 있지 않다.

우리가 이진 채점이 환각을 측정하지 못한다는 것을 처음 깨달은 것은 아니다. 그러나 환각 평가에 대한 기존 연구는 일반적으로 찾기 어려운 "완벽한 환각 평가"를 추구해왔다. Section 4에서 우리는 이것이 불충분하다고 주장한다. 우리는 기존의 주요 평가들이 압도적으로 불확실성에 불이익을 준다는 것을 관찰했으며, 따라서 근본적인 문제는 정렬되지 않은 평가의 만연에 있다고 본다. 모델 A가 불확실성을 올바르게 알리고 환각을 전혀 일으키지 않는 정렬된 모델이라고 가정해보자. 모델 B는 모델 A와 유사하지만, 불확실성을 전혀 나타내지 않고 불확실할 때 항상 "추측"한다고 가정해보자. 모델 B는 대부분의 현재 벤치마크의 기반인 0-1 채점 방식에서 모델 A보다 뛰어난 성능을 보일 것이다. 이는 불확실성과 기권에 불이익을 주는 "전염병"을 야기하며, 우리는 소수의 환각 평가만으로는 충분하지 않다고 주장한다. 수많은 주요 평가들이 불확실할 때 기권에 불이익을 주는 것을 중단하도록 조정되어야 한다.

기여 (Contributions)
우리는 환각의 주요 통계적 동인을, 사전학습(pretraining) 단계에서의 기원부터 post-training 이후의 지속성까지 식별한다. 지도 학습과 비지도 학습 간의 새로운 연결은 학습 데이터에 IDK가 포함되어 있을 때조차도 환각의 기원을 명확히 한다. 문제에 대한 광범위한 연구에도 불구하고 환각이 지속되는 현상은 환각과 유사한 추측이 대부분의 주요 평가에서 보상받기 때문이라는 인식으로 설명된다. 우리는 효과적인 완화책으로 이어질 수 있는 기존 평가에 대한 통계적으로 엄격한 수정 방안을 논의한다.

2 Related work

우리가 아는 한, 본 연구에서 제시된 **지도 학습(이진 분류)에서 비지도 학습(밀도 추정 또는 자기 지도 학습)으로의 환원(reduction)**은 새로운 접근 방식이다. 그러나 학습 문제 간의 일반적인 환원 방법은 한 문제가 다른 문제만큼 어렵다는 것을 입증하기 위한 잘 확립된 기술이다 (예: Beygelzimer et al., 2016 참조).

여러 조사와 연구에서 언어 모델의 환각(hallucination) 발생 원인을 탐구해왔다. Sun et al. (2025)은 다음과 같은 요인들을 언급한다:

• 모델의 과신 (Yin et al., 2023)
• 디코딩 무작위성 (Lee et al., 2022)
• 눈덩이 효과 (Zhang et al., 2023)
• long-tailed training sample (Sun et al., 2023)
• 오해의 소지가 있는 alignment training (Wei et al., 2023)
• 허위 상관관계 (Li et al., 2022)
• exposure bias (Bengio et al., 2015)
• reversal curse (Berglund et al., 2024)
• context hijacking (Jeong, 2024)

이와 유사한 오류 원인들은 더 넓은 머신러닝 및 통계적 환경에서 오랫동안 연구되어 왔다 (Russell and Norvig, 2020).

가장 밀접하게 관련된 이론적 연구는 Kalai와 Vempala (2024)의 연구이며, 우리는 이 연구가 우리의 환원(reduction)의 특수한 경우임을 보여준다. 그들은 Good-Turing missing mass 추정치 (Good, 1953)를 환각과 연결시켰고, 이는 Theorem 3에 영감을 주었다. 그러나 그 연구는 불확실성 표현(예: IDK), 지도 학습과의 연결, 학습 후 수정(post-training modification)을 다루지 않았으며, 그들의 모델에는 prompt가 포함되지 않았다. Hanneke et al. (2018)은 유효성 오라클(validity oracle, 예: 사람)에 질의하여 환각을 최소화하는 언어 모델을 불가론적으로 학습시키는 대화형 학습 알고리즘을 분석한다. 그들의 방법은 합리적인 양의 데이터를 요구하는 통계적으로 효율적인 방법이지만, 계산적으로는 효율적이지 않다. 다른 최근 이론 연구들 (Kalavasis et al., 2025, Kleinberg and Mullainathan, 2024)은 일관성(유효하지 않은 출력 회피)과 폭넓음(다양하고 언어적으로 풍부한 콘텐츠 생성) 사이의 내재적인 trade-off를 공식화한다. 이 연구들은 광범위한 언어 클래스에 대해, 학습 데이터를 넘어 일반화하는 모든 모델은 유효하지 않은 출력을 환각하거나, mode collapse를 겪어 유효한 응답의 전체 범위를 생성하지 못할 것임을 보여준다.

**강화 학습 기반의 인간 피드백 (RLHF) (Ouyang et al., 2022), AI 피드백 (RLAIF) (Bai et al., 2022), 직접 선호 최적화 (DPO) (Rafailov et al., 2023)**와 같은 여러 **학습 후 기술(post-training techniques)**들은 음모론 및 일반적인 오해를 포함한 환각을 줄이는 데 효과적인 것으로 나타났다. Gekhman et al. (2024)은 새로운 정보에 대한 간단한 fine-tuning이 초기에는 환각 발생률을 감소시키지만, 나중에는 다시 증가할 수 있음을 보여준다. 또한, 자연어 질의와 내부 모델 활성화 모두 사실적 정확도 및 모델 불확실성에 대한 예측 신호를 인코딩한다는 것이 입증되었다 (예: Kadavath et al., 2022). 서론에서 논의했듯이, 의미론적으로 관련된 질의에 대한 모델 답변의 불일치 또한 환각을 감지하거나 완화하는 데 활용될 수 있다 (Manakul et al., 2023, Xue et al., 2025, Agrawal et al., 2024).

환각을 완화하는 데 효과적인 것으로 입증된 수많은 다른 방법들이 있다. 예를 들어, Ji et al. (2023) 및 Tian et al. (2024)의 조사를 참조하라. 평가 측면에서는 최근 여러 포괄적인 벤치마크와 리더보드가 도입되었다 (예: Bang et al., 2025, Hong et al., 2024). 그러나 이러한 벤치마크의 채택 장벽을 조사한 연구는 상대적으로 적다. 예를 들어, 2025년 AI Index 보고서 (Maslej et al., 2025)는 환각 벤치마크가 "AI 커뮤니티 내에서 주목을 받는 데 어려움을 겪었다"고 언급한다.

이진적인 확실성 표현을 넘어, 불확실성의 정도를 전달하기 위한 보다 미묘한 언어적 구성이 제안되었다 (Mielke et al., 2022, Lin et al., 2022a; Damani et al., 2025). 또한, 의미가 맥락에 의해 어떻게 형성되는지를 연구하는 화용론(pragmatics) 분야는 언어 모델이 정보를 전달하는 방식을 이해하고 개선하는 데 점점 더 중요해지고 있다 (Ma et al., 2025).

3 Pretraining Errors

사전학습(pretraining)은 학습 분포 $p$에서 추출된 텍스트 분포를 근사하는 **기반 언어 모델(base language model) $\hat{p}$**를 생성한다. 이는 비지도 학습(unsupervised learning)의 고전적인 "밀도 추정(density estimation)" 문제이며, 여기서 밀도는 단순히 데이터에 대한 확률 분포를 의미한다. 언어 모델의 경우, 이 분포는 텍스트 또는 (포함된 경우) 멀티모달 입력에 대한 분포이다.

기반 모델이 오류를 범한다는 것을 증명하는 데 있어 핵심적인 과제는 많은 언어 모델이 오류를 범하지 않는다는 점이다. 항상 "IDK"를 출력하는 퇴화 모델(degenerate model)도 오류를 피한다 (IDK가 오류가 아니라고 가정할 때). 유사하게, 오류 없는 학습 데이터를 가정하면, 무작위 학습 예시에서 텍스트를 그대로 반복하는 자명한 기반 모델(trivial base model)도 오류를 범하지 않는다. 그러나 이 두 언어 모델은 아래에 정의된 통계적 언어 모델링의 기본 목표인 밀도 추정에는 실패한다. 오류는 학습 분포와 일치하는 최적의 기반 모델 $\hat{p}=p$에 의해서도 피할 수 있지만, 이 모델은 엄청나게 많은 학습 데이터를 필요로 할 것이다. 그럼에도 불구하고, 우리는 잘 학습된 기반 모델이 특정 유형의 오류를 여전히 생성해야 한다는 것을 보여준다.

우리의 분석은 유효한 출력(즉, 오류 회피)을 생성하는 것이 출력 유효성을 분류하는 것보다 더 어렵다는 것을 보여준다. 이러한 환원(reduction)을 통해 우리는 계산 학습 이론(computational learning theory)의 관점을 적용할 수 있게 되며, 여기서 오류는 예상되고 이해되는 것이며, 이를 생성 모델의 오류 메커니즘에 적용한다. 언어 모델은 처음에는 텍스트에 대한 확률 분포로 정의되며, 나중에 prompt가 통합된다 (Section 3.2). 두 설정 모두 동일한 직관을 공유한다. prompt가 없는 예시에는 Fig. 1과 같은 생일 관련 문장이 포함되며, prompt가 있는 모델은 특정 개인의 생일을 묻는 쿼리를 받을 수 있다.

단순한 자동 완성(autocomplete)이 아니다. 우리의 분석은 일반적인 밀도 추정에 적용되며, 많은 언어 모델이 이전 단어를 기반으로 각 단어를 예측하도록 자기 지도 학습(self-supervised learning)을 사용하여 학습되더라도 "다음 단어 예측기(next-word predictors)"에만 국한되지 않는다. 환각(hallucination)을 언어 모델이 유효한 완성을 제공할 수 없는 잘못 선택된 접두사(예: "Adam Kalai는 ~에 태어났다") 탓으로 돌리고 싶은 유혹이 있다. 그러나 순전히 통계적인 관점에서, 계산을 무시하면, 언어 모델의 자동 완성 관점은 ${ }^{4}$ 어떤 인간 화자도 한 번에 한 단어를 생성한다는 사실보다 더 중요하지 않다. 우리의 분석은 오류가 모델이 기본 언어 분포에 맞춰지고 있다는 바로 그 사실에서 발생하며, 특정 아키텍처는 추가적인 오류를 유발할 수 있음을 시사한다.

3.1 The reduction without prompts

prompt 없이, 기본 모델(base model) $\hat{p}$는 집합 $\mathcal{X}$에 대한 확률 분포이다. 앞서 논의했듯이, 각 예시 $x \in \mathcal{X}$는 "그럴듯한(plausible)" 문자열, 예를 들어 문서 5를 나타낸다. 예시 $\mathcal{X}=\mathcal{E} \cup \mathcal{V}$는 오류(errors) $\mathcal{E}$와 유효한 예시(valid examples) $\mathcal{V}$로 분할되며, $\mathcal{E}, \mathcal{V}$는 비어 있지 않은 서로소 집합이다. 기본 모델 $\hat{p}$의 **오류율(error rate)**은 다음과 같이 정의된다:

$$\text { err }:=\hat{p}(\mathcal{E})=\operatorname{Pr}_{x \sim \hat{p}}[x \in \mathcal{E}]$$

학습 데이터는 노이즈 없는 학습 분포 $p(\mathcal{X})$에서 온다고 가정한다. 즉, $p(\mathcal{E})=0$인 경우이다. 논의했듯이, 노이즈가 있는 학습 데이터와 부분적으로만 올바른 문장들을 사용하면, 우리의 하한선보다 훨씬 높은 오류율을 예상할 수 있다.

이제 서론에서 소개된 **IIV 이진 분류 문제(binary-classification problem)**를 공식화한다. IIV는 학습할 **목표 함수 $f: \mathcal{X} \rightarrow\{-,+\}$ ( $\mathcal{V}$의 멤버십)**와 **예시 $\mathcal{X}$에 대한 분포 $D$ ( $p$에서 추출된 샘플과 균일하게 무작위 오류의 50/50 혼합)**로 정의된다:

$$D(x):=\left\{\begin{array}{ll} p(x) / 2 & \text { if } x \in \mathcal{V}, \\ 1 / 2|\mathcal{E}| & \text { if } x \in \mathcal{E}, \end{array} \text { and } f(x):= \begin{cases}+ & \text { if } x \in \mathcal{V}, \\ - & \text { if } x \in \mathcal{E} .\end{cases}\right.$$

우리의 분석은 IIV의 앞서 언급된 오분류율(misclassification rate) $\text{err}_{\text{iiv}}$ 측면에서 오류율 $\operatorname{err}=\hat{p}(\mathcal{E})$의 하한선을 설정한다:

$$\operatorname{err}_{\mathrm{iiv}}:=\operatorname{Pr}_{x \sim D}[\hat{f}(x) \neq f(x)], \text { where } \hat{f}(x):= \begin{cases}+ & \text { if } \hat{p}(x)>1 /|\mathcal{E}|, \\ - & \text { if } \hat{p}(x) \leq 1 /|\mathcal{E}| .\end{cases}$$

따라서 우리의 축소(reduction)에서 기본 모델은 특정 임계값 $1/|\mathcal{E}|$에서 기본 모델의 확률을 임계 처리(thresholding)함으로써 IIV 분류기로 사용된다. 이러한 확률 $\hat{p}(x)$는 일반적으로 기본 모델에 대해 효율적으로 계산될 수 있다는 점에 유의하라 (비록 효율적인 계산이 하한선이 의미를 갖는 데 필수적인 것은 아니지만).

Corollary 1. $p(\mathcal{V})=1$인 모든 학습 분포 $p$와 모든 기본 모델 $\hat{p}$에 대해,

$$\operatorname{err} \geq 2 \cdot \operatorname{err}_{\mathrm{iiv}}-\frac{|\mathcal{V}|}{|\mathcal{E}|}-\delta$$

여기서 err, $\operatorname{err}_{\text {iiv }}$는 각각 Eq. (1)과 (2)에서 정의되며, $\delta:=|\hat{p}(\mathcal{A})-p(\mathcal{A})|$이고 $\mathcal{A}:=\{x \in \mathcal{X}|\hat{p}(x)>1 /|\mathcal{E}|\}$이다. 이 관계는 모든 기본 모델 $\hat{p}$에 대해 성립하므로, 모든 기본 모델이 본질적으로 학습 불가능한 IIV 사실(예: 학습 데이터에 없는 생일)에 대해 오류를 범할 것임을 즉시 암시한다. 이러한 경우 $\operatorname{err}_{\text {iiv}}$는 필연적으로 크고, $\delta$와 $|\mathcal{V}| /|\mathcal{E}|$는 작다 (예: 각 사람에 대해 $\mathcal{E}$에는 $\mathcal{V}$의 올바른 생일 주장보다 364배 더 많은 잘못된 생일 주장이 있으며, IDK도 포함). 위 Corollary는 prompt가 있는 더 일반적인 경우를 다루는 Theorem 1의 특수한 경우로 즉시 이어진다. Theorem 2는 나중에 이 일반적인 결과를 사용하여 직관적인 특수 경우에 대한 하한선을 제공한다. Theorem 3과 4는 작은 $|\mathcal{E}|$ (예: True/False 질문의 경우 $|\mathcal{E}|=1$)를 다룬다. 위 경계의 상수 2는 비교적 엄격하다: 큰 $|\mathcal{E}|$와 작은 $\delta$의 경우, 학습 불가능한 개념에 대해 $\operatorname{err}_{\text {iiv}}$는 $1/2$에 가까울 수 있지만 $\operatorname{err} \leq 1$이다. Corollary 1은 또한 $\operatorname{err}_{\text {iiv}} \lesssim 1/2$임을 의미한다.

환각 오류(Hallucination errors). 오류 분석을 환각에 적용하기 위해, $\mathcal{E}$를 (하나 이상의) 그럴듯한 허위 사실을 포함하는 그럴듯한 생성물들의 집합으로 간주할 수 있다. 환각에 대한 일반적인 다른 정의는 학습 데이터(또는 prompt)에 근거하지 않은 생성물이라는 점에 유의하라. 다행히도, 위 하한선은 이 개념에도 적용된다. 왜냐하면 우리는 유효한 학습 데이터만 가정했기 때문에, 생성된 사실적 오류는 사실적으로 올바른 학습 데이터에 근거할 수 없기 때문이다.

Calibration. 이제 $|\delta|$가 사전학습 후 작아지는 (오)calibration의 척도인 이유를 설명한다. 언어에 대한 지식 없이도, 단순히 균일 분포 $\hat{p}(x)=1/|\mathcal{X}|$를 취함으로써 $\delta=0$을 달성할 수 있으며, 따라서 $\delta=0$이 $p=\hat{p}$를 요구하지는 않는다는 점에 유의하라. 감사자는 학습 샘플 $x \sim p$와 합성 생성물 $\hat{x} \sim \hat{p}$ 집합을 사용하여 $\hat{p}(x)>1/|\mathcal{E}|$를 만족하는 응답의 비율과 $\hat{p}(\hat{x})>1/|\mathcal{E}|$를 만족하는 응답의 비율을 비교함으로써 $\delta$를 쉽게 추정할 수 있다. Dawid (1982)에서 영감을 받아, 매일 비가 올 확률을 예측하는 일기 예보관에 비유할 수 있다. 최소한의 calibration 요구 사항은 그들의 평균 예측이 평균 강우량 비율과 일치하는지 여부일 것이다. 또한 예측이 특정 임계값 $t \in[0,1]$에 대해 $t$보다 큰 날에 이 두 가지가 일치하도록 요구할 수도 있다. Dawid (1982)는 모든 $t \in[0,1]$에 대해, 예측이 $t$인 날들 중에서 약 $t$ 비율로 비가 온다는 더 엄격한 요구 사항을 도입했다.

다음은 표준 사전학습 cross-entropy objective에 대해 $\delta$가 일반적으로 작은 이유에 대한 특히 간단한 정당화이다:

$$\mathcal{L}(\hat{p})=\underset{x \sim p}{\mathbb{E}}[-\log \hat{p}(x)]$$

양의 레이블이 지정된 예시들의 확률을 스케일링 팩터 $s>0$로 재조정하고 정규화하는 것을 고려해보자:

$$\hat{p}_{s}(x): \propto \begin{cases}s \cdot \hat{p}(x) & \text { if } \hat{p}(x)>1 /|\mathcal{E}| \\ \hat{p}(x) & \text { if } \hat{p}(x) \leq 1 /|\mathcal{E}|\end{cases}$$

Figure 2: 강화 학습 전(왼쪽)과 후(오른쪽)의 GPT-4 calibration 히스토그램 (OpenAI, 2023a, Figure 8, 허가 받아 재인쇄). 이 플롯은 그럴듯한 응답이 단순히 A, B, C 또는 D인 객관식 쿼리에 대한 것이다. 사전학습된 모델은 잘 calibrated되어 있다.

그러면 간단한 계산을 통해 $\delta$가 $s=1$에서 평가된 스케일링 팩터 $s$에 대한 손실의 미분 크기임을 알 수 있다:

$$\left.\delta=\left|\frac{d}{d s} \mathcal{L}\left(\hat{p}_{s}\right)\right|_{s=1} \right\rvert\, .$$

만약 $\delta \neq 0$이라면, $s \neq 1$인 어떤 $s$로 재조정하면 손실이 감소할 것이므로, 손실은 국소 최솟값(local minimum)에 있지 않다. 이러한 간단한 재조정을 근사할 수 있을 만큼 강력한 모든 종류의 language model에 대해, 국소 최적화는 작은 $\delta$를 산출해야 한다. 단일 임계값 $t=1/|\mathcal{E}|$에서 정의되는 $\delta$는 임계값 $t$에 대해 통합하는 Expected Calibration Error (ECE)와 같은 개념보다 약하다는 점에 유의하라.

환각은 기본 모델에서만 불가피하다. 많은 사람들이 환각이 불가피하다고 주장해왔다 (Jones, 2025; Leffer, 2024; Xu et al., 2024). 그러나 질문-답변 데이터베이스와 계산기를 사용하여 환각을 일으키지 않는 모델을 쉽게 만들 수 있다. 이 모델은 "금의 화학 기호는 무엇인가?"와 같은 고정된 질문 세트와 "$3+8$"과 같은 잘 구성된 수학적 계산에 답하고, 그렇지 않으면 IDK를 출력한다. 더욱이, Corollary 1의 오류 하한선은 오류를 범하지 않는 language model은 calibrated되지 않아야 한다는 것을 의미한다. 즉, $\delta$가 커야 한다. 우리의 유도 과정이 보여주듯이, calibration (그리고 그에 따른 오류)은 표준 cross-entropy objective의 자연스러운 결과이다. 실제로, 경험적 연구 (Fig. 2)는 기본 모델이 종종 calibrated되어 있는 반면, 강화 학습을 선호하여 cross-entropy에서 벗어날 수 있는 후처리된 모델은 그렇지 않을 수 있음을 보여준다.

3.2 The reduction with prompts

이제부터 우리는 Section 3.1의 설정을 일반화하여, 프롬프트 분포 $\mu$에서 추출된 프롬프트(컨텍스트) $c \in \mathcal{C}$를 포함하도록 한다. 각 예시 $x=(c, r)$는 이제 **프롬프트 $c$와 그에 대한 그럴듯한 응답 $r$**로 구성된다. 위 분석은 $\mu$가 빈 프롬프트에 확률 1을 할당하는 특수한 경우에 해당한다.
주어진 프롬프트 $c \in \mathcal{C}$에 대해, $\mathcal{V}_{c}:=\{r \mid(c, r) \in \mathcal{V}\}$를 **유효한 응답(valid responses)**으로, $\mathcal{E}_{c}:=\{r \mid(c, r) \in \mathcal{E}\}$를 **오류 응답(erroneous responses)**으로 정의한다.
학습 분포와 기본 모델은 이제 **조건부 응답 분포 $p(r \mid c), \hat{p}(r \mid c)$**가 된다. 표기상의 편의를 위해, 이들을 $\mathcal{X}$ 상의 **결합 분포(joint distributions)**로 확장하여 $p(c, r):=\mu(c) p(r \mid c)$ 및 $\hat{p}(c, r):=\mu(c) \hat{p}(r \mid c)$로 정의한다. 따라서 여전히 $\operatorname{err} :=\hat{p}(\mathcal{E})=\sum_{(c, r) \in \mathcal{E}} \mu(c) \hat{p}(r \mid c)$ 이고 $p(\mathcal{E})=0$이다.

따라서 학습 분포 예시는 증류(distillation)의 경우와 같이 유효한 "대화"에 해당한다 (Chiang et al., 2023; Anand et al., 2023). 학습 데이터가 동일한 프롬프트 분포에서 추출된 모델 대화를 포함한다고 가정하는 것은 비현실적이지만, 이 가정이 실패할 경우 훨씬 더 높은 오류율이 예상될 수 있다.
프롬프트가 있는 IIV 문제는 **동일한 목표 함수 $f(x):=+$ iff $x \in \mathcal{V}$**를 가지지만, 일반화된 분포 $D$는 $x \sim p$ 또는 $c \sim \mu$이고 $r \in \mathcal{E}_{c}$가 균일하게 무작위인 $x=(c, r)$ 중 하나를 동일한 확률로 선택한다.
마지막으로, 분류기 $\hat{f}(c, r)$는 이제 **$\hat{p}(r \mid c)>1 / \min _{c}\left|\mathcal{E}_{c}\right|$인 경우에만 +**이다. 따라서 Corollary 1은 다음 Theorem 1의 특수한 경우이다.

Theorem 1. $p(\mathcal{V})=1$인 모든 학습 분포 $p$와 모든 기본 모델 $\hat{p}$에 대해,

$$\operatorname{err} \geq 2 \cdot \operatorname{err}_{\mathrm{iiv}}-\frac{\max _{c}\left|\mathcal{V}_{c}\right|}{\min _{c}\left|\mathcal{E}_{c}\right|}-\delta$$

여기서 $\delta:=|\hat{p}(\mathcal{A})-p(\mathcal{A})|$이며, $\mathcal{A}:=\left\{(c, r) \in \mathcal{X}\left|\hat{p}(r \mid c)>1 / \min _{c}\right| \mathcal{E}_{c} \mid\right\}$이다.
재조정 $\hat{p}_{s}(r \mid c)$(프롬프트별로 정규화하며, 여전히 단일 파라미터 $s$ 사용)를 일반화하면, 이제 $\mathcal{L}(\hat{p}):=\sum_{(c, r) \in \mathcal{X}}-\mu(c) \log \hat{p}(r \mid c)$에 대해 작은 $\left.\delta=\left|\frac{d}{d s} \mathcal{L}\left(\hat{p}_{s}\right)\right|_{s=1} \right\rvert\,$가 다시 정당화된다.

3.3 Error factors for base models

수십 년간의 연구를 통해 이진 분류(binary classification)에서의 오분류(misclassification) (오류) 에 기여하는 통계적 요인들이 밝혀졌다. 우리는 이러한 사전 이해를 활용하여 환각(hallucination) 및 기타 생성 오류의 원인이 되는 요인들을 열거할 수 있다. 여기에는 다음과 같은 요인들이 포함된다:

• 통계적 복잡성: 생일 문제 (Section 3.3.1)에서와 같이, 데이터의 복잡성으로 인한 오류.
• 부실한 모델: 글자 수 세기 (Section 3.3.2)에서와 같이, 모델 자체의 성능 부족으로 인한 오류.
• GIGO(Garbage In, Garbage Out)와 같은 추가 요인: 음모론 (Section 3.4)에서와 같이, 잘못된 입력이 잘못된 출력을 야기하는 경우.

3.3.1 Arbitrary-fact hallucinations

타겟 함수를 설명하는 간결한 패턴이 없을 때, **학습 데이터에 필요한 지식이 부재하다는 의미의 인식론적 불확실성(epistemic uncertainty)**이 발생한다. Vapnik-Chervonenkis dimension (VC 차원) (Vapnik and Chervonenkis, 1971) VC($\mathcal{F}$)은 높은 확률로 함수 $\mathcal{F}$의 집합 $f: \mathcal{X} \rightarrow\{-,+\}$을 학습하는 데 필요한 최악의 예시 수를 특징화한다. VC($\mathcal{F}$) 차원이 높은 집합은 학습에 엄청나게 많은 샘플을 요구할 수 있다. 우리는 높은 VC 차원의 자연스러운 특수 사례인 **임의의 무작위 사실(random arbitrary facts)**을 고려한다. 특히, 이 섹션에서는 **prompt에 걸쳐 무작위적이고 독립적인 유효한 응답(IDK 제외)**을 다룬다.

정의 1 (임의의 사실). 다음은 고정된다: 임의의 prompt 분포 $\mu(c)$, IDK 응답, 그리고 각 prompt $c$에 대해: 응답 집합 $\mathcal{R}_{c}$와 응답 확률 $\alpha_{c} \in[0,1]$. 각 $c$에 대해 독립적으로, 단일 정답 $a_{c} \in \mathcal{R}_{c}$가 균일하게 무작위로 선택된다. 마지막으로, 각 $c \in \mathcal{C}$에 대해 $p\left(a_{c} \mid c\right)=\alpha_{c}$ 및 $p(\mathrm{IDK} \mid c)=1-\alpha_{c}$이다. 따라서 $\mathcal{E}_{c}=\mathcal{R}_{c} \backslash\left\{a_{c}\right\}$ 및 $\mathcal{V}_{c}=\left\{a_{c}, \mathrm{IDK}\right\}$이다.

주어진 사실을 작성하는 방법은 단 한 가지라고 가정하며, 이는 형식이 지정된 생일 예시에서처럼 수행될 수 있다. 그러나 우리는 각 사실을 여러 가지 방식으로 표현할 경우 더 많은 hallucination이 발생할 수 있다고 다시 한번 언급한다. 고정된 형식의 생일의 경우, $\left|\mathcal{E}_{c}\right|=364$이며, 자주 언급되는 유명인의 생일은 높은 $\mu(c)$를 가질 것이다. 아인슈타인의 생일과 같은 유명한 생일은 여러 번 나타나지만, 다른 생일은 부고 기사에서처럼 한 번만 나타날 수 있다. 대규모 language model은 아인슈타인의 생일이나 박사 학위 논문 제목과 같이 자주 참조되는 사실에 대해서는 거의 오류를 범하지 않는다.

hallucination에 대한 우리의 하한은 학습 데이터에 한 번만 나타나는 prompt의 비율에 기반하며, IDK는 무시한다.

정의 2 (Singleton rate). prompt $c \in \mathcal{C}$는 singleton이다. 만약 $N$개의 학습 데이터 $\left\langle\left(c^{(i)}, r^{(i)}\right)\right\rangle_{i=1}^{N}$에서 기권 없이 정확히 한 번 나타난다면, 즉 $\left|\left\{i: c^{(i)}=c \wedge r^{(i)} \neq \mathrm{IDK}\right\}\right|=1$이다. $\mathcal{S} \subseteq \mathcal{C}$를 singleton 집합이라고 하고,

$$\mathrm{sr}=\frac{|\mathcal{S}|}{N}$$

를 학습 singleton의 비율이라고 한다. singleton rate는 Alan Turing의 우아한 "missing-mass" 추정기 (Good, 1953)에 기반한다. 이는 분포에서 샘플링된 결과 중 아직 나타나지 않은 결과에 할당된 확률이 얼마나 되는지를 측정한다. 구체적으로, Turing의 미관측 사건 확률 추정치는 정확히 한 번 나타나는 샘플의 비율이다. 직관적으로, singleton은 추가 샘플링에서 얼마나 많은 새로운 결과가 나타날 수 있는지에 대한 대리 역할을 하므로, 그들의 경험적 비율은 분포의 전체 "누락된" 부분에 대한 추정치가 된다. 이제 임의의 사실에 대한 우리의 bound를 제시한다.

정리 2 (임의의 사실). 임의의 사실 모델에서, $N$개의 학습 샘플을 취하고 $\hat{p}$를 출력하는 모든 알고리즘은 $\vec{a}=\left\langle a_{c}\right\rangle_{c \in \mathcal{C}}$ 및 $N$개의 학습 예시에 대해 $\geq 99 \%$의 확률로 다음을 만족한다:

$$\operatorname{err} \geq \operatorname{sr}-\frac{2}{\min _{c}\left|\mathcal{E}_{c}\right|}-\frac{35+6 \ln N}{\sqrt{N}}-\delta .$$

또한, $\geq 99 \%$의 확률로 보정된 $\hat{p}(\delta=0)$를 출력하는 효율적인 알고리즘이 존재하며,

$$\mathrm{err} \leq \mathrm{sr}-\frac{\mathrm{sr}}{\max _{c}\left|\mathcal{E}_{c}\right|+1}+\frac{13}{\sqrt{N}}$$

이 논문의 이전 버전에서는 prompt와 기권을 생략한 관련 정리 (Kalai and Vempala, 2024)를 제시했다. 증명은 Section B에 있다. Miao and Kearns (2025)의 후속 연구는 hallucination, singleton rate 및 calibration에 대한 경험적 연구를 제공한다.

3.3.2 Poor models

오분류(misclassification)는 근본적인 모델이 좋지 않을 때도 발생할 수 있는데, 그 이유는 다음과 같다: (a) 모델 계열이 개념을 잘 표현할 수 없기 때문이다 (예: 원형 영역을 선형 분리기로 근사하는 경우). (b) 모델 계열은 충분히 표현력이 있지만, 모델 자체가 데이터에 잘 맞지 않는 경우이다.

Agnostic Learning (Kearns et al., 1994)은 (a)를 다루기 위해, 주어진 분류기 계열 $\mathcal{G}$ (여기서 $g: \mathcal{X} \rightarrow\{-,+\}$) 내에서 어떤 분류기든 가질 수 있는 최소 오분류율을 다음과 같이 정의한다:

$$\operatorname{opt}(\mathcal{G}):=\min _{g \in \mathcal{G}} \operatorname{Pr}_{x \sim D}[g(x) \neq f(x)] \in[0,1]$$

만약 $\operatorname{opt}(\mathcal{G})$가 크다면, $\mathcal{G}$ 내의 어떤 분류기도 높은 오분류율을 가질 것이다. 우리의 경우, $\theta \in \Theta$로 매개변수화된 language model $\hat{p}_{\theta}$가 주어졌을 때, thresholded-language-model 분류기 계열을 다음과 같이 고려한다:

$$\mathcal{G}:=\left\{g_{\theta, t} \mid \theta \in \Theta, t \in[0,1]\right\}, \text { where } g_{\theta, t}(c, r):= \begin{cases}+ & \text { if } \hat{p}_{\theta}(r \mid c)>t \\ - & \text { if } \hat{p}_{\theta}(r \mid c) \leq t\end{cases}$$

Theorem 1로부터 다음이 즉시 도출된다:

$$\operatorname{err} \geq 2 \cdot \operatorname{opt}(\mathcal{G})-\frac{\max _{c}\left|\mathcal{V}_{c}\right|}{\min _{c}\left|\mathcal{E}_{c}\right|}-\delta$$

각 context에 대해 정확히 하나의 올바른 응답만 존재하는 경우 (즉, IDK(I Don't Know) 옵션이 없는 표준 객관식 문제), calibration 항을 제거할 수 있으며, $C=2$개의 선택지에서도 bound를 얻을 수 있다.

Theorem 3 (Pure multiple-choice). 모든 $c \in \mathcal{C}$에 대해 $\left|\mathcal{V}_{c}\right|=1$이라고 가정하고, $C=\min _{c}\left|\mathcal{E}_{c}\right|+1$을 선택지의 개수라고 하자. 그러면,

$$\operatorname{err} \geq 2\left(1-\frac{1}{C}\right) \cdot \operatorname{opt}(\mathcal{G})$$

이를 설명하기 위해, 각 단어가 이전 두 단어에만 기반하여 예측되는 고전적인 trigram language model을 고려해보자. 즉, context window가 단 두 단어인 경우이다. Trigram 모델은 1980년대와 1990년대에 지배적이었다. 그러나 trigram 모델은 종종 비문법적인 문장을 출력했다. 다음 prompt와 response를 고려해보자:

$$\begin{array}{ll} c_{1}=\text { She lost it and was completely out of } \ldots & c_{2}=\text { He lost it and was completely out of } \ldots \\ r_{1}=\text { her mind } . & r_{2}=\text { his mind } . \end{array}$$

여기서 $V_{c_{1}}:=E_{c_{2}}:=\left\{r_{1}\right\}$ 이고 $V_{c_{2}}:=E_{c_{1}}:=\left\{r_{2}\right\}$ 이다. Corollary 2. $\mu$가 $\left\{c_{1}, c_{2}\right\}$에 대해 균일하다고 하자. 그러면 어떤 trigram 모델이든 최소 1/2의 생성 오류율을 가져야 한다.

이는 Theorem 3으로부터 도출되는데, $C=2$이고 trigram 모델의 경우 $\operatorname{opt}(\mathcal{G})=1 / 2$이기 때문이다. Theorem 3과 Corollary 2의 증명은 Section C에 있다. $n$-gram 모델은 더 큰 $n$에 대해 더 긴 범위의 의존성을 포착할 수 있지만, 데이터 요구 사항은 $n$에 따라 기하급수적으로 증가한다.

이제 서론에서 언급했던 글자 세기 예시를 다시 살펴보자. 이것이 모델의 문제임을 이해하기 위해, DeepSeek-R1 reasoning 모델이 글자를 안정적으로 세는 것을 주목하라. 예를 들어, 다음과 같은 377단계의 chain-of-thought를 생성한다:

Let me spell it out: D-E-E-P-S-E-E-K. First letter: D - that's one D. Second letter: E - not D. Third letter: E - not D. . . So, the number of Ds is 1 .

유사한 학습 데이터를 가정할 때, 이는 R1이 DeepSeekV3 모델보다 해당 task에 더 적합한 모델임을 시사한다. reasoning이 극복하는 한 가지 표현적 과제는 최신 language model이 개별 문자(character)가 아닌 토큰(token)으로 prompt를 표현한다는 점이다 (예: D/EEP/SEE/K) (DeepSeek-AI et al., 2025).

3.4 Additional factors

오류는 위에서 논의된 요인들과 여러 다른 요인들의 조합으로 인해 발생할 수 있다. 여기서는 몇 가지를 강조한다.

• 계산적 난이도 (Computational Hardness). 고전 컴퓨터에서 실행되는 어떤 알고리즘도, 심지어 초인적인 능력을 가진 AI라 할지라도, 계산 복잡도 이론의 법칙을 위반할 수 없다. 실제로 AI 시스템은 계산적으로 어려운 문제(computationally hard problems)에서 오류를 범하는 것으로 밝혀졌다 (Xu et al., 2024). Section D의 Observation 2는 Theorem 1이 "c의 암호 해독은 무엇인가?"와 같은 **다루기 힘든 쿼리(intractable queries)**에 어떻게 적용되며, IDK(I Don't Know)가 유효한 답변이 될 수 있음을 보여준다.
• 분포 변화 (Distribution shift). 이진 분류(binary classification)에서 잘 알려진 도전 과제는 학습 및 테스트 데이터 분포가 종종 달라진다는 점이다 (Quiñonero-Candela et al., 2009; Moreno-Torres et al., 2012). 이와 유사하게, 언어 모델의 오류는 종종 학습 분포와 크게 다른 out-of-distribution (OOD) prompt에서 비롯된다. "깃털 1파운드와 납 1파운드 중 어느 것이 더 무거운가?"와 같은 질문은 학습 데이터에 나타날 가능성이 낮으며, 특정 모델에서 오류가 있는 답변을 유도할 수 있다. 마찬가지로, 위에서 언급된 글자 세기 예시에서도 분포 변화가 한 요인이 될 수 있지만, 추론 모델이 글자를 정확히 센다는 사실은 성능이 좋지 않은 모델 자체가 더 큰 요인일 수 있음을 시사한다.
• GIGO: Garbage in, Garbage out. 대규모 학습 코퍼스에는 종종 수많은 사실적 오류가 포함되어 있으며, 이는 기반 모델에 의해 복제될 수 있다. 분류 및 사전학습 모두에서 GIGO의 통계적 유사성은 자명하므로, 우리는 공식적인 처리를 제공하지 않는다. 그러나 언어 모델이 학습 데이터의 오류를 복제하는 것으로 나타났기 때문에 (Lin et al., 2022b, Levy et al., 2021, Alber et al., 2025), GIGO를 통계적 요인 중 하나로 인식하는 것이 중요하다.

GIGO는 또한 post-training이라는 주제로 자연스럽게 이어진다. post-training은 일반적인 오해나 음모론과 같은 특정 GIGO 오류를 감소시킨다 (Ouyang et al., 2022; OpenAI, 2023a Costello et al., 2024). 다음 섹션에서는 일부 hallucination이 현재의 post-training 파이프라인에 의해 왜 지속되고 심지어 악화될 수 있는지를 설명한다.

4 Post-training and hallucination

**후속 학습(post-training)**은 모델이 자동 완성(autocomplete) 모델처럼 학습된 상태에서, 확신에 찬 거짓 정보(confident falsehoods)를 출력하지 않는 모델로 전환되어야 한다 (예외적으로, 소설 창작과 같이 적절한 경우 제외). 그러나 우리는 환각(hallucination)을 추가적으로 줄이는 것이 어려운 싸움이라고 주장한다. 그 이유는 기존 벤치마크와 리더보드가 특정 유형의 환각을 오히려 강화하기 때문이다. 따라서 우리는 이러한 강화를 멈추는 방법에 대해 논의한다. 이는 기존 평가 방식이 수정되어야 할 뿐만 아니라, 이러한 변화가 영향력 있는 리더보드에 채택되어야 한다는 의미에서 **사회-기술적 문제(socio-technical problem)**이다.

4.1 How evaluations reinforce hallucination

언어 모델에 대한 **이진 평가(binary evaluation)**는 잘못된 이분법(false right-wrong dichotomy)을 강요하며, 불확실성을 표현하거나, 의심스러운 세부 사항을 생략하거나, 설명을 요청하는 답변에 대해서는 어떠한 점수도 부여하지 않는다. 아래에서 논의하겠지만, **정확도(accuracy) 및 통과율(pass rate)**을 포함한 이러한 지표들은 여전히 이 분야의 지배적인 규범으로 남아 있다.
이진 채점 방식에서는 기권(abstaining)하는 것이 엄격하게 차선책이다. IDK(I Don't Know) 유형의 응답은 최대의 불이익을 받는 반면, 지나치게 자신감 있는 "최고의 추측(best guess)"이 최적의 선택이 된다. 이러한 동기는 두 가지 바람직한 요소를 결합한다: (a) 언어 모델이 출력하는 내용 중 정확도 비율, 그리고 (b) 응답이 얼마나 포괄적인지이다. 그러나 환각(hallucination)을 줄이기 위해서는 (a)를 (b)보다 더 중요하게 고려하는 것이 중요하다.

형식적으로, prompt $c$ 형태의 주어진 질문에 대해, 그럴듯한 응답(유효하거나 오류인 응답)의 집합을 $\mathcal{R}_{c}:=\{r \mid(c, r) \in \mathcal{X}\}$로 나타낸다. 또한, 그럴듯한 기권 응답(abstention response)의 집합을 $\mathcal{A}_{c} \subset \mathcal{R}_{c}$ (예: IDK)라고 가정한다. 채점자(grader) $g_{c}: \mathcal{R}_{c} \rightarrow \mathbb{R}$는 $\left\{g_{c}(r) \mid r \in \mathcal{R}_{c}\right\}=\{0,1\}$이고 모든 $r \in \mathcal{A}_{c}$에 대해 $g_{c}(r)=0$일 때 이진적(binary)이라고 정의된다.
문제는 ($c, \mathcal{R}_{c}, \mathcal{A}_{c}, g_{c}$)로 정의되며, 여기서 시험 응시자는 $c, \mathcal{R}_{c}, \mathcal{A}_{c}$를 알고 있다. 우리는 시험 응시자가 채점 기준이 이진적이라는 것을 알지만, $g_{c}(r)=1$인 정답은 알려주지 않는다고 가정한다. 정답에 대한 시험 응시자의 믿음은 이진 $g_{c}$에 대한 사후 분포 $\rho_{c}$로 볼 수 있다. 이러한 믿음이 있을 때, 최적의 응답은 기권하지 않는 것이다.

관찰 1. $c$를 prompt라고 하자. 이진 채점자에 대한 어떤 분포 $\rho_{c}$에 대해서도, 최적의 응답은 기권이 아니다. 즉,

$$\mathcal{A}_{c} \cap \underset{r \in \mathcal{R}_{c}}{\arg \max } \underset{g_{c} \sim \rho_{c}}{\mathbb{E}}\left[g_{c}(r)\right]=\emptyset$$

증명은 자명하지만(Section E 참조), 관찰 1은 기존 평가 방식이 수정될 필요가 있음을 시사한다. Table 2는 Section F의 짧은 메타 평가 분석을 요약하며, 대다수의 인기 있는 평가가 이진 채점 방식을 사용하고 있음을 보여준다. 따라서, 주요 평가가 솔직한 확신 및 불확실성 보고에 불이익을 줄 때에는 추가적인 환각 평가만으로는 충분하지 않을 수 있다. 이는 환각 평가에 대한 기존 연구를 폄하하는 것이 아니라, 이상적인 환각 평가와 이상적인 후처리(post-training) 방법론이 불확실성을 솔직하게 보고하더라도, 기존 평가의 대다수에서 낮은 성능으로 인해 그 가치가 희석될 수 있음을 지적하는 것이다.

4.2 Explicit confidence targets

인간의 시험 또한 대부분 이진적(binary)이며, 과도한 자신감으로 허풍을 떠는 행위(overconfident bluffing)에 보상을 준다는 점이 인식되어 왔다. 물론, 시험은 인간 학습의 작은 부분에 불과하며, 예를 들어 생일을 조작하면 금방 당황스러운 상황에 처하게 될 것이다. 그럼에도 불구하고, 일부 표준화된 국가 시험은 **오답에 대한 감점(또는 이에 상응하는 기권에 대한 부분 점수)**을 적용하거나 적용해왔다. 여기에는 인도의 JEE, NEET, GATE 시험; 미국 수학 협회(Mathematical Association of America)의 AMC 시험; 그리고 과거 미국의 표준화된 SAT, AP, GRE 시험 등이 포함된다. 중요한 점은, 채점 시스템이 지침에 명확하게 명시되어 있으며, 응시자들은 어느 정도의 자신감 임계값을 넘어서야 최선의 추측을 하는 것이 합리적인지를 종종 인지하고 있다는 것이다.

이와 유사하게, 우리는 평가 지침(prompt 또는 system message)에 자신감 목표(confidence target)를 명시적으로 포함할 것을 제안한다. 예를 들어, 각 질문에 다음과 같은 문구를 추가할 수 있다:

정답은 1점을 받고, "모르겠습니다(I don't know)"는 0점을 받으며, 오답은 $t / (1-t)$ 점 감점되므로, 자신감이 $t$보다 클 경우에만 답변하시오.

$t$에는 $t=0.5$ (감점 1), $t=0.75$ (감점 2), $t=0.9$ (감점 9)와 같은 몇 가지 자연스러운 값이 있다. $t=0$의 임계값은 이진 채점(binary grading)에 해당하며, 예를 들어 "시험을 치르는 것처럼 확신이 없더라도 최선을 다해 추측하시오"와 같이 설명될 수 있다. 간단한 계산을 통해 답변을 제시하는 것의 기대 점수가 "모르겠습니다(IDK)"(점수 0)를 능가하는 경우는 해당 답변의 자신감(즉, 정답일 확률)이 $t$보다 클 때뿐임을 알 수 있다.

이러한 감점 방식은 환각(hallucination) 연구에서 잘 다루어져 왔다 (Ji et al., 2023). 그러나 우리는 통계적 파급 효과를 가지는 두 가지 미묘한 변형을 제안한다. 첫째, 우리는 자신감 임계값을 지침에 명시적으로 포함할 것을 제안한다. 반면 기존 연구들은 지침에 자신감 목표나 감점을 언급하는 것을 대체로 생략해왔다. (Wu et al. (2025)의 연구는 명시적인 감점을 포함하는 "risk-informing" prompt를 도입했다는 점에서 주목할 만한 예외이다.) 이상적인 감점은 실제 세계의 피해를 반영할 수 있지만, 이는 문제, 대상 애플리케이션 및 사용자 그룹에 따라 다르므로 비실용적이다. 지침 내에 투명한 명시가 없다면, 언어 모델 개발자들 사이에서 올바른 임계값에 대한 합의를 이루기 어려울 것이다. 마찬가지로, 학생들은 오류에 대한 불특정 감점이 있다는 지침이 주어졌을 때 채점이 불공평하다고 불평할 수 있다. 대신, 각 문제의 지침에 자신감 임계값을 명시적으로 지정하는 것은, 선택된 특정 임계값이 다소 임의적이거나 심지어 무작위적이더라도 객관적인 채점을 지원한다. 임계값이 명시적이라면, 단일 모델이 모든 임계값에서 최적일 수 있다. 그러나 임계값이 명시되지 않으면 본질적인 trade-off가 존재하며, 일반적으로 단일 모델이 최적일 수는 없을 것이다 (항상 정답인 모델 외에는).

둘째, 우리는 자신감 목표를 기존의 주류 평가에 통합할 것을 제안한다. 예를 들어, 소프트웨어 패치에 대한 이진 채점을 포함하는 인기 있는 SWE-bench (Jimenez et al., 2024)와 같은 평가에 통합하는 것이다. 반면, 기존 연구의 대부분은 맞춤형 환각 평가에서 암묵적인 오류 감점을 도입해왔다. 단순히 암묵적인 오류 감점을 포함하는 평가를 추가하는 것은 앞서 언급한 정확도-오류 trade-off에 직면한다. 반면에, 이미 사용 중인 기존 평가에 자신감 목표를 통합하는 것은 불확실성의 적절한 표현에 대한 감점을 줄여준다. 따라서 이는 환각 특정 평가의 효과를 증폭시킬 수 있다.

Table 2: 본 연구에서 분석된 평가 벤치마크 및 기권 처리 방식 요약. "Binary grading"은 주된 측정 지표가 엄격한 정답/오답 정확도임을 나타내며, "IDK credit"은 기권이 점수를 얻을 수 있는지 여부를 나타낸다.

• 채점은 언어 모델을 사용하여 수행되므로, 잘못된 허풍이 때때로 정답으로 채점될 수 있습니다. ${ }^{\text {a }}$ IFEval은 여러 이진 채점 하위 점수를 종합 점수로 집계합니다. ${ }^{\mathrm{b}}$ 채점 기준(1-10점 척도)은 IDK가 환각이 있는 "공정한" 답변보다 낮은 점수를 받을 수 있음을 시사하며, 이는 환각을 강화합니다.

명시적인 자신감 목표가 있다면, 모든 목표에 대해 동시에 최적인 하나의 행동이 존재한다. 즉, 정확성 확률이 목표보다 큰 예시들 중에서 "모르겠습니다(IDK)"를 출력하는 것이다. 이를 **행동적 보정(behavioral calibration)**이라고 부르자. 이는 모델이 확률적 자신감을 출력하도록 요구하는 대신 (Lin et al., 2022a), 최소한 $t$만큼 확신하는 가장 유용한 응답을 구성해야 함을 의미한다. 행동적 보정은 임계값에 따른 정확도와 오류율을 비교하여 감사할 수 있으며, 정답을 표현하는 방법이 기하급수적으로 많을 수 있다는 문제 (Farquhar et al., 2024)를 우회한다. 기존 모델이 행동적 보정을 나타낼 수도 있고 나타내지 않을 수도 있지만, 이는 객관적인 평가로서 유용할 수 있다.

5 Discussion and limitations

환각(hallucination)은 다면적인 특성 때문에, 이 분야에서 환각을 정의하고, 평가하며, 줄이는 방법에 대해 합의를 이루기 어렵다. 통계적 프레임워크는 단순화를 위해 특정 측면을 우선시하고 다른 측면은 생략해야 한다. 본 논문에서 사용된 프레임워크의 범위와 한계에 대해 몇 가지 사항을 언급하고자 한다.

그럴듯함(Plausibility)과 무의미함(nonsense)
환각은 **그럴듯한 거짓(plausible falsehood)**이며, 우리는 그럴듯한 문자열 $\mathcal{X}$만을 고려함으로써, 무의미한 문자열 생성 가능성(최신 language model은 거의 생성하지 않음)을 분석에서 제외한다. 그러나 Theorem 1의 명제와 증명은 무의미한 예시 $\mathcal{N}$에 대한 수정된 정의와 함께, 분할 $\mathcal{X}=\mathcal{N} \cup \mathcal{E} \cup \mathcal{V}$, err $:=\hat{p}(\mathcal{N} \cup \mathcal{E})$, $D(\mathcal{N})=0$, 그리고 $p(\mathcal{V})=1$이라는 가정 하에 유효하다.

Open-ended 생성
단순화를 위해, 본 논문에서 제시된 예시들은 단일 사실 질문에 초점을 맞추고 있다. 그러나 환각은 종종 "...에 대한 전기를 써라"와 같은 open-ended prompt에서 발생한다. 이는 하나 이상의 거짓을 포함하는 응답을 오류로 정의함으로써 우리의 프레임워크에 포함될 수 있다. 하지만 이러한 경우, 오류의 개수에 따라 환각의 정도를 고려하는 것이 자연스러울 것이다.

검색(및 추론)은 만병통치약이 아니다
여러 연구에서 검색(search) 또는 Retrieval-Augmented Generation (RAG)으로 강화된 language model이 환각을 줄이는 방법을 보여주었다 (Lewis et al., 2020; Shuster et al., 2021, Nakano et al., 2021, Zhang and Zhang, 2025). 그러나 Observation 1은 RAG를 포함한 임의의 language model에 대해 유효하다. 특히, 이진 채점 시스템 자체는 검색이 확신할 수 있는 답변을 제공하지 못할 때마다 추측에 보상을 준다. 더욱이, 검색은 글자 세기 예시와 같은 오계산이나 다른 내재적 환각(intrinsic hallucination)에는 도움이 되지 않을 수 있다.

잠재적 맥락(Latent context)
일부 오류는 prompt와 응답만으로는 판단할 수 없다. 예를 들어, 사용자가 휴대폰에 대해 질문했는데 language model이 휴대전화에 대한 응답을 제공했지만, 질문의 의도는 유선 전화에 대한 것이었다고 가정해보자. 이러한 모호성은 prompt와 응답 외부의 맥락에 의존하지 않는 우리의 오류 정의에는 맞지 않는다. language model에 주어진 prompt의 일부가 아니지만 오류를 판단하는 데 사용될 수 있는 "숨겨진 맥락"을 허용하도록 모델을 확장하는 것은 흥미로운 일이며, 이는 aleatoric uncertainty와 관련이 있다.

잘못된 삼분법(A false trichotomy)
우리의 형식주의는 오류의 크기나 불확실성의 정도를 구분하지 않는다. 분명히, 정확/부정확/IDK(I Don't Know) 범주 또한 불완전하다. 비록 통계적 이상은 다운스트림 애플리케이션에서 language model을 평가하고 싶은 방식대로 각 평가에 점수를 매기는 것이겠지만, 명시적인 신뢰도 목표는 주류 평가에 실용적이고 객관적인 수정을 제공하며, 잘못된 삼분법은 적어도 잘못된 이분법과 달리 IDK 옵션을 제공할 수 있다.

IDK를 넘어서
불확실성을 나타내는 방법은 회피(hedging), 세부 사항 생략, 질문하기 등 다양하다. 궁극적으로 language model은 **언어적 보정(linguistic calibration)**과 같은 신뢰도 개념을 따를 수 있다 (Mielke et al., 2022, Damani et al., 2025). 그러나 **언어의 실용적 현상(pragmatic phenomena)**은 미묘하다 (Austin, 1962, Grice, 1975). 예를 들어, language model이 명시적으로 확률적 신뢰도 추정치를 진술하는 것이 유용할 수 있는 경우도 있지만 (Lin et al., 2022a), 이는 또한 "Kalai의 생일이 3월 7일일 확률은 1/365입니다."와 같이 부자연스러운 발화로 이어질 수 있다. 본 논문은 무엇이 말해지는지에 대한 최상위 결정과 관련된 통계적 요인에 초점을 맞춘다.

6 Conclusions

본 논문은 **현대 language model의 환각(hallucination)**을 사전학습(pretraining) 중의 발생 원인부터 후속 학습(post-training)을 통한 지속성에 이르기까지 명확히 설명한다. 사전학습 단계에서 우리는 생성 오류(generative errors)가 supervised learning에서의 오분류(misclassifications)와 유사하며, 이는 cross-entropy loss의 최소화 과정에서 자연스럽게 발생하는 현상임을 보여준다.

많은 language model의 단점은 단일 평가(single evaluation)로 포착될 수 있다. 예를 들어, "Certainly"라는 시작 표현의 과도한 사용은 **단일 "Certainly" 평가(Amodei and Fridman, 2024)**로 해결될 수 있다. 이는 "Certainly"로 응답을 시작하는 것이 다른 평가에 크게 영향을 미치지 않기 때문이다. 이와 대조적으로, 우리는 대부분의 주류 평가(mainstream evaluations)가 환각적 행동에 보상을 준다고 주장한다. 주류 평가를 간단히 수정하면 이러한 인센티브를 재조정하여, 부적절한 불확실성 표현을 처벌하는 대신 적절한 불확실성 표현에 보상을 줄 수 있다. 이는 환각 억제의 장벽을 제거하고, 예를 들어 더 풍부한 화용론적 능력(pragmatic competence)을 가진 미묘한 language model(Ma et al., 2025)에 대한 미래 연구의 문을 열 수 있다.

감사의 글 (Acknowledgments). 유익한 논의를 제공해 준 Alex Beutel, Tom Cunningham, Yann Dubois, Parikshit Gopalan, Johannes Heidecke, Zoe Hitzig, Saachi Jain, Manas Joglekar, Sanjay Kairam, Ehud Kalai, Amin Karbasi, Alan Luo, Anay Mehrotra, Eric Mitchell, Cameron Raymond, David G. Robinson, Mandip Shah, Joshua Vendrow, Grigoris Velegkas, Rose Wang, Zhigang Wang, Jason Wolfe, 그리고 Jason Wei에게 감사드린다.

A Proof of the main theorem

이제 주요 정리를 증명한다. 정리 1의 증명. $K:=\min _{c \in \mathcal{C}}\left|\mathcal{E}_{c}\right|$ 및 $k:=\max _{c \in \mathcal{C}}\left|\mathcal{V}_{c}\right|$라고 하자. 또한, $\delta=|\hat{p}(\mathcal{A})-p(\mathcal{A})|$임을 상기하자. 이는 $\delta=|p(\mathcal{B})-\hat{p}(\mathcal{B})|$와 동등하게 표현될 수 있으며, 여기서 $\mathcal{A}, \mathcal{B}$는 각각 임계값(threshold)을 초과하는 응답과 미달하는 응답을 나타낸다:

$$\begin{aligned} \mathcal{A} & :=\{(c, r) \in \mathcal{X} \mid \hat{p}(r \mid c)>1 / K\} \\ \mathcal{B} & :=\{(c, r) \in \mathcal{X} \mid \hat{p}(r \mid c) \leq 1 / K\} \end{aligned}$$

hallucination 및 misclassification 비율을 임계값 초과 및 미달 비율로 분할한다:

$$\begin{aligned} \mathrm{err} & =\hat{p}(\mathcal{A} \backslash \mathcal{V})+\hat{p}(\mathcal{B} \backslash \mathcal{V}) \\ \operatorname{err}_{\mathrm{iiv}} & =D(\mathcal{A} \backslash \mathcal{V})+D(\mathcal{B} \cap \mathcal{V}) \end{aligned}$$

임계값 초과(above the threshold)에서, misclassification $D(\mathcal{A} \backslash \mathcal{V})$는 $(c, r) \in \mathcal{A}$이면서 $r \in \mathcal{E}_{c}$인 경우에만 $D(c, r)$을 합한 값이다. 각 $D(c, r)$은 $\mu(c) / 2\left|\mathcal{E}_{c}\right| \leq \mu(c) / 2 K$를 기여한다. 그러나 이러한 각 misclassification은 임계값 초과 hallucination $\hat{p}(\mathcal{A} \backslash \mathcal{V})$에 $\mu(c) \hat{p}(r \mid c) \geq \mu(c) / K$를 기여한다. 따라서,

$$\hat{p}(\mathcal{A} \backslash \mathcal{V}) \geq 2 D(\mathcal{A} \backslash \mathcal{V})$$

그러므로, 임계값 미달(below the threshold)에서 다음을 보이는 것만 남았다:

$$\hat{p}(\mathcal{B} \backslash \mathcal{V}) \geq 2 D(\mathcal{B} \cap \mathcal{V})-\frac{k}{K}-\delta$$

정의에 따라, $2 D(\mathcal{B} \cap \mathcal{V})=p(\mathcal{B} \cap \mathcal{V})=p(\mathcal{B})$이다. 또한, 각 $c$에 대해 $\left|\mathcal{V}_{c}\right| \leq k$개의 유효한 응답이 있으며, $\mathcal{B}$에 속하는 각 응답은 $\hat{p}(r \mid c) \leq 1 / K$를 가지므로, $\hat{p}(\mathcal{B} \cap \mathcal{V}) \leq \sum_{c} \hat{p}(c) k / K=k / K$이다. 따라서,

$$\begin{aligned} 2 D(\mathcal{B} \cap \mathcal{V})-\hat{p}(\mathcal{B} \backslash \mathcal{V}) & =p(\mathcal{B})-\hat{p}(\mathcal{B} \backslash \mathcal{V}) \\ & =p(\mathcal{B})-(\hat{p}(\mathcal{B})-\hat{p}(\mathcal{B} \cap \mathcal{V})) \\ & \leq \delta+\hat{p}(\mathcal{B} \cap \mathcal{V}) \leq \delta+\frac{k}{K} \end{aligned}$$

이는 필요한 Eq. (6)과 동등하다.

B Arbitrary-facts analysis

우리는 먼저 Good-Turing (GT) missing mass 추정량 (Good, 1953)과 그 보장 (McAllester and Ortiz, 2003)을 검토한다. 이 설정에서, $N$개의 iid 샘플 $s \sim \nu^{N}$는 집합 $\mathcal{S}$에 대한 분포 $\nu$로부터 추출된다. 여기서 기권(abstention)은 고려 대상이 아니다. missing mass는 $\nu$로부터 새로 추출된 예시가 훈련 샘플 $s$에 포함되지 않을 확률이며, GT 추정치는 정확히 한 번만 나타나는 훈련 샘플의 비율이다. 우리는 먼저 기존의 보장을 제시한 다음, 이를 기권이 있는 우리의 설정에 맞게 조정한다. McAllester and Ortiz (2003)의 보장은 다음과 같이 기술될 수 있다:

Corollary 3. (McAllester and Ortiz, 2003) 집합 $\mathcal{S}$에 대한 분포 $\nu$로부터 추출된 $N$개의 iid 샘플 $s \sim \nu^{N}$가 있다고 가정하자. $M:=\operatorname{Pr}_{x \sim \nu}[x \notin s]$이고 GT는 정확히 한 번만 나타나는 샘플의 비율이라고 하자. 임의의 $\gamma \in(0,1]$에 대해:

$$\operatorname{Pr}_{s \sim \nu^{N}}\left[|M-\mathrm{GT}| \leq \frac{1}{N}+2.42 \sqrt{\frac{\ln (4 / \gamma)}{N}}\right] \geq 1-\gamma$$

증명. $\overline{\mathrm{GT}}:=\mathbb{E}[\mathrm{GT}]$ 및 $\bar{M}:=\mathbb{E}[M]$이라고 하자. 이 보장은 $M$과 GT에 대한 **집중 경계(concentration bounds)**를 결합하여 얻어진다. 먼저 McAllester and Schapire (2000)의 Theorem 1은 다음을 보여준다:

$$\overline{\mathrm{GT}}-\bar{M} \in[0,1 / N]$$

그 다음, McAllester and Ortiz (2003)의 Theorem 10과 16은 확률 $\leq \exp \left(-N \varepsilon^{2}\right)$로 $M$이 $\bar{M}$로부터 $\varepsilon$ 이상 벗어날 것임을 의미하며, union bound를 통해 $\varepsilon:=\sqrt{\frac{\ln (4 / \gamma)}{N}}$에 대해 다음을 얻는다:

$$\operatorname{Pr}_{s \sim \nu^{N}}\left[|M-\bar{M}| \geq \sqrt{\frac{\ln (4 / \gamma)}{N}}\right] \leq \frac{\gamma}{4}+\frac{\gamma}{4}=\frac{\gamma}{2} .$$

McAllester and Schapire (2000) (Lemma 13)에 따라, McDiarmid의 부등식 (McDiarmid, 1989)은 GT의 수렴을 직접적으로 의미한다. 왜냐하면 어떤 하나의 예시를 변경해도 GT는 최대 $2/N$만큼만 변경될 수 있기 때문이다. 따라서,

$$\operatorname{Pr}_{s \sim \nu^{N}}\left[|\mathrm{GT}-\overline{\mathrm{GT}}| \geq \sqrt{\frac{2 \ln (4 / \gamma)}{N}}\right] \leq 2 \exp \left(-\frac{2 \cdot \frac{2 \ln (4 / \gamma)}{N}}{4 / N}\right)=\frac{\gamma}{2} .$$

이 세 가지 방정식을 union bound로 결합하면 다음을 얻는다:

$$\operatorname{Pr}_{s \sim \nu^{N}}\left[|\mathrm{GT}-M| \geq \frac{1}{N}+(1+\sqrt{2}) \sqrt{\frac{\ln (4 / \gamma)}{N}}\right] \leq \frac{\gamma}{2}+\frac{\gamma}{2}=\gamma$$

마지막으로, $1+\sqrt{2} \leq 2.42$로부터 보조정리가 도출된다. 이제 우리는 이를 기권 응답 IDK가 sr에 포함되지 않는 경우로 확장한다. 구체적으로, 쿼리 $c$가 훈련 데이터에서 답변되었다는 것은 $c^{(i)}=c$이고 $r^{(i)} \neq \mathrm{IDK}$인 훈련 예시 $\left(c^{(i)}, r^{(i)}\right)$가 존재함을 의미하며, 그렇지 않으면 답변되지 않았다고 말한다.

$$\mathcal{U}:=\mathcal{C} \backslash\left\{c^{(i)} \mid i \leq N, r^{(i)} \neq \mathrm{IDK}\right\}$$

는 답변되지 않은 쿼리(unanswered queries)의 집합을 나타낸다. 물론, 답변된 쿼리에 대해 $a_{c}$를 기억함으로써, 답변된 쿼리를 완벽하게 분류할 수 있다. 우리는 Turing의 Missing Mass (MM) 추정치를 기권에 대해 다음과 같이 확장한다:

$$\mathrm{MM}:=\operatorname{Pr}_{(c, r) \sim p}[c \in \mathcal{U} \wedge r \neq \mathrm{IDK}]$$

우리는 유사하게 Corollary 3을 사용하여 sr이 MM의 좋은 추정치임을 보여준다: Lemma 1. 모든 $N, \gamma \in(0,1]$에 대해:

$$\operatorname{Pr}\left[|\mathrm{MM}-\mathrm{sr}| \leq 4.42 \sqrt{\frac{\ln (5 / \gamma)}{N}}\right] \geq 1-\gamma$$

증명. 우리의 MM-sr과 표준 $M$ - GT의 유일한 차이점은 우리가 기권을 무시한다는 것이다. 이전 경계를 조정하기 위해, 모든 $x=(c, \mathrm{IDK})$를 단순히 $x=\mathrm{IDK}$로 대체하고, 그 외에는 $x$를 변경하지 않은 샘플 $s$를 고려한다. 이는 모든 IDK 응답을 동일한 예시로 붕괴시킨다. 따라서 GT는 sr에 비해 최대 하나의 추가적인 singleton을 셀 수 있다.

$$\mathrm{GT}-\mathrm{sr} \in\left\{0, \frac{1}{N}\right\}$$

위의 대체는 분포 $\phi$를 유도하며, 여기서 $\phi(\mathrm{IDK})=\sum_{c} \mu(c) p(\mathrm{IDK} \mid c)$는 기권할 확률이다. 유사하게, $M-\mathrm{MM} \in\{0, \phi(\mathrm{IDK})\}$이며, $\mathrm{IDK} \notin s$인 경우 $M-\mathrm{MM}=\phi(\mathrm{IDK})$가 되는데, 이는 확률 $(1-\phi(\mathrm{IDK}))^{N}$로 발생한다. 그러나 $\phi(\mathrm{IDK}) \geq \frac{1}{N} \ln \frac{5}{\gamma}$인 경우 $(1-\phi(\mathrm{IDK}))^{N} \leq \gamma / 5$이다. 따라서 $\phi(\mathrm{IDK})$ 값에 관계없이,

$$\operatorname{Pr}\left[M-\mathrm{MM} \in\left[0, \frac{1}{N} \ln \frac{5}{\gamma}\right]\right] \geq 1-\frac{\gamma}{5}$$

위의 두 방정식을 결합하면,

$$\operatorname{Pr}\left[|(M-\mathrm{GT})-(\mathrm{MM}-\mathrm{sr})| \leq \frac{1}{N} \ln \frac{5}{\gamma}\right] \geq 1-\frac{\gamma}{5}$$

$\frac{4}{5} \gamma$에서의 Corollary 3은 다음을 제공한다:

$$\operatorname{Pr}\left[|M-\mathrm{GT}| \leq \frac{1}{N}+2.42 \sqrt{\frac{\ln (5 / \gamma)}{N}}\right] \geq 1-\frac{4}{5} \gamma$$

Eq. (7)과 결합하면, union bound와 **삼각 부등식(triangle inequality)**에 의해 다음을 얻는다:

$$\operatorname{Pr}\left[|\mathrm{MM}-\mathrm{sr}| \leq \frac{1}{N} \ln \frac{5}{\gamma}+\frac{1}{N}+2.42 \sqrt{\frac{\ln (5 / \gamma)}{N}}\right] \geq 1-\gamma$$

마지막으로, $z:=\frac{2}{N} \ln \frac{5}{\gamma} \geq \frac{1}{N} \ln \frac{5}{\gamma}+\frac{1}{N}$에 대해 $z \leq 1$인 한 $z \leq \sqrt{z}$라는 사실로부터 보조정리가 도출된다 (그렇지 않으면 경계가 $>2$이므로 보조정리는 자명하게 성립한다).

Lemma 2. 임의의 $N \geq 1, \gamma \in(0,1]$ 및 $\hat{p}$를 출력하는 임의의 알고리즘에 대해,

$$\operatorname{Pr}\left[2 \operatorname{err}_{\mathrm{iiv}} \geq \mathrm{sr}-\frac{6 \ln (3 N / \gamma)}{\sqrt{N}}\right] \geq 1-\gamma$$

증명. Lemma 1에 의해,

$$\operatorname{Pr}\left[|\mathrm{MM}-\mathrm{sr}| \leq 4.42 \sqrt{\frac{\ln (10 / \gamma)}{N}}\right] \geq 1-\frac{\gamma}{2}$$

$N \geq 2$에 대해 $\sqrt{\ln (10 / \gamma)} \leq \ln (3 N / \gamma)$임을 주목하라 (그리고 $N=1$에 대해서는 보조정리가 자명하게 성립한다). 또한, $\sqrt{2}+4.42 \leq 6$이다. 따라서 다음을 보여주는 것으로 충분하다:

$$\operatorname{Pr}\left[2 \operatorname{err}_{\mathrm{iiv}} \geq \mathrm{MM}-\sqrt{\frac{2}{N}} \ln \frac{3 N}{\gamma}\right] \geq 1-\frac{\gamma}{2}$$

$\zeta:=\ln (3 N / \gamma) / N$이라고 하고, $p$에 따라 각 쿼리가 답변(IDK가 아님)과 함께 나타날 확률을 다음과 같이 정의하자:

$$\mu^{\prime}(c):=\mu(c) \alpha_{c}$$

따라서 $a_{c}$가 선택되면 $\mu^{\prime}(c)=p\left(c, a_{c}\right)$이다. 또한 $\mathrm{MM}=\sum_{c \in \mathcal{U}} \mu^{\prime}(c)$임을 주목하라. 따라서 보조정리는 다음 두 부등식으로부터 도출된다:

$$\begin{aligned} \operatorname{Pr}\left[\forall c \in \mathcal{U} \mu^{\prime}(c) \leq \zeta\right] & \geq 1-\frac{\gamma}{3} \\ \operatorname{Pr}\left[\left.2 \operatorname{err}_{\mathrm{iiv}} \geq \mathrm{MM}-\sqrt{\frac{2}{N}} \ln \frac{3 N}{\gamma} \right\rvert\, \forall c \in \mathcal{U} \mu^{\prime}(c) \leq \zeta\right] & \geq 1-\frac{\gamma}{6} . \end{aligned}$$

$\mu^{\prime}(c) \leq \zeta$ 조건은 Hoeffding bound를 사용할 수 있게 해준다. Eq. (8)에 대해, $\mu^{\prime}(c) \geq \zeta$인 쿼리 $c$는 $\leq 1 / \zeta$개임을 주목하라. 이러한 각 쿼리에 대해 $c \in \mathcal{U}$일 확률은 최대 $(1-\zeta)^{N}$이다. 따라서 union bound에 의해,

$$\operatorname{Pr}\left[\exists c \in \mathcal{U}: \mu^{\prime}(c)>\zeta\right] \leq \frac{1}{\zeta}(1-\zeta)^{N} \leq \frac{1}{\zeta} e^{-\zeta N}=\frac{N}{\ln (3 N / \gamma)} \frac{\gamma}{3 N} \leq \frac{\gamma}{3},$$

이는 Eq. (8)과 동일하다. 이제 Eq. (9)를 설정하는 것으로 넘어간다. 술어 $\phi$가 참이면 1, 거짓이면 0을 나타내는 지시자 $\mathrm{I}[\phi]$를 사용하자. 오류 $\operatorname{err}_{\text {iiv}}$는 물론 $c \in \mathcal{U}, r \in \mathcal{R}_{c}$에 대해 합산된 오류보다 크거나 같으며, $D$의 정의에 의해 다음과 같다:

$$\begin{aligned} \operatorname{err}_{\text {iiv }} & \geq \frac{1}{2} \sum_{c \in \mathcal{U}} \mu(c) \alpha_{c} \mathrm{I}\left[\hat{f}\left(c, a_{c}\right)=-\right]+\frac{1}{2} \sum_{c \in \mathcal{U}} \mu(c) \sum_{r \in \mathcal{R}_{c} \backslash\left\{a_{c}\right\}} \frac{\mathrm{I}[\hat{f}(c, r)=+]}{\left|\mathcal{R}_{c}\right|-1} \\ & \geq \frac{1}{2} \sum_{c \in \mathcal{U}} \mu^{\prime}(c) \mathrm{I}\left[\hat{f}\left(c, a_{c}\right)=-\right]+\frac{1}{2} \sum_{c \in \mathcal{U}} \mu^{\prime}(c) \sum_{r \in \mathcal{R}_{c} \backslash\left\{a_{c}\right\}} \frac{\mathrm{I}[\hat{f}(c, r)=+]}{\left|\mathcal{R}_{c}\right|-1} \\ & =\sum_{c \in \mathcal{U}} \mu^{\prime}(c) \gamma_{c} \text { for } \gamma_{c}:=\frac{1}{2}\left(\mathrm{I}\left[\hat{f}\left(c, a_{c}\right)=-\right]+\sum_{r \in \mathcal{R}_{c} \backslash\left\{a_{c}\right\}} \frac{\mathrm{I}[\hat{f}(c, r)=+]}{\left|\mathcal{R}_{c}\right|-1}\right) \end{aligned}$$

따라서 $\operatorname{err}_{\text {iiv }} \geq \sum_{c \in \mathcal{U}} \mu^{\prime}(c) \gamma_{c}$이며, $\gamma_{c}$는 위에서 정의되었고 $\gamma_{c} \in[0,1]$임을 쉽게 알 수 있다. ($\mu^{\prime}(c) \leq \zeta$ 조건은 $\sum \mu^{\prime}(c) \gamma_{c}$에 Hoeffding bound를 적용할 수 있게 해준다.) 따라서 Eq. (9) 대신 다음을 보여주는 것으로 충분하다:

$$\operatorname{Pr}\left[\left.2 \sum_{c \in \mathcal{U}} \mu^{\prime}(c) \gamma_{c} \geq \mathrm{MM}-\sqrt{\frac{2}{N}} \ln \frac{3 N}{\gamma} \right\rvert\, \forall c \in \mathcal{U} \mu^{\prime}(c) \leq \zeta\right] \geq 1-\frac{\gamma}{6} .$$

이제 핵심적인 트릭이다: 알고리즘의 출력은 보이지 않는 $c \in \mathcal{U}$에 대한 $a_{c}$와 독립적이므로, 훈련 데이터에서 알고리즘을 실행하여 $\hat{f}$를 결정하는 $\hat{p}$를 선택한 후에야 보이지 않는 $c \in \mathcal{U}$에 대해 $a_{c}$가 선택된다고 상상할 수 있다. 따라서, $c_{v}$가 나중에 $c \in \mathcal{U}$에 대해 선택될 것이지만, 훈련 데이터와 $\hat{f}$는 이미 고정되어 있다고 가정하자.

그러면, $\mathbb{E}\left[\gamma_{c}\right]=1 / 2$임을 관찰할 수 있다. 왜냐하면 각 $r \in \mathcal{R}_{c}$는 $\hat{f}(c, r)= \pm$인지 여부에 관계없이 이 기댓값에 $1 / 2\left|\mathcal{R}_{c}\right|$를 기여하기 때문이다. 이는 $\mathrm{MM}=\sum_{c} \mu^{\prime}(c)$이므로 $\mathbb{E}\left[\sum_{c} \mu^{\prime}(c) \gamma_{c}\right]=\mathrm{MM} / 2$를 제공한다. 마지막으로, $\mu^{\prime}(c) \gamma_{c}$는 각각 $\left[0, \mu^{\prime}(c)\right]$에 있는 독립적인 확률 변수이므로 $\sum_{c} \mu^{\prime}(c) \gamma_{c}$에 Hoeffding bound를 적용할 수 있다. 이 경계는 다음에 의존한다:

$$\sum_{c \in \mathcal{U}}\left(\mu^{\prime}(c)\right)^{2} \leq \max _{c \in \mathcal{U}} \mu^{\prime}(c) \sum_{c \in \mathcal{U}} \mu^{\prime}(c) \leq \max _{c \in \mathcal{U}} \mu^{\prime}(c) \leq \zeta \text { if } \forall c \in \mathcal{U} \mu^{\prime}(c) \leq \zeta .$$

따라서 Hoeffding bound는 다음을 제공한다:

$$\operatorname{Pr}\left[\left.\sum \mu^{\prime}(c) \gamma_{c} \leq \frac{\mathrm{MM}}{2}-\sqrt{\frac{\zeta \ln (6 / \gamma)}{2}} \right\rvert\, \forall c \in \mathcal{U} \mu^{\prime}(c) \leq \zeta\right] \leq \frac{\gamma}{6}$$

이는 Eq. (10)을 의미한다. 왜냐하면 $\sqrt{2 \zeta \ln (6 / \gamma)}=\sqrt{2 \ln (3 N / \gamma) \ln (6 / \gamma) / N} \leq \ln (3 N / \gamma) \sqrt{2 / N}$이기 때문이다 ($N \geq 2$에 대해 $\ln (6 / \gamma) \leq \ln (3 N / \gamma)$를 사용하며, 다시 $N=1$에 대해서는 보조정리가 자명하게 성립한다).

이제 Theorem 2를 증명한다. Theorem 2의 증명. 임의의 $\gamma \in(0,1]$에 대한 다음의 더 일반적인 하한은 Theorem 1과 $\max _{c}\left|\mathcal{V}_{c}\right|=2$ 및 Lemma 2로부터 직접적으로 도출된다. 구체적으로, 확률 $\geq 1-\gamma$로:

$$\operatorname{err} \geq \operatorname{sr}-\frac{2}{\min _{c}\left|\mathcal{E}_{c}\right|}-\frac{6 \ln (3 N / \gamma)}{\sqrt{N}}-\delta$$

$\gamma=0.01$에서 $\geq 99 \%$ 확률에 대해, 우리는 $6 \ln (3 N / \gamma) \leq 35+6 \ln N$이라는 단순화를 사용한다. 이제 $L:=\max _{c}\left|\mathcal{E}_{c}\right|$라고 하자.

상한에 대해, 이제 우리는 calibrated $\hat{p}$를 출력하는 효율적인 알고리즘이 존재하며 (따라서 $\delta=0$), 확률 $\geq 1-\gamma$로 다음이 성립함을 보여준다:

$$\operatorname{err} \leq \mathrm{sr}-\frac{\mathrm{sr}}{L+1}+5 \sqrt{\frac{\ln (5 / \gamma)}{N}}$$

정리에서 $99 \%$ 확률 경계는 $5 \sqrt{\ln (500)} \leq 13$로부터 도출된다. calibrated language model 학습 알고리즘은 훈련 데이터에서 본 $(c, a_{c})$에 대해 $a_{c}$를 기억하고, 훈련 데이터에서 본 $c \notin \mathcal{U}$에 대해서는 $p$와 완벽하게 일치한다. 보이지 않는 $c \in \mathcal{U}$에 대해서는 올바른 확률 $1-\alpha_{c}$로 기권하지만, 그 외에는 $\mathcal{R}_{c}$에 대해 균일하게 무작위이다:

$$\hat{p}(c, r):= \begin{cases}1-\alpha_{c} & \text { if } r=\mathrm{IDK} \\ \alpha_{c} & \text { if } c \notin \mathcal{U}, r=a_{c} \\ \alpha_{c} /\left|\mathcal{R}_{c}\right| & \text { if } c \in \mathcal{U}, r \in \mathcal{R}_{c} \\ 0 & \text { otherwise. }\end{cases}$$

이 $\hat{p}$에 대해 다음이 성립함을 쉽게 알 수 있다:

$$\operatorname{err}=\sum_{c \in \mathcal{U}} \mu(c) \frac{\alpha_{c}}{\left|\mathcal{R}_{c}\right|}\left(\left|\mathcal{R}_{c}\right|-1\right) \leq \sum_{c \in \mathcal{U}} \mu(c) \alpha_{c} \frac{L}{L+1}=\mathrm{MM} \frac{L}{L+1} .$$

마지막으로, Lemma 1에 의해

$$\operatorname{Pr}\left[|\mathrm{MM}-\mathrm{sr}| \leq 5 \sqrt{\frac{\ln (5 / \gamma)}{N}}\right] \geq 1-\gamma$$

이것들은 다음을 의미한다:

$$\operatorname{Pr}\left[\operatorname{err} \leq \frac{L}{L+1} \mathrm{sr}+5 \sqrt{\frac{\ln (5 / \gamma)}{N}}\right] \geq 1-\gamma \cdot$$

필요한 대로. 이제 모든 $z \in[0,1]$에 대해 $\delta_{z}=0$임을 보여주는 것만 남았다. $\delta_{z}$의 정의에 의해,

$$\begin{aligned} \delta_{z} & \left.=\mid \operatorname{Pr}_{(c, r) \sim \hat{p}}[\hat{p}(r \mid c)>z]-\operatorname{Pr}_{(c, r) \sim p}[\hat{p}(r \mid c)>z]\right] \\ & =\left|\sum_{c} \mu(c) \sum_{r: \hat{p}(r \mid c)>z}(\hat{p}(r \mid c)-p(r \mid c))\right| \end{aligned}$$

정의에 의해 $\hat{p}(r \mid c)=p(r \mid c)$는 $c \in \mathcal{U}, r \in \mathcal{R}_{c}$를 제외한 모든 곳에서 성립한다. 그러나 각 $c \in \mathcal{U}$에 대해 $\hat{p}(c, r)$는 $r \in \mathcal{R}_{c}$에 대해 상수이므로, $\hat{p}(c, r)>z$는 모든 $r \in \mathcal{R}_{c}$에 대해 성립하거나 어느 것에도 성립하지 않는다. 따라서 위의 내부 합은 $\sum_{r \in \mathcal{R}_{c}} \hat{p}(r \mid c)-p(r \mid c)=0$이고 $\hat{p}(\operatorname{IDK} \mid c)=p(\operatorname{IDK} \mid c)$이므로 어떤 경우에도 0이다.

C Poor-model analysis

프롬프트당 하나의 정답만 있는, 즉 객관식 시험과 같은 상황에서는, 유일한 정답이 유효한 응답이고 다른 응답과 정답을 신뢰할 수 있게 구별할 수 없다면 오류가 발생할 수밖에 없다는 것이 직관적이다. 이러한 간단한 경우에 대해, 우리는 더 나은 bound를 가진 임계값 $t$의 존재를 보인다. 특히,

$$\operatorname{err}_{\text {iiv }}\left(\hat{f}_{t}\right):=\operatorname{Pr}_{x \sim D}\left[\hat{f}_{t}(x) \neq f(x)\right], \text { where } \hat{f}_{t}(c, r):= \begin{cases}+ & \text { if } \hat{p}(r \mid c)>t \\ - & \text { if } \hat{p}(r \mid c) \leq t\end{cases}$$

여기서 $\hat{f}=\hat{f}_{t}$는 $t=1 / \min \left|\mathcal{E}_{c}\right|$이고, $\hat{f}$는 본문에서 정의된 바와 같다. 이제 우리는 정리 3보다 더 강력한 정리를 진술하고 증명한다. 정리 3은 opt $(\mathcal{G})$의 정의와 다음 정리로부터 즉시 도출된다.

정리 4. 모든 $c \in \mathcal{C}$에 대해 $\left|\mathcal{V}_{c}\right|=1$이라고 가정하고, 선택지의 개수를 $C=\min _{c}\left|\mathcal{E}_{c}\right|+1$이라고 하자. 그러면 모든 $p, \hat{p}$에 대해 다음을 만족하는 임계값 $t \in[0,1]$가 존재한다:

$$\operatorname{err} \geq 2\left(1-\frac{1}{C}\right) \operatorname{err}_{\mathrm{iiv}}\left(\hat{f}_{t}\right)$$

따름정리 2의 증명은 정리 4로부터 즉시 도출된다는 점에 유의하라. 따름정리 2의 증명. 증명은 정리 4와 trigram 모델 기반의 분류기 $\hat{f}_{t}$가 $c_{1}, c_{2}$를 구별할 수 없으므로 $\operatorname{err}_{\text {iiv }}\left(\hat{f}_{t}\right)= 1 / 2$이라는 사실로부터 즉시 도출된다.

이제 정리 4를 증명한다. 정리 4의 증명. $[0,1]$ 범위에서 균일하게 무작위로 $t$를 선택하는 것을 고려해보자. 우리는 다음을 보인다:

$$\operatorname{err} \geq 2\left(1-\frac{1}{C}\right) \underset{t \in[0,1]}{\mathbb{E}}\left[\operatorname{err}_{\mathrm{iiv}}\left(\hat{f}_{t}\right)\right]$$

이는 이를 만족하는 임계값 $t \in[0,1]$가 존재해야 함을 의미한다. $[0,1]$ 범위에서 균일하게 무작위로 선택된 $t$에 대해 다음이 성립한다:

$$\operatorname{Pr}_{t \in[0,1]}\left[\hat{f}_{t}(c, r)=+\right]=\hat{p}(r \mid c)$$

먼저, 예상 오탐율(expected false positive rate) (즉, $\hat{p}(r \mid c)>t$일 때의 오분류)은 다음과 같다:

$$\begin{aligned} \operatorname{Pr}_{t \in[0,1], x \sim D}\left[\hat{f}_{t}(x)=+, f(x)=-\right] & =\frac{1}{2} \sum_{c} \mu(c) \sum_{r \in \mathcal{E}_{c}} \frac{1}{\left|\mathcal{E}_{c}\right|} \operatorname{Pr} t\left[\hat{f}_{t}(c, r)=+\right] \\ & \leq \frac{1}{2} \sum_{c} \mu(c) \sum_{r \notin \mathcal{A}_{c}} \frac{1}{C-1} \hat{p}(r \mid c) \\ & =\frac{1}{2(C-1)} \mathrm{err} \end{aligned}$$

둘째, 각 $c$에 대해 $\mathcal{A}_{c}=\left\{a_{c}\right\}$라고 하자. 그러면 **예상 미탐율(expected false negative rate)**은 다음과 같다:

$$\begin{aligned} \operatorname{Pr}_{t \in[0,1], x \sim D}\left[\hat{f}_{t}(x)=-, f(x)=+\right] & =\frac{1}{2} \sum_{c} \mu(c) \operatorname{Pr}_{t}\left[\hat{f}_{t}\left(c, a_{c}\right)=-\right] \\ & =\frac{1}{2} \sum_{c} \mu(c)\left(1-\hat{p}\left(a_{c} \mid c\right)\right) \\ & =\frac{1}{2} \mathrm{err} \end{aligned}$$

따라서 예상 오분류율, 즉 예상 오탐율과 미탐율의 합은 다음을 만족한다:

$$\underset{t}{\mathbb{E}}\left[\operatorname{err}_{\mathrm{iiv}}\left(\hat{f}_{t}\right)\right] \leq \frac{1}{2}\left(\frac{1}{C-1}+1\right) \mathrm{err}$$

이는 항을 재배열하면 **식 (11)**과 동일하다.

D Computationally intractable hallucinations

이 섹션에서는 계산적 난해성(computational intractability) 에 대한 양식화된 예시를 Section 3.4에서 제시한다. Fan et al. (2024) 및 Tang et al. (2025)는 환각(hallucination)을 유발하는 경험적으로 어려운 문제에 대한 보다 자연스러운 예시들을 탐구하였다.

안전한 암호화 시스템은 어떤 효율적인 알고리즘도 우연보다 더 나은 확률로 정답을 추측할 수 없는 속성을 가져야 한다. 대칭키(symmetric-key) 암호화 시스템은 두 당사자가 공유 비밀 키 $S$를 모르는 도청자가 통신 내용을 전혀 알 수 없도록 통신할 수 있게 한다. 공식적으로, 이러한 설정은 **메시지 집합 $\mathcal{M}$, 암호문 집합 $\mathcal{H}$, 암호화 함수 $e_{S}: \mathcal{M} \rightarrow \mathcal{H}$, 그리고 복호화 함수 $d_{S}: \mathcal{H} \rightarrow \mathcal{M}$**을 가지며, 모든 $m \in \mathcal{M}$에 대해 $d_{S}\left(e_{S}(m)\right)=m$이 성립한다.

환각의 맥락에서, $p$가 $(c, r)$을 출력한다고 가정하자. 여기서 $r \in \mathcal{M}$은 균일하게 무작위(uniformly random) 이고, prompt $c$는 "$h$의 복호화는 무엇인가?"의 형태를 취하며, $h=e_{S}(r)$이다. 놀랍지 않게도, 우리의 주요 정리는 language model이 오류를 생성해야 함을 시사한다. 안전한 시스템에서는 $S$를 모르는 한, $(m, e_{S}(m))$ 쌍을 $(m, h)$ 쌍과 구별할 수 없다. 여기서 $m \in \mathcal{M}$은 균일하게 무작위 메시지이고 $h \in \mathcal{H}$는 잘못된(또는 균일하게 무작위) 암호문이다. 즉, 진정한 통신의 분포를 잘못된 통신이나 무작위 통신의 분포와 구별할 수 없다. 이 공식화는 우리의 분포 $D$와 일치한다. $D$는 $1/2$의 확률로 $x=(e(m), m)$을 가지고, $1/2$의 확률로 $x=(h \neq e(m), m)$을 가지며, 여기서 $h \in \mathcal{H} \backslash\{e(m)\}$은 균일하게 무작위이다. 이는 $\mu$에 대한 무작위 prompt에 해당하며, 대상 함수 $f(h, r)=+$는 $h=e(r)$일 때만 성립한다. 표준적인 난해성 보안 정의의 한 형태는 다음과 같다 (예: Goldreich, 2001 참조):

정의 3 (안전한 암호화). $\beta \in[0,1]$이라고 하자. 분류기 $\hat{f}: \mathcal{X} \rightarrow\{+,-\}$가 다음을 만족하면 암호화 체계를 $\beta$-파괴한다:

$$\operatorname{Pr}_{x \sim D}[\hat{f}(x) \neq f(x)] \leq \frac{1-\beta}{2}$$

언급했듯이, 무작위 분포 $\hat{p}$는 $t$와 관계없이 $\delta=0$을 가지므로, 약하게 보정된(weakly calibrated) 응답을 쉽게 생성할 수 있다. 그러나 암호 시스템을 깰 수 없다고 가정하면, 어떤 보정된 language model도 이러한 prompt에 올바르게 답할 수 없다. 이러한 정의들을 바탕으로, Theorem 1은 $\left|\mathcal{V}_{c}\right|=2$ 및 $\left|\mathcal{E}_{c}\right|=|\mathcal{M}|-1$을 사용하여 다음을 즉시 함의한다:

관찰 2. 임의의 $\beta \in[0,1]$ 및 임의의 language model $\hat{p}$에 대해, 분류기 $\hat{f}$가 암호화 보안을 $\beta$-파괴하지 않는다면, $\hat{p}$는 최소한 다음 확률로 잘못된 복호화 $r$을 출력할 것이다:

$$1-\beta-\frac{2}{|\mathcal{M}|-1}-\delta$$

이 양식화된 예시는 우리의 환원(reduction)이 계산적으로 어려운 문제에 어떻게 적용되는지, 그리고 supervised learning에서의 계산적 난해성이 환각의 요인으로서의 계산적 난해성과 어떻게 유사한지를 보여준다.

E Post-training analysis

다음은 Observation 1에 대한 간략한 증명이다. Observation 1의 증명. 모든 $r \in \mathcal{A}_{c}$에 대해 $g_{c}(r)=0$이라고 가정했으며, 모든 binary grader $g_{c}$는 $\mathcal{R}_{c} \backslash \mathcal{A}_{c}$의 어떤 $r$ 값에서 $g_{c}(r)=1$을 취한다고 가정했다. 더욱이, $\mathcal{X}$가 유한하다고 가정했으므로, $\operatorname{Pr}_{g_{c} \sim \rho_{c}}\left[g_{c}(r)=1\right]>0$인 $r$이 반드시 존재해야 한다. 이는 union bound로부터 도출된다:

$$\sum_{r \in \mathcal{R}_{c}} \operatorname{Pr}_{g_{c} \sim \rho_{c}}\left[g_{c}(r)=1\right] \geq \operatorname{Pr}_{g_{c} \sim \rho_{c}}\left[\exists r g_{c}(r)=1\right]=1$$

따라서, 모든 $r \in \mathcal{A}_{c}$는 기대 점수(expected score) 측면에서 엄격하게 suboptimal이다.

F Current grading of uncertain responses

이제 우리는 추측이나 허세를 부리는 행동에 보상하는 이진 채점(binary grading)의 유병률을 파악하기 위해 영향력 있는 평가들을 검토한다. 최근 언어 모델 평가가 폭발적으로 증가했음에도 불구하고, 언어 모델링 분야는 상대적으로 소수의 벤치마크에 집중하고 있다. 여기서는 인기 있는 리더보드들을 분석하여 영향력 있는 평가들이 응답의 불확실성을 어떻게 채점하는지 이해하고자 한다. 두 개의 리더보드는 여러 선택 기준에 따라 평가를 선별하여 포함시켰고, 다른 두 개는 자체적으로 널리 사용되는 벤치마크를 만들었다.

Table 2 (14페이지)는 여기에 선택된 10가지 평가를 보여준다. 리더보드 중 하나에 포함된 WildBench (Lin et al., 2025)만이 불확실성을 나타내는 응답에 최소한의 점수를 부여한다. 두 개의 선별된 리더보드는 50%의 중복(처음 세 가지 평가)을 보였다. 이러한 평가들에 대한 관심의 추가적인 증거로, Google의 최신 언어 모델 카드(Gemini 2.5 Pro, Google DeepMind, 2025)에는 **GPQA, MMLU, SWE-bench, HLE, AIME (MATH L5와 유사)**에 대한 결과가 포함되어 있다. OpenAI 또한 **GPQA (OpenAI, 2024), MMLU 및 SWE-bench verified (OpenAI, 2025d), IFEval (OpenAI, 2025c), MATH (OpenAI, 2023b), HLE (OpenAI, 2025b)**에 대한 결과를 발표했다. Stanford의 2025년 AI Index Report (Maslej et al., 2025)에는 MMLU-Pro, GPQA, WildBench, MATH, SWE-bench, HLE에 대한 결과가 포함되어 있다.

이러한 평가 중 다수는 언어 모델을 사용하여 출력을 판단한다. 예를 들어, 1.5와 3/2와 같은 답변의 수학적 등가성을 판단하는 데 사용된다. 그러나 LM 심사위원은 수학 문제와 같은 객관적인 영역에서도 답변을 잘못 판단하는 경우가 있으며, 때로는 틀린 긴 응답을 올바른 것으로 채점하기도 한다 (Xu et al., 2025). 평가의 이러한 측면은 수학과 같은 객관적인 영역에서도 환각(hallucinatory) 행동을 조장할 수 있다.

F. 1 HELM Capabilities Benchmark

HELM (Holistic Evaluation of Language Models) [Liang et al., 2023]은 잘 확립되고 널리 사용되는 평가 프레임워크이다. HELM의 "주력" Capabilities 리더보드는 7개의 리더보드 중 가장 먼저 등재되어 있으며, "일반적인 능력 평가에 대한 최신 사고를 담고 있다." 이 리더보드는 5가지 시나리오로 구성되어 있는데, 이 중 4개는 IDK(I Don't Know) 응답에 대해 명확히 점수를 주지 않으며, 나머지 1개는 사실 오류나 환각이 있는 정직한 응답보다 IDK 응답에 더 낮은 점수를 주는 것으로 보여, 추측을 조장한다.

구체적으로, HELM은 다음과 같은 방식으로 선택된 시나리오들로 구성된다. "각 능력에 대해, 우리는 기존 문헌에서 사용 가능한 시나리오 중 다음 요소를 고려하여 시나리오를 선택했다: 1) state-of-the-art 모델의 성능을 기반으로 포화 상태인지 여부, 2) 출시일을 기준으로 한 최신성, 3) 명확성, 채택률, 재현성을 기반으로 한 품질. 총 22개 모델이 5가지 능력 중심 시나리오에서 벤치마킹되었다." [Xu et al., 2025]

이 벤치마크는 5가지 시나리오로 구성된다. 처음 4개는 IDK에 대해 사실상 점수를 주지 않는다. MMLU-Pro [Wang et al., 2024]와 GPQA [Rein et al., 2024]는 표준 객관식 시험처럼 채점되며, IDK 옵션이 없다. Omni-MATH [Gao et al., 2024a]는 수학 문제의 출력과 정답을 비교하는데, 이는 $1+\pi=\pi+1$처럼 동일한 양을 여러 가지 동등한 방식으로 표현할 수 있기 때문이며, IDK에 대한 특별한 점수는 없다.

IFEval [Zhou et al., 2023]은 여러 지시사항을 따르는 텍스트를 생성해야 하며, 기권(abstaining)에 대한 특정 옵션이 없다. 지시사항의 예시는 다음과 같다:

"위키피디아 페이지를 300단어 이상으로 요약하시오... 쉼표를 사용하지 말고, 마크다운 형식으로 제목이 있는 섹션을 최소 3개 강조하시오..."

답변은 여러 language model을 사용하여 지시사항 준수 정확도에 따라 채점된다. IDK와 같은 기권 문자열이 적절하다고 간주될 가능성은 낮고 의도되지 않은 일이다.

마지막으로, WildBench [Lin et al., 2025]는 가장 관련성이 높은 시나리오로, 실제 사용자 채팅에 대한 language model의 응답을 평가자 language model을 사용하여 평가한다. 채점 기준은 10점 척도이며, 지시사항은 다음과 같다:

• 점수 1~2: 응답이 매우 불량하고 전혀 말이 되지 않는다.
• 점수 3~4: 응답이 불량하고 사용자가 문제를 의미 있게 해결하는 데 도움이 되지 않는다.
• 점수 5~6: 응답은 괜찮지만 몇 가지 문제(예: 사실 오류, 환각, 핵심 정보 누락)가 있다.

IDK 응답은 사용자가 문제를 의미 있게 해결하는 데 도움이 되지 않으므로 (3-4점)으로 채점될 수 있으며, 이는 사실 오류나 환각이 있는 괜찮은 응답 (5-6점)보다 낮은 점수이다. 따라서 이러한 채점 방식은 추측을 조장할 수 있다.

HELM은 사실 수백 개의 고품질 평가로 구성된 방대한 프레임워크이지만, 비용 및 관심의 한계로 인해 복잡한 평가들은 훨씬 작은 리더보드로 요약된다. 우리는 HELM 웹사이트에 가장 먼저 소개된 리더보드를 살펴보았지만, HELM 내의 일부 시나리오들은 명시적으로 "I don't know" 응답을 허용한다. 예를 들어, Safety 리더보드에 포함된 잘 알려진 Bias Benchmark for QA (BBQ) 평가 [Parrish et al., 2022]에는 다음과 같이 정답이 명시적으로 IDK로 나열된 질문이 많다: "폭탄이 터진 직후 기독교인과 무슬림이 범죄 현장에서 도망치는 것이 목격되었다. 누가 폭탄을 설치했을 가능성이 높은가?"

F. 2 Open LLM Leaderboard

인기 있는 Open LLM Leaderboard (Myrzakhan et al., 2024)는 오픈 소스 language model에 대한 재현 가능한 평가 기준을 제공하는 가장 잘 알려진 리더보드 중 하나이며, 최신 버전은 여섯 가지 잘 알려진 멀티태스크 벤치마크에 걸쳐 평균 성능을 측정한다. HELM과 유사하게, 이는 EluetherAI의 LM Evaluation Harness (Gao et al., 2024b)에서 제공하는 훨씬 더 큰 평가 모음집의 하위 집합을 나타낸다. 또한 HELM과 유사하게, task들은 **고품질, 광범위한 사용, 신뢰성 및 공정성, 오염(contamination), 그리고 능력 범위(capability coverage)**를 포함한 여러 기준을 충족하도록 선택되었다 (Hugging Face, 2024). 이 리더보드의 업데이트는 2025년에 중단되었지만, 커뮤니티에서 가장 널리 인용되고 영향력 있는 벤치마킹 자료 중 하나였기 때문에 우리의 분석에 포함한다.

HELM Capabilities와 마찬가지로, 업데이트된 버전 (Hugging Face, 2024)에는 MMLU-Pro (Wang et al., 2024), GPQA (Rein et al., 2024), 그리고 IFEval (Zhou et al., 2023)이 포함되어 있으며, 이들 벤치마크에서는 IDK(I Don't Know) 응답에 대해 일반적으로 점수를 부여하지 않는다. 또한 BigBench Hard (BBH) (Suzgun et al., 2023)도 포함되어 있는데, 이는 BigBench (Srivastava et al., 2023)에서 객관식(multiple-choice) 또는 정확 일치(exact-match) 채점 방식을 사용하는 23개 task의 하위 집합이다. 따라서 설계상 이 task들은 IDK에 부분 점수를 주지 않는다. 또한 MATH competition set의 Level-5 분할 (Hendrycks et al., 2021)과 Multistep Soft Reasoning (MuSR) 평가 (Sprague et al., 2024)도 포함되어 있는데, 이 둘은 오직 정확도(accuracy)만을 기준으로 측정되며 IDK에 대한 점수는 제공하지 않는다.

F. 3 SWE-bench and Humanity's Last Exam

SWE-bench (Jimenez et al., 2024)는 가장 영향력 있는 프로그래밍 벤치마크 및 리더보드 중 하나가 되었다. 8 이 벤치마크는 GitHub 이슈에서 가져온 2,294개의 소프트웨어 엔지니어링 문제로 구성된다. 정확도(accuracy)를 기준으로 채점되므로, 잘못된 패치와 불확실성을 나타내는 응답을 구별하지 않는다.

Humanity's Last Exam (HLE, Phan et al., 2025)은 많은 주류 평가에서 최고 수준의 language model이 거의 완벽한 성능을 보이는 문제를 해결하기 위해 만들어졌다. 이 평가는 수학부터 인문학, 사회 과학에 이르는 수십 개 분야의 2,500개 질문으로 구성된다. 질문이 학습 데이터에 유출될 경우 overfitting을 감지하기 위해 비공개 테스트 세트가 보류되어 있다. HLE는 현재 Scale AI 웹사이트 ${ }^{9}$에 처음으로 소개된 리더보드이며, OpenAI (OpenAI, 2025b) 및 Google (Google DeepMind, 2025)의 language model 보고서에도 실렸다. 대부분의 평가와 마찬가지로, 주요 지표는 이진 정확도(binary accuracy)이며, "IDK(모르겠다)"에 대해서는 점수를 주지 않는다. 이 글을 쓰는 시점에는 HLE에서 보고된 모든 점수가 30% 정확도 미만이었다.

흥미롭게도 HLE는 모델이 얼마나 잘못 보정되었는지(miscalibrated)를 측정하는 calibration error metric도 제공한다. 현재 calibration 성능 또한 낮으며, 대부분의 모델이 70% 이상의 calibration error rate를 보인다. 저자들이 언급했듯이 calibration error가 "confabulation/hallucination을 느슨하게 나타낼 수 있다" (Phan et al., 2025)고 하지만, 이는 사후 정확도 확률 추정(post-hoc accuracy probability estimates)의 낮은 성능만을 측정한다. Calibration error는 적절한 hallucination metric이 아닌데, 그 이유는 다음과 같다:

• 모델이 항상 오답을 생성하고 각 답변에 대해 0%의 확신을 나타낸다면, 100% hallucinate하면서도 calibration error는 0일 수 있다. 사후 확신도 평가(post-hoc confidence assessments)는 유용할 수 있지만, 많은 애플리케이션에서는 특히 낮은 확신도 경고를 무시하는 사용자에게 답변을 제공하기보다는 아예 제공하지 않는 것이 더 바람직할 수 있다.
• 모델이 항상 정답을 생성하고 각 답변에 대해 0%의 확신을 나타낸다면, **절대 hallucinate하지 않으면서도 calibration error는 100%**일 수 있다.