PaperlayerView exact revision on arXiv

Source-linked AI summary

Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier

Craig W. Schmidt, Varshini Reddy, Chris Tanner, Yuval Pinter

arXiv:2504.00178v2cs.CLcs.AI

TL;DR

Pre-tokenization leaves common words as full tokens, limiting control over corpus token frequencies. BOUNDLESSBPE merges adjacent full pretokens into superwords. It reports a 9–15% increase in bytes per token over BPE and WordPiece, while the effect of compression on downstream performance is unclear.

  • Problem

    Pre-tokenization leaves common words as single tokens, limiting how much tokenizer training can change the token distribution across a corpus.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    BOUNDLESSBPE extends BPE by merging adjacent pretokens that are each represented by a single token into a superword.

    Source: §3 · p. 3, §3.1 · p. 4

  • Results

    BOUNDLESSBPE (4o) provides a 9–15% increase in overall bytes per token on the 5GB evaluation corpus compared to BPE and WordPiece.

    Source: §4 · p. 7

  • Takeaways & Limitations

    The higher bytes per token means fewer tokens are needed to process or generate a given text, while the effect of compression on downstream performance is unclear.

    Source: §4 · p. 7

    For common words, the pretoken’s role in tokenizer training effectively ends once it becomes a single token, which happens very early.

    Source: §2 · p. 3

Abstract

from arXiv · show

Pre-tokenization, the initial step in many modern tokenization pipelines, segments text into smaller units called pretokens, typically splitting on whitespace and punctuation. While this process encourages having full, individual words as tokens, it introduces a fundamental limitation in most tokenization algorithms such as Byte Pair Encoding (BPE). Specifically, pre-tokenization causes the distribution of tokens in a corpus to heavily skew towards common, full-length words. This skewed distribution limits the benefits of expanding to larger vocabularies, since the additional tokens appear with progressively lower counts. To overcome this barrier, we propose BoundlessBPE, a modified BPE algorithm that relaxes the pretoken boundary constraint. Our approach selectively merges two complete pretokens into a larger unit we term a superword. Superwords are not necessarily semantically cohesive. For example, the pretokens " of" and " the" might be combined to form the superword " of the". This merging strategy results in a substantially more uniform distribution of tokens across a corpus than standard BPE, and compresses text more effectively, with up to a 15% increase in bytes per token.

1 Introduction

Pre-tokenization leaves most common words as full tokens, limiting how much tokenizer training can alter corpus token frequencies. BOUNDLESSBPE introduces superwords and low-frequency token deletion to make token distributions more uniform, reporting improved compression and Rényi efficiency.

1 Introduction

  • Pre-tokenization maps more than 90% of words to single tokens, limiting tokenizer differences and the effect of later-added, lower-frequency vocabulary items.A more uniform token-frequency distribution has been suggested as beneficial for language-model performance, while current pre-tokenization offers limited control over it.Source: §1 · pp. 1–2
  • BOUNDLESSBPE adds superwords by merging adjacent pretokens that are each represented by a single token, and deletes low-frequency intermediate tokens to free vocabulary space.Superwords can combine common words without requiring semantic cohesion; for example, “ of” and “ the” can form “ of the”.Source: §1 · p. 2
  • 9–15% more overall bytes per token and a 3–5% increase in Rényi efficiency are reported for BOUNDLESSBPE versus commonly used baselines.The higher compression means fewer tokens are needed for language-model inference.Source: §1 · p. 2

2 Limitations of pre-tokenizers

Pre-tokenization aligns token boundaries with words, but it leaves most common pretokens as full tokens and limits training’s ability to change the corpus token distribution. The section illustrates this pattern across several tokenizer families and vocabulary sizes.

2 Limitations of pre-tokenizers

  • Pre-tokenization prioritizes preventing tokens from spanning parts of adjacent words, and omitting it entirely produced the poorest downstream performance among 18 evaluated tokenizers.This alignment does not require a one-to-one mapping between tokens and complete words.Source: §2 · p. 2
  • 90–95% of pretokens are represented by one token with BPE and WordPiece, versus 72–73% with UnigramLM across the tested vocabulary sizes.The evaluation uses a 5GB out-of-sample portion of MiniPile; Figure 1 presents the full-token shares by method and vocabulary size.Source: §2 · pp. 2–3, Figure 1 · p. 3
  • Because common pretokens become single tokens early, their role in tokenizer training effectively ends, leaving training little ability to alter the resulting token distribution.For the example “To be or not to be,” baseline tokenizers produce six separate tokens.Source: §2 · p. 3

3 BOUNDLESSBPE

BOUNDLESSBPE extends BPE with supermerges that combine adjacent pretokens when each is represented by a single token. It also uses regular-merge deletions and applies merge, supermerge, and deletion rules during inference.

3.1 Tokenizer training

  • Training selects the higher-frequency regular merge or eligible supermerge, then deletes regular-merge constituents when their IoS exceeds τ = 0.9.Supermerges join adjacent single-token pretokens; eligible pretokens are restricted to word-like forms, excluding digit groups and punctuation.Source: §3.1 · p. 4

3.2 Inference procedure

  • During inference, the tokenizer repeatedly applies the available merge, supermerge, or deletion rule with the earliest training index.The example shows a supermerge becoming eligible only after both adjacent pretokens are single tokens.Source: §3.2 · p. 5

3.3 Efficient training implementation

  • The segmented-pretoken representation is computationally inefficient; the paper describes training-speed techniques separately and releases training and inference code.The efficiency techniques are described in Section C.Source: §3.3 · p. 5

3.4 Training dynamics

  • With supermerges available, selected-merge counts decrease more slowly than baseline counts, resulting in a more uniform token distribution with a higher-frequency tail.Figure 2 compares BOUNDLESSBPE with standard BPE and PickyBPE using two pre-tokenization regular expressions.Source: §3.4 · pp. 5–6, Figure 2 · p. 6
  • 36.6% of merges were supermerges overall, rising to 50.8% in the final 8,192-merge interval.Supermerges become possible only after both candidate pretokens are single tokens, so regular merges dominate early training.Source: §3.4 · p. 6, Figure 3 · p. 6

3.5 Superwords enable improved pre-tokenization

  • BOUNDLESS_PATTERN splits code identifiers into capitalization-based pretokens, which supermerges can recombine into some full names.This permits alignment with identifier sub-components as well as recombination of selected full names.Source: §3.5 · p. 6

4 Token distribution

BOUNDLESSBPE produces a more uniform token-frequency distribution and improves compression on the evaluation corpus. Its results vary with the regex and Rényi efficiency parameter.

4 Token distribution

  • BOUNDLESSBPE has a substantially higher low-frequency tail and lower counts among the 250 most frequent tokens than the baselines across two vocabulary sizes.The authors attribute the tail pattern to higher counts for final merges and deletion of intermediate tokens, and the lower top-token counts to supermerges.Source: §4 · p. 7, Figure 4 · p. 8
  • BOUNDLESSBPE (B) used the highest fraction of its vocabulary across vocabulary sizes, with BOUNDLESSBPE (4o) also performing well.Figure 5 compares the fraction of vocabulary used at least once on the evaluation corpus.Source: §4 · p. 7, Figure 5 · p. 8
  • BOUNDLESSBPE (4o) achieved Rényi efficiency at least 3% above the baselines, while BOUNDLESSBPE (B) had lower efficiency.The authors note sensitivity to the regex and α; they use α = 2.5.Source: §4 · p. 7, Figure 6 · p. 9
  • 9–15% more overall bytes per token than BPE and WordPiece were achieved by BOUNDLESSBPE (4o) on the 5GB evaluation corpus.Higher bytes per token means fewer tokens are needed to process or generate a given text; the effect on downstream performance is unclear.Source: §4 · p. 7, Figure 7 · p. 9

5 Ablation study

The ablation compares pre-tokenization regex choices and PickyBPE deletion variants. Regex choice changed the intrinsic measures more than deletion style did.

5 Ablation study

  • Replacing BOUNDLESS_PATTERN with the GPT4o regex increased bytes per token by 0.15–0.23 and Rényi efficiency by around 0.025.The GPT4O_PATTERN permits a single non-alphanumeric character to combine with word tokens, while BOUNDLESS_PATTERN keeps character classes more separate.Source: §5 · pp. 9–10
  • Different PickyBPE deletion styles had only a very small effect on either intrinsic measure, although deletions may matter for downstream performance.The authors note that low-frequency tokens are harder to learn.Source: §5 · p. 9
  • The ablation compares both PickyBPE deletion variants and no deletions, alongside BOUNDLESS_PATTERN and a GPT4o regex baseline.The table reports the effects of regex pattern and PickyBPE style on intrinsic measures.Source: §5 · p. 9, Table 1 · p. 9

6 Related work

Prior work examines pre-tokenization’s effects on tokenization and downstream performance, and explores multi-word tokens. BoundlessBPE differs from concurrent SuperBPE in how it trains and controls merges.

6 Related work

  • Prior work links pre-tokenization regex choices to compression and downstream performance, and reports stronger downstream effects than vocabulary size or training-corpus variation.Velayuthan & Sarveswaran (2025) discuss pre-tokenization’s role in egalitarian tokenization across languages; Dagan et al. (2024) study regex choices, and Wegmann et al. (2025) compare downstream effects.Source: §6 · p. 10
  • Research on multi-word tokens reports benefits for compression, training cost, model performance, multilingual representations, and machine translation.Kumar & Thawani (2022) found high-PMI multi-word expressions improved machine translation more than high-frequency subword or whole-word tokens.Source: §6 · p. 10
  • BOUNDLESSBPE performs standard merges and supermerges in one pass, unlike SuperBPE’s two-pass approach with a transition-point hyperparameter.The authors state their approach avoids a transition-point search and speeds tokenizer training, while allowing control over which pretokens can merge.Source: §6 · p. 10

7 Conclusion

The conclusion presents BOUNDLESSBPE and BOUNDLESS_PATTERN as contributions for improving token-frequency uniformity and tokenization, while downstream benefits remain a hypothesis.

7 Conclusion

  • BOUNDLESSBPE permits adjacent full pretokens to combine into superwords, yielding improved compression and a more uniform token-frequency distribution.The conclusion identifies BOUNDLESSBPE as a modified BPE training process.Source: §7 · p. 10
  • BOUNDLESS_PATTERN is designed to work with superwords and improves tokenization, particularly for code and named entities, compared with standard regexes such as GPT-2’s.Source: §7 · p. 10
  • The authors hypothesize that BOUNDLESSBPE’s intrinsic performance improvements will positively affect language-model downstream performance.This is presented as a hypothesis based on prior work.Source: §7 · p. 10

A Pre-tokenizer regular expression

The section describes BOUNDLESSBPE’s pre-tokenizer regular expression and its choices for Unicode classes, combining marks, code, whitespace, numbers, and contractions. Its patterns balance token alignment and recombination while addressing specific handling issues.

A Pre-tokenizer regular expression

  • A valid pre-tokenization regex must match all text in a Unicode string; these patterns use Unicode categories that require Python’s `regex` library rather than `re`.The section compares existing regexes and presents BOUNDLESS_PATTERN; the regex branches are joined with the | operator.Source: A Pre-tokenizer regular expression · p. 14

A.1 Separation of Unicode Classes

  • BOUNDLESS_PATTERN keeps Unicode classes well separated, despite mixed prior evidence about whether greater separation helps downstream tasks.The authors hope separated classes yield more word-based tokens that can be combined by supermerges.Source: §A.1 · pp. 15–16

A.2 Combining Marks and Unicode Normalization

  • Unlike letter-only patterns, BOUNDLESS_PATTERN keeps combining marks with their base characters, avoiding split pretokens without requiring non-reversible normalization.The approach also matches combining marks that occur without a base character.Source: §A.2 · p. 16

A.3 Code Related Pretokens

  • Capitalization-based patterns split code names such as XMLHttpRequest into aligned components that supermerges can recombine into full names.With regular BPE, those pretokens would remain separate final tokens.Source: §A.3 · p. 17

A.4 Whitespace

  • BOUNDLESS_PATTERN keeps runs of whitespace together and separates multiple lines at line endings, a choice motivated by concerns about code whitespace.The authors say this whitespace design would benefit from further experimentation.Source: §A.4 · p. 17

A.5 Numbers

  • BOUNDLESS_PATTERN’s number pattern groups digits in sets of up to three, producing pretokens ['1', '234', '567'] for '1234567'.The passage notes that this can enforce right-to-left tokenization without inserting commas into the input.Source: §A.5 · p. 17

A.6 Contractions

  • BOUNDLESS_PATTERN uses a language-independent pattern to keep words containing straight or curly internal apostrophes together as one pretoken.Earlier patterns used English-specific contraction endings.Source: §A.6 · p. 17

B Token distribution at additional vocabulary sizes

At vocabulary sizes 65,536 and 98,304, BOUNDLESSBPE retains the distribution trends seen in Figure 4, with higher counts among low-frequency tokens and lower frequencies among the most common tokens.

B Token distribution at additional vocabulary sizes

  • At vocabulary sizes 65,536 and 98,304, BOUNDLESSBPE has higher counts at the low-frequency end and lower frequencies for the most common tokens than the baselines.The passage identifies both trends as desirable for a more uniform distribution.Source: B Token distribution at additional… · p. 18
  • The distribution trends at both vocabulary sizes are largely the same as those in Figure 4.The passage does not provide additional numerical comparisons for Figure 8.Source: B Token distribution at additional… · p. 18
  • Figure 8 plots log10(count + 1) for tokens sorted from most to least frequent on the evaluation corpus.Its right column zooms in on the 250 most common tokens; +1 allows zero counts to be plotted.Source: Figure 8 · p. 18

C Efficient implementation

The implementation uses separate data representations for regular merges and supermerges, linked by the unlocking of pretokens. Aggregation speeds regular-merge training, while supermerges remain costly to train.

C Efficient implementation

  • Aggregating pretoken counts for regular merges yields more than a 10x speedup, while supermerge training uses a separate, unaggregated copy of the training data.The separate superword data begins with documents divided into pretokens.Source: C Efficient implementation · p. 19
  • A pretoken is unlocked when regular BPE reduces it to a single token, allowing the superword representation to consider merges between adjacent unlocked words.The implementation updates superword counts when a new pretoken is unlocked.Source: C Efficient implementation · p. 19
  • Training on the 1GB dataset took 4.7 CPU days with supermerges, compared with 59 seconds for Huggingface BPE on the same data, vocabulary size, and machine.The passage attributes the cost to the lack of aggregation for supermerges.Source: C Efficient implementation · p. 19

D Metrics for token distribution uniformity

The section uses Rényi efficiency to measure token-distribution uniformity and reports how comparisons with baselines vary with the metric’s α parameter.

D Metrics for token distribution uniformity

E Ablation results at additional vocabulary sizes

The section reports ablations at additional vocabulary sizes and relates tokenization and vocabulary-refinement choices to prior work.

E Ablation results at additional vocabulary sizes

F Additional related work

  • BPE merges frequent adjacent-token pairs, while WordPiece uses PMI and UnigramLM prunes tokens according to their contribution to sequence likelihood.Source: F Additional related work · p. 20
  • Prior work removes scaffold tokens during inference or training; the authors favor integrating deletion into BPE training over purely postprocessing approaches.The cited approaches include splitting scaffold tokens after training, integrating deletion into training, and postprocessing merge rules.Source: F Additional related work · p. 20

Related papers

Loading 2504.00178v2…