Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

• URL: http://arxiv.org/abs/2608.01320v1
• Date: Sun, 02 Aug 2026 15:41:31 GMT
• Title: Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
• Abstract summary: Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples.<n>In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order.<n>Reliable generation is formalized through two eventual guarantees: validity and novelty relative to the observed data.
• Score: 6.204831354195728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.

Related papers

• Mistake-Bounded Language Generation [6.034531760235531]
  We investigate the learning task of language generation in the limit.<n>We shift focus from the traditional time-of-last-mistake metric to a new notion of "mistake-bounded generation"<n>We show that our framework can be extended to accommodate noisy adversaries.
  arXiv  Detail & Related papers  (2026-05-11T16:32:01Z)
• Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
  Speculative generation has emerged as a promising technique to accelerate inference in large language models.<n>In this work, we establish the first tight'' lower bounds on the runtime of any deterministic speculative generation algorithm.
  arXiv  Detail & Related papers  (2025-12-12T16:54:33Z)
• Pareto-optimal Non-uniform Language Generation [11.279808969568252]
  We show that an algorithm whose generation time for some language $L$ is strictly smaller than $tstar(L)$ must satisfy that its generation time for some other language $L'$ is strictly worse than $tstar(L')$.<n>Our framework conveniently adapts to give non-uniform generation algorithms in the practically motivated settings of noisy as well as representative generation.
  arXiv  Detail & Related papers  (2025-10-03T08:08:20Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  We study an online fair division setting, where goods arrive one at a time and there is a fixed set of $n$ agents.<n>Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents.<n>We show how to obtain worst case guarantees with respect to well-known fairness notions.
  arXiv  Detail & Related papers  (2025-05-28T09:48:16Z)
• On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability [16.30681257128492]
  [KM24] is an algorithm for generating from any countable language collection in the limit.<n>Recent work introduces different notions of breadth and explores when generation with breadth is possible.<n>Our results show that generation with many existing notions of breadth becomes equally hard, when stability is required.
  arXiv  Detail & Related papers  (2024-12-24T16:24:43Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• SpecTr: Fast Speculative Decoding via Optimal Transport [30.18181671899423]
  We develop a new autoregressive sampling algorithm called $textitSpecTr$, which provides speedup in decoding while ensuring that there is no quality degradation in the decoded output. We experimentally demonstrate that for state-of-the-art large language models, the proposed approach achieves a wall clock speedup of 2.13X, a further 1.37X speedup over speculative decoding on standard benchmarks.
  arXiv  Detail & Related papers  (2023-10-23T17:47:34Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  We propose a deterministic search algorithm balancing both quality and diversity. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
  arXiv  Detail & Related papers  (2022-11-22T00:26:13Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling. We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
  arXiv  Detail & Related papers  (2022-10-03T00:28:44Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.