Related papers: Mistake-Bounded Language Generation

Mistake-Bounded Language Generation

URL: http://arxiv.org/abs/2605.10809v1
Date: Mon, 11 May 2026 16:32:01 GMT
Title: Mistake-Bounded Language Generation
Abstract summary: 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.
Score: 6.034531760235531
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "mistake-bounded generation." While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al. (2025), enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of $\mathsf{Cdim}(L)$ and a mistake bound of $\lfloor \log_2 |L| \rfloor$, whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes $O(\log i)$ necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary's suboptimality.

Related papers

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms [6.204831354195728]
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.
arXiv Detail & Related papers (2026-08-02T15:41:31Z)
On Language Generation in the Limit with Bounded Memory [17.70989972580602]
We study language generation in the limit under bounded memory.<n>In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples.
arXiv Detail & Related papers (2026-05-28T17:57:03Z)
How LLMs Fail and Generalize in RTL Coding for Hardware Design? [56.361436215029045]
We introduce a new error taxonomy grounded in problem solvability, inspired by cognitive theory.<n>Our taxonomy categorizes failures into syntactic, semantic, solvable functional, and unsolvable functional types.
arXiv Detail & Related papers (2026-04-26T14:34:49Z)
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)
Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
arXiv Detail & Related papers (2025-04-07T18:30:18Z)
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)
Language Generation with Strictly Proper Scoring Rules [70.340673452404]
We propose a strategy for adapting scoring rules to language generation, allowing for language modeling with any non-local scoring rules. We train language generation models using two classic strictly proper scoring rules, the Brier score and the Spherical score, as alternatives to the logarithmic score.
arXiv Detail & Related papers (2024-05-29T09:09:00Z)
Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
arXiv Detail & Related papers (2024-02-24T09:47:46Z)
Generating Sequences by Learning to Self-Correct [64.0249217590888]
Self-Correction decouples an imperfect base generator from a separate corrector that learns to iteratively correct imperfect generations. We show that Self-Correction improves upon the base generator in three diverse generation tasks.
arXiv Detail & Related papers (2022-10-31T18:09:51Z)
The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
We study the problem of regret minimization for episodic Reinforcement Learning (RL) We focus on learning with general function classes and general model classes. We show that a logarithmic regret bound is realizable by algorithms with $O(log T)$ switching cost.
arXiv Detail & Related papers (2022-03-03T02:55:55Z)

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