arXiv Computation and Language

The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination

The paper presents a rate‑distortion framework for understanding factual hallucination in closed‑book question answering. It shows that even when a fact is observed, limited memory forces it to be stored approximately, leading to errors that can be bounded by a combination of compression distortion and missing coverage. The authors derive a theoretical lower bound on error and validate it with simulations and probes on modern language models.

arXiv Machine Learning
Jul 15

Extractable Memorization From First Principles

arXiv:2607. 12649v1 Announce Type: new Abstract: Recent work on extractable memorization in LLMs suffers from two contrasting validity problems.

By A. Feder Cooper, Marika Swanberg, Jamie Hayes, Lea Duesterwald, Christopher De Sa, Daniel E. Ho, Mark A. Lemley, Percy Liang
arXiv AI
Aug 20

Do Large Language Models Hallucinate Electric Fata Morganas?

The paper investigates why large language models (LLMs) produce hallucinations—outputs that are fabricated, unverifiable, or contradictory to source material—and argues that these hallucinations have philosophical implications for machine consciousness. It reviews known causes such as source‑target divergence, training‑inference discrepancies, and overfitting, and presents two empirical studies: one showing that higher temperature settings in GPT models yield plausible but incorrect answers, while lower temperatures produce accurate ones; and another demonstrating that an encoder‑only model trained on encyclopedic data answers factually without embellishment, suggesting hallucinations arise from exposure to subjective, socially diverse data rather than cognitive ability. Drawing on Turing, Searle’s Chinese Room, the frame problem, and cybernetic theory, the authors contend that a model’s self‑reports of emotion or sentience fall within the definition of hallucination, implying that any future machine consciousness may remain epistemically inaccessible because it would be indistinguishable from an advanced hallucination.

By Kristina \v{S}ekrst
arXiv AI
Aug 25

Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal reference

The paper introduces F-ICL, a benchmark that measures in‑context algorithmic reasoning in language models by exhaustively enumerating 86 million valid programs of length ≤13 on a Turing‑complete machine and computing the exact posterior under a bounded Levin–Solomonoff prior. Unlike typical benchmarks, F‑ICL provides a distributional reference rather than just answers, allowing the evaluation of models’ inductive priors. Across 105 configurations of models ranging from 0.8 B to 675 B parameters, models achieve up to 92 % accuracy, yet many still deviate from the Bayes‑optimal reference, and the study derives theoretical bounds on cumulative loss for predictors with positive prior weight on the reference.

By Luan Ozelim, Hector Zenil
arXiv AI
Sep 4

Learning What Not to Forget: Long-Horizon Agent Memory from a Few Kilobytes of Learning

The paper introduces LRE (Learned Relevance Eviction), a lightweight, CPU‑only, language‑model‑free scorer that learns which parts of an agent’s interaction history are task‑critical and preserves them verbatim. In experiments, LRE matches or surpasses baseline eviction policies on accuracy‑cost trade‑offs, recovers 93% of full‑history accuracy, reduces worst‑case prompt size by 52%, and outperforms dense and token‑pruning encoders in conversational memory while being 295–1569× smaller. The method also achieves superior budgeted answer quality on LoCoMo reading and can be trained annotation‑free, recovering 95% of supervised scorer performance.

By Nusrat Jahan Lia, Aritra Mazumder