On the Fundamental Limits of LLMs at Scale

AI summary

Overview

• Research area: Machine learning theory — specifically the theoretical foundations of large language model (LLM) scaling, drawing on computability theory, information theory, and statistical learning theory.
• Technical level: Advanced. The paper is built around formal theorems, proofs, and learning-theoretic bounds (diagonalization, undecidability, VC dimension, PAC and PAC-Bayes bounds, Kolmogorov complexity), with empirical evidence cited alongside.
• Scope (one sentence): The paper presents a unified, proof-informed framework arguing that five failure modes of LLMs — hallucination, context compression, reasoning degradation, retrieval fragility, and multimodal misalignment — are not engineering bugs but consequences of intrinsic computational, informational, and statistical ceilings.

What This Paper Is About

LLMs have improved dramatically as parameters, data, and compute have grown, but they still hallucinate, misreason, forget long contexts, and misalign across modalities. Existing surveys catalogue these failures empirically, but according to the authors they "lack a rigorous theoretical synthesis connecting them to the foundational limits of computation, information, and learning." This paper's goal is to close that gap by deriving formal impossibility and saturation results that characterize when scaling helps, when it plateaus, and when it provably cannot advance.

Key Contributions

1. A unified proof-informed framework formalizing five fundamental limitations of LLM scaling: (1) hallucination, (2) context compression, (3) reasoning degradation, (4) retrieval fragility, and (5) multimodal misalignment. The authors argue prior surveys remain descriptive and lack this formal synthesis.
2. Formal theorems establishing hallucination as mathematically inevitable, including a diagonalization result over any computably enumerable set of LLMs (Theorem 1), a result showing each model hallucinates on infinitely many inputs (Theorem 2), a result showing undecidable problems (e.g., the Halting Problem) force infinite failure sets (Theorem 3), a Kolmogorov-complexity compression bottleneck (Lemma 1), and a sample-complexity lower bound for arbitrary facts (Theorem 4).
3. A three-tier hierarchy of constraints summarizing the results: enumerable model classes fail on adversarial queries; undecidable problems force infinite failure sets; and finite model capacity cannot compress infinite-complexity functions without distortion, while arbitrary facts demand prohibitive sample counts.
4. Derivation of degradation laws for the remaining axes — long-context compression (Section 3), the reasoning-versus-recitation distinction (Section 4), retrieval fragility (Section 5), and multimodal misalignment (Section 6) — plus an analysis of evaluation-benchmark limitations (Section 7) and practical mitigation paths such as bounded-oracle retrieval, positional curricula, and sparse or hierarchical attention.

Note: the provided content is truncated after Section 2.2. The detailed theorems and derivations of Sections 3 through 9 are referenced by title and framing but their statements are not reported in the available text.

Main Findings

• Hallucination is provably inevitable. Theorem 1 shows that for any computably enumerable set of LLMs {h₀, h₁, h₂, …}, there exists a computable ground-truth function f such that every model state — including at any training step j — hallucinates on at least one input. The proof enumerates models and inputs and diagonalizes, defining f(sᵢ) to differ from hᵢ(sᵢ). The result holds regardless of architecture (transformers, RNNs, state-space models), training procedure (supervised, reinforcement learning), or prompt engineering.

• Failures are infinite, not isolated. Theorem 2 constructs a computable f′ that flips the output of the model assigned by iₖ := k mod (k+1), so each model hᵢ is wrong on infinitely many inputs. As the authors put it, "hallucination is not an isolated phenomenon but occurs on infinitely many inputs."

• Undecidable problems impose an insurmountable barrier. Theorem 3 shows that for any computable LLM approximating the Halting Problem characteristic function, the set of inputs on which it hallucinates is infinite. The authors note that if the failure set were finite, a Turing machine with a finite exception table could decide the Halting Problem, contradicting Turing's 1936 result. They argue natural user queries inherit this impossibility, including "Will this loop terminate?", logical consistency checking, and self-referential requests.

• Finite capacity forces compression error. Lemma 1 shows that a model with Kolmogorov complexity K(h) = c cannot encode every function on inputs of length at most n, since the number of such functions grows as |𝒴|^(|Σ|^(n+1)) while only O(2^c) functions have complexity at most c. The fraction of functions requiring K(f) > c approaches 1 as n → ∞. Errors are therefore concentrated on incompressible facts such as specific dates, numerical constants, or rare entity attributes.

• Long-tail facts require prohibitive data. Theorem 4 states that learning m independent binary facts, each with a uniformly random correct answer, to hallucination probability at most ε with confidence at least 1 − δ requires n = Ω((m/ε²) · log(m/δ)) training examples. The authors note that for millions of rare entities, dates, or numerical facts this "exceed[s] the size of any feasible training corpus."

• Generalization bounds leave residual hallucination risk. Equation (3) gives R_hal(h) ≤ empirical hallucination rate + O(√((d log(n/d) + log(1/δ))/n)), where d is the VC dimension and n the number of samples. The PAC-Bayes bound in Equation (6) adds a KL(Q∥P) complexity penalty. For high-capacity models or long-tailed distributions, the generalization term stays large even with low training error.

• Training data compounds the irreducible baseline. The paper identifies incompleteness (a coverage ratio ρ_cov that tends to 0 as the knowledge domain grows), noise, long-tail distributions, temporal decay, conflicting information, exposure bias, and benchmark contamination as data-level hallucination pathways. Equation (10) shows the expected hallucination rate is bounded below by η · (1 − O(√(d/n))) for noise rate η, so even with infinite data a non-zero noise rate imposes a floor.

• Reported empirical magnitudes. The paper cites common web scrapes containing 2–3% demonstrably false factual claims (η ≈ 0.02–0.03). For long-tail entities, it states that GPT-4's factual precision drops below 40% for individuals with fewer than 10 Wikipedia page views per day versus more than 90% for highly popular entities; the Figure 3 caption frames the same effect as dropping from >95% for highly popular entities (100k+ Wikipedia views/day) to <40% for tail entities (<100 views/day). The figure caption also reports that rapidly evolving domains cross the 50% validity threshold within 6 months, while the text states temporal staleness can exceed 0.5 within months.

• Exposure bias compounds generation errors. Because models are trained on gold-standard prefixes but at inference feed back their own predictions, the KL divergence between model and data prefix distributions grows with generation length t. Equation (14) states that the error probability at step t given an earlier error at t₀ is at least the base error probability plus Δ_shift(t − t₀).

• Context, reasoning, retrieval, and multimodality have distinct degradation laws. Even with 128K-token windows, the authors state that positional under-training, encoding saturation, and softmax crowding limit effective context utilization far below nominal capacity, with effective context scaling sub-linearly. Likelihood-based training favors pattern completion over true inference, producing what they call reasoning collapse out of distribution. Retrieval under bounded token budgets suffers semantic drift, ranking noise, and weak coupling, with mutual information to the target decaying as retrieval breadth increases. Multimodal models have language channels dominating gradients while visual features under-adapt.

• A unifying principle. The authors argue that LLM failures scale with capability because each failure mode projects the same underlying triad: computational undecidability, statistical sample insufficiency, and finite information capacity.

• Scaling evidence cited as context. The paper notes that GPT-1 had 117 million parameters while GPT-4 exceeded a trillion, and that the transition from GPT-3.5 to GPT-4 yielded a 16-point gain on MMLU and a 35-point leap on GSM-8K. Scaling laws are attributed to Hoffmann et al. (2022a).

Methodology in Plain English

The authors work primarily by mathematical proof rather than by running new experiments. They model an LLM as a computable function from input strings to outputs and then apply classical tools from theoretical computer science and learning theory:

• Diagonalization: Because both the set of computable LLMs and the set of input strings are countable, the authors enumerate them and construct a ground-truth function that deliberately disagrees with each model on its assigned input. This is the same style of argument Cantor used for uncountable infinities, adapted to learning theory.
• Reduction to undecidability: To show hallucinations cannot be bounded on Halting-Problem-style queries, they assume a finite failure set and show that a machine equipped with that finite exception table plus the model itself would decide the Halting Problem — which is impossible.
• Counting and pigeonhole arguments: They compare the exponentially growing number of possible functions against the O(2^c) functions describable within a fixed Kolmogorov complexity budget to show that most functions cannot be encoded exactly.
• Learning-theoretic bounds: They use VC-dimension generalization bounds and PAC-Bayes bounds to quantify how sample size, model capacity, and prior divergence affect hallucination risk, then derive a lower bound on sample complexity for unstructured facts.
• Pairing theory with cited evidence: Each section pairs theorems with empirical findings from prior literature — for example, accuracy degradation on rare entities, information staleness over time, and exposure bias in autoregressive generation — to indicate where the theoretical ceilings show up in practice.

Why This Matters

Impact on research. The paper reframes scaling from an unbounded engineering problem into a process bounded by intrinsic computational and epistemic constraints. If correct, it implies that benchmark improvements and mitigation techniques can reduce but not universally eliminate certain failure classes, and it argues that evaluation should be rethought — the paper notes that binary grading equates uncertainty with wrong answers, incentivizing fabrication across benchmarks such as MMLU-Pro, GPQA, and MATH, and that this contributes to reward hacking in reinforcement learning from human feedback.

Real-world applications:

• Code analysis and verification tools: Questions like "Will this loop terminate?" inherit undecidability, so deployed assistants need calibrated uncertainty rather than confident answers.
• Retrieval-augmented enterprise and medical question answering: Bounded token budgets and retrieval breadth limits mean grounding cannot be made complete; the paper's mitigation suggestions of bounded-oracle retrieval and positional curricula target these settings directly.
• Time-sensitive domains such as clinical guidance or current-affairs assistants: Because staleness can exceed 50% within months in fast-moving domains, systems need continuous updates balanced against catastrophic forgetting of older knowledge.
• Multimodal assistants: The paper argues cross-modal imbalance means multimodal scaling amplifies rather than removes single-modality brittleness, which matters for any product relying on vision-language alignment.

Industry relevance. The findings argue against treating more parameters, more data, or more alignment as a universal fix. Deployments must budget for an irreducible error floor, distinguish correctable engineering gaps (coverage, freshness, retrieval quality) from provable limits, and design interfaces and evaluation schemes that reward calibrated uncertainty rather than confident fabrication.

Future Directions

• Testing mitigation strategies against the stated bounds. The paper names bounded-oracle retrieval, positional curricula, and sparse or hierarchical attention as practical paths, but the provided content does not report how far these close the gap to the theoretical limits or which limits they leave untouched.
• Separating reducible from irreducible error in practice. Open question: for a given deployment domain, how much of the observed hallucination rate is attributable to data noise, coverage gaps, and staleness (all addressable) versus the computability and information-theoretic floors the paper derives?
• Resolving the continual-update trade-off. The paper highlights the tension between avoiding catastrophic forgetting of past knowledge and retaining outdated information that produces temporally induced hallucinations; how to balance preservation and updating is left open in the available text.
• Redesigning evaluation. The paper criticizes binary grading and reward hacking on benchmarks such as MMLU-Pro, GPQA, and MATH, and devotes Section 7 to the limitations of existing evaluation benchmarks, raising the question of what evaluation protocols would fairly measure a system that is provably unable to be universally correct.

The paper states that Section 9 concludes with "a summary of the key elements and future directions," but that section's content is not included in the provided text.

Target Audience

This paper benefits most readers with a background in theoretical computer science, information theory, or statistical learning theory who want a formal account of why LLM failures persist at scale — including ML researchers working on scaling laws and evaluation, learning theorists interested in impossibility results for language models, and senior practitioners or technical strategists who need to set realistic expectations for what further scaling can and cannot deliver. Readers seeking empirical benchmarks, new experimental results, or implementable recipes will find only cited evidence and high-level mitigation directions, since the paper's contribution is a theoretical synthesis.

Authors’ abstract

Large Language Models (LLMs) have benefited enormously from scaling, yet these gains are bounded by five fundamental limitations: (1) hallucination, (2) context compression, (3) reasoning degradation, (4) retrieval fragility, and (5) multimodal misalignment. While existing surveys describe these phenomena empirically, they lack a rigorous theoretical synthesis connecting them to the foundational limits of computation, information, and learning. This work closes that gap by presenting a unified, proof-informed framework that formalizes the innate theoretical ceilings of LLM scaling. First, computability and uncomputability imply an irreducible residue of error: for any computably enumerable model family, diagonalization guarantees inputs on which some model must fail, and undecidable queries (e.g., halting-style tasks) induce infinite failure sets for all computable predictors. Second, information-theoretic and statistical constraints bound attainable accuracy even on decidable tasks, finite description length enforces compression error, and long-tail factual knowledge requires prohibitive sample complexity. Third, geometric and computational effects compress long contexts far below their nominal size due to positional under-training, encoding attenuation, and softmax crowding. We further show how likelihood-based training favors pattern completion over inference, how retrieval under token limits suffers from semantic drift and coupling noise, and how multimodal scaling inherits shallow cross-modal alignment. Across sections, we pair theorems and empirical evidence to outline where scaling helps, where it saturates, and where it cannot progress, providing both theoretical foundations and practical mitigation paths like bounded-oracle retrieval, positional curricula, and sparse or hierarchical attention.