analiza aiqbench
The paper shows that finding the optimal byte-pair encoding is APX-complete, so no polynomial-time approximation scheme is likely to exist, and it proves that the standard greedy BPE procedure reaches a worst-case approximation ratio between 1/3 and about 0.4324. These are the first worst-case guarantees on BPE's compression quality for all inputs, which helps explain why a heuristic used in most LLM tokenizers works in practice. The bounds are worst-case, though, so they say little about typical tokenization quality on real language data.
Theoretical Analysis of Byte-Pair Encoding
arXiv:2411.08671v2 Announce Type: replace-cross Abstract: Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between $1/3$ and $(1-e^{-2})/2 \approx 0.4324$. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.
Abstract:Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between $1/3$ and $(1-e^{-2})/2 \approx 0.4324$. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.
Extended version of ESA 2026 paper. Changes in v2: (1) an upper bound of ~0.4324 on the approximation ratio of BPE, improving the earlier 0.625, and (2) a modified proof of Claim 5, fixing an inaccuracy in v1
Data Structures and Algorithms (cs.DS); Computation and Language (cs.CL)
arXiv:2411.08671 [cs.DS]
(or arXiv:2411.08671v2 [cs.DS] for this version)
Text integral sub licența deschisă a publicației · 228 cuvinte
Subiecte conexe
Understanding Scattered Forest Search: A Version-Space Perspective on Multi-Turn Program Correction
arXiv · 30 sept. 2026
Provable Speech Attributes Conversion via Latent Independence
arXiv · 28 sept. 2026
Equal Path Cost, Unequal Output Effects: Understanding Perturbation Propagation in Diffusion Models
arXiv · 10 oct. 2026
Robustness of Similarity-based Positional Encoding Under Rotations: Theoretical Analysis and Experimental Validation
arXiv · 17 iun. 2026