AlphaEvolve Menurunkan Eksponen Perkalian Matriks—Bukan Tagihan GPU Anda

Sebuah preprint baru melaporkan bahwa AlphaEvolve membantu menurunkan batas atas terbaik yang diketahui untuk eksponen perkalian matriks, yang biasanya ditulis sebagai huruf Yunani omega, dari $2.371339$ menjadi $2.371177$ . Itu adalah rekor teoretis yang nyata. Namun, ini bukan kernel perkalian matriks baru, bukan percepatan GPU yang diukur, dan bukan alasan untuk mengharapkan tagihan cloud lebih rendah.

Perbedaan ini penting karena perkalian matriks menggerakkan training dan inferensi jaringan neural. Judul tentang eksponen yang lebih baik dapat terdengar seperti akselerasi AI langsung. Dalam kasus ini, para peneliti menggunakan teknik machine learning dan AlphaEvolve untuk mencari masalah optimasi matematis yang sangat besar. Mereka kemudian memakai proses aritmetika eksak yang terpisah untuk mensertifikasi hasil kandidat.

Paper 17 Agustus itu masih berupa preprint, dan kode verifikasi serta solusi yang ditemukan yang dijanjikan belum tersedia untuk publik per 20 Agustus. Karena itu, sertifikat tersebut belum direproduksi secara independen di ruang publik. Kesimpulan yang hati-hati adalah: penulis melaporkan batas atas baru yang telah diperiksa secara rigor, dengan satu langkah penting dalam reproduktibilitas yang masih belum selesai.

Apa arti eksponen perkalian matriks?

Metode yang biasa dipelajari di sekolah mengalikan dua matriks $n \times n$ dengan kira-kira $n^3$ operasi aritmetika. Eksponennya adalah $3$ karena menggandakan dimensi matriks meningkatkan hitungan operasi utama sekitar $2^3=8$ kali.

Pada 1969, Volker Strassen menunjukkan bahwa perkalian matriks dapat menggunakan kurang dari operasi kubik. Itu membuka pertanyaan yang terus berjalan: seberapa dekat eksponen dapat mendekati $2$ , skala yang sekadar diperlukan untuk menulis $n^2$ entri dalam jawaban?

Peneliti memformalkan pertanyaan ini menggunakan omega, $\omega$ . Secara informal, $\omega$ adalah eksponen terkecil yang memungkinkan matriks persegi berukuran cukup besar dikalikan dengan sekitar $n^\omega$ operasi aritmetika, sementara faktor berorde lebih rendah disembunyikan oleh notasi asimtotik.

Ada dua batas yang harus dipisahkan:

Output itu sendiri memberikan batas bawah $\omega \geq 2$ .
Algoritme atau konstruksi matematika yang ditemukan memberikan batas atas, seperti $\omega < 2.371177$ .

Menurunkan batas atas tidak mengungkap nilai omega yang sebenarnya. Itu membuktikan bahwa jawaban yang belum diketahui tidak lebih besar dari angka baru tersebut. Jarak antara $2$ dan $2.371177$ masih terbuka.

Rekor sebelumnya, $\omega < 2.371339$ , diterbitkan dalam prosiding SODA 2025. Perbaikan paper baru adalah $0.000162$ . Angka itu tampak kecil, tetapi kemajuan di bidang ini selama beberapa dekade memang kecil dan sulit. Pelaporan independen dari Quanta memberi konteks yang tepat: rekor-rekor ini membantu peneliti memahami batas teoretis masalah tersebut, sementara metode laser di baliknya dianalisis, bukan dijalankan sebagai implementasi praktis.

Apa yang sebenarnya diubah AlphaEvolve

Hasil baru ini bukan kisah tentang model bahasa yang langsung menciptakan pembuktian final. Pekerjaan tersebut memiliki empat lapisan berbeda: reformulasi matematika, pencarian numerik berskala besar, perbaikan program dengan bantuan AlphaEvolve, dan sertifikasi eksak.

1. Manusia merumuskan ulang masalah optimasi

Rekor omega terbaru menggunakan penyempurnaan metode laser, sebuah teknik teoretis untuk menguraikan dan menganalisis perkalian matriks. Analisis itu dapat dinyatakan sebagai masalah optimasi non-konveks dengan kendala. “Non-konveks” berarti lanskapnya dapat memiliki banyak titik yang baik secara lokal, sehingga mengikuti arah menurun tidak menjamin ditemukannya jawaban terbaik secara keseluruhan.

Rekor sebelumnya mencari konstruksi sampai level rekursi maksimum $3$ , yang melibatkan sekitar 25.000 parameter yang dapat dioptimalkan. Tim baru merumuskan ulang masalah agar dapat mencapai level rekursi $4$ , ketika ruang pencarian bertumbuh menjadi hampir 7 juta parameter.

Ruang pencarian yang lebih besar tidak otomatis lebih baik: ruang itu juga jauh lebih sulit dioptimalkan. Kontribusinya adalah membuatnya dapat ditangani secara komputasional.

2. Alat machine learning membuat pencarian dapat didiferensiasikan dan diparalelkan

Banyak variabelnya adalah distribusi probabilitas. Alih-alih mengoptimalkan probabilitas yang dibatasi secara langsung, peneliti merepresentasikannya sebagai logit tanpa batas lalu mengubah logit tersebut menjadi probabilitas dengan fungsi softmax. Ini adalah pola machine learning standar.

Mereka menggunakan algoritme Sinkhorn-Knopp untuk menangani distribusi entropi maksimum, automatic differentiation untuk menghitung gradien, dan Adam untuk memperbarui parameter. Mereka mengimplementasikan sistem dalam JAX, mengatur ulang komputasi graf yang tidak beraturan menjadi tensor bertopeng dan berkelompok yang dapat diproses GPU secara paralel.

Sistem berbasis gradien ini sudah memperbaiki rekor sebelumnya. Paper menyebut sistem tersebut mengurangi batas sekitar $0.000097$ sebelum AlphaEvolve diterapkan.

3. AlphaEvolve memperbaiki program optimizer

AlphaEvolve adalah coding agent yang mengusulkan perubahan program, menjalankan kandidat terhadap evaluator otomatis, dan mengembangkan versi yang menjanjikan. Di sini, AlphaEvolve tidak mengalikan matriks produksi. Ia memodifikasi program yang digunakan untuk mencari batas matematis yang lebih baik.

Menurut paper baru, setiap optimizer kandidat memerlukan sekitar lima jam pada satu GPU untuk menghasilkan suatu batas. AlphaEvolve menggunakan batas itu sebagai skornya dan mengembangkan kode agar angkanya lebih kecil. Peneliti melaporkan bahwa pengaturan “evolving constructions” membantu: optimizer anak dimulai dari solusi terbaik yang ditemukan induknya, bukan mulai lagi dari nol.

Pembagian kontribusi dalam paper sangat jelas:

Tahap	Kontribusi yang dilaporkan
Rekor yang telah dipublikasikan sebelumnya	$\omega < 2.371339$
Optimasi baru berbasis gradien	Memperbaiki rekor sekitar $0.000097$
Optimasi yang disempurnakan AlphaEvolve	Memperluas total perbaikan menjadi sekitar $0.000162$
Batas akhir yang dilaporkan	$\omega < 2.371177$

AlphaEvolve memperluas sistem optimasi yang telah berhasil, dirancang manusia dan diberdayakan ML. Mengatakan bahwa AlphaEvolve sendirian “memecahkan perkalian matriks” akan menghapus setup matematis dan perbaikan numerik sebelumnya dari tim tersebut.

4. Aritmetika eksak memeriksa kandidat numerik

Optimizer floating-point dapat mengembalikan angka yang menjanjikan tanpa membuktikan bahwa setiap kendala matematis benar-benar terpenuhi. Kesalahan pembulatan kecil penting ketika keuntungan yang diklaim hanya berada pada tempat desimal keempat.

Karena itu, penulis menjelaskan langkah verifikasi yang terpisah. Mereka membulatkan solusi floating-point menjadi bilangan rasional, menghitung kuantitas turunan menggunakan aritmetika rasional eksak, dan membatasi logaritme ke arah konservatif. Ini dimaksudkan untuk mengubah kandidat numerik menjadi sertifikat yang valid untuk batas atas.

Pemisahan tersebut adalah matematika berbantuan komputer yang baik: gunakan komputasi aproksimatif cepat untuk penemuan, lalu metode yang lebih ketat untuk verifikasi. Namun pembaca harus membedakan klaim sertifikasi penulis dari reproduksi independen publik. Paper mengatakan repositori verifikasi sedang disiapkan; repositori itu belum ditautkan dari arXiv ketika publikasi.

Mengapa batas baru tidak membuat perkalian matriks GPU lebih cepat

Eksponen asimtotik menjelaskan bagaimana hitungan operasi tumbuh ketika $n$ menjadi sangat besar. Performa GPU nyata bergantung pada lebih banyak hal:

konstanta dan suku orde lebih rendah yang disembunyikan oleh notasi asimtotik;
ukuran dan bentuk matriks yang digunakan model;
perpindahan memori, perilaku cache, dan komunikasi antarperangkat;
presisi dan stabilitas numerik;
seberapa efektif kernel menggunakan tensor core dan perangkat keras lain; serta
overhead untuk mengubah konstruksi teoretis menjadi langkah yang dapat dieksekusi.

Paper baru tidak menyediakan kernel CUDA, Triton, JAX, atau library vendor yang mengimplementasikan metode laser. Paper itu melaporkan analisis yang lebih baik tentang apa yang mungkin dilakukan secara prinsip.

Perhitungan ilustratif menunjukkan mengapa perubahan eksponen saja tidak dapat memprediksi keuntungan runtime yang berguna. Jika dua algoritme imajiner memiliki konstanta sama dan biaya yang persis proporsional dengan $n^{2.371339}$ dan $n^{2.371177}$ , eksponen yang lebih kecil akan mengurangi suku utama sebesar berikut:

Dimensi matriks $n$	Pengurangan ilustratif pada suku utama
$1{,}000$	sekitar $0.11\%$
$1{,}000{,}000$	sekitar $0.22\%$
$1{,}000{,}000{,}000{,}000$	sekitar $0.45\%$

Ini bukan benchmark. Asumsi konstanta yang sama tidak realistis, dan konstruksi metode laser dapat membawa biaya tersembunyi yang sangat besar. Tabel ini hanya menunjukkan betapa lambat perbedaan eksponen $0.000162$ berlipat. Untuk ukuran praktis, algoritme yang telah dioptimalkan dengan eksponen asimtotik lebih buruk dapat dengan mudah menjadi lebih cepat.

Ini juga memisahkan hasil tersebut dari pekerjaan perkalian matriks AlphaEvolve lainnya. Paper sistem sebelumnya melaporkan konstruksi 48 perkalian untuk masalah bernilai kompleks berukuran $4 \times 4$ tertentu. Preprint omega justru memperbaiki batas asimtotik melalui pipeline optimasi berbeda. Tidak satu pun hasil itu menjadi bukti bahwa perkalian matriks GPU biasa tiba-tiba menjadi lebih murah.

Mengapa hasil ini tetap penting

Nilai langsungnya bersifat metodologis dan teoretis.

Pertama, tim tersebut meningkatkan skala optimasi rumit dari sekitar 25.000 menjadi 7 juta parameter dengan menerjemahkan gagasan dari machine learning modern ke dalam pencarian pembuktian berbantuan komputer. Itu menciptakan jembatan konkret antara rekayasa optimasi dan ilmu komputer teoretis.

Kedua, hasil ini menunjukkan peran berguna coding agent evolusioner. AlphaEvolve mencari program optimizer, bukan hanya pengaturan numerik. Evaluator menyediakan tujuan yang presisi, sementara peneliti manusia menyediakan representasi matematika, sistem komputasi, standar verifikasi, dan interpretasi.

Ketiga, bahkan perbaikan kecil pada batas atas mempersempit hal-hal yang perlu dijelaskan peneliti. Jika eksponen sebenarnya adalah $2$ , analisis metode laser saat ini masih jauh darinya. Jika nilainya lebih besar, batas atas dan bawah yang lebih baik membantu memetakan wilayahnya.

Bagi praktisi, pelajaran yang paling dapat ditransfer bukan perkalian matriks umum yang lebih cepat. Pelajarannya adalah alur kerja:

nyatakan pencarian ilmiah yang sulit sebagai program yang dapat dievaluasi;
gunakan optimasi terdiferensiasikan dan paralelisme perangkat keras jika sesuai;
biarkan coding agent mengeksplorasi perubahan tingkat program di bawah skor yang terukur; dan
verifikasi hasil numerik yang menang dengan metode yang dirancang untuk menyingkirkan kesalahan aproksimasi.

Alur kerja itu lebih menarik daripada versi dramatis judulnya karena menunjukkan tepat di mana sistem AI membantu—dan di mana penilaian matematis manusia tetap penting.

Bukti apa yang seharusnya muncul berikutnya?

Checkpoint pertama adalah repositori yang dijanjikan, berisi kode verifikasi dan solusi yang ditemukan. Peneliti independen seharusnya dapat menjalankan sertifikat, memeriksa arah setiap batas numerik, dan mereproduksi $\omega < 2.371177$ .

Checkpoint berikutnya adalah peer review. Paper ini adalah preprint arXiv, bukan publikasi yang telah ditinjau sejawat. Review dapat mengonfirmasi hasil, menemukan masalah teknis, atau memperjelas bagian konstruksi yang paling pantas diberi bobot.

Terakhir, perhatikan pekerjaan lanjutan yang memisahkan tiga pertanyaan yang sering disatukan dalam satu judul:

Bisakah optimizer menemukan batas asimtotik yang lebih rendah dan tersertifikasi?
Bisakah metode ini mengajarkan peneliti sesuatu yang baru tentang batas pendekatan laser?
Bisakah gagasan terkait menjadi implementasi stabil dan sadar-perangkat-keras untuk matriks realistis?

Hanya pertanyaan pertama yang dijawab oleh rekor yang dilaporkan. Untuk menyegarkan linear algebra di balik perkalian matriks, mulai dengan panduan kami dari vektor ke embedding. Untuk kerangka menilai perbaikan yang dilaporkan, lihat bagaimana evaluasi membentuk produk AI.