Melhorando o Desempenho da CPU do Tokenizador Unigram

Reimplementamos nosso tokenizador Unigram do zero como um projeto focado em desempenho. Em comprimentos de entrada de produção, o novo codificador reduz a latência p50 em aproximadamente 5x em comparação com o crate tokenizers da Hugging Face, ~2x em comparação ao SentencePiece (C++) e ~1,5x em comparação ao tokenizador do IREE (C), com zero alocações de heap em regime permanente. Na produção, isso reduziu a utilização da CPU em nossa pilha de inferência em 5-6x e reduziu a latência do reranker em dois dígitos em milissegundos.

O custo de inferência de LLM é geralmente enquadrado como trabalho de GPU: caches KV, kernels de atenção, roteamento de especialistas. Mas uma parte significativa do tráfego de produção roda em modelos muito menores, duas a três ordens de magnitude menores que os transformers de fronteira. Modelos de embedding, classificadores e rerankers ainda rodam em GPUs, mas a passagem direta (forward pass) é curta o suficiente para que tudo ao seu redor comece a importar.

O caso mais claro é um reranker pontuando centenas de documentos candidatos por solicitação. Com um modelo pequeno, a computação da GPU geralmente termina em milissegundos de um único dígito, mas cada entrada ainda precisa passar pela tokenização no lado da CPU primeiro, transformando texto em IDs de vocabulário. Quando o lote é grande, isso pode representar uma fração significativa da latência total da solicitação.

Este trabalho tem como alvo o XLM-RoBERTa, um vocabulário Unigram de 250 mil tokens treinado com SentencePiece. Codificadores da família RoBERTa com ajuste fino (fine-tuned) são uma escolha comum para tarefas de classificação, recuperação e similaridade. Relatamos a latência por codificação em thread única; na produção, paralelizamos entre núcleos usando rayon.

Ao longo desta postagem, tratamos o crate tokenizers da Hugging Face como a referência em relação à qual fazemos o benchmark, já que é o tokenizador Rust padrão que a maioria das equipes utiliza. SentencePiece (C++) e IREE (C) são incluídos para comparação como as outras duas principais implementações de produção.

A tokenização Unigram, introduzida por Kudo em 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) e disponibilizada no SentencePiece, enquadra a segmentação como um problema de caminho mais provável: cada token de vocabulário possui uma log-probabilidade aprendida, e o codificador escolhe a segmentação cujas pontuações de token somam o valor mais alto. O problema é resolvido com o algoritmo de Viterbi (1967), com posições de byte como camadas de grafo e tokens de vocabulário como arestas que abrangem um intervalo contíguo de bytes. A recorrência é uma DP unidimensional sobre as posições de byte:

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

O loop externo é linear no comprimento da entrada, limitado em cada posição pelo token de vocabulário mais longo (48 bytes UTF-8 para XLM-RoBERTa). A caminhada trie interna é o caminho crítico: em uma entrada de 16 mil tokens, ele executa centenas de milhares de transições e retira dezenas de milhões de instruções por codificação.

O tokenizers v0.22 da Hugging Face implementa a recorrência diretamente, com um hash-map para a busca reversa e hash-map-children em cada nó trie:

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
}

E o loop interno (simplificado) – cada correspondência de pesquisa de prefixo aloca uma nova string e então testa o 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
}

O código é Rust legível, mas muito trabalho acontece que é invisível no nível da fonte. A próxima seção detalha para onde vai o tempo.

Antes de Viterbi rodar, a entrada passa pela normalização Unicode (NFKC) e marcação de limite de palavra. A análise de desempenho (profiling) coloca o pré-processamento em menos de 5% do tempo total de codificação em nossos cenários, então focamos na passagem direta de Viterbi pelo restante da postagem.

Existem duas maneiras de acelerar o código da CPU: executar menos instruções ou obter IPC (instruções por ciclo) mais alto. O Cachegrind mede o primeiro, o perf stat mede o segundo. Cada otimização nesta postagem foca em um ou outro.

As CPUs sofrem paradas por quatro motivos: falhas de cache (L1d ~4 ciclos, uma falha de L3 para DRAM é centenas), cadeias de carga dependentes que o motor de execução fora de ordem não consegue paralelizar, previsões de ramificação incorretas (~15-20 ciclos descartados por palpite errado) e chamadas de alocador. A implementação do motor unigram de referência atinge todos os quatro:

Gargalo	Mecanismo	Impacto medido
Alocação por correspondência	String::from_utf8 nos bytes correspondentes mais uma busca em AHashMap por correspondência trie; o ID do token já está na folha, mas a referência não o armazena lá	7.295 alocações em 512 tokens, 14.542 em 1k, 299.171 em 16k
Busca de ponteiro por byte	Um AHashMap em cada nó trie, fazendo hash do próximo byte e desreferenciando dois ponteiros por passo; a estrutura Node também agrupa campos frios como is_leaf, puxando-os para o cache a cada visita	A taxa de falha L1d permanece baixa (~2,5% em 1k) porque as páginas quentes do alocador vivem no L1; o custo aparece como latência de carga dependente
L2 thrashing em entradas longas	Tabela DP, scratch de prefixo e a lista de tokens de saída são todos alocados recentemente a cada chamada	A taxa de falha L2 sobe de 12% em 128 tokens para 50% em 16k à medida que a pegada de alocação cumulativa excede o L2 de 2 MB por núcleo

Referência dos gargalos, mecanismos e impactos medidos do tokenizador.

O custo dominante é a alocação por correspondência. Em 1k tokens, a implementação de referência retira (conclui) cerca de 7 milhões de instruções por codificação com IPC de 2,8, a maioria delas em chamadas de alocador e conversões de string. As falhas de L2 só importam após ~1k tokens, uma vez que a pegada de alocação cumulativa transborda o cache por núcleo.

Latência p50 e p99 do tokenizador de referência por tamanho de entrada.

Taxa de falta no cache L2 do tokenizador de referência por tamanho de entrada.

Bytes alocados por codificação pelo tokenizador de referência em diferentes tamanhos de entrada.

A alocação por token é constante: cerca de 2 KB e ~18 alocações por token, independentemente do tamanho da entrada. A não linearidade da latência vem do L2: bytes cumulativos cruzam 2 MB por volta de 1k tokens, a taxa de falha sobe de 8% para ~50% e a curva p99 se curva para acompanhar.

Comparamos três tokenizadores de produção, todos rodando o mesmo algoritmo Unigram contra o mesmo modelo XLM-RoBERTa:

Motor	Linguagem	Trie
Hugging Face	Rust	Trie de prefixo HashMap-children
SentencePiece	C++	Trie de matriz dupla Darts
Tokenizador IREE	C	Trie de matriz dupla Darts

Implementações de tokenizador, linguagens e representações em trie usadas na comparação.

Vinculamos o SentencePiece e o IREE através de FFI C/C++ direto em vez de seus wrappers Rust; os wrappers adicionam alocações por chamada e conversões de string que não fazem parte do custo da biblioteca subjacente.

Todos os motores são construídos com otimizações completas (O3, direcionamento nativo, otimização em tempo de vinculação). As medições rodam fixadas em um núcleo silencioso em um Intel Xeon Platinum 8488C. Para cada motor e tamanho de entrada, coletamos a latência de relógio (p50 e p99, 10.000 iterações após 1.000 de aquecimento), instruções retiradas via Valgrind cachegrind, IPC e taxas de falha de cache dos contadores de hardware perf stat, e alocações de heap contadas por um wrapper de alocador global ao redor da janela medida.

Em 514 tokens (os +2 sobre 512 são injeção BOS/EOS):

Implementação	Latência p50	Instruções	IPC	Alocações
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

Latência do tokenizador, contagem de instruções, IPC e alocações em 514 tokens.

SP e IREE chegam a aproximadamente um terço da latência da referência. Eles retiram cerca de metade das instruções, rodam com IPC mais alto e alocam uma a duas ordens de magnitude a menos.

SentencePiece e IREE usam a trie de matriz dupla introduzida por Aoe em 1989 (Aoe, 1989; Karoonboonyanan). A trie é codificada em duas matrizes de inteiros planas, base e check:

cpp

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

Uma busca de filho é:

cpp

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

Cada passo da travessia trie precisa apenas de duas cargas de matriz, uma adição de inteiro e uma comparação, sem hashing, sem busca de ponteiro e sem alocação de heap por nó. A construção posiciona cada nó de forma que seus filhos caiam em slots livres na matriz de validação, permitindo que vários pais compartilhem regiões desde que seus filhos difiram no byte que seguem.

Para o vocabulário de 250 mil do XLM-RoBERTa, a trie inteira cabe em ~9 MB de memória contígua (~780 mil slots × 12 bytes para o deslocamento, validação e ID de token por slot). O conjunto de trabalho quente de uma única codificação é da ordem de 100 KB, confortavelmente em L2, e o pré-buscador de hardware trava no padrão de acesso regular.

A referência, por outro lado, mantém um hash-map de filhos por nó, custando aproximadamente quatro cargas dependentes por passo de byte. Faça o hash do byte, carregue o bucket, siga um ponteiro para a entrada do bucket, siga outro ponteiro para o nó filho no heap, então consulte seu próprio hash-map para o próximo byte. Objetos de heap se espalham e a maioria das cargas perde o cache.

SP e IREE armazenam o ID do token diretamente no nó trie. A implementação trie de referência retorna apenas os bytes correspondentes, então o codificador tem que alocar uma nova string para cada correspondência, buscá-la em um hash-map lateral para recuperar o ID do token e ler a pontuação de um vetor separado. O SP retorna o ID como o valor armazenado da trie e lê a pontuação de uma matriz de float plana:

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;
}

O IREE usa uma API de cursor com estado em vez de retornar todas as correspondências em uma única chamada, mas o modelo de custo é o mesmo: IDs de token e pontuações são alcançáveis como índices de matriz plana, sem alocação ou hashing na própria caminhada trie. O IREE aloca apenas um buffer de saída por codificação; o SP aloca adicionalmente um nó de rede por correspondência durante a DP, totalizando cerca de 1.559 alocações em 514 tokens.

Antes de alterar a trie, isolamos o custo do algoritmo do custo da implementação: quão rápido a referência roda com o trabalho desnecessário removido?

A linha de base mantém a trie hash-map-children da referência, mas faz duas alterações. Uma estrutura scratch de propriedade do chamador contém a tabela DP, bytes pré-processados e IDs de token de saída, então o caminho crítico não faz alocações após o aquecimento. O ID do token e a pontuação são armazenados diretamente no nó trie, removendo a conversão de string por correspondência e a busca no hash-map lateral.

Loop interno:

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,
        }
    }
}

Este é o mesmo algoritmo, com a mesma forma de trie e o mesmo padrão de acesso, apenas sem alocações e sem pesquisas redundantes. Resultados em 514 tokens:

Motor	p50	Instruções	IPC	Alocações
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
Linha de base	156 µs	1.53M	2.62	0

A linha de base sem alocações comparada às implementações de tokenizador existentes em 514 tokens.

Remover a materialização de string por correspondência e a pesquisa de hash-map secundária corta as instruções em 2,4x em comparação com a referência. O IPC cai com eles (2,86 → 2,62) porque a busca de ponteiro de hash-map, anteriormente escondida atrás do trabalho do alocador, agora é o custo dominante por byte.

Latência p50 e p99 dos tokenizadores de referência e da linha de base sem alocações por tamanho de entrada.

Taxa de falta no cache L2 dos tokenizadores de referência e da linha de base sem alocações por tamanho de entrada.

A linha de base corta a latência p50 em 2-3x em relação à referência em cada tamanho, e sua taxa de falha L2 permanece perto de 2-3% até 2k tokens versus os 8-48% da referência. O custo restante é a busca de ponteiro HashMap, que a próxima seção aborda.

A trie hash-map é uma busca de ponteiro. SP e IREE resolvem isso com uma trie de matriz dupla (veja a seção anterior), e pegamos emprestada a mesma estrutura de dados. A diferença é que SP e IREE são bibliotecas de uso geral que suportam entrada em streaming, deslocamentos de saída e vários modos de codificação; essa flexibilidade custa-lhes contabilidade extra em torno da trie (uma rede no SP, um pipeline de oito estágios no IREE). Não precisamos de nada disso, então colocamos a trie inline diretamente no loop de Viterbi e descartamos o resto.

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
    }
}

Um passo de byte custa duas leituras de matriz, uma adição de inteiro e uma comparação. A trie inteira tem cerca de 9 MB, mas qualquer codificação única caminha apenas ~100 KB dela, então os dados quentes permanecem em L2.

Motor	p50	p99	Instruções	Falha L2%	Falha L3%
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%
Linha de base	155 µs	1.170 µs	1.53M	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	6.45%	11.42%

Latência do tokenizador, instruções e taxas de falta de cache após adotar a trie de array duplo.

O relógio cai 2,3x da linha de base e 4,8x da referência. As instruções caem outros 28% da linha de base. Cortar a rede e o pipeline nos permite retirar 1,10 milhão de instruções por codificação contra 1,82 milhão do SP e 1,61 milhão do IREE na mesma forma de trie; o intervalo é a contabilidade que eles mantêm para APIs de uso geral que não precisamos.

A trie Darts da Otimização 1 precisa de duas cargas dependentes por passo de byte. Primeiro o deslocamento base do pai, depois a entrada check no slot do filho candidato para confirmar que o pai o possui. A entrada check apenas valida a propriedade. A mesma pergunta pode ser respondida por um bitmap por nó que registra quais bytes têm filhos. Pela construção da trie de matriz dupla, o bit para o byte b no bitmap do pai é definido exatamente quando o slot candidato para esse byte é possuído pelo pai. O bitmap e a matriz de check carregam a mesma informação, então podemos descartar a matriz de check da estrutura de tempo de execução inteiramente.

A busca de bitmap compila para um teste de bit único contra uma palavra de 64 bits, que roda em cerca de um ciclo. A instrução POPCNT relacionada, que conta todos os bits definidos em um registrador, é o que outros designs de trie indexados por bitmap usam para calcular um deslocamento de filho a partir do bitmap diretamente. Não precisamos dele porque a construção Darts já armazena esse deslocamento no campo base do nó.

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)
}

Enquanto estamos nisso, embalamos os quatro campos por nó (bitmap, base, ID de token e pontuação) em uma linha de cache de 64 bytes. Uma única visita ao nó agora puxa tudo: a pontuação e o ID do token que precisamos nos nós terminais, mais o bitmap e a base para o próximo passo. A matriz de check só é usada durante a construção e é descartada do layout de tempo de execução. A indexação do caminho crítico não é verificada porque a construção da trie e a estrutura do loop já garantem os limites. O trade-off é o Espaço: a 64 bytes por nó × ~780 mil slots a trie cresce de ~9 MB para ~50 MB.

Resultados em 514 tokens:

Motor	p50	p99	Instruções	Acessos L2	Falha L2%	Falha L3%
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%
Linha de base	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 e Embalagem Inline	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

Resultados do tokenizador em 514 tokens após adicionar bitmap e empacotamento inline.

O relógio cai sistematicamente outros 4,5% em 514 tokens e cresce com o comprimento da entrada, chegando a 6-7% em 4k e 16k. Descartar a matriz de check transforma o passo da trie por byte de duas cargas de linha de cache em uma, o que é 2,5x menos acessos L2 por codificação (1,8K versus os 4,6K da Darts simples). A taxa de falha salta de 6% para 20%, mas a maior parte disso é o denominador: com menos da metade dos acessos, as falhas que temos ocupam uma parcela maior.

Os dados da trie são de aproximadamente 50 MB (780.000 nós a 64 bytes cada). Em um processo Linux padrão, essa memória é suportada por páginas de 4 KB, então a trie completa abrange cerca de 12.000 páginas virtuais distintas, muito além do que o Translation Lookaside Buffer de dados de primeiro nível da CPU pode conter (Sapphire Rapids tem 96 entradas). Cada passo de Viterbi toca um nó diferente, e em uma codificação de 512 tokens queimamos cerca de 9.000 ciclos em caminhadas de tabela de página, cerca de 3% do orçamento por codificação.

A solução é suportar a trie com páginas grandes de 2 MB em vez de 4 KB. Os mesmos 50 MB agora abrangem 25 páginas, cabem inteiramente no Translation Lookaside Buffer, e os diretórios da tabela de página param de competir com a trie pelo cache L2.

O Linux tem duas maneiras de suportar memória com páginas de 2 MB. A oportunista é a de páginas grandes transparentes (THP): seu programa pede ao kernel para atualizar uma região de memória de páginas de 4 KB para 2 MB, e um tópico (thread) de kernel em segundo plano tenta fazer isso quando tem tempo e memória física contígua disponível. A outra alternativa é alocar a trie diretamente de um pool de páginas grandes pré-reservado que o kernel reserva na inicialização:

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,
    )
};

O pool precisa existir no host (vm.nr_hugepages definido na inicialização). Em nossas instâncias de produção, 10.561 páginas grandes são reservadas; a trie consome 24 delas. Após o mmap, /proc/<pid>/smaps confirma a região: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

O ganho é de 3–12% no relógio em vários tamanhos de entrada, consistente e proporcional ao comprimento do conjunto de trabalho:

Tokens	Sem páginas grandes	Com páginas grandes	Δ
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%

Latência do tokenizador com e sem páginas enormes em diferentes tamanhos de entrada.

A maior vitória é em 4k tokens, onde o conjunto de trabalho é grande o suficiente para que o tráfego de tabela de página estivesse competindo ativamente com os dados da trie por largura de banda L2. Além de 4k, o ganho diminui porque as falhas de L3 dominam e as caminhadas de tabela de página se tornam uma parcela menor do tempo total.

Reunindo as três otimizações, aqui está o motor final medido contra todos os outros tokenizadores RoBERTa que testamos. Junto com os binários nativos SentencePiece (C++) e IREE (C), também comparamos os crates de wrapper Rust disponíveis que um usuário de produção utilizaria, sentencepiece e iree-tokenizer. O crate sentencepiece mede uma latência 1,6-1,9x maior do que o binário C++ nativo em todos os tamanhos de entrada, com o overhead vindo do wrapper alocando uma lista nova de peças de token, cada uma mantendo sua própria cópia do texto da peça, em cada codificação. O crate iree-tokenizer dimensiona seu buffer interno para cada entrada, o que evita uma alocação constante por codificação que o binário nativo IREE paga independentemente do tamanho da entrada, e isso importa mais em entradas curtas onde a alocação dominaria o trabalho real de tokenização. Em comprimentos de entrada de produção, o custo constante amortece e o próprio overhead por chamada do wrapper de copiar tokens de volta para o Rust empurra sua latência acima da do binário nativo.

Latência p50 e p99 por codificação entre implementações de tokenizador e tamanhos de entrada.

O motor final roda o mesmo Viterbi sobre o mesmo vocabulário de 250.000 tokens, não aloca nada no caminho crítico e produz saída exata ao token contra a referência. Cada passo de byte é agora uma carga de linha de cache de 64 bytes, um teste de bitmap e uma adição de inteiro, abaixo de uma sondagem HashMap, uma chamada de alocador e várias ramificações de caso especial na implementação da linha de base. Instruções por codificação caíram de 3,66 milhões para 1,04 milhão, uma queda de 3,5x. O relógio corresponde a essa proporção em entradas curtas e aumenta ainda mais em entradas longas, onde as alocações por token da referência começam a transbordar L2 e L3.

Na prática, este trabalho reduziu a utilização da CPU na camada de pré-processamento da nossa pilha de inferência em 5-6x e reduziu a latência do reranker em dois dígitos em milissegundos.

A maior parte da redução de latência veio de mudanças leves que removeram trabalho desperdiçado: descartar alocações por codificação, substituir a trie HashMap-children por uma matriz dupla e eliminar o overhead de API genérica. Usar o bitmap por nó existente como verificação de validade e suportar a trie com páginas grandes de 2 MB combinadas representaram 10-20% além da mudança maior para uma trie de matriz dupla, dependendo do tamanho da entrada.

Os crates de wrapper Rust de prateleira em torno do SentencePiece e IREE ilustram o mesmo ponto inversamente. Em cima dos tokenizadores C e C++ nativos, a fronteira FFI e as alocações por chamada que os wrappers introduzem são visíveis nos números de latência. A fonte Rust para o codificador Viterbi final está disponível em 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}
}

Motivação

O Algoritmo de Viterbi

Implementação de Referência

Uma Nota sobre Pré-processamento

Onde a Implementação de Referência Gasta Seu Tempo

Como Medimos

Por que SentencePiece e IREE são mais rápidos: A Trie de Matriz Dupla

Linha de base: Uma porta de alocação zero da referência

Otimização 1: Trie de Matriz Dupla Sem Abstrações Extras

Otimização 2: Bitmap e empacotamento embutido

Otimização 3: Páginas grandes para o trie

Comparação final

Considerações finais

Referências

Citação