- El artículo de ICLR 2025 Tree Diffusion propone un modelo neuronal que, en lugar de generar programas un token a la vez, edita repetidamente el programa tomando como referencia los resultados de ejecución
- La idea central es que aprende sobre árboles sintácticos construidos con una gramática libre de contexto, revirtiendo ruido de forma similar a la diffusion en imágenes
- El ruido se agrega mediante mutaciones aleatorias que reemplazan nodos arbitrarios del árbol sintáctico por otros nodos del mismo tipo válido
- Como corrige el código manteniendo un estado gramaticalmente válido, es fácil combinarlo con búsqueda (search) en el espacio de programas
- En inverse graphics, puede convertir imágenes en programas generativos y, al combinarse con búsqueda, depurar programas gráficos observando el resultado de ejecución para ajustarlos a la especificación requerida
Enfoque de Tree Diffusion
- Tree Diffusion es un método que aplica diffusion sobre árboles sintácticos para la síntesis de programas
- Están disponibles el paper, arXiv y el código y los pesos
- Los modelos de lenguaje grandes tradicionales usan un enfoque autorregresivo que genera código un token a la vez, sin retroalimentación de los resultados de salida del programa durante la generación
- Los enfoques que entrenan al LLM para proponer ediciones directamente pueden ser difíciles porque requieren suficientes datos de edición
- Tree Diffusion modifica programas con un modelo que revierte el ruido aplicado a árboles sintácticos de una gramática libre de contexto
Ruido, búsqueda y casos de uso
- El ruido consiste en seleccionar un nodo arbitrario del árbol sintáctico y reemplazarlo por otro nodo del mismo tipo válido
- En vez de generar el programa secuencialmente desde cero, lo edita de manera iterativa mientras mantiene la validez sintáctica
- Gracias a esta propiedad, es fácil combinar el modelo neuronal con búsqueda en el espacio de programas
- En tareas de inverse graphics, aprende a recibir una imagen de entrada y convertirla en un programa que genere esa imagen
- El sistema combinado con búsqueda puede escribir programas gráficos, verificar sus resultados de ejecución y luego depurarlos para que cumplan con la especificación requerida
- También muestra que puede escribir programas gráficos a partir de bocetos dibujados a mano
1 comentarios
Comentarios en Hacker News
Suena más parecido al trabajo hecho con Racket y la generación de pistas para MOOCs
No recuerdo con certeza de qué universidad era, pero vi una charla sobre generar pistas para estudiantes transformando árboles sintácticos y analizando qué había que cambiar para llegar a la respuesta objetivo
Creo que fue una charla de RacketCon de hace unos 10 años, y quizá este tipo de metodología podría combinarse con enfoques modernos de aprendizaje automático
Encontré la charla: https://invidious.baczek.me/watch?v=ijyFC36kVis
Es interesante que esta mutación de subárboles sea un tema que Koza y Adami trataron bastante a fondo en los 90 bajo el nombre de algoritmos genéticos
Solo era un poco distinta la función de optimización
El artículo incluye una referencia del año 2000 sobre algoritmos genéticos para generar árboles de programas rápidamente, pero parece que falta el trabajo central
Ojalá los autores lean eso y profundicen en el trabajo de esas personas
FFX y PGE son ambos muy rápidos
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
Como creador de PGE, he pensado que el aprendizaje por refuerzo y, más recientemente, las técnicas de difusión podrían ayudar con este tipo de algoritmos
Todos los algoritmos necesitan formas de guiar mejor la búsqueda o de salir de óptimos locales en los que caen sorprendentemente rápido
La mayor parte de la investigación en programación genética/cómputo evolutivo se centra en evitar la convergencia prematura
Según la descripción del sitio, es “el libro de texto de IA más autorizado y más usado, adoptado por más de 1500 escuelas”
https://aima.cs.berkeley.edu/
Vaya, fue un error mío
Tengo los dos libros gruesos de Koza publicados en 1992 y 1994, Genetic Programming: On the Programming of Computers by Means of Natural Selection y Genetic Programming II : Automatic Discovery of Reusable Programs
No leí los dos libros posteriores
En ese momento, los grandes problemas atascados eran en parte hacerlo lo suficientemente rápido y en parte lograr que los resultados fueran comprensibles para las personas
En lo segundo, los modelos grandes de lenguaje parecen mucho mejores
Se terminaba invirtiendo mucho tiempo en reestructurar y podar árboles para obtener resultados interpretables, así que el valor principal parecía limitarse a casos en los que valía la pena dedicar muchos recursos a encontrar versiones más optimizadas de algoritmos muy pequeños y compactos
Pero la mayoría de los codebases tienen demasiada fruta al alcance de la mano mucho más fácil de recoger, así que rara vez se llega al punto en que valga la pena intentar algo así
Aun así, conceptualmente me sigue gustando
[1] https://www.genetic-programming.com/johnkoza.html
https://web.archive.org/web/20021224053225/http://smi-web.st...
https://www.genetic-programming.com/jkpdf/tr1314.pdf
Usar Markov chain Monte Carlo para síntesis de programas no es una idea particularmente nueva
La referencia que se me vino de inmediato a la mente es el trabajo de Josh Tenenbaum
WebPPL (lenguaje de programación probabilística para la web) también tiene muchos demos, como síntesis de naves espaciales 3D
También recomiendo mucho los libros The Design and Implementation of Probabilistic Programming Languages y Probabilistic Models of Cognition
Los artículos del MIT Probabilistic Computing Project también valen la pena
[1] Human-level concept learning through probabilistic program induction. https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science....
[2] http://webppl.org/
[3] https://dritchie.github.io/web-procmod/
[4] https://dippl.org/
[5] http://probmods.org/
[6] http://probcomp.csail.mit.edu/
No me queda muy claro a qué se refiere la “magia” aquí
En un enfoque tradicional, se habría generado una imagen aleatoria, calculado alguna métrica de distancia y luego minimizado esa distancia con un método de optimización como el recocido simulado
Aquí entiendo que se optimiza la diferencia entre representaciones de imágenes, pero no entiendo cómo el cambio de tokens de un programa podría ser diferenciable
La idea clave parece ser que se puede entrenar un modelo de red neuronal que proponga modificaciones al programa alterando nodos al azar
Al ejecutar este modelo de red neuronal, puede hacer modificaciones sintácticamente correctas según una gramática libre de contexto; por ejemplo, ediciones donde un número solo se reemplaza por otro número
Me pregunto cómo sería aplicar esto a la optimización de compiladores/intérpretes
¿Se podría “disecar” parte de la ejecución, quizá a nivel de ensamblador, para generar optimizaciones especializadas del código compilado que no cambien la salida pero que los compiladores modernos no pueden encontrar de forma determinista?
Aquí, la salida no se refiere al binario generado, sino a la salida esperada del programa
No esperaría que una herramienta así “descubriera” ensamblador a menos que se entrenara con resultados de compilación
El modelo no tiene ninguna noción de cómo o dónde se ejecuta el código
Después de décadas de investigación en compiladores y de que los supercompiladores hayan dado tantas vueltas, ya estamos en un punto donde es casi imposible descubrir nuevas optimizaciones que produzcan mejoras notables
Los compiladores actuales son realmente buenos
Aun así, el valor de un enfoque así podría estar en optimizar la intención del código
Si determina que estás ordenando números, podría cambiar el código por un algoritmo de ordenamiento más rápido con las mismas propiedades funcionales
Si está almacenando datos que no se usan, podría dejar de almacenarlos
Hay una perspectiva de ver el código un nivel por encima de lo que ve el compilador, entendiendo no solo qué hace, sino también por qué lo hace
Usé ofuscación para crear un gran dataset a partir de un pequeño conjunto de funciones con respuesta correcta, e hice un modelo que clasificaba código binario ofuscado no visto como la función conocida más cercana
La aplicación que tenía en mente durante la investigación era el análisis estático de malware, pero la optimización en realidad está en el lado opuesto de la ofuscación
Algo que me gustaría probar en el futuro es un modelo de difusión que trate la ofuscación como “ruido” que debe eliminarse
Una cosa que aprendí es que los compiladores optimizadores producen salidas muy regulares
Una vez normalizadas las direcciones, el tamaño del “vocabulario” de bloques básicos resulta ser bastante pequeño, como de unos 2000 tokens
Ciertas “frases” se correlacionan con el significado del código fuente original sin importar cuánta ofuscación se les haya añadido encima
Hay gente que también aplica técnicas de síntesis a la superoptimización
Así que sí podría haber posibilidades de aplicar un enfoque así
Hace tiempo se habló de que GitHub agregaría integración con herramientas de build generales
¿Qué pasaría si se pudieran compilar todos los proyectos que compilan con LLVM en GitHub y ejecutar un modelo de difusión sobre su representación intermedia?
¿La difusión podría funcionar también a nivel binario?
¿Se podría entrenar un modelo de difusión que, dado un prompt, genere el binario final de un programa?
Probablemente un árbol de sintaxis abstracta sería mejor, pero al menos los binarios parecen muy fáciles de probar rápidamente para ver si funcionan
Habría muchas desventajas, pero si fuera posible, me emociona pensar en el día en que uno pueda decir “créame una app que haga esto” y un modelo de difusión genere todos los bytes de esa app
Solo lo pregunto por curiosidad
Eso aumentaría la probabilidad de generar un programa válido
Podrías generar directamente código máquina, sin necesidad de pasar por un montón de pasos intermedios como Python o JS
Me gustaría ver esto aplicado también a SDF
¿Estás pensando en aproximar la función de distancia con expresiones algebraicas y tratar el álgebra misma como un “lenguaje de programación”?
El PDF renderiza increíblemente lento
Supongo que es porque contiene instrucciones para dibujos generados por programación
Da esa sensación de artículo académico que ya extrañaba últimamente
https://arxiv.org/pdf/2405.20519
La parte aplicada al trabajo de gráficos inversos me recordó a este artículo publicado una semana antes: https://arxiv.org/abs/2405.15306