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

A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Controlled text generation · 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.

Shows that eventually consistent language generators cannot achieve nontrivial timely density under deadlines, and that allowing vanishing hallucination rate recovers density 1/2 timely generation for any superlinear deadline via a black-box reduction to Kleinberg–Wei's generator.

Problem

Language generation in the limit under a global preference order on strings requires breadth, but generated strings should also be produced early (timeliness) under a deadline function; prior consistent generators may suffer mode collapse under such deadlines.

Approach

Impose per-string deadlines defined by rank in a preference order; prove consistent generators fail, then relax to vanishing hallucination rate and build a randomized speculative black-box reduction (SBG) that achieves timely lower density 1/2 for any superlinear deadline, with hallucination rate matching a near-tight bound.

Key results

• Eventually consistent generators achieve timely lower density 0 for some language family under any deadline function.
• Under linear deadlines, any generator with vanishing hallucination rate achieves timely lower density 0.
• For any feasible superlinear deadline profile (D,H), a randomized black-box algorithm achieves timely lower density 1/2 with hallucination rate at most H(t).

Surprising findings

• Hallucination is necessary for timely dense generation: eventually consistent generators must sacrifice timely density under any deadline.

Limitations

• Results are theoretical and only for superlinear deadlines; linear deadlines are impossible with nontrivial density.
• Timeliness is measured only per string, not over language hypotheses; a golden-ratio conjecture about language-level timeliness remains open.

Experimental setup

Metrics: timely lower density hallucination rate

Baselines: Kleinberg-Wei eventually consistent generator

Builds on: Kleinberg-Mullainathan language generation in the limit Kleinberg-Wei density Gold language identification Angluin

Closest papers by meaning

• Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.88)
• On Union-Closedness of Language Generation (NeurIPS 2025 · similarity 0.86)
• Closing the Curious Case of Neural Text Degeneration (ICLR 2024 · similarity 0.86)
• On Generation in Metric Spaces (NeurIPS 2026 · similarity 0.86)
• Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.85)
• Arrows of Time for Large Language Models (ICML 2024 · similarity 0.85)