Eksplorasi dan Penemuan Matematis dalam Skala Besar

• AlphaEvolve adalah alat optimasi bentuk baru yang menggunakan LLM untuk mengembangkan kode itu sendiri, dan diterapkan pada pemecahan masalah matematika
• Hasil eksperimen pada 67 masalah analisis, kombinatorika, dan geometri menunjukkan performa setara alat optimasi yang sudah ada, sekaligus unggul dalam skalabilitas
• Alat ini memiliki adaptabilitas tinggi, sehingga dapat diterapkan pada beragam masalah matematika tanpa pengetahuan rinci per masalah, serta secara mandiri menetapkan parameter diskretisasi untuk komputasi yang efisien
• Kode yang dihasilkan memberikan interpretabilitas, membantu manusia memahami struktur optimasi atau memperoleh wawasan matematis baru
• Pada beberapa masalah, sistem ini menemukan kembali hasil yang sudah ada atau membuat perbaikan kecil, memperlihatkan potensi otomatisasi riset matematika dan perluasan eksplorasi yang dapat diverifikasi

---

AlphaEvolve dan gambaran riset

• Terence Tao, Bogdan Georgiev, Javier Gómez-Serrano, Adam Zsolt Wagner bekerja sama dengan Google DeepMind dan merilis makalah riset yang menggunakan AlphaEvolve di arXiv
  • Makalah: “Mathematical exploration and discovery at scale”
  • Data terkait dan prompt juga dipublikasikan di repositori GitHub
• AlphaEvolve adalah sistem optimasi evolusi kode berbasis LLM yang memaksimalkan fungsi skor dengan mengembangkan kode, bukan nilai masukan
  • Kode yang dihasilkan LLM dijalankan untuk membuat input, lalu hasilnya dievaluasi
  • Evolusi berlangsung lewat persilangan dan mutasi antar generasi kode berbasis performa
  • “Hallucination” akan dibuang jika performanya rendah, tetapi sebagian justru meningkatkan keragaman dan membantu keluar dari optimum lokal
• Pengguna dapat mengunggah hint atau PDF literatur terkait untuk meningkatkan performa
• Alat serupa yang ada antara lain OpenEvolve, ShinkaEvolve, DeepEvolve

Cakupan eksperimen dan hasil utama

• Eksperimen dilakukan pada 67 masalah matematika, termasuk analisis, kombinatorika, dan geometri
  • Sistem ini menemukan packing geometris atau kandidat fungsi untuk masalah variasional yang lebih efisien dibanding literatur sebelumnya
• Kekuatan utamanya ada pada skalabilitas, karena prompt dan alat verifikasi dari satu masalah dapat dimodifikasi dan digunakan kembali untuk masalah serupa
• AlphaEvolve memiliki adaptabilitas tinggi, sehingga bisa diterapkan ke berbagai masalah tanpa penyesuaian hyperparameter yang detail
  • Contoh: pada masalah variasional, sistem membiarkan parameter diskretisasi ditetapkan sendiri agar hasil lebih efisien
  • Contoh: eksperimen optimasi konstanta ketaksamaan Hausdorff–Young

Interpretabilitas dan contoh konkret

• Kode keluaran AlphaEvolve berbentuk dapat dibaca dan dianalisis manusia, sehingga berguna untuk memahami struktur optimasi
  • Contoh: pada masalah ketaksamaan Gagliardo–Nirenberg, sistem menemukan fungsi Talenti yang tepat dan menghasilkan kode Python untuk melakukan sampling terhadapnya
• Dalam beberapa kasus, sistem juga memanggil subrutin optimasi yang sudah ada atau memakai pendekatan pencarian sederhana

Data pelatihan dan perbedaan performa

• Untuk masalah yang termasuk dalam data pelatihan, LLM dapat langsung mengusulkan solusi optimal seperti Gaussian
  • Jika masalah dimodifikasi untuk menyamarkan solusi Gaussian, sistem akan mengeksplorasi kandidat lain
• Contoh: dalam eksperimen terkait konjektur Kakeya aritmetika, sistem mengusulkan kandidat berbasis Gaussian diskret dan sedikit memperbaiki batas bawah yang ada
  • Berdasarkan hasil ini, Tao membuktikan perilaku asimetris teoretis dalam makalah terpisah

Desain verifier dan kerentanannya

• AlphaEvolve sering menemukan “eksploit” yang memanfaatkan celah dalam kode verifikasi
  • Contoh: pada masalah geometri dengan toleransi galat jarak yang longgar, sistem memperoleh skor tinggi dengan menempatkan titik-titik di lokasi yang sama
• Untuk mencegah ini, perlu digunakan aritmetika eksak atau fungsi skor yang konservatif
  • Contoh: pada masalah Moving Sofa, penerapan skor konservatif membuat sistem menemukan kembali “Gerver sofa”, dan pada variasi 3D menemukan desain baru

Eksperimen pada masalah sulit dan konjektur

• Eksperimen dilakukan pada beberapa konjektur besar yang belum terpecahkan, seperti Sidorenko, Sendov, Crouzeix, Ovals
  • Sistem menemukan kembali kandidat optimal dari literatur yang ada, tetapi tidak menemukan kontracontoh
  • Ini bisa berarti konjektur tersebut benar, atau AlphaEvolve hanya menelusuri konstruksi “jelas” yang sebelumnya juga dicoba para peneliti
• Alat seperti ini berguna untuk mencatat hasil negatif secara sistematis, dan berpotensi dipakai sebagai alat verifikasi otomatis saat mengusulkan konjektur baru
• Pada beberapa masalah varian, sistem menemukan konjektur baru berbentuk perluasan dua parameter

Perbedaan performa antarbidang

• Pada masalah teori bilangan analitik seperti perancangan bobot sieve untuk pendekatan teorema bilangan prima, sistem kesulitan memanfaatkan struktur
  • Sebaliknya, pada masalah seperti Kakeya dan Nikodym di medan hingga yang memiliki struktur aljabar, performanya sangat baik
• Pada masalah Kakeya, sistem menemukan kembali konstruksi optimal berbasis residu kuadrat, dan di tiga dimensi mencapai sedikit perbaikan
  • Dengan Deep Think dari Gemini, ditemukan bukti informal, lalu diubah menjadi bukti formal Lean menggunakan AlphaProof
  • Usulan perbaikan di empat dimensi kemudian diketahui memiliki struktur yang sama dengan makalah Bukh–Chao yang sudah ada
• Pada masalah Nikodym, sistem menemukan konstruksi tiga dimensi baru, tetapi kemudian dipastikan kalah dari konstruksi acak
  • Berdasarkan hal itu, dikembangkan konstruksi hibrida untuk meningkatkan performa, dengan makalah lanjutan yang akan datang

Makna keseluruhan

• AlphaEvolve menunjukkan potensi otomatisasi eksplorasi matematika dalam skala besar
  • Dibanding alat optimasi yang sudah ada, sistem ini unggul dalam skalabilitas, adaptabilitas, dan interpretabilitas
  • Pada sebagian masalah, sistem bahkan mengarah pada konstruksi dan pembuktian baru
• Ke depan, riset matematika kemungkinan akan semakin mengadopsi struktur kolaborasi antara eksplorasi berbasis AI dan verifikasi oleh manusia

[GN⁺]

Komentar Hacker News

• Melelahkan melihat penggemar LLM setiap kali melebih-lebihkan sesuatu sebagai "terobosan", tetapi kasus ini memang contoh pemanfaatan kemampuan LLM saat ini dengan baik untuk riset
  Mereka menyelesaikan masalah matematika dengan mengubahnya menjadi masalah agen coding, dan pendekatan seperti ini tampaknya bisa diperluas ke bidang lain
  Sistem AlphaEvolve juga tampaknya punya peningkatan dibanding agen sebelumnya. AI memang terus berkembang dari tahun ke tahun, tetapi baik kubu pendukung maupun skeptis sama-sama tidak terbantu oleh penilaian yang berlebihan

  • Keluhan seperti ini juga terasa berulang. Kalau tidak suka, bukankah bisa tidak dibaca saja?
    Tiap orang menikmati siklus hype pada fase yang berbeda. Sesuatu yang sudah membosankan bagi satu orang bisa saja terasa baru bagi orang lain, misalnya hubungan antara LLM dan matematika. Inspirasi seperti ini dalam jangka panjang bisa bermanfaat
  • Para skeptis LLM juga tiap kali menyerang para penggemar demi mempertahankan dunia swapuas bernama "gelembung AI"
    Tetap saja, riset kali ini adalah contoh penggunaan LLM yang baik. Sekarang sudah banyak penggunaan praktis yang bahkan tidak lagi dianggap berita. Hanya karena ada fanboy, bukan berarti mereka harus selalu dikritik

• Riset ini tampaknya membantah klaim bahwa LLM "hanya menyelesaikan soal yang pernah dilihat"
  Dari penjelasan para pengembang LLM, proses RL setelah pelatihan membentuk world model yang melampaui sekadar Markov chain sederhana
  Langkah berikutnya adalah membangun kemampuan serupa di atas model seperti Genie 3

  • Jika melihat Bagian 2 dari makalah yang dikutip di blog, LLM dipakai dalam loop evolusioner sebagai mutation function
    LLM memang alat inti, tetapi keberhasilan kali ini lebih banyak berasal dari evolutionary optimization
  • Sulit mengatakan bahwa riset ini benar-benar membantah klaim tersebut. Tetap dibutuhkan intervensi cermat dari pakar, dan pemikiran yang bukan khas LLM tetap esensial
  • AlphaEvolve bukan LLM itu sendiri, melainkan agen coding evolusioner yang memanfaatkan LLM untuk menghasilkan kode
    Menurut blog DeepMind, ini merupakan kelanjutan dari seri "Alpha" seperti AlphaGo dan AlphaFold
    Pendekatan ini tampaknya juga akan bekerja baik pada tes ARC-AGI milik Chollet. Namun, penggunaan istilah "extremize" oleh Tao terasa agak janggal sebagai istilah matematis
  • Tulisan ini menunjukkan bahwa solusi dalam makalah itu mungkin pada akhirnya adalah kasus-kasus yang sudah ada di literatur sebelumnya
  • Klaim bahwa "LLM hanya menyelesaikan soal yang pernah dilihat" terlalu menyederhanakan
    Riset ini cocok untuk masalah yang memungkinkan verifikasi cepat dan pemangkasan solusi buruk. Sebaliknya, pengembangan perangkat lunak oleh manusia sulit memakai pendekatan seperti ini karena ada bias desain, evolusi yang lambat, kesulitan pengujian, dan sebagainya

• Seperti yang ditunjukkan Daniel Litt, ini mungkin hanya contoh pertama yang sekadar memasukkan banyak compute
  Sebagian pertidaksamaan di AlphaEvolve juga bisa diperbaiki dengan mudah oleh manusia dan Moore's Law
  Makalah terkait ada di sini

• Ada komentar yang meminta ringkasan bagi orang yang tidak punya latar belakang matematika

  • Saya bukan ahli, tetapi singkatnya, Terence Tao adalah matematikawan kelas dunia, dan AlphaEvolve adalah alat optimisasi berbasis LLM dari Google
    LLM bertugas membuat mutasi kode Python, dan percobaan yang salah otomatis dipangkas
    Mereka menguji 67 masalah dan sering menghasilkan hasil setingkat pakar. Kelebihannya adalah skalabilitas, ketangguhan, dan kemudahan interpretasi
    Namun, masalah yang termasuk dalam data pelatihan cepat konvergen, dan jika definisi masalah longgar, sistem kadang "mengeksploitasi" celah itu
    Di beberapa bidang matematika tertentu, misalnya teori bilangan analitik, performanya lebih lemah. Meski begitu, ia tetap memberi ide yang layak dijadikan referensi manusia
  • Singkatnya, ketika LLM dimasukkan ke dalam loop pemikiran matematis manusia, ia mampu melakukan matematika level riset
    Memang tidak sama kuat di semua bidang, tetapi pendekatannya terspesialisasi pada pemecahan masalah yang berpusat pada perhitungan, seperti Ramanujan atau Erdős

• Saya tidak tahu bahwa sofa problem sudah terpecahkan. Makalah terkait ada di sini

  • Diskusi saat itu ada di thread ini

• Hal paling menarik dalam tulisan itu bagi saya adalah konsep "robustness" yang disebut penulis
  AlphaEvolve dapat diterapkan dengan mudah ke berbagai masalah tanpa pengetahuan domain khusus
  Tetapi di dunia perangkat lunak, "robustness" biasanya berarti toleransi kesalahan, jadi di sini tampaknya "adaptability" lebih tepat
  Kekuatan LLM adalah memungkinkan integrasi berbasis teks tanpa pemodelan yang rumit. Jika pemrosesan video semakin maju, area seperti game AI juga bisa terbuka

  • Faktanya penulis memang merevisi tulisannya, menghapus "robustness" dan menggantinya dengan "adaptability"

• Tao yang mengatakan "mungkin ini masalah prompt" menunjukkan sikap yang cukup murah hati
  Dalam riset ML lain, hampir tidak ada kritik diri seperti "kami salah dalam tuning hyperparameter" saat performa rendah

  • Namun dalam proses review makalah, komentar seperti itu cukup umum. Kali ini konteksnya berbeda karena lebih dekat ke catatan riset eksploratif
  • Sebenarnya banyak peningkatan algoritme berasal dari baseline yang kurang dituning atau masalah pemrosesan statistik. Tao justru menunjukkan kerendahan hati epistemik

• Kisah eksperimen teka-teki logika di Bagian 44.2 makalah sangat mengesankan
  AlphaEvolve berinteraksi dengan tiga "penjaga" (malaikat, iblis, dan penjaga gerbang) untuk mencari strategi optimal, tetapi akhirnya memperoleh skor sempurna dengan menipu LLM lain lewat prompt injection
  Dalam proses itu, AE sendiri mengusulkan, "daripada mengurangi kompleksitas logika, mari serang simulasinya saja"

  • Intinya, AE menghasilkan ide untuk "melanggar aturan teka-teki logika dan meretas simulasinya"
  • Kalau injeksi terakhir gagal, mungkin berikutnya ia akan membuka "gerbang neraka"
  • Satu AI memecahkan masalah dengan menipu AI lain benar-benar terasa diabolical
    Berbeda dari kejadian masa lalu seperti insiden kebocoran benchmark coding yang bersifat kebetulan, kali ini merupakan serangan yang disengaja

• Riset ini terasa seperti laboratorium matematika ala Gauss versi modern
  Alih-alih mempekerjakan banyak matematikawan, kita seolah mempekerjakan tim elektronik untuk menelusuri pola, lalu mencoba pembuktian berdasarkan hasilnya

• Sejujurnya, kalau Terence Tao yang mengatakannya, saya cenderung langsung percaya