Who Pays the Token Tax in Speech? Group-Robust Vocabularies for Discrete Acoustic Units

Many speech language models do not read audio directly. They first turn each 20 ms frame into one symbol from a small fixed alphabet: a codebook of a few hundred "discrete acoustic units" produced by clustering self-supervised features. Then, as in text, they merge frequent unit sequences into a larger vocabulary using byte-pair encoding (BPE), a greedy procedure that repeatedly fuses the most common adjacent pair. Both steps are learned from frequency counts, and the speech corpora they are learned from are heavily male-skewed. Our hypothesis is that male speech ends up with compact, well-fitted tokens, while female and gender-diverse speakers get longer, more fragmented token sequences. If so, the tokenizer charges a "token tax" on speakers already underrepresented in the data, and that tax may contribute to the gender error gaps measured in downstream recognition.

This note proposes to measure that tax and then remove it in a principled way. Vocabulary selection over a fixed unit alphabet is a known hard combinatorial problem. We recast it as a max-min coverage problem, in which the vocabulary is chosen to maximize compression for the worst-served speaker group. Using a truncated-coverage surrogate, the greedy solution carries a provable guarantee. The question is not only whether this narrows gaps, but whether it does better than the obvious fix of rebalancing the tokenizer's training data. We expect the answer to be no in the two-group case and yes when there are many small intersectional groups. The design is built to tell those cases apart.

Core Claim

Over a fixed acoustic alphabet, frequency-driven tokenizers produce measurable per-group compression disparities between male, female, and "Other" speakers. These disparities split into two parts: one from the codebook (the alphabet itself) and one from the merge vocabulary. The vocabulary part can be reduced by a group-robust partition-cover tokenizer with an approximation guarantee. This tokenizer should beat simple corpus reweighting precisely in the regime that matters most: many intersecting groups (gender × dialect), some with very little data, where balancing every group would require discarding most of the data or duplicating tiny groups.

Where this sits

Three strands of prior work set the theoretical stakes. Tokenisation is NP-Complete shows that optimal vocabulary selection for compression is NP-complete. Tokenisation over Bounded Alphabets is Hard extends the result to binary and unary alphabets and proves APX-hardness, which means no arbitrarily good polynomial-time approximation exists. Together these establish that a small acoustic codebook offers no escape from hardness. A Partition Cover Approach to Tokenization recasts tokenization as covering the corpus with substrings and relaxes it to weighted maximum coverage. Its greedy method, GreedTok, is solvable with standard guarantees and achieves ~3% fewer tokens per word than BPE, with gains on 11 downstream tasks at 1B parameters. That paper explicitly suggests adding fairness constraints, but none of these works includes any demographic objective. We reuse GreedTok's coverage relaxation as our method substrate and inherit the hardness results as the reason a guarantee is worth having.

The fairness strand motivates the problem. Parity-Aware Byte-Pair Encoding is the closest existing work. At each BPE merge it picks the most frequent pair from whichever language currently compresses worst, cutting the cross-language Gini coefficient of compression from 0.064 to 0.011 on text. It is a heuristic for parallel text across languages and offers no guarantee. We move the same intuition to demographic groups within one language and to acoustic units, and replace the merge heuristic with a coverage objective that has a provable guarantee. Tokenization Matters shows that BPE fragments neopronouns and fixes this by hand-inserting them as atomic tokens. That fix needs a known list of target strings, which does not exist for acoustic units.

Two speech-tokenization papers supply the pipeline but ignore demographics. Exploring the Benefits of Tokenization of Discrete Acoustic Units shows that BPE over units is valuable, dropping grapheme-to-unit CER from 87.96% to 3.19%. Exploring the Effect of Segmentation and Vocabulary Size on Speech Tokenization maps how segment width and vocabulary size trade off. Both report only aggregate metrics.

On the bias side, Twists, Humps, and Pebbles constrains our story in an important way. It finds that pitch and intensity do not predict gender gaps in Whisper and SeamlessM4T, whereas internal gender extractability does (ρ = −0.65). The same paper reports "Other" penalties of up to 52%. This rules out the naive mechanism "high-pitched voices map to sparse units." Any tokenization effect we find must be tested against representation-level explanations rather than assumed to be acoustic.

Research Program

Measurement. We extract HuBERT-style units with codebooks of 100, 500, and 1000 symbols. We then train standard BPE and GreedTok vocabularies of several sizes on naturally skewed corpora, and on Common Voice subsets subsampled to controlled male:female ratios from 50:50 to 90:10. For each speaker group we report units and tokens per second of audio, the worst-to-best group ratio, and the Gini coefficient. We also measure fragmentation: how often a single phone's audio span is split across multiple tokens, which requires forced alignments.

Decomposition. A 2×2 factorial design crosses a codebook trained on skewed versus balanced audio with a merge vocabulary trained on skewed versus balanced unit streams. This separates the alphabet's share of the disparity from the vocabulary's share. If the alphabet dominates, the max-min tokenizer below is aimed at the wrong layer, and we will report that.

Method. Let $S$ be the selected vocabulary with $|S| \le K$. For each speaker group $g = 1, \dots, G$, let $f_g(S)$ be the normalized coverage gain under GreedTok's relaxation, meaning the fraction of group $g$'s unit positions saved. This function is monotone and submodular, so adding a token helps less as the vocabulary grows. We want

$$\max_{|S| \le K} \; \min_{g} f_g(S).$$

The minimum of submodular functions is not submodular, so GreedTok's guarantee does not carry over directly. We instead greedily maximize the truncated surrogate

$$F_c(S) = \frac{1}{G} \sum_{g} \min\big(f_g(S),\, c\big),$$

which is again monotone submodular, and binary-search the target level $c$. The standard saturation argument for truncated coverage then gives a bicriteria guarantee: the worst group reaches level $c$ while the vocabulary exceeds $K$ only by a logarithmic factor. The theory deliverables are this guarantee stated precisely for the tokenization relaxation, together with the observation that the fairness-constrained decision problem inherits NP-hardness from the binary-alphabet result (set $G = 1$). Because the relaxation is not the true encoding, we always evaluate actual encoded lengths rather than the relaxed objective.

Downstream. For every tokenizer we train an identical small unit-to-text recognizer and a unit language model under fixed compute. We then measure per-group WER, worst-group WER, aggregate WER, and per-group gender extractability from hidden states, following the probe of Twists, Humps, and Pebbles.

Baselines

The do-nothing reference is standard frequency BPE over units, trained on the corpus's natural skew, as in Exploring the Benefits of Tokenization of Discrete Acoustic Units. A second naive reference applies no merges at all and uses the raw unit sequence, which has zero vocabulary-level disparity by construction but long sequences.

The strongest existing competitor is Parity-Aware BPE, including its hybrid and moving-window variants, with speaker groups substituted for languages. It is the only published method that explicitly targets worst-group compression. Its reported result is a cross-lingual compression Gini of 0.011 versus 0.064 for classical BPE on text. For gender groups over acoustic units there is no reported result found on Lacuna, so we will establish that number ourselves.

Unweighted GreedTok is a second strong baseline. It isolates whether gains come from switching from merges to coverage rather than from the fairness objective. Lim et al. report ~3% fewer tokens per word than BPE on text; no reported result found on Lacuna for GreedTok on acoustic units.

The ablation that isolates our key ingredient is group-reweighted GreedTok: the same coverage objective, but each group's corpus is reweighted to equal mass and the average is maximized rather than the minimum.

All methods share the same unit streams, vocabulary budgets, group labels, and tokenizer training data, plus an equal hyperparameter search budget per method. This includes Parity-BPE's window size and our target level $c$. Downstream models use identical architectures and token-matched training.

Beating a baseline has two parts. First, our method must lower worst-group token rate and worst-group WER beyond seed variance, using a mixed-effects model with speaker as a random effect in the style of FaiST. Second, aggregate compression must stay within 2% of the best baseline and aggregate WER must not get worse.

Why not just…?

Why not just rebalance the tokenizer's training corpus by gender? For two groups with plenty of data this is the real threat, and it may match us. Reweighting and max-min coincide when groups have similar compressibility. The reweighted-GreedTok ablation is exactly this alternative, run with the same budget. Our claim rests on the intersectional regime: gender × dialect cells on the 13-hour podcast set from Modeling Gender and Dialect Bias in ASR, and the tiny "Other" group in Common Voice. There, balancing forces heavy duplication of a few speakers. If reweighting still matches max-min in that regime, we will report that tokenizer-level fairness reduces to data weighting, which is itself a useful negative result.

Why not just port Parity-Aware BPE to gender groups? It is the strongest baseline above and may perform well. It optimizes merges one at a time, though, so early majority-driven merges cannot be undone, and it has no guarantee. Comparing worst-group token rates at equal $K$, especially as $G$ grows from 2 to roughly 12 intersectional cells, will show whether the coverage formulation matters.

Why not just fix the acoustic model, by oversampling female speech or fine-tuning on balanced data? The Balancing Act shows that SMOTE equalizes male and female WER while naive duplication sometimes worsens gaps. This addresses the model, not the token sequence, and does not reduce the extra sequence length that underserved groups pay at inference. We include SMOTE-style balanced fine-tuning on top of standard BPE as a downstream comparator. If it erases WER gaps while token-rate gaps persist, the remaining value of our method is efficiency parity, not accuracy, and we will say so.

Why not drop discrete merges and pool continuous frames, as AdaTS does? Similarity-based pooling may also compress majority speech more. AdaTS never reports per-group rates, so we will measure its per-group compression as an additional reference.

Decisive Checks

Three results decide the project. First, standard unit BPE must show a group compression gap on Common Voice and CCD V2 that grows with training-set skew. If no gap appears at a 90:10 skew, the premise fails and we stop. Second, the factorial decomposition must attribute a substantial share of the gap to the merge vocabulary rather than the codebook. Third, across tokenizers and seeds, per-group token rate must predict per-group WER after controlling for gender extractability. If extractability alone explains the WER gap, the tax is real but cosmetic for accuracy, and the method's value narrows to inference-cost parity. That outcome would be consistent with the representation-level account in Twists, Humps, and Pebbles, and it is a clean, publishable answer either way.