Research map / Large language models / Language, safety and interpretability

Generating in the Limit with Infinitely Many Hallucinations

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: LLM unlearning and benchmarks · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Recasts language generation in the limit as a precision-recall problem, allowing vanishing-rate hallucinations and continuous novelty, and gives generators achieving precision 1 with improved or full recall.

Problem

Generation in the limit forces eventual validity and strict novelty, creating a tension between coverage (recall) and validity; prior work had no complementary precision notion for infinite sets and no analysis of allowing vanishing-rate errors or partial novelty.

Approach

Define precision and recall for infinite languages via exhaustions and a tail-precision notion; allow infinitely many hallucinations at vanishing rate, interleave safe generation with sparse exploration rounds that enumerate all strings, and relax novelty to a gamma-fraction constraint.

Key results

• Without novelty (gamma=0), a generator achieves lower recall 1 and lower precision 1 for any func-bounded adversary exhaustion.
• With novelty (gamma=1), the algorithm achieves precision 1 and recall at least max(1 - beta, alpha/3), which can approach 1 when the adversary is sparse, while the no-hallucination bound approaches zero.
• For any gamma in [0,1), a gamma-novel generator achieves precision 1 and recall 1.

Surprising findings

• Allowing hallucinations at a vanishing rate can yield tail precision 0 while precision stays 1.
• Any fixed allowance of non-novel outputs (gamma<1) permits recall 1 and precision 1 in the limit.

Limitations

• Results are theoretical; no empirical evaluation with actual language models.
• Exploration rounds require enumerating the full alphabet-star, which is computationally impractical.
• Assumes countable collection of infinite languages and fixed enumeration of the target.

Experimental setup

Metrics: precision recall tail precision

Baselines: Kleinberg and Mullainathan generator (recall 1/2 bound) eventually valid generators

Builds on: language generation in the limit (Kleinberg and Mullainathan) density-based generation (Kleinberg and Wei style density results) pods algorithm for novel generation

Closest papers by meaning

• Language Generation in the Limit (NeurIPS 2024 · similarity 0.91)
• Large language models suffer from a curse of ambiguity (NeurIPS 2026 · similarity 0.88)
• A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse (NeurIPS 2026 · similarity 0.88)
• Contrastive Identification and Generation in the Limit (NeurIPS 2026 · similarity 0.87)
• Training on the Test Task Confounds Evaluation and Emergence (ICLR 2025 · similarity 0.87)
• PolyPythias: Stability and Outliers across Fifty Language Model Pre-Training Runs (ICLR 2025 · similarity 0.87)