Pareto-optimal Non-uniform Language Generation

• URL: http://arxiv.org/abs/2510.02795v1
• Date: Fri, 03 Oct 2025 08:08:20 GMT
• Title: Pareto-optimal Non-uniform Language Generation
• Authors: Moses Charikar, Chirag Pabbaraju,
• Abstract summary: 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.
• Score: 11.279808969568252
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kleinberg and Mullainathan (2024) recently proposed an interesting model for language generation in the limit: Given a countable collection of languages, and an adversary enumerating the strings of some language $L$ from the collection, the objective is to generate new strings from the target language, such that all strings generated beyond some finite time are valid. Li, Raman and Tewari (2024) and Charikar and Pabbaraju (2024) showed strong non-uniform generation guarantees in this model, giving algorithms that generate new valid strings from $L$ after seeing a number of distinct input strings $t(L)$ that depends only on $L$ (and the collection), but not the enumeration order. However, for both these works, the language-wise generation times $t(L)$ of the algorithm can be strictly sub-optimal. In this work, we study Pareto-optimality of non-uniform language generation in the limit. We propose an algorithm, whose generation times $t^\star(L)$ are (almost) Pareto-optimal: any other algorithm whose generation time for some language $L$ is strictly smaller than $t^\star(L)$, must satisfy that its generation time for some other language $L'$ is strictly worse than $t^\star(L')$. Pareto-optimality is essentially the best that one can achieve for non-uniform generation. Our algorithmic framework conveniently adapts to further give Pareto-optimal non-uniform generation algorithms in the practically motivated settings of noisy as well as representative generation.

Related papers

• Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations [1.6203023551115867]
  We study the framework of emphlanguage generation in the limit, where an adversary enumerates strings from an unknown language.<n>We show that generation in the limit remains achievable, and if $C$ has lower density $alpha$ in $K$, the algorithm's output achieves density at least $alpha/2$.<n>We characterize when identification in the limit is possible -- when hypotheses $M_t$ eventually satisfy $C subseteq M subseteq K$.
  arXiv  Detail & Related papers  (2025-11-07T14:56:04Z)
• Language Generation in the Limit: Noise, Loss, and Feedback [10.280148603465697]
  We show that a finite union of uniformly generatable collections is generatable in the limit, and asked if the same is true for non-uniform generation.<n>We show the equivalence of these models for uniform and non-uniform generation, and provide a characterization of non-uniform noisy generation.
  arXiv  Detail & Related papers  (2025-07-21T07:18:04Z)
• Density Measures for Language Generation [2.2872032473279065]
  We study the trade-off between validity and breadth of language generation algorithms.<n>Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language.<n>We show, however, that we provide an algorithm for language generation in the limit whose outputs have strictly positive density in $K$.
  arXiv  Detail & Related papers  (2025-04-19T18:08:18Z)
• 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)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  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)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit.<n>We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation.<n>We also provide a precise characterization of the language collections for which exhaustive generation is possible.
  arXiv  Detail & Related papers  (2024-11-22T22:13:40Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Interactive Code Generation via Test-Driven User-Intent Formalization [60.90035204567797]
  Large language models (LLMs) produce code from informal natural language (NL) intent. It is hard to define a notion of correctness since natural language can be ambiguous and lacks a formal semantics. We describe a language-agnostic abstract algorithm and a concrete implementation TiCoder.
  arXiv  Detail & Related papers  (2022-08-11T17:41:08Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth. We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
  arXiv  Detail & Related papers  (2020-10-15T04:42:29Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  We develop a meta-algorithm that selects between base algorithms. We show through a lower bound that even when one of the base algorithms has $O(sqrtT)$ regret, in general it is impossible to get better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2020-03-03T18:46:34Z)

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.