# MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization

arXiv: https://arxiv.org/abs/2609.31705 · HTML: https://mlsanity.com/paper/2609.31705/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 20 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [An MLP Baseline for Handwriting Recognition Using Planar Curvature and Gradient Orientation](https://mlsanity.com/paper/2508.11803/) (2025)
- [A Sobel-Gradient MLP Baseline for Handwritten Character Recognition](https://mlsanity.com/paper/2508.11902/) (2025)
- [Significance-Gain Pair Encoding for LLMs: A Statistical Alternative to Frequency-Based Subword Merging](https://mlsanity.com/paper/2603.19261/) (2026)
- [StepCache: Step-Level Reuse with Lightweight Verification and Selective Patching for LLM Serving](https://mlsanity.com/paper/2603.28795/) (2026)

## Abstract (arXiv)

Byte-Pair Encoding (BPE) constructs subword vocabularies through greedy pair merging, but conventional BPE requires the number of merges or target vocabulary size to be specified externally. Significance-Gain Pair Encoding (SG-BPE) replaces frequency-only selection with a statistical criterion based on how strongly an observed pair exceeds its expected co-occurrence under an independence model. This paper introduces MDL-Calibrated Significance-Gain Pair Encoding (MDL-SG), a three-stage procedure separating discovery, replication, and utility. Candidate pairs are ranked by Significance-Gain on a discovery partition, tested for replication on a separate partition using an exact one-sided hypergeometric test with per-iteration Benjamini-Hochberg correction, and then evaluated on a utility partition using a Minimum Description Length (MDL) criterion. Merging stops automatically when no replicated candidate yields positive held-out MDL gain. On WikiText-103, MDL-SG stops at 209, 433, and 847 merges for 120K, 250K, and 500K-character tokenizer-training samples, respectively. At 500K characters, it selects a stored vocabulary of 1,017 tokens without prescribing the vocabulary size in advance. In a compute-matched TinyGPT experiment with identical 2,024,448-parameter models and 500 optimizer updates per language model, MDL-SG achieves validation/test BPC of 3.2612/3.2436, compared with test BPC of 3.2894 for SG-BPE and 3.3493 for frequency BPE. Frequency BPE achieves stronger raw compression, while MDL-SG achieves lower BPC, showing that compression-oriented merge selection and language-model utility need not coincide.