Research map / Learning theory and algorithms / Prediction and decision losses

On Generation in Metric Spaces

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Metric and ordinal embedding · 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.

Extends Kleinberg-Mullainathan language generation to separable metric spaces via metric novelty with asymmetric scales, characterizes uniform/non-uniform generatability by a scale-sensitive closure dimension, and shows doubling spaces are stable while ℓ² generation can fail abruptly.

Problem

Language generation in the limit (Kleinberg and Mullainathan 2024) assumes countable instance spaces and defines novelty only as distinctness, which is inadequate for continuous or structured spaces where generated outputs should be sufficiently far from observed ones.

Approach

Define novelty via metric separation with asymmetric adversary (ε) and generator (ε') scales, introduce the scale-sensitive (ε,ε')-closure dimension that characterizes uniform and non-uniform generatability, and show that doubling spaces make generatability invariant to scales and equivalent metrics while ℓ² exhibits abrupt scale-dependent failures.

Key results

• Defines the (ε,ε')-closure dimension and proves a complete characterization of (ε,ε')-uniform generatability: uniformly generatable iff the closure dimension is finite.
• In doubling spaces (including finite-dimensional normed spaces), uniform and non-uniform generatability are invariant to the choice of ε, ε' and preserved under equivalent metrics.
• In ℓ², a single hypothesis class can exhibit all regimes from not generatable in the limit to uniformly generatable depending on (ε,ε'), and generatability in the limit can be lost when ε increases past a threshold.

Surprising findings

• Generatability in the limit is not monotone in ε: increasing the adversary scale ε can cause generation to fail.
• Generatability can fail under an equivalent metric: a class uniformly generatable under the standard ℓ² metric may be non-uniformly non-generatable under an equivalent metric.

Limitations

• Purely theoretical; no empirical evaluation.
• Restricted to binary hypothesis classes and separable metric spaces.
• Symmetry-equivalence of outputs not addressed (listed as open direction).

Experimental setup

Builds on: Kleinberg and Mullainathan (2024) language generation in the limit closure dimension

Closest papers by meaning

• On Union-Closedness of Language Generation (NeurIPS 2025 · similarity 0.87)
• A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse (NeurIPS 2026 · similarity 0.86)
• Representative Language Generation (ICML 2025 · similarity 0.83)
• On the Query Complexity of Verifier-Assisted Language Generation (ICML 2025 · similarity 0.82)
• Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.81)
• Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.81)