Which Pieces Does Unigram Tokenization Really Need?

• URL: http://arxiv.org/abs/2512.12641v1
• Date: Sun, 14 Dec 2025 11:13:49 GMT
• Title: Which Pieces Does Unigram Tokenization Really Need?
• Abstract summary: The Unigram tokenization algorithm offers a probabilistic alternative to the greedy adapters of Byte-Pair.<n>We bridge this gap between theory and practice by providing a clear guide to implementation and parameter choices.
• Score: 6.722891561991933
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The Unigram tokenization algorithm offers a probabilistic alternative to the greedy heuristics of Byte-Pair Encoding. Despite its theoretical elegance, its implementation in practice is complex, limiting its adoption to the SentencePiece package and adapters thereof. We bridge this gap between theory and practice by providing a clear guide to implementation and parameter choices. We also identify a simpler algorithm that accepts slightly higher training loss in exchange for improved compression.

Related papers

• MinGram: A Minimalist Unigram Tokenizer with High Compression and Competitive Morphological Alignment [0.0]
  We introduce MinGram, which keeps the token-list representation but simplifies training using a BPE-derived seed vocabulary.<n>In controlled downstream language-model training, Unigram-family tokenizers, with MinGram among the best, consistently beat BPE in bits-per-byte.
  arXiv  Detail & Related papers  (2026-06-25T13:31:02Z)
• Tokenisation via Convex Relaxations [14.99534435778172]
  Tokenisation is an integral part of the current NLP pipeline.<n>We formulate tokeniser construction as a linear program and solve it using convex optimisation tools.<n>We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models.
  arXiv  Detail & Related papers  (2026-05-21T17:59:56Z)
• Prefix Parsing is Just Parsing [53.010152712125766]
  Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar.<n>We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing.<n>We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector.
  arXiv  Detail & Related papers  (2026-04-23T01:20:40Z)
• Single-pass Adaptive Image Tokenization for Minimum Program Search [75.59409288259151]
  We propose a single-pass adaptive tokenizer, KARL, which predicts the appropriate number of tokens for an image in a single forward pass.<n> KARL matches the performance of recent adaptive tokenizers while operating in a single pass.
  arXiv  Detail & Related papers  (2025-07-10T17:59:53Z)
• Foundations of Top-$k$ Decoding For Language Models [19.73575905188064]
  We develop a theoretical framework that both explains and generalizes top-$k$ decoding.<n>We show how to optimize it efficiently for a large class of divergences.
  arXiv  Detail & Related papers  (2025-05-25T23:46:34Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• CODA: Repurposing Continuous VAEs for Discrete Tokenization [31.932323809073477]
  textbfCODA(textbfCOntinuous-to-textbfDiscrete textbfAdaptation) is a framework that decouples compression and discretization.<n>Our approach achieves a remarkable codebook utilization of 100% and notable reconstruction FID (rFID) of $mathbf0.43$ and $mathbf1.34$ for $8 times$ and $16 times$ compression on ImageNet 256$times$ 256 benchmark.
  arXiv  Detail & Related papers  (2025-03-22T12:59:00Z)
• Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism [0.0]
  This paper presents a novel pathway that translates bit-parallel string matching algorithms into the quantum framework.<n>By embedding quantum search within a bit-parallel model, we reduce the time complexity of string matching.<n>We also enhance their performance to achieve a quadratic speedup through Grover's search.
  arXiv  Detail & Related papers  (2025-03-07T17:24:00Z)
• A Partition Cover Approach to Tokenization [24.595558878756787]
  Tokenization is a process of encoding strings into tokens of a fixed vocabulary size.<n>Byte-Pair corpora (BPE) formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges.<n>We show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC.
  arXiv  Detail & Related papers  (2025-01-08T17:07:07Z)
• Constant Depth Code Deformations in the Parity Architecture [0.0]
  We present a protocol to encode and decode arbitrary quantum states in the parity architecture with constant circuit depth. We show that our method can reduce the depth of implementing the quantum Fourier transform by a factor of two when allowing measurements.
  arXiv  Detail & Related papers  (2023-03-15T13:15:26Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  We develop an unsupervised parallelizable learner that discovers high-quality generation orders purely from training data. We implement the encoder as a Transformer with non-causal attention that outputs permutations in one forward pass. Empirical results in language modeling tasks demonstrate that our method is context-aware and discovers orderings that are competitive with or even better than fixed orders.
  arXiv  Detail & Related papers  (2021-10-27T16:08:09Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
  arXiv  Detail & Related papers  (2021-07-05T11:41:16Z)
• Learned transform compression with optimized entropy encoding [72.20409648915398]
  We consider the problem of learned transform compression where we learn both, the transform and the probability distribution over the discrete codes. We employ a soft relaxation of the quantization operation to allow for back-propagation of gradients and employ vector (rather than scalar) quantization of the latent codes.
  arXiv  Detail & Related papers  (2021-04-07T17:58:01Z)

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.