CPU-prestaties van Unigram-tokenizer verbeteren

We hebben onze Unigram-tokenizer vanaf de basis opnieuw geïmplementeerd als een gericht prestatieproject. Bij productie-invoerlengtes vermindert de nieuwe encoder de p50-latentie met ongeveer 5× ten opzichte van de Hugging Face tokenizers-crate, ~2× ten opzichte van SentencePiece (C++), en ~1,5× ten opzichte van de tokenizer van IREE (C), met nul steady-state heap-allocaties. In productie verlaagde dit het CPU-gebruik in onze inferentiestack met 5-6× en bracht het de latentie van de reranker met dubbele cijfers in milliseconden omlaag.

LLM-inferentiekosten worden meestal beschreven als GPU-werk: KV-caches, attention-kernels, expert-routing. Maar een betekenisvol deel van het productieverkeer draait op veel kleinere modellen, twee tot drie ordes van grootte kleiner dan frontier-transformers. Embedding-modellen, classifiers en rerankers draaien nog steeds op GPU's, maar de forward pass is kort genoeg dat alles eromheen begint mee te tellen.

Het duidelijkste geval is een reranker die honderden kandidaat-documenten per verzoek scoort. Bij een klein model is de GPU-berekening meestal klaar in enkele milliseconden, maar elke invoer moet eerst door CPU-side tokenisatie gaan, waarbij tekst wordt omgezet in vocabulaire-ID's. Wanneer de batch groot is, kan dat een aanzienlijk deel van de totale latentie van het verzoek uitmaken.

Dit werk richt zich op XLM-RoBERTa, een 250K-token Unigram-vocabulaire getraind met SentencePiece. Fine-tuned RoBERTa-familie-encoders zijn een gebruikelijke keuze voor ranking-, retrieval- en gelijkenistaken. We rapporteren de single-threaded latentie per encodering; in productie parallelliseren we over cores met rayon.

In deze post behandelen we de tokenizers-crate van Hugging Face als de referentie waartegen we benchmarken, aangezien dit de standaard Rust-tokenizer is waar de meeste teams voor kiezen. SentencePiece (C++) en IREE (C) zijn ter vergelijking opgenomen als de twee andere belangrijke productie-implementaties.

Unigram-tokenisatie, geïntroduceerd door Kudo in 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) en uitgebracht in SentencePiece, kadert segmentatie als een probleem van het meest waarschijnlijke pad: elk vocabulaire-token heeft een geleerde log-waarschijnlijkheid, en de encoder kiest de segmentatie waarvan de token-scores optellen tot de hoogste waarde. Het probleem wordt opgelost met het Viterbi-algoritme (1967), met byte-posities als graaflagen en vocabulaire-tokens als randen die een aaneengesloten byte-bereik overspannen. De recursie is een eendimensionale DP over byte-posities:

python

best = [-inf] * (n + 1)
best[0] = 0
back = [None] * (n + 1)

for i in 0..n:
    if best[i] == -inf:
        continue
    if byte i is a UTF-8 continuation byte:
        continue

    walk the vocabulary trie from byte position i:
        for each matching token t ending at position j:
            cand = best[i] + score(t)
            if cand > best[j]:
                best[j] = cand
                back[j] = (i, token_id(t))

    if no token matched, fall back to <unk>

backtrack from position n using back[] to recover token IDs

De buitenste lus is lineair in de invoerlengte, begrensd op elke positie door het langste vocabulaire-token (48 UTF-8 bytes voor XLM-RoBERTa). De innerlijke trie-walk is het hete pad: op een 16k-token invoer voert het honderdduizenden overgangen uit en voltooit het tientallen miljoenen instructies per encodering.

Tokenizers v0.22 van Hugging Face implementeert de recursie direct, met een hash-map voor de omgekeerde opzoeking en hash-map-children bij elk trie-knooppunt:

rust

vocab:        Vec<(String, f64)>           // indexed by token ID
token_to_ids: AHashMap<String, u32>        // reverse lookup
trie:         Trie<u8>                     // byte-level prefix trie

struct Node<Label> {
    is_leaf: bool,
    children: AHashMap<Label, Node<Label>>, // heap-allocated map per node
}

En de innerlijke lus (vereenvoudigd) – elke prefix-zoekmatch wijst een nieuwe string toe en onderzoekt vervolgens de hash-map:

rust

fn encode_optimized(&self, sentence: &str) -> Result<Vec<String>> {
    // alloc
    let mut best = vec![BestPathNode::default(); sentence.len() + 1];

    let mut starts_at = 0;
    while starts_at < sentence.len() {
        for tok_bytes in self.trie.common_prefix_search(sentence.bytes().skip(starts_at)) {
            // alloc per match
            let token: String = String::from_utf8(tok_bytes).unwrap();
            // hash lookup
            let id = self.token_to_ids.get(&token).unwrap();
            let score = self.vocab[*id as usize].1;
            // DP update at best[starts_at + tok_bytes.len()]
            // ...
        }
        starts_at += mblen;
    }
    // backtrace into Vec<String>, one allocation per output token
}

De code is leesbare Rust, maar er gebeurt veel werk dat onzichtbaar is op bronniveau. De volgende sectie analyseert waar de tijd naartoe gaat.

Voordat Viterbi draait, gaat de invoer door Unicode-normalisatie (NFKC) en woordgrensmarkering. Profiling plaatst preprocessing op minder dan 5% van de totale encoderingstijd in onze scenario's, dus we concentreren ons op de Viterbi forward pass voor de rest van de post.

Er zijn twee manieren om CPU-code te versnellen: minder instructies uitvoeren of een hogere IPC behalen. Cachegrind meet de eerste, perf stat meet de tweede. Elke optimalisatie in deze post valt in de ene of de andere categorie.

CPU's haperen op vier dingen: cache-missers (L1d ~4 cycli, een L3-miss-to-DRAM is honderden), afhankelijke-load-ketens die de out-of-order engine niet kan parallelliseren, branch-mispredicts (~15-20 cycli leeggemaakt per verkeerde gok), en allocator-aanroepen. De referentie-unigram-engine-implementatie raakt ze alle vier:

Flessenhals	Mechanisme	Gemeten impact
Allocatie per match	String::from_utf8 op de gematchte bytes plus een AHashMap-opzoeking per trie-match; het token-ID zit al in het blad, maar de referentie slaat het daar niet op	7.295 allocaties bij 512 tokens, 14.542 bij 1k, 299.171 bij 16k
Pointer chase per byte	Een AHashMap bij elk trie-knooppunt, waarbij de volgende byte wordt gehasht en twee pointers per stap worden gederefereerd; de Node-struct bundelt ook koude velden zoals is_leaf, waardoor ze bij elk bezoek in de cache worden getrokken	L1d-miss-percentage blijft laag (~2,5% bij 1k) omdat allocator-hot-pages in L1 leven; de kosten verschijnen als latentie van afhankelijke-loads
L2-thrashing bij lange invoer	DP-tabel, prefix-scratch en de lijst met uitvoertokens worden bij elke aanroep opnieuw toegewezen	L2-miss-percentage klimt van 12% bij 128 tokens naar 50% bij 16k omdat de cumulatieve allocatie-voetafdruk de 2 MB L2 per core overschrijdt

Referentie-tokenizerknelpunten, mechanismen en gemeten impact.

De dominante kosten zijn de allocatie per match. Bij 1k tokens voltooit de referentie-implementatie ongeveer 7M instructies per encodering bij een IPC van 2,8, waarvan de meeste in allocator-aanroepen en string-conversies. L2-missers zijn alleen van belang voorbij ~1k tokens, zodra de cumulatieve allocatie-voetafdruk de cache per core overstroomt.

Referentie-tokenizer p50- en p99-latentie per invoergrootte.

Referentie-tokenizer L2-cache-misspercentage per invoergrootte.

Aantal bytes toegewezen per encode door de referentie-tokenizer over verschillende invoergroottes.

Allocatie per token is constant: ongeveer 2 KB en ~18 allocaties per token, ongeacht de invoergrootte. De niet-lineariteit van de latentie komt van L2: cumulatieve bytes overschrijden 2 MB rond 1k tokens, het miss-percentage klimt van 8% naar ~50%, en de p99-curve buigt mee.

We vergelijken drie productie-tokenizers, die allemaal hetzelfde Unigram-algoritme draaien tegen hetzelfde XLM-RoBERTa-model:

Engine	Taal	Trie
Hugging Face	Rust	HashMap-children prefix trie
SentencePiece	C++	Darts double-array trie
IREE tokenizer	C	Darts double-array trie

Tokenizer-implementaties, talen en trie-representaties gebruikt in de vergelijking.

We koppelen SentencePiece en IREE via directe C/C++ FFI in plaats van hun Rust-wrappers; de wrappers voegen allocaties en string-conversies per aanroep toe die geen deel uitmaken van de kosten van de onderliggende bibliotheek.

Alle engines zijn gebouwd met volledige optimalisaties (O3, native targeting, link-time optimalisatie). Metingen worden uitgevoerd op één rustige core van een Intel Xeon Platinum 8488C. Voor elke engine en invoergrootte verzamelen we wall-clock latentie (p50 en p99, 10.000 iteraties na 1.000 warmup), voltooide instructies via Valgrind cachegrind, IPC en cache-miss-percentages van perf stat hardware-tellers, en heap-allocaties geteld door een globale allocator-wrapper rond het gemeten venster.

Bij 514 tokens (de +2 bovenop 512 is BOS/EOS-injectie):

Implementatie	p50-latentie	Instructies	IPC	Allocaties
Hugging Face	349 µs	3,60M	2,89	7.295
SentencePiece	128 µs	1,83M	3,39	1.559
IREE	112 µs	2,28M	3,06	1

Tokenizerlatentie, instructieaantal, IPC en allocaties bij 514 tokens.

SP en IREE landen op ongeveer een derde van de latentie van de referentie. Ze voltooien ongeveer de helft minder instructies, draaien op een hogere IPC en wijzen één tot twee ordes van grootte minder toe.

SentencePiece en IREE gebruiken beide de double-array trie die in 1989 door Aoe werd geïntroduceerd (Aoe, 1989; Karoonboonyanan). De trie is gecodeerd in twee platte integer-arrays, base en check:

cpp

int base[N];   // base[node] = offset for this node's children
int check[N];  // check[child] == node validates the parent-child link

Een child-lookup is:

cpp

int next = base[node] + byte;
if (check[next] == node) { /* valid transition; child node = next */ }

Elke stap van de trie-traversal heeft slechts twee array-loads, één integer-optelling en één vergelijking nodig, zonder hashing, zonder pointer-chasing en zonder heap-allocatie per knooppunt. De constructie plaatst elk knooppunt zo dat zijn kinderen op vrije slots in de validatie-array vallen, waardoor meerdere ouders regio's kunnen delen zolang hun kinderen verschillen in de byte die ze volgen.

Voor de 250K vocab van XLM-RoBERTa past de hele trie in ~9 MB aaneengesloten geheugen (~780K slots × 12 bytes voor de offset, validatie en token-ID per slot). De hete werkset van één encodering is in de orde van 100 KB, comfortabel in L2, en de hardware-prefetcher lockt op het regelmatige toegangspatroon.

De referentie daarentegen houdt een hash-map van kinderen per knooppunt bij, wat ongeveer vier afhankelijke loads per byte-stap kost. Hash de byte, laad de bucket, volg een pointer naar het bucket-item, volg een andere pointer naar het kind-knooppunt op de heap, en raadpleeg dan de eigen hash-map voor de volgende byte. Heap-objecten verspreiden zich en de meeste loads missen de cache.

SP en IREE slaan beide het token-ID direct op in het trie-knooppunt. De referentie-trie-implementatie retourneert alleen de gematchte bytes, dus de encoder moet voor elke match een nieuwe string toewijzen, deze opzoeken in een zij-hash-map om het token-ID te herstellen, en de score lezen uit een aparte vector. SP retourneert het ID als de opgeslagen waarde van de trie en leest de score uit een platte float-array:

cpp

// unigram_model.cc:567
const size_t num_nodes = trie_->commonPrefixSearch(
    begin, trie_results.data(), trie_results.size(),
    static_cast<int>(end - begin));

for (size_t k = 0; k < num_nodes; ++k) {
    const int   id    = trie_results[k].value;   // already in the trie
    const float score = GetScoreInlined(id);     // flat float[] indexed by id
    Lattice::Node *node = lattice->Insert(begin_pos, length);
    node->id = id;
    node->score = score;
}

IREE gebruikt een stateful cursor-API in plaats van alle matches in één aanroep te retourneren, maar het kostenmodel is hetzelfde: token-ID's en scores zijn bereikbaar als platte-array-indices, zonder allocatie of hashing tijdens de trie-walk zelf. IREE wijst slechts één uitvoerbuffer per encodering toe; SP wijst daarnaast tijdens de DP een rooster-knooppunt per match toe, in totaal ongeveer 1.559 allocaties bij 514 tokens.

Voordat we de trie veranderen, isoleren we de algoritmekosten van de implementatiekosten: hoe snel draait de referentie met het onnodige werk verwijderd?

De baseline behoudt de hash-map-children trie van de referentie, maar maakt twee wijzigingen. Een door de aanroeper beheerde scratch-struct bevat de DP-tabel, gepreprocessede bytes en uitvoer-token-ID's, zodat het hete pad na de warmup geen allocaties meer maakt. Het token-ID en de score worden direct in het trie-knooppunt opgeslagen, wat de string-conversie per match en de zij-hash-map-opzoeking verwijdert.

Innerlijke lus:

rust

for pos in 0..n {
    if scratch.prep[pos] & 0xC0 == 0x80 { continue; }
    let s0 = scratch.best_score[pos];
    if s0 == f32::NEG_INFINITY { continue; }

    let mut node = 0u32;
    for end in pos..n {
        let byte = scratch.prep[end];
        match self.nodes[node as usize].children.get(&byte) {
            Some(&child) => {
                node = child;
                let n = &self.nodes[node as usize];
                if n.is_terminal {
                    let total = s0 + n.score;
                    if total > scratch.best_score[end + 1] {
                        scratch.best_score[end + 1] = total;
                        scratch.best_start[end + 1] = pos as u32;
                        scratch.best_id[end + 1] = n.token_id;
                    }
                }
            }
            None => break,
        }
    }
}

Dit is hetzelfde algoritme, met dezelfde trie-vorm en hetzelfde toegangspatroon, alleen zonder allocaties en zonder redundante opzoekingen. Resultaten bij 514 tokens:

Engine	p50	Instructies	IPC	Allocaties
Hugging Face	326 µs	3,66M	2,86	7.295
SentencePiece	127 µs	1,81M	3,55	1.559
IREE	111 µs	1,58M	3,26	1
Baseline	156 µs	1,53M	2,62	0

De zero-allocation-basislijn vergeleken met bestaande tokenizer-implementaties bij 514 tokens.

Het verwijderen van string-materialisatie per match en de secundaire hash-map-opzoeking vermindert instructies met 2,4× ten opzichte van de referentie. IPC daalt daarmee (2,86 → 2,62) omdat de hash-map pointer-chase, voorheen verborgen achter allocator-werk, nu de dominante kosten per byte is.

Referentie- en zero-allocation-basislijn-tokenizer p50- en p99-latentie per invoergrootte.

Referentie- en zero-allocation-basislijn-tokenizer L2-cache-misspercentage per invoergrootte.

De baseline verlaagt de p50-latentie met 2-3× ten opzichte van de referentie bij elke grootte, en het L2-miss-percentage blijft rond 2-3% tot 2k tokens ten opzichte van de 8-48% van de referentie. De resterende kosten zijn de HashMap pointer-chase, die in de volgende sectie wordt aangepakt.

De hash-map trie is een pointer-chase. SP en IREE lossen dit op met een double-array trie (zie de vorige sectie), en wij lenen dezelfde datastructuur. Het verschil is dat SP en IREE algemene bibliotheken zijn die streaming-invoer, uitvoer-offsets en meerdere encoderingsmodi ondersteunen; die flexibiliteit kost hen extra boekhouding rond de trie (een rooster in SP, een acht-fasen pijplijn in IREE). Wij hebben daar niets van nodig, dus we inlinen de trie direct in de Viterbi-lus en laten de rest weg.

rust

fn child(&self, node: u32, byte: u8) -> Option<u32> {
    let base = self.base[node as usize];
    let next = base + byte as i32;
    if self.check[next as usize] == node as i32 {
        Some(next as u32)
    } else {
        None
    }
}

Een byte-stap kost twee array-reads, een integer-optelling en een vergelijking. De hele trie is ongeveer 9 MB, maar elke encodering doorloopt slechts ~100 KB ervan, dus de hete data blijft in L2.

Engine	p50	p99	Instructies	L2 miss%	L3 miss%
Hugging Face	327 µs	3.340 µs	3,66M	8,17%	14,66%
SentencePiece	127 µs	1.140 µs	1,82M	4,74%	4,07%
IREE	111 µs	132 µs	1,61M	5,82%	3,87%
Baseline	155 µs	1.170 µs	1,53M	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	6,45%	11,42%

Tokenizerlatentie, instructies en cache-misspercentages na toepassing van de double-array trie.

De wall-clock daalt 2,3× vanaf de baseline en 4,8× vanaf de referentie. Instructies dalen nog eens 28% vanaf de baseline. Door het rooster en de pijplijn weg te snijden, kunnen we 1,10M instructies per encodering voltooien tegenover 1,82M van SP en 1,61M van IREE bij dezelfde trie-vorm; het verschil is de boekhouding die zij bijhouden voor algemene API's die wij niet nodig hebben.

De Darts-trie uit Optimalisatie 1 heeft twee afhankelijke loads per byte-stap nodig. Eerst de basis-offset van de ouder, dan het check-item op de kandidaat-kind-slot om te bevestigen dat de ouder het bezit. Het check-item valideert alleen het eigendom. Dezelfde vraag kan worden beantwoord door een bitmap per knooppunt die registreert welke bytes kinderen hebben. Door de constructie van de double-array trie is de bit voor byte b in de bitmap van de ouder precies ingesteld wanneer het kandidaat-slot voor die byte eigendom is van de ouder. De bitmap en de check-array dragen dezelfde informatie, dus we kunnen de check-array volledig uit de runtime-structuur verwijderen.

De bitmap-opzoeking compileert naar een enkele bit-test tegen één 64-bit woord, wat in ongeveer een cyclus draait. De bijbehorende POPCNT-instructie, die alle ingestelde bits in een register telt, is wat andere bitmap-geïndexeerde trie-ontwerpen gebruiken om een kind-offset direct uit de bitmap te berekenen. Dat hebben we niet nodig omdat de Darts-constructie die offset al in het base-veld van het knooppunt opslaat.

rust

#[repr(C, align(64))]
struct NodeHot {
    bitmap:   [u64; 4],     // 32 B  — "which bytes have children"
    base:     i32,          //  4 B  — child slot offset
    token_id: i32,          //  4 B  — vocab id (-1 if not terminal)
    score:    f64,          //  8 B  — Viterbi log-prob
    _pad:     [u8; 16],     // 16 B  — pad to one cache line
}

// Lookup: one cache-line load, one bit test, one add.
fn child(&self, parent: u32, byte: u8) -> Option<u32> {
    let h = &self.node_hot[parent as usize];
    if !h.bitmap.test(byte) { return None; }
    Some(h.base.wrapping_add(byte as i32) as u32)
}

Terwijl we toch bezig zijn, pakken we de vier velden per knooppunt (bitmap, base, token-ID en score) in één 64-byte cache-regel. Eén knooppuntbezoek trekt nu alles binnen: de score en het token-ID die we nodig hebben bij eindknooppunten, plus de bitmap en base voor de volgende stap. De check-array wordt alleen tijdens de constructie gebruikt en wordt uit de runtime-lay-out verwijderd. De indexering van het hete pad is ongecontroleerd omdat trie-constructie en lusstructuur de grenzen al garanderen. De afruil is de Ruimte: bij 64 bytes per knooppunt × ~780K slots groeit de trie van ~9 MB naar ~50 MB.

Resultaten bij 514 tokens:

Engine	p50	p99	Instructies	L2 accesses	L2 miss%	L3 miss%
Hugging Face	327 µs	3.340 µs	3,66M	15.0K	8,17%	14,66%
SentencePiece	127 µs	1.140 µs	1,82M	7.5K	4,74%	4,07%
IREE	111 µs	132 µs	1,61M	4.7K	5,82%	3,87%
Baseline	155 µs	1.170 µs	1,53M	6.1K	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	4.6K	6,45%	11,42%
+ Bitmap and Inline Packing	65 µs	77 µs	1,06M	1.8K	20,53%	15,01%

Tokenizerresultaten bij 514 tokens na toevoeging van bitmap en inline packing.

De wall-clock daalt systematisch met nog eens 4,5% bij 514 tokens en groeit met de invoerlengte, tot 6-7% bij 4k en 16k. Het verwijderen van de check-array verandert de trie-stap per byte van twee cache-line loads naar één, wat 2,5× minder L2-toegangen per encodering is (1.8K tegenover de 4.6K van de standaard Darts). Het miss-percentage springt van 6% naar 20%, maar het grootste deel daarvan is de noemer: met minder dan de helft zoveel toegangen nemen de missers die we wél hebben een groter aandeel in.

De trie-data is ongeveer 50 MB (780.000 knooppunten bij 64 bytes elk). Op een standaard Linux-proces wordt dat geheugen ondersteund door 4 KB pagina's, dus de volledige trie beslaat ongeveer 12.000 afzonderlijke virtuele pagina's, ver voorbij wat de Translation Lookaside Buffer van de CPU op het eerste niveau kan bevatten (Sapphire Rapids heeft 96 entries). Elke Viterbi-stap raakt een ander knooppunt, en over een encodering van 512 tokens verbruiken we ongeveer 9.000 cycli in pagina-tabel-walks, ongeveer 3% van het budget per encodering.

De oplossing is om de trie te ondersteunen met 2 MB huge pages in plaats van die van 4 KB. Dezelfde 50 MB beslaat nu 25 pagina's, past volledig in de Translation Lookaside Buffer, en de pagina-tabel-mappen zelf stoppen met concurreren met de trie voor L2-cache.

Linux heeft twee manieren om geheugen te ondersteunen met 2 MB pagina's. De opportunistische manier is transparent huge pages (THP): uw programma vraagt de kernel om een geheugenregio te upgraden van 4 KB naar 2 MB pagina's, en een achtergrond-kernel-draad probeert dit te doen wanneer het tijd en aaneengesloten fysiek geheugen beschikbaar heeft. Het andere alternatief is om de trie direct toe te wijzen vanuit een vooraf gereserveerde huge-page-pool die de kernel bij het opstarten apart zet:

rust

let raw = unsafe {
    libc::mmap(
        std::ptr::null_mut(),
        alloc_len,
        libc::PROT_READ | libc::PROT_WRITE,
        libc::MAP_PRIVATE | libc::MAP_ANONYMOUS | libc::MAP_HUGETLB,
        -1,
        0,
    )
};

De pool moet op de host bestaan (vm.nr_hugepages ingesteld bij het opstarten). Op onze productie-instanties zijn 10.561 huge pages gereserveerd; de trie verbruikt er 24. Na de mmap bevestigt /proc/<pid>/smaps de regio: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

De winst is 3–12% wall-clock over invoergroottes, consistent en evenredig aan de lengte van de werkset:

Tokens	Zonder huge pages	Met huge pages	Δ
130	15,7 µs	15,2 µs	−3,6%
514	65,4 µs	63,1 µs	−3,4%
1.026	129,5 µs	125,3 µs	−3,3%
4.098	773 µs	679 µs	−12,0%
16.386	3.808 µs	3.554 µs	−6,8%

Tokenizerlatentie met en zonder huge pages over verschillende invoergroottes.

De grootste winst is bij 4k tokens, waar de werkset groot genoeg is dat pagina-tabel-verkeer actief concurreerde met trie-data voor L2-bandbreedte. Voorbij 4k krimpt de winst omdat L3-missers domineren en pagina-tabel-walks een kleiner deel van de totale tijd worden.

De drie optimalisaties samengevoegd, hier is de uiteindelijke engine gemeten tegen elke andere RoBERTa-tokenizer die we hebben getest. Naast de native C++ SentencePiece- en C IREE-binairen hebben we ook de standaard Rust-wrapper-crates benchmarkt waar een productiegebruiker naar zou grijpen, sentencepiece en iree-tokenizer. De sentencepiece-crate meet 1,6-1,9× hogere latentie dan de native C++-binaire bij elke invoergrootte, waarbij de overhead komt van de wrapper die een nieuwe lijst met token-stukjes toewijst, elk met een eigen kopie van de stuk-tekst, bij elke encodering. De iree-tokenizer-crate schaalt de interne buffer aan elke invoer aan, wat een constante allocatie per encodering vermijdt die de native IREE-binaire betaalt, ongeacht de invoergrootte, en dat is vooral belangrijk bij korte invoer waar de allocatie anders het eigenlijke tokenisatiewerk zou domineren. Bij productielengtes amortiseren de constante kosten en de eigen overhead per aanroep van de wrapper door tokens terug naar Rust te kopiëren duwt de latentie boven die van de native binaire.

p50- en p99-latentie per encode over tokenizerimplementaties en invoergroottes.

De uiteindelijke engine draait dezelfde Viterbi over hetzelfde vocabulaire van 250.000 tokens, wijst niets toe op het hete pad en produceert token-exacte uitvoer tegenover de referentie. Elke byte-stap is nu een enkele 64-byte cache-regel load, één bitmap-test en één integer-optelling, omlaag van een HashMap-probe, een allocator-aanroep en verschillende special-case vertakkingen in de baseline-implementatie. Instructies per encodering daalden van 3,66M naar 1,04M, een daling van 3,5×. De wall-clock komt overeen met die verhouding bij korte invoer en wordt groter bij lange invoer, waar de per-token allocaties van de referentie L2 en L3 beginnen te overstromen.

In de praktijk verminderde dit werk het CPU-gebruik in de preprocessing-laag van onze inferentiestack met 5-6× en bracht het de latentie van de reranker met dubbele cijfers in milliseconden omlaag.

Het grootste deel van de latentiereductie kwam van lichtgewicht wijzigingen die verspild werk verwijderden: het laten vallen van allocaties per encodering, het vervangen van de HashMap-children trie door een double-array, en het strippen van de generieke-API-overhead. Het gebruik van de bestaande bitmap per knooppunt als validiteitscontrole en het ondersteunen van de trie met 2 MB huge pages samen waren goed voor 10-20% bovenop de grotere overstap naar een double-array trie, afhankelijk van de invoergrootte.

De standaard Rust-wrapper-crates rond SentencePiece en IREE illustreren hetzelfde punt in omgekeerde volgorde. Bovenop native C- en C++-tokenizers zijn de FFI-grens en allocaties per aanroep die de wrappers introduceren zichtbaar in de latentiecijfers. De Rust-bron voor de uiteindelijke Viterbi-encoder is beschikbaar op github.com/perplexityai/pplx-garden.

Hugging Face tokenizers — https://github.com/huggingface/tokenizers

SentencePiece — https://github.com/google/sentencepiece

IREE tokenizer — https://github.com/iree-org/iree

Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. An Implementation of Double-Array Trie. https://linux.thai.net/~thep/datrie/datrie.html

POPCNT (x86) — https://www.felixcloutier.com/x86/popcnt

Huge pages — https://docs.kernel.org/admin-guide/mm/hugetlbpage.html

BibTeX

@online{perplexity2026ImprovingUnigramTokenizerCpuPerformance,
  author = {{Perplexity} and Vladimir Zaytsev and Bex Brooker and Daisy Lee and Roshan Shankar},
  title = {{Improving unigram tokenizer CPU performance}},
  date = {2026-05-20},
  url = {https://www.perplexity.ai/hub/blog/improving-unigram-tokenizer-cpu-performance}
}

Motivatie

Het Viterbi-algoritme

Referentie-implementatie

Een opmerking over preprocessing

Waar de referentie-implementatie haar tijd besteedt

Hoe we hebben gemeten

Waarom SentencePiece en IREE sneller zijn: de Double-Array Trie

Baseline: een zero-allocatie port van de referentie

Optimalisatie 1: Double-Array Trie zonder extra abstracties

Optimalisatie 2: Bitmap en inline packing

Optimalisatie 3: Huge pages voor de trie

Definitieve vergelijking

Slotgedachten

Referenties

Citaat