Cover Image

Exploring Facets of Language Generation in the Limit

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Charikar, Moses, Pabbaraju, Chirag
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Artificial Intelligence Computation and Language Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

A Characterization of List Language Identification in the Limit
by: Charikar, Moses, et al.
Published: (2025)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

Differentially Private Language Generation and Identification in the Limit
by: Mehrotra, Anay, et al.
Published: (2026)

On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
by: Kalavasis, Alkis, et al.
Published: (2024)

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

Contrastive Identification and Generation in the Limit
by: Li, Xiaoyu, et al.
Published: (2026)

Language Generation with Infinite Contamination
by: Mehrotra, Anay, et al.
Published: (2025)

On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
by: Kalavasis, Alkis, et al.
Published: (2024)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

The CLRS-Text Algorithmic Reasoning Language Benchmark
by: Markeeva, Larisa, et al.
Published: (2024)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Characterizing the Effect of Noise in Language Generation in the Limit
by: Li, Aaron, et al.
Published: (2026)

Quantifying the Gain in Weak-to-Strong Generalization
by: Charikar, Moses, et al.
Published: (2024)

Learning Linear Attention in Polynomial Time
by: Yau, Morris, et al.
Published: (2024)

A Tighter Complexity Analysis of SparseGPT
by: Li, Xiaoyu, et al.
Published: (2024)

GateLoop: Fully Data-Controlled Linear Recurrence for Sequence Modeling
by: Katsch, Tobias
Published: (2023)

The Library Theorem: How External Organization Governs Agentic Reasoning Capacity
by: Mainen, Zachary F.
Published: (2026)

Dynamic Data Layout Optimization with Worst-case Guarantees
by: Rong, Kexin, et al.
Published: (2024)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing
by: Liu, Minghui, et al.
Published: (2024)

Learning Algorithms in the Limit
by: Papazov, Hristo, et al.
Published: (2025)

Breaking the Metric Voting Distortion Barrier
by: Charikar, Moses, et al.
Published: (2023)

Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
by: Guo, Anxin, et al.
Published: (2026)

Agnostic Language Identification and Generation
by: Høgsgaard, Mikael Møller, et al.
Published: (2026)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Model Stealing for Any Low-Rank Language Model
by: Liu, Allen, et al.
Published: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

SubGen: Token Generation in Sublinear Time and Memory
by: Zandieh, Amir, et al.
Published: (2024)

Provably Extracting the Features from a General Superposition
by: Liu, Allen
Published: (2025)

Provably Learning from Modern Language Models via Low Logit Rank
by: Golowich, Noah, et al.
Published: (2025)

Limits of Approximating the Median Treatment Effect
by: Addanki, Raghavendra, et al.
Published: (2024)

On the Price of Privacy for Language Identification and Generation
by: Li, Xiaoyu, et al.
Published: (2026)

Neuro-symbolic Syntactic Parsing: Shaping a Neural Network with the CYK Algorithm
by: Zanzotto, Fabio Massimo, et al.
Published: (2026)

A Partition Cover Approach to Tokenization
by: Lim, Jia Peng, et al.
Published: (2025)

Algorithmically Establishing Trust in Evaluators
by: de Wynter, Adrian
Published: (2025)