💬 NLP

Tokenisation over Bounded Alphabets is Hard

Este artículo demuestra que la tokenización sobre alfabetos acotados, incluyendo los casos binario y unario, es fundamentalmente NP-completa y APX-dura, estableciendo que su intratabilidad computacional es una barrera inherente en lugar de un artefacto de los grandes alfabetos de entrada y explicando la necesidad de enfoques heurísticos en los algoritmos prácticos actuales.

Autores originales: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Publicado 2026-08-11

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando enviar un mensaje secreto a un amigo, pero la única forma de enviarlo es dividiendo tus palabras en trozos diminutos y previamente aprobados. Si envías "superduper", es posible que tengas que dividirlo en "super" y "duper" en lugar de la palabra completa, porque el diccionario de tu amigo solo tiene esas dos piezas. Esto es el corazón de la tokenización, el primer paso para enseñar a las computadoras a entender el lenguaje humano. Antes de que una computadora pueda leer una oración, debe trocearla en estos "tokens" manejables (como piezas de Lego). El objetivo es trocear el texto de tal manera que se utilicen la menor cantidad de piezas posible, haciendo que el mensaje sea más corto y rápido de enviar. Esto se llama compresión. Si puedes comprimir un libro en menos piezas, la computadora puede leerlo más rápido y aprender de él de manera más eficiente. Durante años, los científicos han estado construyendo algoritmos astutos y codiciosos —como un niño que agarra la pieza de Lego más grande que encuentra— para hacer este troceado automáticamente. Pero una gran pregunta ha persistido: ¿Existe una forma perfecta y matemáticamente óptima de trocear cualquier texto, o estamos atrapados con suposiciones de "suficientemente buenas"?

Este artículo, titulado "Tokenisation Over Bounded Alphabets Is Hard", se sumerge en las profundidades de esa pregunta. Los autores, un equipo de investigadores de la ETH Zürich y la Universidad de Sofía, se propusyer el objetivo de demostrar si encontrar ese método de troceado perfecto es en realidad una pesadilla para las computadoras, incluso cuando las reglas son simples. Se centran en dos formas principales de trocear: la Tokenización Directa, donde eliges el mejor conjunto de piezas de Lego (un vocabulario) todo a la vez, y la Tokenización Bottom-Up, donde comienzas con letras individuales y sigues pegando pares hasta que te quedas sin pegamento (fusiones). El gran giro en su historia es que prueban estos métodos no con el alfabeto infinito y caótico de todos los sonidos humanos posibles, sino con los conjuntos pequeños y fijos que realmente usamos en las computadoras: binario (solo 0s y 1s, como un interruptor de luz) y unario (solo un símbolo único, como una cuerda de cuentas idénticas).

El principal hallazgo del artículo es un rotundo "No, no puedes encontrar fácilmente la solución perfecta". Los autores demuestran que, incluso con los alfabetos más simples posibles —como un mundo hecho solo de ceros y unos—, encontrar la forma óptima de comprimir texto es NP-completo y APX-duro. En lenguaje sencillo, esto significa que no importa cuánta potencia de cómputo le lances al problema, no existe un algoritmo rápido y eficiente que pueda garantizar el mejor resultado posible. No es solo que el problema sea difícil; es que es fundamentalmente difícil. El artículo descarta explícitamente la idea de que la dificultad provenga de la complejidad del lenguaje humano o de alfabetos enormes. En su lugar, demuestran que la barrera existe incluso en los escenarios más simples y restringidos. Además, demuestran que ni siquiera puedes acercarte "lo suficiente" a la respuesta perfecta en un tiempo razonable; no existe un esquema de aproximación de tiempo polinómico (PTAS) que pueda acercarse arbitrariamente a la mejor solución a menos que se resuelva un gran misterio matemático (P = NP).

Los investigadores también abordan el caso unario, donde el alfabeto tiene un solo símbolo (piensa en un mensaje hecho enteramente de la letra "a"). Podrías pensar: "Si solo tengo una letra, ¿qué tan difícil puede ser?". Sorprendentemente, demuestran que incluso aquí, encontrar la forma óptima de trocear el texto es fuertemente NP-completo. Este es un resultado matemático pesado que sugiere que la dificultad no es solo una peculiaridad de los grandes conjuntos de datos; está integrada en la lógica misma de intentar comprimir texto de manera óptima.

Entonces, ¿qué significa esto para el futuro? El artículo no ofrece un nuevo algoritmo mágico para resolver el problema. En su lugar, explica por que las herramientas que usamos hoy, como BPE (Byte-Pair Encoding) y UnigramLM, están obligadas a ser heurísticas, lo que significa que utilizan trucos astutos y suposiciones en lugar de calcular la respuesta perfecta. Los autores argumentan que, debido a que la respuesta perfecta es computacionalmente imposible de encontrar rápidamente, los investigadores deberían dejar de perseguir el "santo grial" del tokenizador óptimo y, en su lugar, enfocarse en construir mejores métodos de aproximación que sean demostrablemente buenos. La puerta a la perfección está cerrada con llave, y la llave no existe; lo mejor que podemos hacer es aprender a elegir la mejor ganzúa que tengamos.

Planteamiento del Problema
Trabajos teóricos recientes han establecido que encontrar un tokenizador óptimo para un conjunto de datos es NP-completo. Sin embargo, estos resultados previos se basan en la suposición de que la tokenización opera sobre alfabetos ilimitadamente grandes. En el procesamiento de lenguaje natural práctico, los tokenizadores operan sobre alfabetos de tamaño fijo y acotado (por ejemplo, bytes con tamaño 256, caracteres Unicode con tamaño ~170,000, o cadenas binarias/de bits con tamaño 2). Sigue siendo una cuestión abierta si la intratabilidad computacional de la tokenización persiste cuando el tamaño del alfabeto está acotado por una constante. Este artículo aborda esta brecha analizando la complejidad de la tokenización sobre alfabetos acotados, investigando específicamente si los tokenizadores óptimos pueden encontrarse eficientemente para alfabetos binarios (tamaño 2) y unarios (tamaño 1).

Metodología
Los autores definen el problema de la tokenización $n$ -aria, donde el alfabeto de entrada $\Sigma$ tiene tamaño $n$ . Analizan dos variantes naturales de la tokenización:

Tokenización Directa: Encontrar un vocabulario $S$ de tamaño $K$ que, al aplicarse de manera óptima a un conjunto de datos, minimice la longitud total comprimida.
Tokenización Bottom-up (de abajo hacia arriba): Encontrar una secuencia de $K$ operaciones de fusión que, aplicadas secuencialmente a un conjunto de datos, minimicen la longitud total comprimida.

La función objetivo utilizada es la longitud comprimida (el número total de tokens tras la codificación), la cual se correlaciona con los costes de entrenamiento e inferencia de los modelos. Los autores emplean técnicas estándar de la teoría de la complejidad para establecer la dureza:

NP-Hardness (NP-dureza): Probada mediante reducciones en tiempo polinomial desde problemas conocidos como NP-duros (específicamente 3-OCC-MAX2SAT y Vertex Cover) hacia los problemas de decisión de tokenización.
APX-Hardness (APX-dureza): Probada mediante reducciones L (reducciones que preservan la aproximación) desde problemas APX-completos. Esto demuestra que los problemas no pertenecen a la clase PTAS (Esquema de Aproximación en Tiempo Polinomial), lo que significa que no pueden aproximarse arbitrariamente bien en tiempo polinomial a menos que P = NP.
Problemas de Brecha (Gap Problems): Los autores definen versiones de brecha de los problemas para derivar constantes explícitas de dureza de aproximación.

Contribuciones Clave y Resultados

La Tokenización Binaria es APX-Hard:
El artículo demuestra que tanto la tokenización directa binaria como la tokenización bottom-up binaria son APX-hard.

Caso Directo: Se demuestra que la tokenización directa binaria no puede aproximarse en tiempo polinomial con una razón de aproximación $\rho < 1.000002$ (a menos que P = NP).
Caso Bottom-up: Del mismo modo, la tokenización bottom-up binaria es APX-hard con una constante de dureza de $\rho < 1.0000001$ .
Estos resultados implican que, incluso para el alfabeto no trivial más simple (binario), encontrar un tokenizador óptimo es computacionalmente intratable, y ningún algoritmo de tiempo polinomial puede garantizar una aproximación arbitrariamente cercana al óptimo.

La Tokenización Unaria es Fuertemente NP-Completa:
Los autores investigan el caso unario (alfabeto de tamaño 1), que es teóricamente la variante "más fácil".

Demuestran que la tokenización directa unaria es fuertemente NP-completa. Esto se logra mediante una reducción del problema Vertex Cover. La prueba establece que la dureza es intrínseca a la estructura del problema y no un artefacto de la representación de la entrada (cadena vs. longitud de cadena).
Para la tokenización bottom-up unaria, el artículo establece que una variante conocida como Optimal Pair Encoding (OPE) es (al menos) débilmente NP-completa, mediante una reducción del problema de la Cadena de Adición (Addition Chain). La complejidad de la tokenización bottom-up unaria estándar sigue siendo una cuestión abierta en este trabajo.

Jerarquía de Dureza:
El artículo establece una jerarquía clara: si la tokenización $n$ -aria es dura, entonces la tokenización $n'$ -aria para todo $n' > n$ también lo es. Consecuentemente, los resultados de dureza para los casos binario y unario se extienden trivialmente a todos los alfabetos acotados más grandes (incluyendo alfabetos de bytes y Unicode).

Significancia y Reivindicaciones
El artículo afirma que estos resultados alteran fundamentalmente la comprensión de la complejidad de la tokenización. Al demostrar que la tokenización sigue siendo difícil incluso sobre alfabetos unarios y binarios, los autores demuestran que la intratabilidad computacional no es un artefacto de alfabetos grandes o de operaciones de fusión complejas. En cambio, es una barrera fundamental inherente al problema de comprimir datos de manera óptima mediante la tokenización.

Estos hallazgos proporcionan una justificación teórica de por qué los algoritmos prácticos actuales, como Byte-Pair Encoding (BPE) y UnigramLM, dependen de heurísticas y estrategias ávidas (greedy) en lugar de una optimización exacta. El artículo concluye que la investigación futura debería centrarse en desarrollar algoritmos de aproximación demostrablemente buenos o en relajar las restricciones del problema, ya que encontrar tokenizadores óptimos exactos es probablemente imposible para cualquier tamaño de conjunto de datos no trivial.

Más como este