WorksComputer Science
Characterizing Local Breadth in Language Generation
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 in a countable family, we characterize its optimal lower Banach density via equivalent combinatorial and topological formulations. One eventually valid generator attains all simultaneously. Every occurs as in some countable family; finite Cantor–Bendixson point rank guarantees , even without a uniform rank bound. 2. Unavoidable trade-offs in higher dimensions: For , 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 , 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 at all finite-point-rank targets, for every , improving the previous polylogarithmic threshold. The exact endpoint can fail even for a rank-zero singleton family.