Resumen Técnico: Tokenización mediante Relajaciones Convexas

Enunciado del Problema

La tokenización es un componente fundamental de la tubería de Procesamiento del Lenguaje Natural (PLN), que convierte cadenas de bytes en secuencias de tokens para los modelos de lenguaje (ML). Aunque investigaciones recientes sugieren una correlación entre la eficiencia de compresión de la tokenización y el rendimiento de los ML aguas abajo, encontrar un tokenizador óptimo es un problema NP-difícil. Los métodos actuales de vanguardia, como la Codificación Byte-Pair (BPE) y Unigram, dependen de algoritmos voraces. Estos métodos toman decisiones localmente óptimas (por ejemplo, fusionar iterativamente los pares de tokens más frecuentes) sin considerar la optimalidad global del vocabulario resultante. En consecuencia, pueden generar tokens intermedios innecesarios y no lograr la máxima compresión. El desafío central abordado por este artículo es cómo aproximar un tokenizador globalmente óptimo de manera eficiente, superando las limitaciones de las heurísticas voraces.

Metodología

Los autores proponen ConvexTok, un algoritmo de tokenización novedoso que formula la construcción de un tokenizador como un programa lineal (PL) derivado de una relajación convexa de un programa entero (PE).

1. Formulación en Grafo

El problema se reformula primero como un problema de camino más corto en un grafo acíclico dirigido (DAG):

• Vértices: Representan las posiciones entre bytes en las cadenas de bytes del conjunto de datos.
• Aristas:
  • Aristas-byte: Conectan bytes adyacentes (representando caracteres individuales).
  • Aristas-token: Conectan vértices no adyacentes, representando tokens potenciales de múltiples bytes.
• Coloreado: Las aristas-token se colorean según la secuencia de bytes específica que representan. Un "color" corresponde a un token único.
• Objetivo: Encontrar un camino desde el inicio hasta el final del grafo que minimice la longitud total del camino (compresión) utilizando un vocabulario de a lo sumo $K$ colores (tokens) distintos.

2. Programación Entera (PE)

El problema del grafo se traduce en un Programa Entero. Los autores definen matrices de incidencia para las aristas libres (aristas-byte) y las aristas con costo (aristas-token), junto con una matriz de partición de colores. Las variables de optimización son vectores binarios que representan:

• Qué aristas se utilizan en la segmentación ($f$ para libres, $p$ para con costo).
• Qué colores (tokens) se seleccionan para el vocabulario ($c$).
  El objetivo es minimizar la longitud total del camino sujeto a restricciones de flujo (asegurando un camino válido) y una restricción de presupuesto (limitando el número de colores seleccionados a $K$).

3. Relajación Convexa (PL)

Dado que resolver el PE es NP-difícil, los autores relajan las restricciones discretas ($x \in \{0, 1\}$) a intervalos continuos ($x \in [0, 1]$). Esto transforma el problema en un Programa Lineal (PL), que puede resolverse de manera eficiente utilizando solucionadores estándar (específicamente, el método PDLP en NVIDIA CuOPT).

• El Poliedro de Tokenización: El espacio de soluciones de este PL relajado permite "tokens parciales" (valores fraccionarios), representando una combinación convexa de vocabularios potenciales.

4. Esquemas de Redondeo

Dado que los ML requieren vocabularios discretos, la solución fraccionaria del PL debe discretizarse. El artículo propone y evalúa tres esquemas de redondeo:

• Determinista (Det): Selecciona los $K$ colores con los valores PL más altos.
• Sesgado (Bias): Clasifica los colores según la relación entre su valor PL y la longitud del token ($c / \text{longitud}(c)$), favoreciendo tokens más cortos cuando las puntuaciones son comparables.
• Solo Entero (Int): Selecciona solo aquellos colores donde el valor del PL ya está cerca de 1 (esencialmente "forzados" por la relajación), lo que a menudo resulta en un vocabulario más pequeño que el presupuesto $K$.

Contribuciones Clave

1. Formulación: El artículo proporciona la primera formulación de la construcción de un tokenizador como un programa lineal mediante técnicas poliedrales, vinculando explícitamente la tokenización con problemas de camino más corto en grafos coloreados.
2. Algoritmo (ConvexTok): Introduce un nuevo algoritmo que aproxima un tokenizador globalmente óptimo, evitando los óptimos locales inherentes a los enfoques voraces como BPE.
3. Certificación de Optimalidad: La solución del PL proporciona una cota inferior demostrable sobre la compresión alcanzable por cualquier tokenizador en un conjunto de datos dado. Esto permite a los investigadores certificar qué tan cerca está un tokenizador específico (por ejemplo, BPE o ConvexTok) del óptimo teórico.
4. Análisis de Redondeo: El artículo evalúa sistemáticamente tres estrategias de redondeo distintas para convertir soluciones fraccionarias del PL en tokenizadores funcionales.

Resultados Experimentales

Los autores evaluaron ConvexTok frente a BPE en varios tamaños de vocabulario (de 8k a 256k) utilizando el conjunto de datos ClimbMix400B y transformadores de solo decodificador estilo GPT.

• Calidad de la Solución PL: A medida que aumenta el tamaño del vocabulario, la solución del PL se vuelve cada vez más entera (más cercana a 0 o 1), lo que sugiere que a escalas mayores, las elecciones de tokens óptimos son menos ambiguas.
• Brecha de Optimalidad: La cota inferior del PL revela que los tokenizadores existentes están notablemente cerca del óptimo. En tamaños de vocabulario comunes (128k, 256k), tanto BPE como las variantes de ConvexTok se encuentran dentro del 1% de la cota de compresión óptima.
• Métricas Intrínsecas:
  • El esquema de redondeo Sesgado (Bias) superó consistentemente a BPE y a otros esquemas en métricas intrínsecas como la utilización del vocabulario, la relación tipo-token y la tasa de compresión.
  • Se encontró que BPE es más estable que las variantes de ConvexTok al reentrenarse en diferentes subconjuntos aleatorios de datos, probablemente debido a su naturaleza local impulsada por la frecuencia.
• Rendimiento en Modelado de Lenguaje:
  • Bits por Byte (BpB): El esquema de redondeo Determinista (Det) logró consistentemente las mejores puntuaciones de BpB, superando a menudo a BPE, particularmente en tamaños de vocabulario más grandes.
  • Tareas Aguas Abajo (CORE): Los resultados en los puntos de referencia aguas abajo (razonamiento, opción múltiple, sentido común) fueron mixtos. Aunque las variantes de ConvexTok fueron competitivas con BPE, no mostraron una ventaja consistente y significativa en todas las tareas y profundidades de los modelos.
• Estabilidad: BPE demostró una mayor estabilidad con respecto al muestreo de datos de entrenamiento en comparación con ConvexTok, aunque el esquema de redondeo Solo Entero mostró una mayor estabilidad que las otras variantes de ConvexTok.

Significado y Afirmaciones

El artículo afirma que la tokenización optimizada globalmente es una alternativa prometedora a los métodos basados en fusiones voraces locales. El significado principal radica en la capacidad de:

1. Resolver la Tokenización Globalmente: Demostrar que la tokenización puede abordarse mediante optimización convexa en lugar de heurísticas voraces.
2. Certificar el Rendimiento: Proporcionar una cota inferior rigurosa para medir qué tan lejos está cualquier tokenizador del óptimo teórico. Los autores encontraron empíricamente que, en tamaños de vocabulario estándar, los métodos actuales ya están muy cerca de este óptimo (dentro del 1%).
3. Mejorar la Compresión: Mostrar que, aunque BPE ya es casi óptimo, esquemas de redondeo específicos (como Bias) pueden producir métricas de compresión intrínseca ligeramente mejores.

Los autores mantienen modestia con respecto a las mejoras en tareas aguas abajo, señalando que, aunque BpB mejoró consistentemente, las ganancias en las tareas CORE aguas abajo fueron menos consistentes. Concluyen que, si bien su método ofrece un marco teóricamente superior y cotas certificables, las ganancias prácticas sobre métodos voraces altamente ajustados como BPE son incrementales en el contexto del entrenamiento actual de modelos de lenguaje grandes.