Characterizing Local Breadth in Language Generation

Jon Kleinberg, Fan WeiarXiv 2026 · arXiv

TL;DR

This paper provides a rigorous mathematical characterization of the trade-off between "validity" (avoiding hallucinations) and "breadth" (avoiding mode collapse) in language generation. The authors discover a fundamental phase shift: while a single generator can be optimal for all possible targets in one dimension, higher-dimensional output spaces (like vector embeddings) force unavoidable trade-offs where prioritizing one target language necessarily degrades performance on another.

What Problem Does This Paper Address?

In the era of Large Language Models (LLMs), two failure modes are common: hallucination (generating invalid strings) and mode collapse (generating only a narrow, repetitive subset of valid strings). This paper studies this tension within the "generation in the limit" framework.

In this model, a generator receives positive examples from an unknown target language in an arbitrary, potentially adversarial order. The goal is to eventually generate only valid strings (validity) while covering as much of the target language as possible (breadth).

The authors focus on a demanding measure of breadth called lower Banach density. Unlike standard asymptotic density, which looks at the average coverage over long prefixes, Banach density requires coverage in every sufficiently large local region. This makes it sensitive to "sparse holes"—large regions of the output space that the model systematically neglects.

Methods

The researchers employ a mix of combinatorial topology and game theory to map the limits of generation:

  • Combinatorial Obstruction Trees: They define "admissible obstruction trees" to represent the adversary's ability to mislead the generator by revealing increasingly specific subsets of a language.
  • Finite-Evidence History Topology: They develop a new topological framework where "neighborhoods" are defined by the finite sets of strings already observed. This allows them to characterize what a generator can "protect" based on current evidence.
  • Geometric Stopping Games: For higher dimensions ($d \ge 2$), they replace simple counting with a game where a generator must satisfy overlapping rectangular requirements. This captures the geometric complexity of modern vector embeddings.
  • Formal Verification: Uniquely for a theoretical CS paper, the authors formalized and verified all 64 distinct mathematical results using the Lean 4 theorem prover, ensuring the absolute correctness of their complex proofs.

Datasets

As a theoretical work in the tradition of algorithmic learning theory, this paper does not use empirical datasets like Common Crawl. Instead, it uses:

  • Countable families of infinite languages: Abstract sets of strings or vectors in $\mathbb{Z}^d$.
  • Constructed counter-examples: Specifically designed language families used to prove the "failure of simultaneous optimality" in higher dimensions.

Key Insights and Ideas

  • The Dimensionality Gap: In one dimension (e.g., strings ranked by a single priority), a single "master" generator can achieve the best possible density for every language in a family. In two or more dimensions, this is impossible. Generator design becomes a multi-objective optimization problem where you must choose which targets to prioritize.
  • The Cost of a Chain: The difficulty for a generator isn't the length of the history, but how the "layers" of possible languages intersect. If an adversary can force a model to jump between many layers within a small region, the model loses density.
  • Geometry vs. Topology: The authors show that while topology determines which refinement histories can be excluded by evidence, geometry determines whether the remaining density requirements are even compatible.
  • Near-Half Guarantees: For languages with "finite Cantor-Bendixson rank" (a measure of topological complexity), models can achieve a density of nearly $1/2$. This means the generator can claim almost half of the available "space" in the language, even against an adversary.

Key Results

The paper’s findings are summarized in the following table from the text:

Table 1: Main results, informally.
  • 1D Optimality: The authors provide an exact structural value $b(K)$ that defines the maximum achievable density for any target $K$.
  • Higher-Dimensional Trade-offs: They prove that in $d \ge 2$, any generator guaranteeing density $x$ at one language and $y$ at others must satisfy $x + y \le 1/2$. You cannot have your cake and eat it too.
  • Threshold Improvement: They improve the non-degeneracy condition for broad generation from a polylogarithmic threshold to a near-logarithmic one ($h(V) = \log^{1+\tau}(V)$), bringing the theory closer to the limits of what is mathematically possible.

Limitations and Future Work

  • Information-Theoretic Focus: The results are architecture-independent and assume arbitrary computation. Future work could explore how specific architectures (like Transformers) are further limited by computational constraints.
  • The Sharp Endpoint: While they achieve $1/2 - \varepsilon$ density, they show that the exact $1/2$ endpoint is unattainable in higher dimensions even for simple cases. Characterizing the exact nature of this "gap" remains an open question.
  • Discrete vs. Continuous: The study is conducted on the integer lattice $\mathbb{Z}^d$. Extending these local breadth characterizations to continuous embedding spaces ($\mathbb{R}^d$) is a natural next step.

Summary updated

Abstract

Large language models sharpen the validity--breadth trade-off: a generator should avoid hallucinations without collapsing onto a narrow set of valid outputs. We study generation from positive examples of an unknown target in the Kleinberg--Mullainathan model, with arbitrary, possibly adversarial order and no distributional or computational assumptions. Breadth is measured by lower Banach density, which rules out arbitrarily large sparse holes, unlike prefix-based lower asymptotic density. 1. Exact optima in one dimension: For each target $K$ in a countable family, we characterize its optimal lower Banach density $b(K)$ via equivalent combinatorial and topological formulations. One eventually valid generator attains all $b(K)$ simultaneously. Every $α\in[0,1/2]$ occurs as $b(K)$ in some countable family; finite Cantor--Bendixson point rank guarantees $b(K)=1/2$, even without a uniform rank bound. 2. Unavoidable trade-offs in higher dimensions: For $d\ge2$, there need not be a single best generator: optimizing density for one target may worsen the guarantee for another. An explicit family quantifies this intrinsically multi-objective trade-off. 3. Complete characterization of density profiles: We characterize the full region of simultaneously achievable guarantees, with equivalent combinatorial and topological formulations, after excluding geometrically degenerate rectangles. Every prescribed product $\prod_i[0,α_i]$, $α_i\in[0,1/2]$ can occur as an exact achievable region for some language collection. 4. Near-half guarantees and the sharp endpoint: Under a near-logarithmic nondegeneracy condition, one generator achieves filtered density at least $1/2-\varepsilon$ at all finite-point-rank targets, for every $\varepsilon>0$, improving the previous polylogarithmic threshold. The exact $1/2$ endpoint can fail even for a rank-zero singleton family.
BibTeX
@misc{kleinberg2026characterizing,
  author = {Jon Kleinberg and Fan Wei},
  title = {{Characterizing Local Breadth in Language Generation}},
  year = {2026},
  eprint = {2611.14887},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14887},
}
Figure