Cover Image

Tokenisation over Bounded Alphabets is Hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kastreva, Violeta, Whittington, Philip, Komm, Dennis, Pimentel, Tiago
Format:	Preprint
Published:	2025
Subjects:	Computation and Language Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tokenisation is NP-Complete
by: Whittington, Philip, et al.
Published: (2024)

Tokenisation via Convex Relaxations
by: Tempus, Jan, et al.
Published: (2026)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Encodings for Range Minimum Queries over Bounded Alphabets
by: Jo, Seungbum, et al.
Published: (2026)

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

Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
by: Kleinberg, Jon, et al.
Published: (2025)

Coupling without Communication and Drafter-Invariant Speculative Decoding
by: Daliri, Majid, et al.
Published: (2024)

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

Online String Attractors
by: Whittington, Philip
Published: (2024)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

Hardness of High-Dimensional Linear Classification
by: Munteanu, Alexander, et al.
Published: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

Mistake-Bounded Language Generation
by: Kleinberg, Jon, et al.
Published: (2026)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
by: Chauhan, Rohan, et al.
Published: (2025)

Better Bounds for the Distributed Experts Problem
by: Woodruff, David P., et al.
Published: (2026)

Scalable network reconstruction in subquadratic time
by: Peixoto, Tiago P.
Published: (2024)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

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

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

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

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

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

Block Verification Accelerates Speculative Decoding
by: Sun, Ziteng, et al.
Published: (2024)

SpecTr: Fast Speculative Decoding via Optimal Transport
by: Sun, Ziteng, et al.
Published: (2023)

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

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

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

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

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