¿Qué tan poderosos son los LLM de Difusión en comparación con los LLM autorregresivos clásicos, una vez que se trata la generación como un algoritmo con complejidad temporal y espacial, no solo como un truco de decodificación? Un nuevo artículo de investigación de un equipo de investigadores del Instituto Tecnológico Toyota de Chicago y el MIT da una respuesta formal. Esta nueva investigación compara modelos autorregresivos (ARM), modelos de difusión enmascarada (MDM) y una nueva familia llamada Any-Process MDM (AP-MDM), utilizando la teoría de la complejidad y tareas de razonamiento controlado.
ARM vs MDM: Misma expresividad, diferente tiempo paralelo
ARM utiliza la predicción del siguiente token en un orden estricto de izquierda a derecha. Trabajos anteriores ya muestran que con suficientes pasos intermedios, ARM es Turing completo, por lo que puede representar cualquier función computable en principio, dado suficiente contexto y computación.
MDM, el estilo de difusión discreta utilizado en los LLM de difusión, funciona en una secuencia enmascarada. El modelo comienza a partir de una secuencia completamente enmascarada y desenmascara los tokens de forma iterativa. Puede actualizar muchas posiciones en paralelo y en cualquier orden. MDM se modela como un transformador solo codificador con longitud de contexto (S(n)) y pasos de decodificación (T(n)) para una entrada de tamaño (n).
El equipo de investigación muestra:
MDM puede simular cualquier algoritmo PRAM (Máquina de acceso aleatorio paralelo) con tiempo paralelo (T(n)) utilizando (O(T(n))) pasos de difusión y contexto (S(n)) proporcional al trabajo total. Esto hace que MDM Turing sea completo y le permite igualar el tiempo paralelo ideal en problemas en NC, como la conectividad de gráficos y algunas tareas de lenguaje libre de contexto, donde ARM necesita un tiempo lineal en la longitud de la secuencia.
Por lo tanto, los LLM de difusión ganan eficiencia en problemas paralelizables, no poder expresivo adicional por sí mismos.
La generación de cualquier pedido tiene beneficios limitados
Una pregunta natural es si la generación de cualquier orden es estrictamente más poderosa que la generación de izquierda a derecha.
Para aislar esto, el equipo de investigación define un MDM de cualquier orden (AO-MDM) y un ARM enmascarado correspondiente con la misma arquitectura y un presupuesto de token similar, pero decodificando de forma fija de izquierda a derecha sobre una secuencia rellena de máscaras.
El resultado principal:
Cualquier cálculo realizado por AO-MDM con un token por paso y contexto (S(n)) puede reorganizarse en un cronograma de izquierda a derecha y simularse mediante un ARM enmascarado con una longitud de secuencia (O(S(n))) más un número constante de capas adicionales.
En otras palabras, una vez que se controla el paralelismo y la arquitectura, cualquier generación de órdenes por sí sola no expande la clase de problemas más allá de lo que ARM ya puede manejar.
Tanto ARM como AO-MDM también comparten una limitación de espacio. Con una longitud de contexto (S(n)), no pueden resolver eficientemente problemas que requieren más que aproximadamente (S(n)3) tiempo de serie. Con el contexto polinomial, están efectivamente limitados a problemas de clase P y no pueden manejar tareas difíciles generales de NP simplemente escalando el tiempo de prueba.
Generación de cualquier proceso y AP-MDM
Para ir más allá de estos límites, el equipo de investigación propone Any-Process Generation, instanciado como Any-Process MDM (AP-MDM).
AP-MDM mantiene la vista de difusión enmascarada pero amplía la función de transición con tres operaciones adicionales, además del desenmascaramiento habitual:
reenmascarar: convertir un token ya decodificado nuevamente en el token de máscara M insertar: insertar un nuevo token de máscara en una posición elegida eliminar: eliminar un token de máscara que ya no es necesario
Estos están controlados por un vector de 3 bits por posición (ct,i = (ct,i[1]ct, yo[2]ct, yo[3]). La misma columna vertebral de Transformer predice tanto los logits de contenido como estos bits de control.
remask utiliza el primer bit para decidir si se sobrescribe una posición con M, lo que permite retroceder y autocorregir. insertar y eliminar utilizan el segundo y tercer bits para agregar o eliminar tokens de máscara, de modo que la longitud de la secuencia pueda aumentar o reducirse durante la decodificación.
Desde el punto de vista arquitectónico, AP-MDM solo agrega tres pequeños cabezales lineales encima de un transformador solo con codificador, por lo que es fácil agregarlo encima de los LLM de difusión de estilo MDM existentes.
El resultado teórico clave:
AP-MDM puede simular cualquier algoritmo PRAM con tiempo paralelo óptimo y espacio óptimo, utilizando un contexto proporcional al espacio real (S(n)) en lugar de trabajo total. Con contexto polinomial, AP-MDM puede realizar cálculos en PSPACE, mientras que MDM y ARM estándar bajo el mismo presupuesto de contexto están restringidos a P.
El equipo de investigación también intentó demostrar que existe un AP-MDM de profundidad constante cuyo proceso de generación no puede ser simulado por ningún ARM de profundidad constante o ARM enmascarado, bajo supuestos de complejidad estándar.
Resultados empíricos: Sudoku, Dyck, Gráficos, Paridad
Los experimentos coinciden con la teoría y concretan las diferencias.
Sudokus
El Sudoku, generalizado a cuadrículas (n2 x n2), es NP completo.
AP-MDM alcanza una precisión del 99,28 por ciento con alrededor de 1,2 millones de parámetros y sólo 100 instancias de entrenamiento. Una línea de base ARM con pedidos alcanza el 87,18 por ciento utilizando 1,8 millones de instancias de entrenamiento y aproximadamente 5 veces más parámetros. La mejor línea de base de AO-MDM alcanza el 89,49 por ciento bajo el mismo régimen de big data.
Esto muestra que las operaciones de edición, especialmente la reenmascaramiento, son cruciales para aprovechar el escalamiento del tiempo de prueba en tareas de razonamiento difíciles.
Lenguajes Dyck y restricciones de estilo de codificación.
La investigación también analiza los lenguajes Dyck k de dos caras, que modelan paréntesis coincidentes y son una abstracción central para la sintaxis del código. Demuestra que los modelos ARM fijos no pueden garantizar una generación válida para longitudes arbitrarias, mientras que existe un AP-MDM que genera exactamente el lenguaje Dyck mediante inserción y reenmascaramiento.
Esto coincide con la forma en que las tareas de codificación requieren ediciones conscientes de la estructura bajo restricciones globales, por ejemplo, corchetes equilibrados y alcances consistentes.
Generación de gráficos y edición estructural.
Para tareas de edición de gráficos bajo restricciones globales, AP-MDM utiliza insertar, eliminar y reenmascarar para implementar una secuencia de ediciones estructuradas sobre una representación de gráfico. La precisión informada se mantiene casi perfecta a medida que aumenta el tamaño del gráfico, mientras que ARM se degrada a medida que el gráfico se hace más grande.
Generalización de paridad y longitud.
En paridad, AP-MDM aprende una regla de eliminación local eliminando repetidamente pares de bits, impulsada por reenmascaramiento y eliminación. Se entrena solo en secuencias de longitud 2 y luego logra una generalización del 100 por ciento a longitudes arbitrarias. Las líneas de base de ARM luchan por alcanzar una generalización similar incluso con secuencias de entrenamiento mucho más largas.
Conclusiones clave
Los modelos de difusión enmascarada de cualquier orden son tan expresivos como los modelos autorregresivos una vez que se corrige la arquitectura y el paralelismo; principalmente brindan eficiencia paralela en lugar de nueva potencia computacional. Los modelos de difusión enmascarada pueden simular algoritmos PRAM y lograr una aceleración exponencial en tareas paralelizables en NC, pero con un contexto polinomial permanecen efectivamente limitados a problemas de clase P, similar a los modelos autorregresivos. Any Process MDM extiende los LLM de difusión con operaciones de reenmascaramiento, inserción y eliminación, implementadas a través de un vector de control de tres bits por token, y puede simular PRAM con tiempo paralelo óptimo y espacio óptimo, alcanzando expresividad de nivel PSPACE en un contexto polinómico. En tareas de razonamiento difíciles como el Sudoku generalizado, los lenguajes Dyck, la edición de gráficos y la paridad, AP MDM muestra fuertes ventajas empíricas, por ejemplo, logra aproximadamente un 99,28 por ciento de precisión en el Sudoku con solo 100 instancias de entrenamiento y un presupuesto de parámetros mucho menor que las líneas base de MDM autorregresivas y de cualquier orden. Para dominios como codificación, matemáticas y AI4Science que involucran ediciones estructuradas e historiales de revisión, AP MDM se alinea mejor con los procesos de generación subyacentes que la predicción del próximo token, y sus operaciones de edición son probablemente difíciles de simular con modelos autorregresivos de profundidad constante.
Any-Process MDM es un paso importante porque trata la generación como un algoritmo completo, no solo como una orden de decodificación. El trabajo de investigación muestra que los modelos de difusión enmascarada ya coinciden con el tiempo paralelo de PRAM, pero permanecen en P en un contexto polinómico, similar a los modelos autorregresivos. Al agregar reenmascaramiento, inserción y eliminación, AP-MDM alcanza expresividad a nivel de PSPACE con contexto polinómico y logra fuertes ganancias empíricas en Sudoku, Dyck, edición de gráficos y paridad. En general, AP-MDM presenta argumentos sólidos para que los futuros LLM de vanguardia deberían adoptar la generación de cualquier proceso basada en edición, no solo una autorregresión más rápida.
Consulte el documento y el repositorio. No dude en consultar nuestra página de GitHub para tutoriales, códigos y cuadernos. Además, no dude en seguirnos en Twitter y no olvide unirse a nuestro SubReddit de más de 100.000 ML y suscribirse a nuestro boletín. ¡Esperar! estas en telegrama? Ahora también puedes unirte a nosotros en Telegram.
Asif Razzaq es el director ejecutivo de Marktechpost Media Inc.. Como emprendedor e ingeniero visionario, Asif está comprometido a aprovechar el potencial de la inteligencia artificial para el bien social. Su esfuerzo más reciente es el lanzamiento de una plataforma de medios de inteligencia artificial, Marktechpost, que se destaca por su cobertura en profundidad del aprendizaje automático y las noticias sobre aprendizaje profundo que es técnicamente sólida y fácilmente comprensible para una amplia audiencia. La plataforma cuenta con más de 2 millones de visitas mensuales, lo que ilustra su popularidad entre el público.
🙌 Siga MARKTECHPOST: agréguenos como fuente preferida en Google.