PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Azam Nouri

arXiv:2609.31705v1cs.CVcs.CL

TL;DR

Conventional BPE requires a preset merge count or target vocabulary size, while statistically significant pairs can still offer little representation-cost benefit. MDL-SG separates discovery, replication, and held-out utility to stop without a preset size; in the reported comparison, it has lower observed BPC than the baselines, while frequency BPE produces shorter token sequences.

  • Problem

    Conventional BPE requires a preset merge count or vocabulary size, while significance-only stopping can accept sparse pairs that add little representation-cost benefit.

    Source: §1 · p. 2

  • Method

    MDL-SG ranks candidates by Significance-Gain, tests replication on separate data, and uses held-out MDL gain to decide whether to continue merging.

    Source: §7 · p. 14

  • Results

    Test BPC was 3.2436 for MDL-SG, versus 3.2894 for SG-BPE and 3.3493 for frequency BPE; frequency BPE produced shorter token sequences.

    Source: §7 · p. 14

  • Takeaways & Limitations

    MDL-SG stops without a predetermined merge count, selecting data-dependent stopping points for the tested tokenizer-training sample sizes.

    Source: §1 · p. 3, §7 · p. 14

    The TinyGPT comparison uses one seed, so it does not quantify run-to-run variability or the stability of the observed BPC differences.

    Source: §6 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

MDL-SG separates candidate discovery, replication, and held-out utility to stop merging without a preset merge count. On WikiText-103, stopping points vary with sample size, and raw compression and language-model performance favor different tokenizers.

Background

  • Conventional BPE chooses the most frequent adjacent pair and requires an externally specified merge count or target vocabulary size.Frequency alone may favor pairs whose count reflects common constituent tokens rather than strong pair-specific dependence.Source: §1 · pp. 1–2

Motivation

  • Sparse late-stage pairs can have large standardized associations despite offering little representation-cost reduction, so significance alone may keep merging or require another tuned stopping threshold.The fixed minimum pair-count rule screens candidates but does not determine termination.Source: §1 · p. 2

Method

  • MDL-SG ranks candidates by Significance-Gain, tests them on a disjoint replication partition, and evaluates replicated candidates using held-out description length.Per-iteration Benjamini–Hochberg correction is applied to exact one-sided hypergeometric replication tests at q = 0.05.Source: §1 · pp. 2–3
  • A merge is accepted only when its held-out MDL gain is positive, balancing coding benefit against the added representation cost without an empirically tuned zero threshold.The objective follows the Minimum Description Length principle of balancing fit and representation complexity.Source: §1 · p. 3

Results

  • At 120K, 250K, and 500K characters, MDL-SG stops at 209, 433, and 847 merges; at 500K, it also yields lower BPC than frequency BPE despite weaker raw compression.The best remaining replicated candidates at those stopping points have net MDL gains of −0.4223, −0.1507, and −0.0474 bits.Source: §1 · pp. 3–4

2 Methodology

MDL-SG separates discovery, replication, and held-out utility using disjoint corpus partitions. It accepts statistically replicated candidates only when their held-out MDL gain is positive, stopping when no qualifying merge remains.

2 Methodology

  • MDL-SG makes merge decisions through statistical discovery, replication on separate data, and held-out utility evaluation.The same accepted merge is applied to all three partitions to keep their token inventories synchronized.Source: §2 · p. 4

2.1 Data Partitioning

  • The tokenizer-training corpus is divided into three disjoint subsets for candidate-merge ranking, replication testing, and utility evaluation, avoiding reuse of discovery observations to assess replication or held-out coding benefit.Source: §2.1 · p. 4

2.2 Stage I: Significance-Gain Discovery

  • Significance-Gain ranks discovery candidates by combining empirical support with unexpectedly strong adjacency, but a high score alone does not qualify a merge.The minimum candidate count is a screening criterion, not the stopping rule.Source: §2.2 · pp. 4–5

2.3 Stage II: Statistical Replication on a Disjoint Partition

  • Candidates are tested on a separate replication partition with a one-sided hypergeometric test and per-iteration Benjamini–Hochberg correction at q = 0.05.The paper claims no global false-discovery-rate guarantee across the adaptive merge trajectory.Source: §2.3 · p. 5

2.4 Stage III: Held-Out MDL Utility

  • Replicated candidates are evaluated on held-out MDL utility, including a BIC-style penalty for active vocabulary growth and the cost of storing each merge rule.Positive net gain means the held-out description-length reduction exceeds the added representation cost.Source: §2.4 · pp. 5–6

2.5 Automatic Stopping Criterion

  • Training stops when no candidate passes replication or when no replicated candidate has positive net held-out MDL gain; final vocabulary size is not preset.Computational maximum-vocabulary and maximum-merge limits were not reached in the reported experiments.Source: §2.5 · p. 6

3 Experimental Setup

Experiments test whether MDL-SG selects corpus-size-dependent stopping points and compare its tokenization and language-model evaluation setup with matched baselines. They use WikiText-103 and assess both compression and character-normalized predictive performance.

3.1 Dataset and Preprocessing

  • WikiText-103 tokenizer samples contain 120,000, 250,000, or 500,000 characters, with tokenizer training and language-model validation and test using separate corpus splits.The 500K-character sample is partitioned into 350K discovery, 75K replication, and 75K utility characters; preprocessing normalizes repeated spaces, tabs, and long newline runs.Source: §3.1 · pp. 7–8

3.2 Automatic-Stopping Experiments

  • MDL-SG stops at 209, 433, and 847 merges for 120K-, 250K-, and 500K-character samples, respectively, when no replicated candidate has positive held-out MDL gain.The stopping boundary was checked by reevaluating remaining replicated candidates; the table summarizes stopping behavior and remaining MDL gains.Source: §3.2 · p. 8, Table 1 · p. 8

3.3 Baseline Tokenizers

  • At the 847-merge comparison point, all methods share 1,017 stored tokens, while active vocabularies are 1,002 for frequency BPE, 981 for SG-BPE, and 976 for MDL-SG.MDL-SG reaches 847 merges through its stopping procedure rather than an externally imposed merge count.Source: §3.3 · p. 9

3.4 Tokenizer-Only Evaluation

  • At matched 847 merges and 1,017 stored tokens, frequency BPE compresses best, while MDL-SG produces the longest sequences and does not improve raw compression.MDL-SG tests held-out description-length benefit rather than directly optimizing TPC, accounting for vocabulary-complexity and merge-rule costs.Source: §3.4 · p. 9, Table 2 · p. 9

3.5 Language-Model Evaluation

  • All tokenizer-specific language models use the same architecture, have exactly 2,024,448 trainable parameters, and receive exactly 500 optimizer updates.The fixed-update comparison controls the number of optimizer steps and token-level training targets across models.Source: §3.5 · pp. 9–10

3.6 Evaluation Metric

  • Bits per character is the primary evaluation metric because it normalizes negative log-likelihood by the number of original characters across tokenizers with different segmentations.Perplexity is reported only as a secondary, tokenizer-dependent diagnostic.Source: §3.6 · p. 10

4 Results

In fixed-update TinyGPT comparisons, MDL-SG achieved the lowest observed BPC, while frequency BPE achieved stronger test compression. Validation BPC favored MDL-SG throughout the evaluated checkpoints, though the single-seed runs had not established convergence.

4.1 Compute-Matched Language-Model Performance

4.2 Compression and Predictive Utility

  • Frequency BPE achieves the lowest test TPC, yet its test BPC (3.349258) exceeds MDL-SG’s (3.243573).The result distinguishes sequence compression from character-normalized predictive performance at the tested operating point.Source: §4.2 · p. 11

4.3 Learning Curves Under the Fixed-Update Budget

  • At updates 200, 300, and 500, validation BPC ordering remains MDL-SG < SG-BPE < frequency BPE; the single-seed runs do not establish full convergence.At update 500, validation BPC is 3.2612 for MDL-SG, 3.2994 for SG-BPE, and 3.3407 for frequency BPE.Source: §4.3 · p. 11

5 Discussion

The discussion presents data-dependent stopping and lower observed character-normalized loss in the reported fixed-update, single-seed comparison. It emphasizes that replication alone does not ensure token utility, and that stronger compression need not yield lower BPC.

5 Discussion

  • MDL-SG provides data-dependent stopping and lower observed character-normalized loss than frequency BPE and SG-BPE in the reported fixed-update, single-seed comparison.The discussion treats these as distinct properties of the procedure.Source: §5 · p. 12

5.1 Why Statistical Replication Alone Is Not Sufficient

  • Across 120K-, 250K-, and 500K-character samples, stopping followed 209, 433, and 847 merges; at 500K, 1,890 replicated candidates still had no positive MDL gain.At that stopping boundary, 6,564 discovery candidates remained.Source: §5.1 · p. 12

5.2 Why Lower TPC Does Not Imply Lower BPC

  • Frequency BPE uses fewer test tokens, but MDL-SG reduces test BPC by 3.16% versus frequency BPE and 1.39% versus SG-BPE.The paper concludes that raw sequence compression and predictive usefulness can favor different merge choices.Source: §5.2 · pp. 12–13

5.3 Relationship to Significance-Gain BPE

  • At matched 847 merges and 1,017 stored tokens, MDL-SG lowers test BPC from SG-BPE’s 3.289352 to 3.243573 (1.39%), with replication and positive held-out MDL gain required.The comparison uses one common random seed.Source: §5.3 · p. 13

6 Limitations

The evaluation is bounded by its corpus, sample sizes, partitioning, training setup, MDL choices, and greedy search procedure.

6 Limitations

  • All reported experiments use WikiText-103, so broader conclusions about stopping behavior or downstream performance await evaluation on more corpora, domains, and languages.Source: §6 · p. 13
  • 209, 433, and 847 merges across three sample sizes do not establish a general scaling relationship.The samples contain 120K, 250K, and 500K tokenizer-training characters.Source: §6 · p. 13
  • Contiguous 70%/15%/15% partitions may differ in content distribution, motivating comparison with block-disjoint or interleaved splits that avoid artificial boundary pairs.Source: §6 · p. 14
  • The TinyGPT comparison uses one common seed, which aids comparability but does not quantify run-to-run variability or the stability of BPC differences.Source: §6 · p. 14
  • Because all models reach their lowest observed validation BPC at update 500, the comparison is under a fixed budget, not evidence of full convergence.Source: §6 · p. 14
  • The empirical sequence code, BIC-style penalty, and fixed-width merge-rule cost are one MDL formulation; alternatives could change the stopping point.The paper calls for sensitivity analysis of alternative codes, penalties, and dictionary encodings.Source: §6 · p. 14
  • MDL-SG greedily accepts the first ranked candidate passing replication with positive held-out gain, so earlier merges affect later available structures.It does not globally maximize gain across candidates or complete merge sequences.Source: §6 · p. 14

7 Conclusion

MDL-SG separates candidate ranking, replication, and held-out utility to control vocabulary growth without a preset merge count. On WikiText-103, it stops automatically, and the reported TinyGPT comparison shows lower BPC than the two baselines alongside weaker raw compression than frequency BPE.

7 Conclusion

  • MDL-SG assigns distinct roles to Significance-Gain candidate ranking, replication on disjoint data, and held-out MDL evaluation of token utility.Source: §7 · p. 14
  • Without a predetermined vocabulary size or merge count, MDL-SG stops at 209, 433, and 847 merges for 120K-, 250K-, and 500K-character WikiText-103 samples.Source: §7 · p. 14
  • 3.2612/3.2436 validation/test BPC for MDL-SG compared with SG-BPE's 3.2994/3.2894 and frequency BPE's 3.3407/3.3493 under the reported matched TinyGPT setup.Source: §7 · p. 14
  • Frequency BPE produces shorter token sequences, while MDL-SG yields lower observed BPC under the reported training configuration.The results suggest raw sequence compression and lowest downstream predictive loss need not coincide.Source: §7 · p. 14
  • Broader evaluation remains needed across larger corpora, domains, languages, multiple training seeds, and alternative MDL formulations.Source: §7 · p. 14

Code Availability

The implementation and experiment code is publicly available in the project repository.

Code Availability

  • The project repository publicly provides code to implement MDL-SG, reproduce tokenizer experiments, verify stopping boundaries, and run matched TinyGPT evaluations.Source: Code Availability · p. 15

Related papers

Loading 2609.31705v1…