# Contrastive Identification and Generation in the Limit

arXiv: https://arxiv.org/abs/2605.06211 · HTML: https://mlsanity.com/paper/2605.06211/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 36 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 27 of 27)

- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [Multiple Instance Learning: A Survey of Problem Characteristics and Applications](https://mlsanity.com/paper/1612.03365/) (2016)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Classification from Pairwise Similarity and Unlabeled Data](https://mlsanity.com/paper/1802.04381/) (2018)
- [Generation through the lens of learning theory](https://mlsanity.com/paper/2410.13714/) (2024)
- [Exploring Facets of Language Generation in the Limit](https://mlsanity.com/paper/2411.15364/) (2024)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [On Union-Closedness of Language Generation](https://mlsanity.com/paper/2506.18642/) (2025)
- [Language Generation in the Limit: Noise, Loss, and Feedback](https://mlsanity.com/paper/2507.15319/) (2025)
- [(Im)possibility of Automated Hallucination Detection in Large Language Models](https://mlsanity.com/paper/2504.17004/) (2025)
- [On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability](https://mlsanity.com/paper/2412.18530/) (2024)
- [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025)
- [Pareto-optimal Non-uniform Language Generation](https://mlsanity.com/paper/2510.02795/) (2025)
- [Language Generation with Infinite Contamination](https://mlsanity.com/paper/2511.07417/) (2025)
- [Learning Algorithms in the Limit](https://mlsanity.com/paper/2506.15543/) (2025)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Language Generation: Complexity Barriers and Implications for Learning](https://mlsanity.com/paper/2511.05759/) (2025)
- [Safe Language Generation in the Limit](https://mlsanity.com/paper/2601.08648/) (2026)
- [Language Generation with Replay: A Learning-Theoretic View of Model Collapse](https://mlsanity.com/paper/2603.11784/) (2026)
- [Characterizing the Effect of Noise in Language Generation in the Limit](https://mlsanity.com/paper/2601.21237/) (2026)
- [Agnostic Language Identification and Generation](https://mlsanity.com/paper/2601.23258/) (2026)
- [On Generation in Metric Spaces](https://mlsanity.com/paper/2602.07710/) (2026)
- [On the Price of Privacy for Language Identification and Generation](https://mlsanity.com/paper/2604.07238/) (2026)
- [Differentially Private Language Generation and Identification in the Limit](https://mlsanity.com/paper/2604.08504/) (2026)

## Built on by (most cited first, 4 of 4)

- [Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit](https://mlsanity.com/paper/2606.14688/) (2026)
- [Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy](https://mlsanity.com/paper/2609.10525/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)
- [GenLimitLib: A Formal Library for Language Generation in the Limit and AI-Assisted Mathematical Research](https://mlsanity.com/paper/2609.36663/) (2026)

## Abstract (arXiv)

In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [2024] introduced generation in the limit, where the learner instead must eventually output novel elements of the target's support. Both lines of work focus on positive-only or fully labeled data. Yet many natural supervision signals are inherently relational rather than singleton, which encode relationships between examples rather than labels of individual ones. We initiate the study of contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data: a stream of unordered pairs x,y satisfying h(x)ne h(y) for an unknown target binary hypothesis h, but which element is positive is hidden from the learner. We first present three results in the noiseless setting: an exact characterization of contrastive identifiable classes (a one-line geometric refinement of Angluin [1980]'s tell-tale condition), a combinatorial dimension called contrastive closure dimension (a contrasitive analogue of the closure dimension in Raman et al. [2025]) and exactly characterizing uniform contrastive generation with tight sample complexity, and a strict hierarchy in which contrastive generation and text identification are mutually incomparable. We then prove a sharp reversal under finite adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget by a single budget-independent algorithm, yet not identifiable from positive examples under even one corrupted observation. The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.