Diffusion em Árvores Sintáticas para Síntese de Programas
(tree-diffusion.github.io)- O artigo da ICLR 2025 Tree Diffusion propõe um modelo neural que, em vez de gerar programas token por token, edita iterativamente o programa com base no resultado de sua execução
- O ponto central é que ele aprende sobre uma árvore sintática construída a partir de uma gramática livre de contexto, revertendo ruído de forma semelhante ao diffusion em imagens
- O ruído é adicionado como mutações aleatórias que substituem nós arbitrários da árvore sintática por outros nós do mesmo tipo correto
- Como o código é corrigido mantendo a validade gramatical, fica fácil combinar o método com busca (search) no espaço de programas
- Em inverse graphics, ele pode converter imagens em programas geradores e, combinado com busca, depurar programas gráficos observando o resultado da execução para atender à especificação desejada
A abordagem do Tree Diffusion
- Tree Diffusion é um método que aplica diffusion em árvores sintáticas para síntese de programas
- O artigo, o arXiv e o código com pesos estão disponíveis publicamente
- Os grandes modelos de linguagem existentes usam um método autorregressivo para gerar código token por token, sem feedback da observação da saída do programa durante a geração
- Abordagens que treinam o LLM para propor edições diretamente podem ser difíceis por exigirem dados suficientes de edição
- O Tree Diffusion modifica programas com um modelo que reverte o ruído aplicado à árvore sintática de uma gramática livre de contexto
Ruído, busca e casos de uso
- O ruído consiste em selecionar um nó arbitrário da árvore sintática e substituí-lo aleatoriamente por outro nó do mesmo tipo correto
- Em vez de gerar o programa do zero de forma sequencial, o método o edita repetidamente mantendo a validade sintática
- Graças a essa característica, é fácil combinar o modelo neural com busca no espaço de programas
- Em tarefas de inverse graphics, o método aprende a receber uma imagem como entrada e convertê-la em um programa que gera essa imagem
- O sistema combinado com busca pode escrever programas gráficos, verificar o resultado da execução e depois depurá-los para satisfazer a especificação requerida
- O trabalho também mostra que é possível escrever programas gráficos até mesmo para esboços desenhados à mão
1 comentários
Opiniões no Hacker News
Parece mais com o trabalho feito com Racket e geração de dicas para MOOCs
Não tenho certeza de qual universidade era, mas vi uma apresentação em que eles transformavam árvores sintáticas e analisavam como elas precisavam ser modificadas para chegar à solução-alvo, gerando dicas para os alunos
Provavelmente foi uma apresentação da RacketCon de uns 10 anos atrás, e talvez seja possível combinar esse tipo de metodologia com abordagens modernas de aprendizado de máquina
Encontrei a apresentação: https://invidious.baczek.me/watch?v=ijyFC36kVis
É interessante porque esse tipo de mutação de subárvores foi explorado com bastante profundidade por Koza e Adamı nos anos 90 sob o nome de algoritmos genéticos
A função de otimização era apenas um pouco diferente
O artigo tem uma referência de 2000 relacionada a algoritmos genéticos para gerar árvores de programa rapidamente, mas parece deixar de fora o trabalho central
Seria bom se os autores lessem isso e se aprofundassem no trabalho deles
FFX e PGE são ambos muito rápidos
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
Como criador do PGE, venho pensando que aprendizado por reforço e, mais recentemente, técnicas de difusão poderiam ajudar esses algoritmos
Todos os algoritmos precisam de uma forma de orientar melhor a busca ou de escapar de ótimos locais nos quais caem surpreendentemente rápido
Grande parte da pesquisa em programação genética/computação evolutiva se concentra em evitar convergência prematura
Segundo a descrição do site, é “o livro-texto de IA mais autorizado e mais amplamente usado, adotado em mais de 1500 escolas”
https://aima.cs.berkeley.edu/
Bem, erro meu
Tenho os dois livros volumosos de Koza, de 1992 e 1994: Genetic Programming: On the Programming of Computers by Means of Natural Selection e Genetic Programming II : Automatic Discovery of Reusable Programs
Não li os dois posteriores
O grande problema que travava a área na época era, em parte, fazer isso rápido o bastante e, em parte, fazer com que os resultados fossem compreensíveis por humanos
Neste último ponto, modelos de linguagem grandes parecem muito melhores
Acabava-se gastando muito tempo reestruturando e podando árvores para obter resultados decifráveis, então acho que o principal valor ficava limitado a casos em que valia a pena investir muitos recursos para encontrar versões mais otimizadas de algoritmos muito pequenos e densos
Só que a maioria das bases de código tem tantas oportunidades muito mais fáceis de aproveitar que raramente se chega ao ponto em que vale a pena tentar algo assim
Ainda assim, conceitualmente, continuo gostando da ideia
[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íntese de programas não é exatamente uma ideia nova
A referência que me veio imediatamente à cabeça foi o trabalho de Josh Tenenbaum
O WebPPL (linguagem de programação probabilística para a web) também tem várias demos, como síntese de naves espaciais 3D
Também recomendo muito os livros relacionados a The Design and Implementation of Probabilistic Programming Languages e Probabilistic Models of Cognition
Os artigos do MIT Probabilistic Computing Project também valem a 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/
Não entendi bem a “mágica” mencionada aqui
Em uma abordagem tradicional, provavelmente se geraria uma imagem aleatória, calcularia alguma métrica de distância e depois minimizaria essa distância com um método de otimização como simulated annealing
Aqui eu entendo que se está otimizando a diferença entre representações de imagens, mas não sei como uma alteração de tokens de um programa poderia ser diferenciável
A ideia central parece ser que é possível treinar um modelo de rede neural que proponha modificações no programa transformando nós aleatoriamente
Ao executar esse modelo de rede neural, ele consegue fazer edições sintaticamente corretas de acordo com uma gramática livre de contexto, por exemplo substituindo números apenas por números
Fico curioso para saber como isso poderia ser aplicado à otimização de compiladores/interpretadores
Será que seria possível “dissecar” parte da execução, talvez no nível de assembly, e criar otimizações específicas para o código compilado que compiladores modernos não conseguem encontrar de forma determinística, sem alterar a saída?
Aqui, saída não significa o binário gerado, mas a saída esperada do programa
Eu não esperaria que uma ferramenta dessas “descobrisse” assembly sem ter sido treinada com resultados de compilação
O modelo não tem noção de como ou onde o código é executado
Depois de décadas de pesquisa em compiladores e supercompiladores rodando, chegamos a um ponto em que é quase impossível descobrir uma nova otimização que gere melhorias visíveis
Os compiladores de hoje são realmente bons
Ainda assim, o valor dessa abordagem pode estar em otimizar a intenção do código
Se ela perceber que está fazendo ordenação de números, poderia trocar o código por um algoritmo de ordenação mais rápido com as mesmas propriedades funcionais
Se estiver armazenando dados não usados, poderia parar de armazená-los
É uma perspectiva de olhar o código um nível acima do que o compilador vê, entendendo não só o que ele faz, mas também por quê
Usei ofuscação para criar um grande dataset a partir de um pequeno conjunto de funções corretas e construí um modelo que classificava código binário ofuscado, nunca visto antes, como a função conhecida mais próxima
A aplicação que eu tinha em mente na época era análise estática de malware, mas otimização é, na verdade, o lado oposto da ofuscação
O que eu gostaria de tentar no futuro é um modelo de difusão que trate a ofuscação como “ruído” a ser removido
Uma coisa que aprendi é que compiladores otimizadores produzem saídas muito regulares
Depois de normalizar os endereços, o tamanho do “vocabulário” dos blocos básicos fica bem pequeno, algo como cerca de 2000 tokens
Certas “frases” têm correlação com o significado do código-fonte original, por mais ofuscação que se coloque por cima
Também há pessoas aplicando técnicas de síntese à superotimização
Então há possibilidade de essa abordagem ser aplicada
Um tempo atrás houve uma conversa de que o GitHub adicionaria integração com ferramentas de build comuns
E se fosse possível compilar todos os projetos no GitHub que compilam com LLVM e rodar um modelo de difusão sobre essa representação intermediária?
Será que difusão também poderia funcionar no nível binário?
Seria possível treinar um modelo de difusão que, dado um prompt, gerasse o binário final de um programa?
Talvez uma árvore sintática abstrata seja melhor, mas um binário ao menos parece muito fácil de testar rapidamente para ver se funciona
Haveria muitas desvantagens, mas, se for possível, fico ansioso pelo dia em que se diga “crie um app que faça isso” e o modelo de difusão gere todos os bytes desse app
Estou só jogando a ideia por curiosidade
Assim a probabilidade de criar um programa válido seria maior
Dá para gerar código de máquina diretamente, especialmente sem motivo para passar por um monte de etapas intermediárias como Python ou JS
Gostaria de ver isso aplicado também a SDF
Você está pensando em algo como aproximar uma função de distância por expressões algébricas e tratar a própria álgebra como uma “linguagem de programação”?
O PDF renderiza de forma extremamente lenta
Talvez seja porque contém comandos de figuras geradas por programação
Dá aquela sensação de artigo acadêmico de que sinto falta hoje em dia
https://arxiv.org/pdf/2405.20519
A parte aplicada a tarefas de gráficos inversos me lembra este artigo que saiu uma semana antes: https://arxiv.org/abs/2405.15306