Resumen Técnico: Tokenización con Árboles de División (ToaST)

Enunciado del Problema

La tokenización es un paso fundamental en el procesamiento del lenguaje natural, sin embargo, los métodos existentes a menudo dependen de heurísticas codiciosas que pueden no optimizar la compresión o el rendimiento en tareas posteriores. Mientras que la Codificación de Pares de Bytes (BPE) minimiza la cantidad de tokens mediante una estrategia de fusión codiciosa, es una aproximación heurística. Trabajos anteriores han establecido que encontrar un tokenizador que maximice la compresión es NP-completo, incluso sobre alfabetos acotados. Además, la relación entre la compresión y el rendimiento en tareas posteriores sigue siendo debatida; aunque algunos estudios sugieren una correlación, otros argumentan que la compresión por sí sola es insuficiente para explicar la calidad de la tokenización. Las alternativas existentes, como UnigramLM o PathPiece, utilizan procedimientos de inferencia diferentes (por ejemplo, inferencia ablativa de arriba hacia abajo o inferencia de camino más corto), pero aún enfrentan desafíos en la optimización global y la escalabilidad computacional.

Metodología

Los autores introducen Tokenización con Árboles de División (ToaST), un método de tokenización de subpalabras que desacopla la construcción de tokens candidatos de la selección del vocabulario final. El enfoque consta de tres etapas principales:

1. Construcción del Árbol de División

A diferencia de BPE, que construye tokens de abajo hacia arriba, o UnigramLM, que aprende probabilidades de arriba hacia abajo, ToaST construye un árbol binario completo para cada pretoken único en el corpus de entrenamiento, independientemente de cualquier vocabulario.

• Preprocesamiento: Los datos de entrenamiento se dividen en pretokens utilizando una expresión regular.
• Lógica de División: Para un pretoken dado, el algoritmo lo divide recursivamente en dos partes no vacías. El punto de división se elige de manera determinista para maximizar el recuento mínimo de los n-gramas de bytes resultantes (izquierda y derecha) ($\max \min(c_p, c_{p'})$) basándose en estadísticas de n-gramas precalculadas del corpus.
• Estructura: Este proceso continúa hasta que las hojas son bytes individuales. Los nodos de estos árboles forman el conjunto de todos los tokens candidatos. Esta construcción es independiente del vocabulario final y no requiere entrenamiento iterativo.

2. Inferencia Recursiva

Dado un vocabulario $V$, la tokenización se realiza mediante un descenso recursivo por el árbol de división:

• Comenzando en la raíz (el pretoken completo), el algoritmo verifica si el nodo actual está en $V$.
• Si el nodo está en $V$, se emite como un token.
• Si no, el algoritmo procesa recursivamente a los dos hijos.
• Propiedades: Este procedimiento asegura que cualquier vocabulario que contenga todos los bytes individuales necesarios produzca una tokenización válida. Eliminar un token del vocabulario simplemente fuerza a la inferencia a descender más profundamente en el árbol, sin efectos en cascada sobre otros tokens, a diferencia de los métodos basados en fusión.

3. Selección de Vocabulario mediante Programación Entera

La innovación central es formular la selección de vocabulario como un Programa Entero (PE) para minimizar el recuento total de tokens en el corpus de entrenamiento.

• Variables: Variables binarias $x_i$ indican si el token candidato $i$ está en el vocabulario. Variables binarias $z_{jk}$ indican si el nodo $k$ en el árbol de división $j$ se emite durante la inferencia.
• Objetivo: Minimizar el recuento ponderado total de tokens emitidos: $\min \sum_{j} c_j \sum_{k} z_{jk}$.
• Restricciones:
  • Tamaño del Vocabulario: La suma de los tokens seleccionados debe ser igual al tamaño objetivo $m$.
  • Cobertura: Para cada camino desde una hoja hasta la raíz, exactamente un nodo debe ser seleccionado (asegurando que todo el pretoken esté cubierto).
  • Consistencia: Un nodo solo puede ser emitido ($z_{jk}=1$) si está en el vocabulario ($x_i=1$) y ninguno de sus antepasados lo está.
• Resolución: El PE se relaja a un Programa Lineal (PL). En la práctica, la relajación del PL es "casi entera", lo que significa que la solución contiene muy pocos valores fraccionarios. Se aplica una heurística de redondeo simple para obtener una solución entera que es demostrablemente casi óptima (dentro de una fracción despreciable del óptimo global).

Contribuciones Clave

1. Nuevo Marco de Tokenización: ToaST introduce un enfoque basado en árboles de división que evita las aproximaciones codiciosas de BPE y las restricciones específicas de inferencia de UnigramLM.
2. Optimización Global: Al formular la selección de vocabulario como un PE con una relajación PL ajustada, ToaST encuentra un vocabulario que minimiza globalmente los recuentos de tokens para un conjunto dado de árboles de división, en lugar de depender de decisiones codiciosas locales.
3. Escalabilidad: El método escala cuadráticamente con el número de árboles de división, permitiendo el procesamiento de grandes corpus (que cubren el 99% de los recuentos de pretokens) dentro de tiempos de entrenamiento factibles.
4. Diseño Desacoplado: La separación de la construcción del árbol (basada en estadísticas del corpus) y la selección del vocabulario (basada en optimización) permite extensiones flexibles, como incorporar preferencias morfológicas o a nivel de carácter sin reentrenar el modelo de optimización.

Resultados Experimentales

Los autores evaluaron ToaST en texto inglés utilizando el conjunto de datos CulturaX y lo compararon con BPE, WordPiece y UnigramLM.

• Compresión: En tamaños de vocabulario de 40,960 y superiores, ToaST reduce la cantidad de tokens en más del 11% en comparación con todas las líneas base. Esto se mide en bytes por token.
• Distribución de Tokens: ToaST reduce significativamente la frecuencia de tokens "Hoja" (alternativas de un solo byte) en un factor de 14–19 en comparación con las líneas base en un tamaño de vocabulario de 65,536. Por el contrario, produce sustancialmente más tokens "Raíz" (pretokens completos), lo que indica una mejor retención de unidades semánticas.
• Eficiencia de Rényi: ToaST logra una mayor eficiencia de Rényi (con $\alpha=2.5$), lo que indica una distribución de tokens más uniforme y menos tokens de alta frecuencia, lo cual a menudo se correlaciona con un mejor rendimiento en tareas posteriores.
• Rendimiento en Tareas Posteriores: En experimentos de entrenamiento de modelos de lenguaje de 1.5 mil millones de parámetros (nanochat), ToaST logró la puntuación CORE más alta (un promedio de 22 benchmarks), superando a las líneas base entre un 2.6% y un 7.6%. Superó significativamente a BPE y UnigramLM, y fue el mejor rendimiento en 13 de 22 tareas individuales.
• Calidad de la Optimización: Se encontró que la relajación del PL era excepcionalmente ajustada. En 128 instancias del problema, la brecha relativa máxima entre la solución entera redondeada y el límite del PL fue de $5.76 \times 10^{-7}$, con muchas instancias siendo completamente enteras.

Significado y Afirmaciones

El artículo afirma que ToaST demuestra el valor de optimizar la tokenización directamente para la compresión utilizando un marco de optimización global en lugar de depender de heurísticas codiciosas. Los autores argumentan que la compresión superior conduce a una ventana de contexto efectiva más grande y, en consecuencia, a un mejor rendimiento en tareas posteriores.

El significado del trabajo radica en:

• Practicidad: A pesar de la NP-complejidad teórica de la tokenización óptima, la relajación del PL hace que el enfoque sea computacionalmente factible y práctico para el entrenamiento a gran escala.
• Rendimiento: Los resultados empíricos sugieren que la reducción del 11% en el recuento de tokens se traduce en ganancias medibles en el rendimiento del modelo de lenguaje (puntuación CORE), apoyando la hipótesis de que una mejor compresión se correlaciona con una mejor utilidad del modelo.
• Flexibilidad: La arquitectura permite futuras extensiones, como el manejo de caracteres multibyte o divisiones morfológicas, modificando la jerarquía de construcción del árbol sin alterar la lógica de optimización del vocabulario.

Los autores señalan limitaciones, específicamente que los experimentos se realizaron exclusivamente en texto inglés, y que la efectividad del entrenamiento en los pretokens agregados superiores puede variar para idiomas sin delimitación por espacios. También revelan el uso de LLMs para la implementación del código y la generación de figuras.