betaFeedback

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 KK in a countable family, we characterize its optimal lower Banach density b(K)b(K) via equivalent combinatorial and topological formulations. One eventually valid generator attains all b(K)b(K) simultaneously. Every α∈[0,1/2]α\in[0,1/2] occurs as b(K)b(K) in some countable family; finite Cantor–Bendixson point rank guarantees b(K)=1/2b(K)=1/2, even without a uniform rank bound. 2. Unavoidable trade-offs in higher dimensions: For d≥2d\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 ∏i[0,αi]\prod_i[0,α_i], αi∈[0,1/2]α_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−ε1/2-\varepsilon at all finite-point-rank targets, for every ε>0\varepsilon>0, improving the previous polylogarithmic threshold. The exact 1/21/2 endpoint can fail even for a rank-zero singleton family.

Paper details

vlnc:W_vtp8wy2h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…