Source-linked AI summary
Adaptive Frequency Threshold Byte Pair Encoding for Mixed Natural Language and Structured Symbolic Corpora
Pietro Di Nicco, Lucio La Cava, Andrea Tagarelli
TL;DR
Whitespace-based tokenization can split meaningful multiword expressions and formal-language structures, while greedy merging may overlook candidate length and underrepresented domains. AdaBPE adapts frequent-pattern thresholds by pattern length and type, with a focus on LaTeX. Across the evaluated datasets, it reports domain-specific compression gains without degrading general-language performance, including up to 7% relative encoding reduction versus SuperBPE on LaTeX-domain datasets.
Problem
Whitespace is not a reliable semantic boundary for multiword expressions or structured LaTeX, and greedy frequency-driven merging does not explicitly account for candidate length or underrepresented formal languages.
Source: §1 · pp. 1–2Method
AdaBPE uses frequent-pattern mining with merge thresholds adapted to candidate length and language type, distinguishing general-language from formal-language patterns in one vocabulary.
Source: §1 · p. 2Results
AdaBPE achieves the lowest AEL on latex-formulas and Image2Struct, with up to 7% relative length reduction versus SuperBPE, while remaining competitive on natural-language benchmarks.
Source: §4.2 · p. 7Takeaways & Limitations
AdaBPE more effectively captures LaTeX commands and general-language multiword expressions as coherent units while maintaining competitive natural-language performance.
Source: §7 · p. 8The authors identify extension beyond LaTeX, task-oriented hyperparameter optimization, and scalability on larger models as future directions.
Source: §7 · p. 8
Abstract
from arXiv · showhide
Modern language models rely on subwording tokenization to define the discrete units of input processing, typically using methods like Byte Pair Encoding (BPE) that treat whitespace as a fixed semantic boundary. This design is inherently limited, as many meaningful concepts---including multiword expressions and the structured environments of formal languages like LaTeX---frequently span across whitespaces. While recent superword tokenization methods attempt to address this by relaxing whitespace constraints, they often rely on greedy frequency-driven merging that fails to account for token length or the specific needs of underrepresented domain-specific languages. In this paper, we introduce Adaptive Frequency Threshold Byte Pair Encoding (AdaBPE), a new tokenization method that leverages an adaptive frequent-pattern mining approach. AdaBPE features a twofold dynamicity: it adapts minimum frequency thresholds based on both the length of a candidate token, to prevent favoring frequent short patterns, and its type, to distinguish between general and formal language patterns, using LaTeX as case in point. This allows the model to efficiently allocate vocabulary capacity to domain-specific notations, such as LaTeX, even when they represent a small fraction of the training data. We evaluate AdaBPE across five datasets spanning LaTeX and natural language, showing consistent gains in encoding efficiency and downstream language-model performance on domain-specific content without compromising general-language performance.
1 Introduction
Whitespace-based tokenization can split meaningful multiword expressions and structured LaTeX units, while existing superword methods still use greedy frequency-driven merges. AdaBPE adapts frequency thresholds by pattern length and type; evaluations across five datasets report stronger domain-specific compression without degrading general-language performance.
Motivations of this study
- Whitespace boundaries can split multiword expressions and formal-language structures such as LaTeX mathematical environments into separate tokens.Conventional tokenizers may process each command, delimiter, and surrounding text separately.Source: §1 · p. 1
Related work
- Recent superword tokenizers relax whitespace constraints, but their vocabulary induction still relies on greedy frequency-driven merging.The introduction cites SuperBPE and BoundlessBPE as approaches that permit merges across whitespace boundaries.Source: §1 · p. 2
Motivations of this study
- Greedy frequency-driven merging may favor frequent short patterns because it does not explicitly account for candidate length or compression benefit, with the issue compounded for underrepresented formal languages.The introduction highlights LaTeX as a structured, whitespace-independent notation that may be relatively scarce in training data.Source: §1 · p. 2
Contributions
- AdaBPE uses adaptive frequent-pattern mining, adjusting merge thresholds by candidate length and language type while building one vocabulary for general and formal-language patterns.Its design emphasizes LaTeX and aims to capture domain-specific notation even when it represents a small share of training data.Source: §1 · p. 2
Evaluation
- Across five LaTeX and general-language datasets, AdaBPE shows consistent compression gains on domain-specific content without degrading general-language performance.The study also evaluates downstream language-model performance on five benchmarks.Source: §1 · p. 2
2 Methodology
AdaBPE extends BPE with iterative frequent-pattern mining and thresholds that vary by candidate length and language type. The method calibrates these thresholds against a target vocabulary budget and uses a lightweight lexical test to identify LaTeX and mathematical patterns.
2.1 Preliminaries
- SuperBPE first learns subwords with whitespace pre-tokenization, then disables it to learn multiword supertokens; AdaBPE starts from a BPE vocabulary and expands it iteratively.AdaBPE’s iterations can combine previously learned patterns into longer sequences; three iterations suffice in practice for patterns containing up to eight BPE tokens.Source: §2.1 · pp. 2–3, §2.2 · p. 3
2.2 Adaptive Frequency Threshold BPE
- AdaBPE compares each candidate pattern’s support with a threshold modulated by both pattern length and whether the pattern is general-language or LaTeX.The method takes a corpus, BPE vocabulary, global threshold, and iteration limit as inputs.Source: §2.2 · p. 3
- The method repeatedly tokenizes the corpus and mines bigrams, adding qualifying patterns to the vocabulary; its running time is bounded linearly in the initial-BPE token count for fixed iterations.As merges reduce the corpus token count, a previously identified candidate’s support does not decrease.Source: §2.2 · p. 3
2.2.1 Setting min_thr.
- With a 160k-token starting vocabulary and a roughly 200k target, AdaBPE sets min_thr to 10^-4 to admit about 10^3 bigrams before language-specific scaling.The target budget implies adding about 4·10^4 tokens overall; the first-iteration frequency distributions are estimated from a 1.5·10^8-bigram sample.Source: §2.2.1 · p. 4, Figure 1 · p. 4
- The method calibrates separate general-language and LaTeX threshold parameters from their frequency distributions, with estimated ranges of 0.2–0.5 and 0.02–0.06, respectively.The vocabulary-budget discussion bounds first-iteration admissions to leave capacity for later iterations.Source: §2.2.1 · p. 4
- The threshold settings are intended to narrow the search to a vocabulary-compatible range, not to impose hard constraints.The authors describe the data-driven settings as capturing general distributional patterns rather than corpus-specific heuristics.Source: §2.2.1 · p. 4
2.3 LATEX and Math Parsing
- A lightweight regular expression flags LaTeX and mathematical candidates through control sequences, structural operators, and mixed alphanumeric patterns, without validating syntax.The lexical test is chosen to be cheap at corpus scale and to flag structural notation markers.Source: §2.3 · p. 5
3 Evaluation Methodology
The evaluation compares BPE, SuperBPE, and AdaBPE under matched training data and vocabulary-size conditions across technical LaTeX and general-language datasets. It assesses compression, supertoken use, token-distribution properties, and downstream performance using controlled small-model comparisons.
3.1 Experimental Setup
- BPE, SuperBPE, and AdaBPE are trained on the same 10 GB OLMo-2 corpus, with AdaBPE configured for three iterations and a final vocabulary of 204,601 tokens.The setup targets a 200k vocabulary for comparison with BPE and SuperBPE.Source: §3.1 · p. 5
3.2 Evaluation Data
- The five evaluation datasets pair LaTeX-focused technical content with general-language benchmarks to test specialization and general-text compression.latex-formulas and Image2Struct provide the technical setting; DROP, SQuAD, and CommonsenseQA provide the general-language setting.Source: §3.2 · p. 5
3.3 Evaluation Goals and Assessment Criteria
- The evaluation combines qualitative segmentation and tokenizer-exclusive-token inspection with quantitative measures of encoding efficiency, supertoken contribution, and token-distribution statistics.The quantitative criteria include Average Encoding Length, Supertoken Share, Mean Savings, Total Savings, N-gram diversity, and Rényi efficiency.Source: §3.3 · pp. 5–6
- Average Encoding Length measures mean tokens per document, and lower values indicate shorter sequences that reduce language-model computation and inference costs.BPB is also used because it normalizes cross-entropy by original-text bytes, enabling comparisons across tokenizers with different vocabularies and token lengths.Source: §3.3 · p. 6
- For downstream validation, OLMo-2 models using AdaBPE and SuperBPE are trained on the same 100 GB data with identical architecture and budget, differing only in tokenizer.The models are evaluated on MATH500, BoolQ, Winogrande, CSQA, and GSM8K using benchmark accuracy.Source: §3.3 · p. 6
4 Results
AdaBPE better preserves LaTeX structures and natural-language multiword expressions, while delivering substantial supertoken savings and lower average encoding length on LaTeX datasets. Its token-distribution results show a trade-off between compression and diversity or balance.
4.1 Qualitative Analysis
- AdaBPE represents LaTeX commands such as \frac and \begin{equation} as single tokens, while preserving multiword expressions from common terms to extended phrases as indivisible units.SuperBPE splits some LaTeX commands and does not capture the cited extended phrases; the exclusive-token analysis reports this natural-language pattern across datasets.Source: §4.1 · pp. 6–7
4.2 Average Encoding Length
- AdaBPE achieves the lowest average encoding length on latex-formulas and Image2Struct, reducing relative length by up to 7% versus SuperBPE, while remaining competitive on natural-language benchmarks.The results indicate comparable tokenization efficiency between AdaBPE and SuperBPE overall.Source: §4.2 · p. 7
4.3 Supertoken contribution
- AdaBPE increases supertoken share by about 105% on latex-formulas and over 200% on DROP and SQuAD, with up to 161% higher mean and over 670% higher total savings than SuperBPE on token-intensive datasets.The comparison covers Supertoken Share, Mean Savings, and Total Savings.Source: Table 3 · p. 7, §4.3 · p. 7
4.4 Token distribution analysis
- AdaBPE has higher lexical diversity than BPE and remains comparable to SuperBPE, but SuperBPE retains a small, consistent edge in distributional balance.AdaBPE trades a small amount of n-gram diversity and token-frequency balance for substantially higher compression of recurrent expressions.Source: §4.4 · pp. 7–8, Table 4 · p. 8
5 Sensitivity Analysis
The sensitivity analysis shows that AdaBPE’s thresholds trade vocabulary size against compression and separately govern natural-language and LaTeX-heavy datasets. The most aggressive settings reduce AEL but require vocabularies unlikely to be practical for real training.
5 Sensitivity Analysis
- As thresholds decrease, the vocabulary grows from 168k tokens to more than 1.6M while AEL drops.The most permissive settings add more supertokens than the most restrictive settings.Source: §5 · p. 8
- θmin_general governs AEL on DROP, SQuAD, and CSQA, while θmin_latex governs AEL on latex-formulas and Image2Struct.This decoupling matches the design intent of separate thresholds for the two language regimes.Source: §5 · p. 8
- The most aggressive settings yield large AEL reductions but require vocabularies an order of magnitude larger than the baseline, unlikely to be practical in real training.The analysis therefore identifies a compression–vocabulary trade-off.Source: §5 · p. 8
6 Downstream validation
AdaBPE’s encoding-efficiency configuration yielded comparable or improved downstream behavior relative to SuperBPE in small-scale model evaluations. Results show higher accuracy on general-language benchmarks and a BPB advantage on mathematical benchmarks, although the tested configuration was not necessarily optimal for downstream performance.
6 Downstream validation
- OLMo2-AdaBPE achieved higher benchmark accuracy than OLMo2-SuperBPE on BoolQ, CSQA, and Winogrande, with a slight BPB penalty on two datasets.The paper reports that general-language performance did not come at the cost of downstream task performance.Source: §6 · p. 8
- On GSM8K and MATH500, both models showed a floor effect in accuracy, while AdaBPE achieved a clear BPB advantage.The authors attribute the accuracy floor to the models’ limited scale.Source: §6 · p. 8
- AdaBPE’s encoding-efficiency configuration produced comparable or improved downstream behavior relative to SuperBPE.The selected configuration was not necessarily optimal for downstream performance.Source: §6 · p. 8, Table 5 · p. 8
7 Conclusions
The conclusion presents AdaBPE as a frequent-pattern-mining extension of BPE that adapts merge thresholds to pattern length and type. Its evaluations report improved encoding of LaTeX and multiword expressions, with future work targeting broader language coverage, tuning, and scale.
7 Conclusions
- AdaBPE extends BPE with frequent-pattern mining and adjusts merge criteria by pattern length and type, distinguishing general-language from formal-language patterns.The method emphasizes LaTeX structures.Source: §7 · p. 8
- Evaluations show more coherent units for LaTeX commands and general-language multiword expressions, up to 7% relative encoding reduction on mathematical LaTeX content, and competitive natural-language performance.Small decoder experiments report improved accuracy and lower bits-per-byte on mathematical benchmarks, with comparable general-language results.Source: §7 · p. 8
- Future work will examine AdaBPE beyond LaTeX, task-oriented hyperparameter optimization, and scalability on larger models.Source: §7 · p. 8
Appendix A: Evaluation Datasets
The appendices describe five evaluation datasets spanning LaTeX and general language and define the criteria used to assess tokenization and model performance. These criteria cover encoding length, supertoken use and savings, token diversity, and bits-per-byte.
Appendix A: Evaluation Datasets
- The evaluation covers five datasets: latex-formulas and Image2Struct for LaTeX, plus DROP, SQuAD, and CommonsenseQA for general language.Image2Struct uses equation and algorithm subsets; latex-formulas contains mathematical expressions written in LaTeX.Source: Appendix A · p. 11
Appendix B: Assessment Criteria
- Average Encoding Length measures the average number of tokens produced per corpus instance.Source: Appendix B · p. 11
- Supertoken criteria measure the token-stream share made up of supertokens, mean base-BPE tokens saved per supertoken, and total savings over the corpus.A supertoken has depth greater than one in its decomposition into base BPE tokens.Source: Appendix B · p. 12
- The appendix defines N-gram diversity by summing distinct-n-gram fractions across orders 1 through N; experiments use N=4, while BPB uses original-text byte count and cross-entropy loss.Source: Appendix B · p. 12
Appendix C: Training Data for the Tokenizers
Tokenizer training uses a shared, unfiltered 10GB corpus subset for reproducibility and algorithmic comparability. Hyperparameters are selected from sampled training-distribution patterns rather than manually tuned for a downstream setting.
Appendix C: Training Data for the Tokenizers
- All tokenizers use the same unfiltered 10GB OLMo2 corpus subset, isolating tokenizer-algorithm differences and supporting reproducibility.The subset is drawn from a roughly 100GB release and already includes document-truncation preprocessing.Source: Appendix C · p. 13
- AdaBPE hyperparameters are selected data-first from sampled training-distribution patterns, rather than manually tuned for a downstream setting.The frequency estimates use file-level random sampling until 1.5 · 10^8 bigrams are extracted.Source: Appendix C · p. 13
Appendix D: Qualitative Comparison
Qualitative examples show AdaBPE merging complete LaTeX syntactic units and longer natural-language expressions more often than SuperBPE. The tokenizers typically agree on short, frequent multiword expressions.
Appendix D: Qualitative Comparison
- AdaBPE tends to merge complete LaTeX syntactic units, while SuperBPE often makes only partial merges.Examples include \begin{equation}, \end{equation}, \sum_{i=, and \rightarrow.Source: Appendix D · p. 14
- For longer expressions, AdaBPE merges phrases such as state of the art and on the side of the road that SuperBPE splits across multiple tokens.AdaBPE also learns expressions including At the end of and late at night, plus the phrasal verb standing in.Source: Appendix D · p. 15
- The tokenizers typically agree on short, high-frequency multiword expressions, with Artificial Intelligence as an exception that AdaBPE merges into one token.SuperBPE keeps Artificial Intelligence as two words.Source: Appendix D · p. 15
Appendix E: Exclusive Tokens
Exclusive-vocabulary examples show AdaBPE’s LaTeX tokens capturing well-formed constructs and its general-language tokens reflecting more compositional structures. The downstream model comparison holds architecture and training budget fixed, varying the tokenizer.
Appendix E: Exclusive Tokens
- On LaTeX-heavy datasets, AdaBPE-exclusive tokens capture well-formed constructs, including environment delimiters, indexed-variable patterns, and command prefixes.SuperBPE often splits these constructs into multiple tokens.Source: Appendix E · p. 15
- On general-language datasets, AdaBPE-exclusive tokens tend toward compositional phrases, while SuperBPE-exclusive tokens often capture dataset-specific entities or lexicalized expressions.The passage characterizes AdaBPE’s pattern as arguably more compositional and syntactic.Source: Appendix E · p. 15
Appendix F: Details on Model Training for Downstream Evaluation
- The downstream AdaBPE and SuperBPE models share architecture and training budget, differing only in the tokenizer used to preprocess training data.This setup is intended to isolate tokenization effects in the reported downstream comparison.Source: Appendix F · p. 15, Table 7 · p. 15
Appendix G: Details on Sensitivity Analysis
The sensitivity analysis varies AdaBPE parameters on evaluation data while holding other settings fixed. Its main-experiment configuration is the baseline, and subsequent rows progressively relax thresholds.
Appendix G: Details on Sensitivity Analysis
- Table 13 reports evaluation AEL as parameters vary individually, with other settings fixed; the main-experiment configuration is the baseline.The remaining rows progressively relax thresholds; the table caption identifies the measure as AEL scores.Source: Appendix G · p. 15, Table 13 · p. 18