Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Guo, Anxin, Li, Jingwei
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Artificial Intelligence Computation and Language Data Structures and Algorithms Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
by: Beigi, Salman, et al.
Published: (2025)

SpecTr: Fast Speculative Decoding via Optimal Transport
by: Sun, Ziteng, et al.
Published: (2023)

On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
by: Kalavasis, Alkis, et al.
Published: (2024)

On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
by: Kalavasis, Alkis, et al.
Published: (2024)

The Library Theorem: How External Organization Governs Agentic Reasoning Capacity
by: Mainen, Zachary F.
Published: (2026)

Best Agent Identification for General Game Playing
by: Stephenson, Matthew, et al.
Published: (2025)

Block Verification Accelerates Speculative Decoding
by: Sun, Ziteng, et al.
Published: (2024)

Optimal Rates for Differentially Private Hypothesis Testing with E-values
by: Jacobsen, Ben, et al.
Published: (2026)

TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
by: Zandieh, Amir, et al.
Published: (2025)

Contrastive Identification and Generation in the Limit
by: Li, Xiaoyu, et al.
Published: (2026)

A Tighter Complexity Analysis of SparseGPT
by: Li, Xiaoyu, et al.
Published: (2024)

Guaranteed Recovery of Unambiguous Clusters
by: Mazooji, Kayvon, et al.
Published: (2025)

Robust Fair Clustering with Group Membership Uncertainty Sets
by: Duppala, Sharmila, et al.
Published: (2024)

Exploration Space Theory: Formal Foundations for Prerequisite-Aware Location-Based Recommendation
by: Sadallah, Madjid
Published: (2026)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

Differentially Private Language Generation and Identification in the Limit
by: Mehrotra, Anay, et al.
Published: (2026)

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

The CLRS-Text Algorithmic Reasoning Language Benchmark
by: Markeeva, Larisa, et al.
Published: (2024)

Language Generation with Infinite Contamination
by: Mehrotra, Anay, et al.
Published: (2025)

A Characterization of List Language Identification in the Limit
by: Charikar, Moses, et al.
Published: (2025)

GateLoop: Fully Data-Controlled Linear Recurrence for Sequence Modeling
by: Katsch, Tobias
Published: (2023)

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

Learning Linear Attention in Polynomial Time
by: Yau, Morris, et al.
Published: (2024)

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
by: Guo, Anxin, et al.
Published: (2024)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
by: Saha, Barna, et al.
Published: (2024)

On Unbiased Low-Rank Approximation with Minimum Distortion
by: Barnes, Leighton Pate, et al.
Published: (2025)

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
by: Asi, Hilal, et al.
Published: (2024)

Learning Algorithms in the Limit
by: Papazov, Hristo, et al.
Published: (2025)

HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing
by: Liu, Minghui, et al.
Published: (2024)

A Distribution Testing Approach to Clustering Distributions
by: Kumar, Gunjan, et al.
Published: (2025)

Optimal high-precision shadow estimation
by: Chen, Sitan, et al.
Published: (2024)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
by: Vahidi, Soroush, et al.
Published: (2024)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Optimal Survival Trees: A Dynamic Programming Approach
by: Huisman, Tim, et al.
Published: (2024)