@inproceedings{xi-etal-2026-cost,
title = "The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination",
author = "Xi, Wang and
Xu, Shijia and
Guo, Rongfeng",
editor = "Zhang, Yue and
Xu, Ruifeng and
Purwarianti, Ayu and
Rong, Tong and
Suzuki, Jun",
booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {IJCNLP}-{AACL} 2026",
month = nov,
year = "2026",
address = "Hengqin, China",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.findings-aacl.232/",
pages = "4579--4598",
ISBN = "979-8-89176-444-6",
abstract = "While chain-of-thought prompting and scratchpads are frequently conceptualized as external memory for reasoning tasks, this perspective breaks down when a final answer must be generated from a bounded, jointly retained state. We formulate this limitation through a minimal constraint-satisfaction model in which an agent must exactly output $N$ independent binary constraints using a shared internal and external memory configuration yielding at most $2^B$ distinguishable states. Under this framework, we mathematically prove a tight phase law:\par $p^\star(N,B)=\min\{1,2^{B-N}\}.$\par This Joint Memory Budget Theorem establishes that each independent constraint exceeding the retained memory budget exponentially halves the probability of exact success. We further generalize this limit with adversarial robustness and a min-entropy extension that separates raw prompt length from effective independent information. To empirically test the qualitative predictions of this theory, we introduce a two-call retention protocol that forces large language models to reconstruct constraint hands solely from their bounded written representations. Comprehensive evaluations across modern long-context and reasoning models reveal sharp, capacity-dependent performance cliffs. While variables such as scratchpad formatting, effective task entropy, and answer-time external access can shift this phase boundary, they do not eliminate it. Ultimately, we demonstrate that long-context and scratchpad reasoning are fundamentally bottlenecked not by nominal context length, but by the independent information jointly available at the time of answer generation."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="xi-etal-2026-cost">
<titleInfo>
<title>The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination</title>
</titleInfo>
<name type="personal">
<namePart type="given">Wang</namePart>
<namePart type="family">Xi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Shijia</namePart>
<namePart type="family">Xu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Rongfeng</namePart>
<namePart type="family">Guo</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-11</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Findings of the Association for Computational Linguistics: IJCNLP-AACL 2026</title>
</titleInfo>
<name type="personal">
<namePart type="given">Yue</namePart>
<namePart type="family">Zhang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ruifeng</namePart>
<namePart type="family">Xu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ayu</namePart>
<namePart type="family">Purwarianti</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Tong</namePart>
<namePart type="family">Rong</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jun</namePart>
<namePart type="family">Suzuki</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Hengqin, China</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-444-6</identifier>
</relatedItem>
<abstract>While chain-of-thought prompting and scratchpads are frequently conceptualized as external memory for reasoning tasks, this perspective breaks down when a final answer must be generated from a bounded, jointly retained state. We formulate this limitation through a minimal constraint-satisfaction model in which an agent must exactly output N independent binary constraints using a shared internal and external memory configuration yielding at most 2^B distinguishable states. Under this framework, we mathematically prove a tight phase law:\par p^\star(N,B)=\min{1,2^B-N}.\par This Joint Memory Budget Theorem establishes that each independent constraint exceeding the retained memory budget exponentially halves the probability of exact success. We further generalize this limit with adversarial robustness and a min-entropy extension that separates raw prompt length from effective independent information. To empirically test the qualitative predictions of this theory, we introduce a two-call retention protocol that forces large language models to reconstruct constraint hands solely from their bounded written representations. Comprehensive evaluations across modern long-context and reasoning models reveal sharp, capacity-dependent performance cliffs. While variables such as scratchpad formatting, effective task entropy, and answer-time external access can shift this phase boundary, they do not eliminate it. Ultimately, we demonstrate that long-context and scratchpad reasoning are fundamentally bottlenecked not by nominal context length, but by the independent information jointly available at the time of answer generation.</abstract>
<identifier type="citekey">xi-etal-2026-cost</identifier>
<location>
<url>https://aclanthology.org/2026.findings-aacl.232/</url>
</location>
<part>
<date>2026-11</date>
<extent unit="page">
<start>4579</start>
<end>4598</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination
%A Xi, Wang
%A Xu, Shijia
%A Guo, Rongfeng
%Y Zhang, Yue
%Y Xu, Ruifeng
%Y Purwarianti, Ayu
%Y Rong, Tong
%Y Suzuki, Jun
%S Findings of the Association for Computational Linguistics: IJCNLP-AACL 2026
%D 2026
%8 November
%I Association for Computational Linguistics
%C Hengqin, China
%@ 979-8-89176-444-6
%F xi-etal-2026-cost
%X While chain-of-thought prompting and scratchpads are frequently conceptualized as external memory for reasoning tasks, this perspective breaks down when a final answer must be generated from a bounded, jointly retained state. We formulate this limitation through a minimal constraint-satisfaction model in which an agent must exactly output N independent binary constraints using a shared internal and external memory configuration yielding at most 2^B distinguishable states. Under this framework, we mathematically prove a tight phase law:\par p^\star(N,B)=\min{1,2^B-N}.\par This Joint Memory Budget Theorem establishes that each independent constraint exceeding the retained memory budget exponentially halves the probability of exact success. We further generalize this limit with adversarial robustness and a min-entropy extension that separates raw prompt length from effective independent information. To empirically test the qualitative predictions of this theory, we introduce a two-call retention protocol that forces large language models to reconstruct constraint hands solely from their bounded written representations. Comprehensive evaluations across modern long-context and reasoning models reveal sharp, capacity-dependent performance cliffs. While variables such as scratchpad formatting, effective task entropy, and answer-time external access can shift this phase boundary, they do not eliminate it. Ultimately, we demonstrate that long-context and scratchpad reasoning are fundamentally bottlenecked not by nominal context length, but by the independent information jointly available at the time of answer generation.
%U https://aclanthology.org/2026.findings-aacl.232/
%P 4579-4598Markdown (Informal)
[The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination](https://aclanthology.org/2026.findings-aacl.232/) (Xi et al., Findings 2026)
ACL