Adaptive Frequency Threshold Byte Pair Encoding for Mixed Natural Language and Structured Symbolic Corpora

Pietro Di Nicco; Lucio La Cava; Andrea Tagarelli

cs.CLOct 23, 2026

Adaptive Frequency Threshold Byte Pair Encoding for Mixed Natural Language and Structured Symbolic Corpora

Authors: Pietro Di Nicco, Lucio La Cava, Andrea Tagarelli

Organizations: DIMES Department, University of Calabria, Italy

Abstract

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.

Figures & tables

Figure 1: Bigram frequency distribution estimated from a random sample of size $1.5\cdot 10^{8}$ .

Figure 2: Frequency distribution of natural-language bigrams (right) and of L a T e X bigrams (left).

Dataset	BPE	SuperBPE	AdaBPE
CSQA	16.63	12.43 (25.3%)	12.24 (26.4%)
latex-formulas	68.58	59.49 (13.3%)	54.88 (20.0%)
SQuAD	163.63	125.11 (23.5%)	126.03 (23.0%)
DROP	264.26	206.78 (21.7%)	210.43 (20.4%)
Image2Struct	247.32	212.43 (14.1%)	207.96 (15.9%)
avg decr. w.r.t. BPE	–	19.58 %	21.14 %

Table 1: Average Encoding Length (AEL) comparison between BPE, SuperBPE, and AdaBPE. Numbers in parentheses indicate the relative reduction with respect to the BPE baseline. Best results are bolded.

Dataset	BPE	SuperBPE	AdaBPE
CSQA	1.81	1.68	1.77
latex-formulas	34.22	25.52	25.49
SQuAD	74.41	68.54	68.77
DROP	10.88	8.27	8.32
Image2Struct	0.63	0.44	0.42

Table 2: Average tokenization time (in seconds).

	Tokenizer	Super Share	Mean Savings	Total Savings
latex	SuperBPE	0.133	1.169	0.156
	AdaBPE	0.272	2.094	0.569
	$\Delta$ (%)	+104.5%	+79.1%	+264.7%
I2S	SuperBPE	0.147	1.134	0.167
	AdaBPE	0.366	2.049	0.750
	$\Delta$ (%)	+149.0%	+80.7%	+349.1%

Table 3: Comparison of AdaBPE and SuperBPE in terms of Supertoken Share, Mean Savings, and Total Savings. Best results per dataset are in bold.

Dataset	BPE			SuperBPE			AdaBPE
	NDiv	RE 1	RE 2	NDiv	RE 1	RE 2	NDiv	RE 1	RE 2
CSQA	2.05	0.70	0.50	2.72	0.80	0.51	2.67	0.80	0.50
latex	0.48	0.59	0.48	0.72	0.63	0.52	0.74	0.65	0.52
SQuAD	0.49	0.66	0.41	0.67	0.80	0.57	0.66	0.80	0.56
DROP	0.17	0.67	0.45	0.23	0.78	0.59	0.22	0.77	0.57
I2S	0.98	0.67	0.51	1.26	0.72	0.57	1.23	0.72	0.53

Table 4: Comparison over N-gram diversity (NDiv) and Rényi efficiency (RE α , with

\alpha

= {1,2}).

Dataset	OLMo2-AdaBPE		OLMo2-SuperBPE
Dataset	Acc.	BPB	Acc.	BPB
GSM8K	na	1.51	na	1.56
MATH500	na	1.21	na	1.27
BoolQ	0.6171	1.84	0.6150	1.44
CSQA	0.1966	8.27	0.1949	7.30
Winogrande	0.5043	0.56	0.4972	0.58

Table 5: Downstream task results.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Statistic	DROP	Image2Struct	CSQA	latex-forms.	SQuAD
# Instances	9,535	600	9,741	100,000 (∗)	87,599
Characters per instance
Min	290	39	20	29	179
Max	5,578	3,869	405	440	26,203
Avg	1,111.27	632.50	78.84	145.05	814.94
Std	598.84	634.03	30.43	74.97	320.16

Appendix

Table 6: Summary statistics of the evaluation datasets. (∗) The full dataset contains approximately one million instances; for evaluation we selected the first

100{,}000

. (∗∗) Words are regarded as sequences of characters separated by whitespace. (∗∗∗) BPE tokens containing at least one digit.

	OLMo-AdaBPE	OLMo-SuperBPE
Architecture	OLMo-2	OLMo-2
Hidden size	2048	2048
Position embedding	RoPE	RoPE
Attention heads	16	16
Activation function	SiLU	SiLU
Layers	16	16

Appendix

Table 7: Main hyperparameters used during model training

AdaBPE only			SuperBPE only
Rank	Token	Frequency	Rank	Token	Frequency
1	end{align*}	98,652	1	left(	15,092
2	begin{align*}	58,772	2	(t	12,354
3	\begin{align	40,418	3	\right	11,718
4	_{n	10,119	4	,Ġ\	9,964
5	_{k	6,384	5	left(\	9,765

Appendix

Table 8: Top exclusive tokens by frequency on latex-formulas. Left: tokens used by AdaBPE but absent from SuperBPE. Right: tokens used by SuperBPE but absent from AdaBPE.

AdaBPE only			SuperBPE only
Rank	Token	Frequency	Rank	Token	Frequency
1	ĠdoĠwhat	201	1	WhatĠhappens	80
2	Ġdo?	178	2	ĠwasĠhe	67
3	,ĠwhatĠwas	81	3	TheĠman	65
4	Ġdidn	72	4	WhatĠcan	54
5	ĠwhatĠto	68	5	Ġficus	53

Appendix

Table 9: Top exclusive tokens by frequency on CSQA.

AdaBPE only			SuperBPE only
Rank	Token	Frequency	Rank	Token	Frequency
1	:Ġ	1,735	1	citationĠneeded	3,488
2	.ĠWhatĠwasĠthe	1,664	2	?Ġ	2,407
3	ĠtheĠlateĠ	1,239	3	ĠÂ°C	1,655
4	:Ġthe	1,121	4	ĠuntilĠ	1,564
5	.ĠWhatĠtypeĠof	1,061	5	Ġcity’s	1,214

Appendix

Table 10: Top exclusive tokens by frequency on SQuAD.

AdaBPE only			SuperBPE only
Rank	Token	Frequency	Rank	Token	Frequency
1	S.	3,874	1	),Ġ	5,274
2	ĠtheĠfourth	1,637	2	UnitedĠStates	4,956
3	ĠtheĠlead	1,260	3	U.S.	3,864
4	ĠunderĠtheĠageĠofĠ	1,086	4	ĠonĠaĠ	1,890
5	ĠThereĠwere	640	5	ĠfromĠtwo	1,238

Appendix

Table 11: Top exclusive tokens by frequency on DROP.

AdaBPE only			SuperBPE only
Rank	Token	Frequency	Rank	Token	Frequency
1	_{t	263	1	}Ċ	1,483
2	Ġ\textbf{	219	2	$Ċ	498
3	\end{equation*}	205	3	*}Ċ	409
4	hat{\	202	4	i,	294
5	\begin{equation*}	198	5	]Ċ	288

Appendix

Table 12: Top exclusive tokens by frequency on Image2Struct.

Parameters	$\|V\|$	DROP	SQuAD	CSQA	LS	I2S
baseline	204,601	210.43	126.03	12.24	54.88	207.96
$\theta_{latex}^{min}=0.05,$	181,752	222.60	136.02	13.44	52.93	202.47
$\theta_{general}^{min}\!=\!0.5$		(-5.78%)	(-7.92%)	(-9.80%)	(+3.55%)	(+2.64%)
$\theta_{latex}^{min}=0.08$ ,	168,292	222.60	136.02	13.44	55.75	211.63
$\theta_{general}^{min}\!=\!0.5$		(-5.78%)	(-7.92%)	(-9.80%)	(-1.58%)	(-1.76%)
$\theta_{latex}^{min}=0.05,$	208,043	210.43	126.03	12.24	52.57	200.41

Appendix

Table 13: Sensitivity analysis of AdaBPE: AEL scores for different settings of

\theta_{general}^{min}

and

\theta_{latex}^{min}

. Values in parentheses indicate the percentage variation relative to the baseline.

Subword Tokenization

Subword tokenization divides text into reusable units smaller than words to support efficient and flexible language modeling.

See all 83 papers

Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization
Aug 6, 2025Negar Foroutan, Clara Meister, Debjit Paul +4Low-Resource Language Processing Subword Tokenization
EPFL · University of Zurich
MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization
Sep 20, 2026Azam NouriSubword Tokenization Byte-Pair Encoding
Department of Science, Technology & Mathematics, Lincoln University, MO, USA
Rethinking BPE: Merge Selection as Model Selection
Oct 19, 2026Vijini Liyanage, François YvonTokenization in Language Models Tokenization
Sorbonne-Université, CNRS, ISIR, Paris

Aug 6, 2025J/K move · Enter open · S save

Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization

Negar Foroutan, Clara Meister, Debjit Paul, Joel Niklaus+3

EPFL · University of Zurich

Low-Resource Language Processing Subword Tokenization Byte-Pair Encoding Tokenization

Open paper AskPDF arXiv

Tokenization is the first -- and often least scrutinized -- step of most NLP pipelines. Standard algorithms for learning tokenizers rely on frequency-based objectives, which favor languages dominant in the training data and consequently leave lower-resource languages with tokenizations that are disproportionately longer, morphologically implausible, or even riddled with

<UNK>

placeholders. This phenomenon ultimately amplifies computational and financial inequalities between users from different language backgrounds. To remedy this, we introduce Parity-aware Byte Pair Encoding (BPE), a variant of the widely-used BPE algorithm. At every merge step, Parity-aware BPE applies a fair-max rule that maximizes the compression gain of the currently worst-compressed language, trading a small amount of global compression for cross-lingual parity. We find empirically that Parity-aware BPE reduces tokenization inequality -- operationalized by the Gini coefficient of per-language token costs -- by up to 89% relative to Classical BPE. This comes with negligible impact on global compression rate and no evidence of systematic degradation in downstream LM performance.

Abstract

Subword Tokenization

Explore similar work

Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization

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

Rethinking BPE: Merge Selection as Model Selection