On Generation in Metric Spaces

Jiaxun Li, Vinod Raman, Ambuj TewariarXiv 2026 · arXiv

TL;DR

This paper extends the theoretical framework of machine learning generation from countable sets (like text strings) to continuous metric spaces, capturing how generative AI creates novel objects in structured domains like proteins or functions. By introducing a scale-sensitive $(\varepsilon, \varepsilon')$-closure dimension, the authors reveal a sharp geometric contrast: generation is stable and robust in finite-dimensional spaces but can fail abruptly based on minor scale and metric changes in infinite-dimensional spaces like $\ell^2$.

What Problem Does This Paper Address?

Recent foundational work in learning theory (notably Kleinberg and Mullainathan, 2024) established a formal framework for generation—modeling how systems like Large Language Models (LLMs) learn to produce novel, valid data. However, these early frameworks assumed a countable example space, where "novelty" simply meant generating an item that hadn't been explicitly seen before.

This assumption breaks down when generative AI is applied to continuous, richly structured domains, such as generating 3D protein structures or simulating physics via function generation. In a continuous space, merely being "distinct" from the training data isn't enough; a generated sample must be geometrically distant enough to be considered truly novel. This paper addresses the lack of theoretical guarantees and mathematical characterizations for data generation within these continuous metric spaces.

Methods

The authors formalize generation as a two-player game in a separable metric space. An adversary reveals a sequence of points from a hidden target language (hypothesis), and the generator must eventually output novel points within that language.

To handle the geometry of continuous spaces, the authors introduce two key innovations:

  1. Asymmetric Novelty Parameters: They define $\varepsilon$ as the adversary’s revelation scale (how tightly the training data covers the space) and $\varepsilon'$ as the generator's novelty threshold (how far the generated output must be from seen data).
  2. $(\varepsilon, \varepsilon')$-Closure Dimension: This is a scale-sensitive metric analogue of the classical closure dimension. It quantifies the maximum number of points an adversary can show such that the generator is completely trapped and unable to produce a valid, novel point at the required scales.

They also extend standard algorithmic frameworks by showing how a generator can be implemented using an Empirical Risk Minimization (ERM) oracle in a metric space setting.

Datasets

Not discussed in the paper. This is a purely theoretical paper with no empirical datasets or benchmarks.

Key Insights and Ideas

  • The Scale-Sensitivity of Novelty: In discrete spaces, whether a concept class can be generated is an intrinsic, binary property. In metric spaces, generatability is highly dependent on scale; a class might be easily generatable at a coarse resolution but impossible to generate at a fine resolution.
  • The Finite vs. Infinite-Dimensional Divide: The paper uncovers a stark geometric contrast based on the type of metric space:
  • Doubling Spaces: In spaces where large balls can be covered by a finite number of smaller balls (which includes all finite-dimensional normed spaces like $\mathbb{R}^d$), generation is robust. Small changes to the novelty scales or switching to a topologically equivalent metric will not break the system's ability to generate.
  • General/Infinite-Dimensional Spaces: In infinite-dimensional spaces like the Hilbert space $\ell^2$, generation is highly volatile. The ability to generate can completely vanish due to tiny adjustments in scale parameters or mild distortions in the metric.

Key Results

  • Uniform Generatability Characterization: The authors prove that a hypothesis class is uniformly generatable if and only if its $(\varepsilon, \varepsilon')$-closure dimension is finite ($C_{\varepsilon}^{\varepsilon'}(\mathcal{H}) < \infty$).
  • Non-Uniform Generatability: They show that non-uniform generation is possible if and only if the hypothesis class can be decomposed into a countable union of subclasses, each having a finite $(\varepsilon, \varepsilon')$-closure dimension.
  • Pathological Counterexamples: Through explicit mathematical constructions in $\ell^2$ (Examples 4.8, 4.9, and 4.11), the authors demonstrate cases where a learning problem transitions abruptly from being perfectly uniformly generatable to completely ungeneratable based purely on scale thresholds or metric choices.

Limitations and Future Work

  • Handling Symmetries: The current framework does not account for continuous domains that possess natural symmetries, such as rotational and translational invariances in protein folding.
  • Beyond Doubling Spaces: While the authors identified doubling spaces as a safe harbor for stable generation, they note that identifying broader geometric conditions that ensure stable behavior remains an open problem.
  • Algorithmic Constraints: The proposed ERM-based generator is guaranteed to terminate efficiently when the number of observed samples is large ($t \ge C(\mathcal{H}) + 1$). However, designing an algorithm that uses a finite number of ERM calls during early learning rounds ($t < C(\mathcal{H}) + 1$) remains an open challenge.

Summary updated

Abstract

We study generation in separable metric instance spaces. We extend the language generation framework from Kleinberg and Mullainathan [2024] beyond countable domains by defining novelty through metric separation and allowing asymmetric novelty parameters for the adversary and the generator. We introduce the $(\varepsilon,\varepsilon')$-closure dimension, a scale-sensitive analogue of closure dimension, which yields characterizations of uniform and non-uniform generatability and a sufficient condition for generation in the limit. Along the way, we identify a sharp geometric contrast. Namely, in doubling spaces, including all finite-dimensional normed spaces, generatability is stable across novelty scales and invariant under equivalent metrics. In general metric spaces, however, generatability can be highly scale-sensitive and metric-dependent; even in the natural infinite-dimensional Hilbert space $\ell^2$, all notions of generation may fail abruptly as the novelty parameters vary.
BibTeX
@misc{li2026generation,
  author = {Jiaxun Li and Vinod Raman and Ambuj Tewari},
  title = {{On Generation in Metric Spaces}},
  year = {2026},
  eprint = {2602.07710},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.07710},
}
Figure