Diffusion Pohon Sintaks untuk Sintesis Program

• Makalah ICLR 2025 Tree Diffusion mengusulkan model saraf yang secara berulang mengedit program dengan merujuk pada hasil eksekusi, alih-alih menghasilkan program satu token demi satu
• Intinya adalah model ini belajar di atas pohon sintaks yang dibangun dari tata bahasa bebas konteks sembarang, dengan cara membalikkan noise seperti diffusion pada gambar
• Noise ditambahkan sebagai mutasi acak yang mengganti node acak pada pohon sintaks dengan node lain yang memiliki tipe yang benar yang sama
• Karena kode diperbaiki sambil mempertahankan keadaan yang valid secara tata bahasa, pendekatan ini mudah digabungkan dengan pencarian (search) di ruang program
• Dalam inverse graphics, model ini dapat mengubah gambar menjadi program pembangkitnya, lalu digabungkan dengan pencarian untuk men-debug program grafis agar sesuai dengan spesifikasi yang diminta sambil melihat hasil eksekusi

---

Pendekatan Tree Diffusion

• Tree Diffusion adalah metode yang menerapkan diffusion pada pohon sintaks untuk sintesis program
• Makalah, arXiv, dan kode beserta bobot telah dipublikasikan
• Model bahasa besar yang ada selama ini menggunakan pendekatan autoregresif yang menghasilkan kode satu token demi satu, tanpa umpan balik yang mengamati hasil keluaran program selama proses generasi
• Pendekatan yang melatih LLM agar langsung mengusulkan edit dapat sulit karena membutuhkan data pengeditan yang memadai
• Tree Diffusion memodifikasi program dengan model yang membalikkan noise yang diberikan pada pohon sintaks dari tata bahasa bebas konteks

Noise, pencarian, dan contoh penerapan

• Noise adalah mutasi acak yang memilih node acak dari pohon sintaks, lalu menggantinya dengan node lain yang memiliki tipe yang benar yang sama dengan node target pengganti
• Alih-alih menghasilkan program secara berurutan dari awal, model ini mempertahankan validitas sintaksis sambil melakukan pengeditan berulang
• Berkat sifat ini, model saraf mudah digabungkan dengan pencarian di ruang program
• Pada tugas inverse graphics, model mempelajari cara menerima gambar sebagai input lalu mengubahnya menjadi program yang menghasilkan gambar tersebut
• Sistem yang digabungkan dengan pencarian dapat menulis program grafis, memeriksa hasil eksekusinya, lalu men-debug-nya agar memenuhi spesifikasi yang diminta
• Ditunjukkan juga bahwa model ini dapat menulis program grafis bahkan untuk sketsa yang digambar tangan

[GN⁺]

Opini Hacker News

• Ini terdengar lebih mirip dengan pekerjaan yang pernah dilakukan dengan Racket dan pembuatan petunjuk untuk MOOC
  Saya tidak yakin universitas mana, tetapi saya pernah melihat presentasi tentang memodifikasi pohon sintaks dan menganalisis perubahan apa yang diperlukan untuk mencapai jawaban target, lalu menghasilkan petunjuk untuk mahasiswa
  Mungkin itu presentasi RacketCon sekitar 10 tahun lalu, dan metodologi semacam ini mungkin bisa digabungkan dengan pendekatan machine learning modern
  Saya menemukan presentasinya: https://invidious.baczek.me/watch?v=ijyFC36kVis

• Mutasi subpohon seperti ini menarik karena pada tahun 90-an Koza dan Adamı membahasnya cukup mendalam dengan nama algoritma genetika
  Hanya fungsi optimisasinya saja yang agak berbeda
  Di makalah itu ada satu referensi tahun 2000 tentang algoritma genetika untuk menghasilkan pohon program dengan cepat, tetapi pekerjaan intinya tampaknya terlewat
  Saya berharap para penulis membacanya dan mendalami karya mereka

  • Alternatif yang lebih baru dibanding pemrograman genetika Koza menggunakan mekanisme pencarian yang cukup berbeda
    FFX dan PGE sama-sama sangat cepat
    https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
    https://arxiv.org/pdf/2209.09675
    Sebagai pembuat PGE, saya sudah lama berpikir bahwa reinforcement learning dan, belakangan, teknik difusi bisa membantu algoritma-algoritma seperti ini
    Semua algoritma membutuhkan cara untuk mengarahkan pencarian dengan lebih baik, atau untuk keluar dari optimum lokal yang ternyata bisa terjadi sangat cepat
    Sebagian besar riset pemrograman genetika/komputasi evolusioner berfokus pada menghindari konvergensi dini
  • Sebelumnya saya mengatakan para penulis mungkin tidak terlalu mengenal Koza dan Adami, tetapi saya tidak menyadari bahwa penulis korespondensinya adalah Stuart Russell, yang menulis Artificial Intelligence: A Modern Approach bersama Peter Norvig
    Menurut deskripsi situsnya, itu adalah “buku teks AI paling otoritatif dan paling banyak digunakan, diadopsi oleh lebih dari 1500 sekolah”
    https://aima.cs.berkeley.edu/
    Wah, itu kesalahan saya
  • Tepatnya, itu adalah pemrograman genetika
    Saya punya dua buku tebal Koza dari tahun 1992 dan 1994, yaitu Genetic Programming: On the Programming of Computers by Means of Natural Selection dan Genetic Programming II : Automatic Discovery of Reusable Programs
    Dua buku berikutnya belum saya baca
    Masalah besar yang mengganjal saat itu sebagian adalah membuatnya cukup cepat, dan sebagian lagi membuat hasilnya bisa dipahami manusia
    Untuk yang terakhir, model bahasa besar tampaknya jauh lebih baik
    Banyak waktu harus dihabiskan untuk menyusun ulang dan memangkas pohon agar mendapatkan hasil yang dapat diuraikan, sehingga nilai utamanya tampaknya terbatas pada kasus ketika layak mengerahkan banyak sumber daya untuk menemukan versi algoritma yang sangat kecil dan padat yang lebih teroptimasi
    Namun di sebagian besar codebase ada terlalu banyak peluang yang jauh lebih mudah dipetik, sehingga jarang sekali sampai pada titik di mana upaya seperti ini sepadan
    Meski begitu, secara konseptual saya masih menyukainya
    [1] https://www.genetic-programming.com/johnkoza.html
  • Apakah referensinya yang ini?
    https://web.archive.org/web/20021224053225/http://smi-web.st...
    https://www.genetic-programming.com/jkpdf/tr1314.pdf
  • Kalau dilihat begitu, backpropagation juga bisa disebut aturan rantai dari berabad-abad lalu

• Menggunakan Markov chain Monte Carlo untuk sintesis program bukanlah ide yang benar-benar baru
  Referensi yang langsung terlintas adalah karya Josh Tenenbaum
  WebPPL (bahasa pemrograman probabilistik web) juga punya banyak demo seperti sintesis pesawat luar angkasa 3D
  Saya juga sangat merekomendasikan buku-buku terkait The Design and Implementation of Probabilistic Programming Languages dan Probabilistic Models of Cognition
  Makalah-makalah dari MIT Probabilistic Computing Project juga layak dilihat
  [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/

  • Perlu juga dicatat bahwa penulis pertama, Shreyas, adalah mahasiswa Tenenbaum di MIT sebelum pergi ke Berkeley

• Saya kurang memahami “keajaiban” yang dimaksud di sini
  Kalau memakai pendekatan tradisional, orang mungkin akan membuat gambar acak, menghitung suatu metrik jarak, lalu meminimalkan jarak itu dengan metode optimisasi seperti simulated annealing
  Di sini saya paham bahwa yang dioptimalkan adalah perbedaan antarrepresentasi gambar, tetapi saya tidak tahu bagaimana perubahan token pada program bisa dibuat terdiferensiasi

  • Mengubah token program itu sendiri tidak terdiferensiasi
    Ide utamanya tampaknya adalah bahwa kita bisa melatih model neural network yang mengusulkan modifikasi program dengan mengubah node secara acak
    Saat model neural network ini dijalankan, ia dapat melakukan penyuntingan yang secara sintaksis valid menurut tata bahasa bebas konteks, misalnya mengganti angka hanya dengan angka

• Saya penasaran bagaimana kalau ini diterapkan pada optimisasi compiler/interpreter
  Bisakah sebagian eksekusi, mungkin pada level assembly, “dibedah” untuk menghasilkan optimisasi khusus kode terkompilasi yang tidak mengubah output tetapi tidak dapat ditemukan secara deterministik oleh compiler modern?
  Output di sini maksudnya bukan binary yang dihasilkan, melainkan output program yang diharapkan

  • Sepertinya jawabannya “tidak”
    Saya tidak berharap alat seperti ini akan “menemukan” assembly kecuali dilatih dengan hasil kompilasi
    Model tidak punya konsep tentang bagaimana atau di mana kode dijalankan
    Setelah puluhan tahun riset compiler dan supercompiler dijalankan, kita kini berada pada titik di mana kemungkinan menemukan optimisasi baru yang memberikan peningkatan mencolok nyaris mustahil
    Compiler masa kini benar-benar bagus
    Namun nilai dari pendekatan seperti ini bisa jadi ada pada optimisasi maksud kode
    Jika ia menilai bahwa kode sedang mengurutkan angka, ia bisa mengganti kode dengan algoritma pengurutan yang lebih cepat dengan sifat fungsional yang sama
    Jika kode menyimpan data yang tidak digunakan, ia bisa berhenti menyimpannya
    Ada sudut pandang yang melihat kode pada satu tingkat lebih tinggi daripada yang dilihat compiler, dan memahami bukan hanya apa yang dilakukan, tetapi juga mengapa dilakukan
  • Disertasi PhD saya juga membahas masalah serupa
    Saya menggunakan obfuscation untuk membuat dataset besar dari sekumpulan kecil fungsi jawaban benar, lalu membuat model yang mengklasifikasikan kode binary terobfuskasi yang belum pernah dilihat ke fungsi dikenal yang paling dekat
    Saat riset itu, aplikasi yang saya bayangkan adalah analisis statis malware, tetapi optimisasi sebenarnya berada di sisi berlawanan dari obfuscation
    Yang ingin saya coba ke depan adalah model diffusion yang memperlakukan obfuscation sebagai “noise” yang harus dihilangkan
    Satu hal yang saya pelajari adalah bahwa optimizing compiler menghasilkan output yang sangat teratur
    Setelah alamat dinormalisasi, ukuran “kosakata” basic block menjadi cukup kecil, kira-kira sekitar 2000 token
    “Frasa” tertentu berkorelasi dengan makna source code asli, tidak peduli seberapa banyak obfuscation ditambahkan di atasnya
  • Ini disebut superoptimisasi: https://en.wikipedia.org/wiki/Superoptimization
    Ada juga orang-orang yang menerapkan teknik sintesis pada superoptimisasi
    Jadi ada kemungkinan pendekatan seperti ini bisa diterapkan

• Dulu ada pembicaraan bahwa GitHub akan menambahkan integrasi dengan build tool umum
  Bagaimana jika kita bisa mengompilasi semua proyek di GitHub yang dikompilasi dengan LLVM, lalu menjalankan model diffusion di atas intermediate representation-nya?

  • Output-nya akan berupa apa?

• Bisakah diffusion juga bekerja pada level binary?
  Bisakah kita melatih model diffusion yang, ketika diberi prompt, menghasilkan binary akhir sebuah program?
  Mungkin abstract syntax tree lebih baik, tetapi binary setidaknya tampak sangat mudah untuk menguji dengan cepat apakah ia berjalan atau tidak
  Kekurangannya pasti banyak, tetapi kalau memungkinkan, saya menantikan hari ketika kita bisa berkata “buatkan aplikasi yang melakukan hal seperti ini” dan model diffusion menghasilkan setiap byte aplikasi itu
  Sekadar melempar rasa penasaran

  • Jika penyuntingannya memakai feedback dari output program seperti pekerjaan ini, mungkin lebih cocok untuk terlebih dahulu melakukan disassembly pada binary agar bisa menyunting abstract syntax tree bahasa assembly, lalu meng-assemble-nya kembali
    Dengan begitu peluang menghasilkan program yang valid lebih tinggi
  • Itu akan benar-benar menakjubkan
    Kita bisa menghasilkan kode mesin secara langsung, dan khususnya tidak ada alasan untuk melewati banyak tahap perantara seperti Python atau JS

• Saya ingin melihatnya juga diterapkan pada SDF

  • Bisa jelaskan lebih rinci?
    Apakah maksudnya memperkirakan fungsi jarak dengan ekspresi aljabar, lalu memandang aljabar itu sendiri sebagai “bahasa pemrograman”?

• PDF-nya sangat lambat dirender
  Mungkin karena berisi perintah-perintah untuk gambar yang dibuat secara programatis
  Memberi nuansa makalah akademis yang belakangan ini saya rindukan
  https://arxiv.org/pdf/2405.20519

• Bagian yang menerapkannya pada tugas inverse graphics mengingatkan saya pada makalah ini yang terbit seminggu lebih dulu: https://arxiv.org/abs/2405.15306