Mejora del rendimiento de la CPU del tokenizador Unigram

Implementamos de nuevo nuestro tokenizador Unigram desde cero como un proyecto enfocado en el rendimiento. Con las longitudes de entrada de producción, el nuevo codificador reduce la latencia p50 en aproximadamente 5× frente a la crate de tokenizadores de Hugging Face, ~2× frente a SentencePiece (C++) y ~1.5× frente al tokenizador de IREE (C), sin asignaciones en el montón en estado estacionario. En producción, esto redujo la utilización de CPU en nuestra pila de inferencia entre 5 y 6× y recortó milisegundos de dos dígitos en la latencia del reordenador.

El costo de inferencia de LLM suele enmarcarse como trabajo de GPU: cachés KV, núcleos de atención, enrutamiento de expertos. Pero una parte significativa del tráfico de producción se ejecuta en modelos mucho más pequeños, de dos a tres órdenes de magnitud más pequeños que los transformadores de frontera. Los modelos de incrustación, los clasificadores y los reordenadores aún se ejecutan en GPUs, pero el paso hacia adelante es lo suficientemente corto como para que todo lo que lo rodea empiece a importar.

El caso más claro es un reordenador que puntúa cientos de documentos candidatos por solicitud. Con un modelo pequeño, el cálculo de GPU normalmente termina en milisegundos de un solo dígito, pero cada entrada aún debe pasar primero por la tokenización del lado de la CPU, convirtiendo el texto en IDs de vocabulario. Cuando el lote es grande, eso puede representar una fracción significativa de la latencia total de la solicitud.

Este trabajo se centra en XLM-RoBERTa, un vocabulario Unigram de 250K tokens entrenado con SentencePiece. Los codificadores de la familia RoBERTa afinados son una opción común para tareas de clasificación, recuperación y similitud. Informamos la latencia por codificación de un solo hilo en todo momento; en producción paralelizamos entre núcleos usando rayon.

A lo largo de esta publicación, tratamos la crate de tokenizers de Hugging Face como la referencia con la que nos comparamos, ya que es el tokenizador de Rust predeterminado al que recurren la mayoría de los equipos. SentencePiece (C++) e IREE (C) se incluyen para comparar como las otras dos implementaciones principales de producción.

La tokenización Unigram, introducida por Kudo en 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) e incorporada en SentencePiece, enmarca la segmentación como un problema de ruta más probable: cada token de vocabulario tiene una probabilidad logarítmica aprendida, y el codificador elige la segmentación cuyas puntuaciones de tokens suman el valor más alto. El problema se resuelve con el algoritmo de Viterbi (1967), con las posiciones de los bytes como capas de grafos y los tokens de vocabulario como aristas que abarcan un rango de bytes contiguos. La recurrencia es una programación dinámica unidimensional sobre las posiciones de los bytes:

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

El bucle externo es lineal respecto a la longitud de la entrada, limitado en cada posición por el token de vocabulario más largo (48 bytes UTF-8 para XLM-RoBERTa). El recorrido interno del trie es la ruta crítica: en una entrada de 16k tokens, ejecuta cientos de miles de transiciones y completa decenas de millones de instrucciones por codificación.

Los tokenizers v0.22 de Hugging Face implementan la recurrencia directamente, con un mapa hash para la búsqueda inversa y mapas hash de hijos en cada nodo del 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
}

Y el bucle interno (simplificado): cada coincidencia de búsqueda de prefijos asigna una cadena nueva y luego sondea el mapa hash:

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
}

El código es Rust legible, pero ocurre una gran cantidad de trabajo que es invisible a nivel de código fuente. La siguiente sección desglosa a dónde va el tiempo.

Antes de que se ejecute Viterbi, la entrada pasa por la normalización Unicode (NFKC) y el marcado de límites de palabras. La perfilación sitúa el preprocesamiento en menos del 5% del tiempo total de codificación en nuestros escenarios, por lo que nos centramos en el paso hacia adelante de Viterbi para el resto de la publicación.

Hay dos formas de acelerar el código de CPU: ejecutar menos instrucciones o conseguir un IPC más alto. Cachegrind mide lo primero, perf stat mide lo segundo. Cada optimización en esta publicación recae en una u otra.

Las CPUs se bloquean por cuatro cosas: errores de caché (L1d ~4 ciclos, un error de L3 a DRAM son cientos), cadenas de cargas dependientes que el motor fuera de orden no puede paralelizar, errores de predicción de ramas (~15-20 ciclos descartados por conjetura incorrecta) y llamadas al asignador. La implementación del motor unigráfico de referencia sufre las cuatro:

Cuello de botella	Mecanismo	Impacto medido
Asignación por coincidencia	String::from_utf8 en los bytes coincidentes más una búsqueda en AHashMap por cada coincidencia en el trie; el ID del token ya está en la hoja, pero la referencia no lo almacena allí	7295 asignaciones con 512 tokens, 14 542 con 1k, 299 171 con 16k
Búsqueda de punteros por byte	Un AHashMap en cada nodo del trie, aplicando hash al byte siguiente y desreferenciando dos punteros por paso; la estructura Node también agrupa campos fríos como is_leaf, arrastrándolos a la caché en cada visita	La tasa de fallos de L1d se mantiene baja (~2.5% a 1k) porque las páginas activas del asignador viven en L1; el costo se manifiesta como latencia de cargas dependientes
Thrashing de L2 en entradas largas	La tabla de PD, el búfer temporal de prefijos y la lista de tokens de salida se asignan de nuevo en cada llamada	La tasa de fallos de L2 asciende del 12% con 128 tokens al 50% con 16k a medida que la huella de asignaciones acumuladas supera la L2 de 2 MB por núcleo

Referencia sobre cuellos de botella del tokenizador, mecanismos e impactos medidos.

El costo dominante es la asignación por coincidencia. A 1k tokens, la implementación de referencia completa (ejecuta) aproximadamente 7M de instrucciones por codificación con un IPC de 2.8, la mayoría en llamadas al asignador y conversiones de cadenas. Los fallos de L2 solo importan pasado ~1k tokens, una vez que la huella de asignación acumulada desborda la caché por núcleo.

Latencia p50 y p99 del tokenizador de referencia por tamaño de entrada.

Tasa de fallos de caché L2 del tokenizador de referencia por tamaño de entrada.

Bytes asignados por codificación del tokenizador de referencia en distintos tamaños de entrada.

La asignación por token es constante: alrededor de 2 KB y ~18 asignaciones por token, independientemente del tamaño de la entrada. La no linealidad de la latencia proviene de L2: los bytes acumulados superan los 2 MB alrededor de los 1k tokens, la tasa de fallos asciende del 8% a ~50%, y la curva de p99 se flexiona para coincidir.

Comparamos tres tokenizadores de producción, todos ejecutando el mismo algoritmo Unigram contra el mismo modelo XLM-RoBERTa:

Motor	Lenguaje	Trie
Hugging Face	Rust	Trie de prefijos con hijos en HashMap
SentencePiece	C++	Trie de matriz doble Darts
Tokenizador de IREE	C	Trie de matriz doble Darts

Implementaciones de tokenizadores, lenguajes y representaciones de trie usadas en la comparación.

Vinculamos SentencePiece e IREE a través de FFI directo en C/C++ en lugar de sus wrappers de Rust; los wrappers añaden asignaciones por llamada y conversiones de cadenas que no forman parte del costo de la biblioteca subyacente.

Todos los motores se compilan con optimizaciones completas (O3, segmentación nativa, optimización en tiempo de enlace). Las mediciones se ejecutan fijadas a un núcleo silencioso en un Intel Xeon Platinum 8488C. Para cada motor y tamaño de entrada, recopilamos la latencia de reloj de pared (p50 y p99, 10 000 iteraciones después de 1000 de calentamiento), instrucciones completadas a través de Valgrind cachegrind, tasas de IPC y fallos de caché de los contadores de hardware de perf stat, y asignaciones de montón contadas por un envoltorio de asignador global alrededor de la ventana medida.

A 514 tokens (el +2 sobre 512 es la inyección BOS/EOS):

Implementación	Latencia p50	Instrucciones	IPC	Asignaciones
Hugging Face	349 µs	3.60M	2.89	7295
SentencePiece	128 µs	1.83M	3.39	1559
IREE	112 µs	2.28M	3.06	1

Latencia del tokenizador, número de instrucciones, IPC y asignaciones en 514 tokens.

SP e IREE se sitúan en aproximadamente un tercio de la latencia de la referencia. Completan aproximadamente la mitad de instrucciones, se ejecutan a un IPC más alto y asignan de uno a dos órdenes de magnitud menos.

SentencePiece e IREE utilizan el trie de matriz doble introducido por Aoe en 1989 (Aoe, 1989; Karoonboonyanan). El trie está codificado en dos matrices de enteros planos, base y check:

cpp

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

Una búsqueda de hijos es:

cpp

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

Cada paso del recorrido del trie necesita solo dos lecturas de matriz, una suma de enteros y una comparación, sin funciones hash, sin búsqueda de punteros y sin asignación de montón por nodo. La construcción coloca cada nodo de modo que sus hijos caigan en ranuras libres en la matriz de validación, permitiendo que varios padres compartan regiones siempre que sus hijos difieran en el byte que siguen.

Para el vocabulario de 250K de XLM-RoBERTa, todo el trie cabe en ~9 MB de memoria contigua (~780K ranuras × 12 bytes para el desplazamiento, la validación y el ID de token por ranura). El conjunto de trabajo activo de una sola codificación es del orden de 100 KB, cómodamente en L2, y el prefetcher del hardware se fija en el patrón de acceso regular.

La referencia, por el contrario, mantiene un mapa hash de hijos por nodo, lo que cuesta aproximadamente cuatro cargas dependientes por paso de byte. Aplica hash al byte, carga el cubo, sigue un puntero a la entrada del cubo, sigue otro puntero al nodo hijo en el montón y luego consulta su propio mapa hash para el siguiente byte. Los objetos del montón se dispersan y la mayoría de las cargas fallan en la caché.

Tanto SP como IREE almacenan el ID del token directamente en el nodo del trie. La implementación del trie de referencia devuelve solo los bytes coincidentes, por lo que el codificador tiene que asignar una cadena nueva para cada coincidencia, buscarla en un mapa hash secundario para recuperar el ID del token y leer la puntuación de un vector separado. SP devuelve el ID como el valor almacenado del trie y lee la puntuación de una matriz plana de números de coma flotante:

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 utiliza una API de cursor con estado en lugar de devolver todas las coincidencias en una sola llamada, pero el modelo de costos es el mismo: los IDs de tokens y las puntuaciones son accesibles como índices de matriz plana, sin asignación ni hash en el propio recorrido del trie. IREE asigna solo un búfer de salida por codificación; SP asigna además un nodo de celosía por coincidencia durante la PD, totalizando aproximadamente 1559 asignaciones con 514 tokens.

Antes de cambiar el trie, aislamos el costo del algoritmo del costo de implementación: ¿qué tan rápido se ejecuta la referencia con el trabajo innecesario eliminado?

La línea base mantiene el trie de hijos con mapas hash de la referencia, pero realiza dos cambios. Una estructura temporal propiedad del invocador contiene la tabla de PD, los bytes preprocesados y los IDs de tokens de salida, por lo que la ruta crítica no realiza asignaciones después del calentamiento. El ID del token y la puntuación se almacenan directamente en el nodo del trie, eliminando la conversión de cadenas por coincidencia y la búsqueda en el mapa hash secundario.

Bucle 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 es el mismo algoritmo, con la misma forma de trie y el mismo patrón de acceso, solo que sin asignaciones y sin búsquedas redundantes. Resultados con 514 tokens:

Motor	p50	Instrucciones	IPC	Asignaciones
Hugging Face	326 µs	3.66M	2.86	7295
SentencePiece	127 µs	1.81M	3.55	1559
IREE	111 µs	1.58M	3.26	1
Línea base	156 µs	1.53M	2.62	0

El punto de referencia sin asignaciones comparado con implementaciones de tokenizadores existentes en 514 tokens.

Eliminar la materialización de cadenas por coincidencia y la búsqueda en el mapa hash secundario reduce las instrucciones 2.4× frente a la referencia. El IPC disminuye con ellas (2.86 → 2.62) porque la búsqueda de punteros en el mapa hash, antes oculta tras el trabajo del asignador, es ahora el costo dominante por byte.

Latencia p50 y p99 del tokenizador de referencia y del punto de referencia sin asignaciones por tamaño de entrada.

Tasa de fallos de caché L2 del tokenizador de referencia y del punto de referencia sin asignaciones por tamaño de entrada.

La línea base reduce la latencia p50 entre 2 y 3× frente a la referencia en cada tamaño, y su tasa de fallos de L2 se mantiene cerca del 2-3% hasta 2k tokens frente al 8-48% de la referencia. El costo restante es la búsqueda de punteros en el HashMap, que la siguiente sección aborda.

El trie de mapa hash es una búsqueda de punteros. SP e IREE resuelven esto con un trie de matriz doble (consulte la sección anterior) y tomamos prestada la misma estructura de datos. La diferencia es que SP e IREE son bibliotecas de uso general que admiten entradas de flujo continuo, desplazamientos de salida y múltiples modos de codificación; esa flexibilidad les cuesta una contabilidad adicional alrededor del trie (una celosía en SP, una canalización de ocho etapas en IREE). No necesitamos nada de eso, por lo que integramos el trie directamente en el bucle de Viterbi y descartamos el 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
    }
}

Un paso de byte cuesta dos lecturas de matriz, una suma de enteros y una comparación. Todo el trie ronda los 9 MB, pero cualquier codificación individual solo recorre ~100 KB de él, por lo que los datos activos permanecen en L2.

Motor	p50	p99	Instrucciones	% de fallos de L2	% de fallos de L3
Hugging Face	327 µs	3340 µs	3.66M	8.17%	14.66%
SentencePiece	127 µs	1140 µs	1.82M	4.74%	4.07%
IREE	111 µs	132 µs	1.61M	5.82%	3.87%
Línea base	155 µs	1170 µs	1.53M	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	6.45%	11.42%

Latencia del tokenizador, instrucciones y tasas de fallos de caché tras adoptar el trie de doble arreglo.

El tiempo de reloj de pared se reduce 2.3× desde la línea base y 4.8× desde la referencia. Las instrucciones disminuyen otro 28% respecto a la línea base. Eliminar la celosía y la canalización nos permite completar 1.10M de instrucciones por codificación frente a los 1.82M de SP y 1.61M de IREE con la misma forma de trie; la diferencia es la contabilidad que mantienen para las APIs de propósito general que no necesitamos.

El trie Darts de la Optimización 1 necesita dos cargas dependientes por paso de byte. Primero el desplazamiento base del padre, luego la entrada check en la ranura del hijo candidato para confirmar que el padre lo posee. La entrada check solo valida la propiedad. Se puede responder a la misma pregunta mediante un mapa de bits por nodo que registre qué bytes tienen hijos. Por la construcción del trie de matriz doble, el bit del byte b en el mapa de bits del padre se establece exactamente cuando la ranura candidata para ese byte es propiedad del padre. El mapa de bits y la matriz check llevan la misma información, por lo que podemos eliminar por completo la matriz check de la estructura en tiempo de ejecución. Los accesos en la ruta crítica no se comprueban porque la construcción del trie y la estructura del bucle ya garantizan los límites.

La búsqueda en el mapa de bits se compila en una sola prueba de bits contra una palabra de 64 bits, que se ejecuta en aproximadamente un ciclo. La instrucción POPCNT relacionada, que cuenta todos los bits establecidos en un registro, es lo que otros diseños de tries indexados por mapas de bits usan para calcular un desplazamiento de hijo directamente desde el mapa de bits. No lo necesitamos porque la construcción Darts ya almacena ese desplazamiento en el campo base del nodo.

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

Ya que estamos en ello, empaquetamos los cuatro campos por nodo (mapa de bits, base, ID de token y puntuación) en una sola línea de caché de 64 bytes. Una sola visita al nodo ahora trae todo: la puntuación y el ID de token que necesitamos en los nodos terminales, además del mapa de bits y la base para el siguiente paso. La matriz check solo se usa durante la construcción y se descarta del diseño en tiempo de ejecución. La indexación de la ruta crítica no está comprobada porque la construcción del trie y la estructura del bucle ya garantizan los límites. El equilibrio es el Espacio: a 64 bytes por nodo × ~780K ranuras, el trie crece de ~9 MB a ~50 MB.

Resultados con 514 tokens:

Motor	p50	p99	Instrucciones	Accesos a L2	% de fallos de L2	% de fallos de L3
Hugging Face	327 µs	3340 µs	3.66M	15.0K	8.17%	14.66%
SentencePiece	127 µs	1140 µs	1.82M	7.5K	4.74%	4.07%
IREE	111 µs	132 µs	1.61M	4.7K	5.82%	3.87%
Línea base	155 µs	1170 µs	1.53M	6.1K	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	4.6K	6.45%	11.42%
+ Mapa de bits y empaquetado en línea	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

Resultados del tokenizador en 514 tokens después de agregar bitmap y empaquetado en línea.

El tiempo de reloj de pared disminuye sistemáticamente otro 4.5% con 514 tokens y crece con la longitud de la entrada, alcanzando el 6-7% a 4k y 16k. Descartar la matriz check convierte el paso del trie por byte de dos cargas de línea de caché a una, lo que supone 2.5× menos accesos a L2 por codificación (1.8K frente a los 4.6K del Darts simple). La tasa de fallos salta del 6% al 20%, pero la mayor parte de eso es el denominador: con menos de la mitad de accesos, los fallos que tenemos ocupan una proporción mayor.

Los datos del trie ocupan aproximadamente 50 MB (780 000 nodos de 64 bytes cada uno). En un proceso de Linux predeterminado, esa memoria está respaldada por páginas de 4 KB, por lo que todo el trie abarca unas 12 000 páginas virtuales distintas, muy por encima de lo que el búfer de traducción de lookaside (TLB) de datos de primer nivel de la CPU puede contener (Sapphire Rapids tiene 96 entradas). Cada paso de Viterbi toca un nodo diferente, y durante una codificación de 512 tokens gastamos aproximadamente 9000 ciclos en recorridos de tablas de páginas, alrededor del 3% del presupuesto por codificación.

La solución consiste en respaldar el trie con páginas grandes de 2 MB en lugar de las de 4 KB. Los mismos 50 MB ahora abarcan 25 páginas, caben por completo en el búfer de traducción de lookaside y los propios directorios de tablas de páginas dejan de competir con el trie por la caché L2.

Linux tiene dos formas de respaldar la memoria con páginas de 2 MB. La oportunista es la de páginas grandes transparentes (THP): su programa le pide al núcleo que actualice una región de memoria de páginas de 4 KB a 2 MB, y un hilo en segundo plano del núcleo intenta hacerlo cuando tiene tiempo y memoria física contigua disponible. La otra alternativa es asignar el trie directamente desde un grupo de páginas grandes pre-reservado que el núcleo aparta en el arranque:

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

El grupo debe existir en el host (vm.nr_hugepages configurado en el arranque). En nuestras instancias de producción, se reservan 10 561 páginas grandes; el trie consume 24 de ellas. Tras el mmap, /proc/<pid>/smaps confirma la región: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

La ganancia es del 3 al 12% en el reloj de pared en todos los tamaños de entrada, consistente y proporcional a la longitud del conjunto de trabajo:

Tokens	Sin páginas grandes	Con páginas grandes	Δ
130	15.7 µs	15.2 µs	−3.6%
514	65.4 µs	63.1 µs	−3.4%
1026	129.5 µs	125.3 µs	−3.3%
4098	773 µs	679 µs	−12.0%
16 386	3808 µs	3554 µs	−6.8%

Latencia del tokenizador con y sin huge pages en distintos tamaños de entrada.

La mayor ventaja se obtiene con 4k tokens, donde el conjunto de trabajo es lo suficientemente grande como para que el tráfico de la tabla de páginas compitiera activamente con los datos del trie por el ancho de banda de L2. Más allá de 4k, la ganancia se reduce porque los fallos de L3 dominan y los recorridos de la tabla de páginas representan una parte menor del tiempo total.

Juntando las tres optimizaciones, aquí está el motor final medido frente a cualquier otro tokenizador de RoBERTa que probamos. Junto con los binarios nativos en C++ de SentencePiece y en C de IREE, también realizamos pruebas de rendimiento con las crates contenedoras de Rust listas para usar a las que recurriría un usuario de producción: sentencepiece y iree-tokenizer. La crate sentencepiece mide una latencia entre 1.6 y 1.9× mayor que el binario nativo de C++ en cada tamaño de entrada, y la sobrecarga proviene de que el wrapper asigna una lista nueva de fragmentos de tokens, cada uno conteniendo su propia copia del texto del fragmento, en cada codificación. La crate iree-tokenizer dimensiona su búfer interno para cada entrada, lo que evita una asignación constante por codificación que el binario nativo de IREE paga independientemente del tamaño de la entrada, y eso importa más en entradas cortas donde la asignación de otro modo dominaría el trabajo de tokenización real. Con longitudes de entrada de producción, el costo constante se amortiza y la sobrecarga propia por llamada del wrapper al copiar los tokens de vuelta a Rust eleva su latencia por encima de la del binario nativo.

Latencia p50 y p99 por codificación en distintas implementaciones de tokenizadores y tamaños de entrada.

El motor final ejecuta el mismo Viterbi sobre el mismo vocabulario de 250 000 tokens, no asigna nada en la ruta crítica y produce una salida exacta en los tokens en comparación con la referencia. Cada paso de byte es ahora una única carga de línea de caché de 64 bytes, una prueba de mapa de bits y una suma de enteros, frente a una sonda de HashMap, una llamada al asignador y varias ramificaciones de casos especiales en la implementación base. Las instrucciones por codificación cayeron de 3.66M a 1.04M, una caída de 3.5×. El reloj de pared coincide con esa proporción en entradas cortas y se amplía aún más en entradas largas, donde las asignaciones por token de la referencia comienzan a desbordar L2 y L3.

En la práctica, este trabajo redujo la utilización de la CPU en la capa de preprocesamiento de nuestra pila de inferencia entre 5 y 6× y recortó milisegundos de dos dígitos en la latencia del reordenador.

La mayor parte de la reducción de la latencia provino de cambios ligeros que eliminaron el trabajo desperdiciado: prescindir de las asignaciones por codificación, reemplazar el trie de hijos con mapa hash por una matriz doble y eliminar la sobrecarga de la API genérica. El uso del mapa de bits por nodo existente como comprobación de validez y el respaldo del trie con páginas grandes de 2 MB combinados representaron un 10-20% adicional sobre el cambio mayor a un trie de matriz doble, dependiendo del tamaño de la entrada.

Las crates contenedoras de Rust listas para usar alrededor de SentencePiece e IREE ilustran el mismo punto a la inversa. Además de los tokenizadores nativos en C y C++, la frontera FFI y las asignaciones por llamada que introducen los wrappers son visibles en los números de latencia. El código fuente en Rust para el codificador Viterbi final está disponible en github.com/perplexityai/pplx-garden.

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

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

Tokenizador de IREE — 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

Páginas grandes (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}
}

Motivación

El algoritmo de Viterbi

Implementación de referencia

Una nota sobre el preprocesamiento

Dónde gasta su tiempo la implementación de referencia

Cómo medimos

Por qué SentencePiece e IREE son más rápidos: el trie de matriz doble

Línea base: una adaptación sin asignaciones de la referencia

Optimización 1: trie de matriz doble sin abstracciones adicionales

Optimización 2: Mapa de bits y empaquetado en línea

Optimización 3: Páginas enormes para el trie

Comparación final

Reflexiones finales

Referencias

Citación