- Los Transformers y los LLM son fuertes en conversación, comprensión de imágenes y completado de código, pero les cuesta ofrecer un rendimiento estable en la planificación de múltiples pasos y el razonamiento de alto nivel
- Este artículo convierte las tareas de planificación y las soluciones óptimas en secuencias de tokens, e incorpora a los datos de entrenamiento incluso la traza de ejecución de cómo A* resuelve el problema
- Searchformer primero imita el proceso de búsqueda de A* y luego se ajusta finamente para producir secuencias de búsqueda más cortas mientras mantiene el plan óptimo
- En experimentos con Sokoban, los modelos de la familia Searchformer resolvieron el 93.7% de las tareas de prueba y usaron en promedio 26.8% menos pasos de búsqueda que una implementación de referencia de A*
- Aunque las trazas de ejecución aumentan la longitud de las secuencias generadas en 10×~100×, el modelo genera planes óptimos para tareas desconocidas con mayor frecuencia incluso usando menos secuencias de entrenamiento que modelos más grandes entrenados solo con soluciones
Lo que hacen bien los Transformers y las tareas de planificación donde son débiles
- Las arquitecturas basadas en Transformers muestran alto rendimiento en varias tareas
- conversación a nivel humano
- comprensión de imágenes de alta calidad
- generación de video
- generación multimodal
- completado de código
- Modelos como los LLM, entrenados con datos a escala de internet, pueden generalizar bien en casos de uso reales
- Pero en tareas de planificación y razonamiento todavía mantienen limitaciones
- Los LLM muestran carencias en tareas de planificación de múltiples pasos
- También aparecen dificultades al realizar razonamiento de alto nivel
Límites de los prompts de razonamiento paso a paso
- Enfoques recientes buscan mejorar el rendimiento guiando a los Transformers para que generen “pensamientos” intermedios antes de responder
- Los prompts de Chain-of-Thought (CoT) y Tree-of-Thoughts (ToT) fomentan que el modelo “piense” por etapas
- Estas técnicas suelen ser efectivas, pero por razones como self-enforcing también pueden empeorar el rendimiento
- Un método que funciona bien en un dataset puede fallar en otro
- Un ejemplo es cuando cambia el tipo de razonamiento requerido, como en razonamiento espacial frente a razonamiento matemático
- Sigue siendo un tema de investigación activo cómo lograr que los Transformers y los LLM realicen de forma estable planificación, toma de decisiones en múltiples pasos y razonamiento
Incluir la dinámica de búsqueda de A* en los datos de entrenamiento
- Este enfoque se centra en entrenar a un Transformer para resolver tareas complejas de planificación de manera más robusta
- El modelo se entrena, como un LLM, para predecir la siguiente palabra dada una secuencia de palabras
- Los experimentos se realizaron con un dataset generativo sintético que usa lenguaje sintético y vocabulario sintético
- Las tareas de planificación y los planes de solución óptimos se representan como secuencias de palabras llamadas tokens
- El proceso de cálculo realizado por A* se registra como una secuencia de tokens de traza de ejecución
- La traza de ejecución forma un dataset secuencial que contiene la dinámica de búsqueda de A*
- A través de secuencias enriquecidas con búsqueda, el Transformer se entrena para generar secuencias de tokens que codifican tanto la dinámica de búsqueda de A* como el plan óptimo
Procedimiento de entrenamiento de Searchformer
- El modelo final, Searchformer, se construye en dos etapas
- Primero se entrena al Transformer para imitar el proceso de búsqueda de A*
- Después se ajusta finamente para que encuentre el plan con menos pasos de búsqueda mientras sigue produciendo el plan óptimo
- A este proceso se le llama search dynamics bootstrapping
- El objetivo es obtener un Transformer que resuelva tareas complejas de planificación con menos pasos de búsqueda que una implementación de referencia de A*
Experimentos con Sokoban y capacidad de generalización
- En el rompecabezas Sokoban, los modelos de la familia Searchformer resolvieron el 93.7% del total de tareas de prueba
- El promedio de pasos de búsqueda fue 26.8% menor que en la implementación de referencia de A*
- Experimentos que controlaron la complejidad de las tareas, el tamaño del dataset y el tamaño del modelo confirmaron el efecto de incluir trazas de ejecución
- Incluir trazas de ejecución en los datos de entrenamiento aumenta la longitud de las secuencias generadas en 10×~100×
- Aun así, el rendimiento mejora en conjuntos independientes de tareas de prueba
- El modelo search-augmented genera planes óptimos para tareas desconocidas con mayor frecuencia que un modelo solution-only más grande, incluso con 10 veces menos secuencias de entrenamiento
- El modelo search-augmented se entrena con datos que incluyen descripción de la tarea, solución y traza de ejecución
- El modelo solution-only se entrena con secuencias que solo incluyen la descripción de la tarea y su solución
- Estos resultados muestran que incluir la dinámica de búsqueda de A* en el proceso de entrenamiento de un Transformer puede mejorar el rendimiento en tareas de planificación
1 comentarios
Opiniones de Hacker News
También hubo una investigación más interesante sobre el uso de transformers para planificación de movimiento robótico 0
El problema de mover un brazo robótico del punto A al punto B evitando colisiones es muy difícil porque es continuo y de alta dimensionalidad, y los métodos de planificación existentes suelen requerir mucho cómputo y aun así no rinden muy bien.
Por eso es una de las razones por las que los movimientos de los robots se ven “poco naturales” y por las que los robots no hacen bien muchas de las tareas que queremos; este enfoque parece bastante competitivo frente a otros métodos, al planear rutas casi óptimas más rápido.
Antes de ir por la vía de la investigación, me pregunto si probaron el algoritmo J modificado*, una optimización de A* para búsqueda en grafos/rutas de juegos.
Para quien tenga curiosidad, está en Game AI Pro 2 0
Este paper prueba qué tan bien los transformers predicen trazas de ejecución, por ejemplo en casos como un compilador JIT, y si eso ayuda a mejorar heurísticas en lugares como la búsqueda de rutas.
Aun así, los transformers son lentos, así que lo miro con cautela.
Los problemas de planificación ya están bien cubiertos por técnicas establecidas como búsqueda en grafos, solucionadores SAT, investigación de operaciones y Prolog.
Normalmente lo central es optimizar entre varias alternativas posibles, y no tengo claro que los transformers sean adecuados para eso.
El rol de las técnicas de la familia LLM parece estar más en traducir descripciones en lenguaje natural a programas ejecutables, aunque Prolog ya está bastante cerca, dado que originalmente fue diseñado para procesamiento clásico de lenguaje natural.
La traducción automática antes requería decodificación gramatical compleja usando búsqueda, pero hoy usa transformers con una decodificación mucho más simple y prácticamente sin necesidad de búsqueda.
Ahora podríamos llegar incluso a estructuras completamente recursivas.
La idea sería aprender heurísticas para neural architecture search (NAS) con los mejores modelos predictivos actuales y buscar nuevos bloques de redes neuronales mejores que transformer o mamba.
Se acerca la singularidad…
Si te interesan los juegos tipo Sokoban, vale la pena ver https://thinky.gg
Hay una variante de Sokoban interesante llamada Sokopath, y otra variante NP-hard llamada Pathology, cuyo objetivo es ir del punto A al punto B en el menor número de pasos.
La comunidad intentó crear varios solucionadores, pero se vuelve muy difícil cuando la grilla supera 5x5, y la comunidad de thinky también encontró, mediante simulated annealing, niveles interesantes con cantidades máximas de pasos muy grandes.
“26.8% menos pasos de búsqueda que la búsqueda A* estándar”
O sea que, en Sokoban, apenas es un poco mejor que A*, que está lejos del estado del arte (https://festival-solver.site/)
No sé qué tiene de impresionante este paper ni por qué llegó a Hacker News.
Pero si en el dominio donde se busca hay otras restricciones aprovechables, se puede superar a A*.
Por ejemplo, Jump Point Search aprovecha propiedades de la búsqueda en grillas donde solo se puede mover de ciertas maneras.
Si pudiéramos crear un algoritmo de búsqueda general que aproveche “automáticamente” y de forma efectiva las propiedades especiales del dominio subyacente, sin que una persona tenga que analizarlas manualmente, creo que sería útil.
A* es más bien una solución base “ingenua”, y ellos no se pusieron a diseñar algoritmos explícitamente.
Es bastante impresionante que un transformer encoder-decoder simple pueda lograr eso.
“Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
Este paper es interesante como ejemplo de uso de transformers para toma de decisiones, y no me importa mucho si ahora mismo está al nivel de A*.
Claro que esa hipótesis tiene una versión fuerte y una débil, y la versión fuerte probablemente no sea cierta, pero mientras parezca que nos acercamos a “una única forma verdadera” en que la naturaleza aprende cosas, lo considero una noticia importante.
Si los transformers pueden planificar, quizá eso signifique que para la inteligencia artificial general solo hace falta una mejor educación.
También se necesita aprendizaje en línea y varias capas más.
Para quienes aprenden mejor escuchando, hay una versión de este paper en formato audiolibro resumido.
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f
Soy muy optimista sobre usar heurísticas aprendidas en algoritmos discretos como A*, Focal search y varias familias de programación lineal entera.
En la mayoría de las bibliotecas modernas de optimización discreta como CPLEX, las diferencias de rendimiento se explican por heurísticas y tuning.
Me convence menos reemplazar rutinas de búsqueda óptima bien entendidas por enfoques aprendidos de extremo a extremo, aunque puede que sea una preocupación infundada.
Aun así, parece que los autores dejaron pasar esa oportunidad.
Quizá yo también debería resolver tres en raya con transformers y pedir dinero de VC.
Tal vez en unos años todos estén escribiendo sobre cuánto más eficiente es el código real que la IA ;)
Si aprendes una heurística admisible, puedes mantener el rendimiento en el peor caso, y ese siempre ha sido el estándar de estos algoritmos.
No es nada raro encontrar soluciones que sean más rápidas en casos promedio o p99, pero que no ofrezcan garantías en el peor caso.
Me pregunto si alguien está recopilando una lista de algoritmos clásicos o problemas NP-completos que ahora se desempeñan mejor gracias al deep learning.