Rekayasa Algoritma Agentic: Meningkatkan Exact Minimum Cut Memori Bersama

Agen LLM otonom mengoptimalkan solver exact min-cut mutakhir, mencapai percepatan hingga 127\times pada instans inti DIMACS

David A. Bader; Adil Chhabra; Ernestine Großmann; Monika Henzinger; Alexander Noe; Christian Schulz· 2026· DOI 10.48550/arXiv.2609.07204

Masalah inti

Masalah minimum cut untuk graf berbobot sisi tak berarah berupaya mempartisi himpunan simpul menjadi dua blok sambil meminimalkan jumlah berbobot sisi yang melintasi cut. Secara formal, diberikan graf G = (V, E) dengan bobot sisi w : E \to R^{+}, minimum cut adalah: S \subset V min e \in δ (S) \sum w (e) di mana δ (S) adalah himpunan sisi dengan tepat satu titik akhir di S . Masalah fundamental ini memiliki aplikasi dalam keandalan jaringan, clustering, dan segmentasi citra. Selama beberapa tahun terakhir, penulis telah merekayasa berbagai algoritma cepat untuk masalah ini, yang berpuncak pada algoritma exact yang tersedia dalam paket open-source VieCut. Pada instans dunia nyata, VieCut mengungguli solver tercepat sebelumnya dengan faktor hingga 2,5 secara sekuensial dan hingga 12,9 secara paralel. Meskipun telah dilakukan penyetelan manual secara ekstensif, penulis berhipotesis bahwa optimasi lebih lanjut masih belum ditemukan. Makalah ini memperkenalkan agentic algorithm engineering (AAE), sebuah metodologi di mana agen large language model (LLM) otonom menjalankan siklus rekayasa algoritma pada basis kode yang ada: mereka membentuk hipotesis tentan

Proses AAE menemukan optimasi signifikan pada algoritma VieCut, meskipun telah dilakukan penyetelan manual sebelumnya secara ekstensif. Peningkatan dikuantifikasi sebagai faktor percepatan relatif terhadap algoritma asli. Pada k-core dunia nyata, agen mencapai percepatan 1,28\times secara sekuensial dan 1,63\times dengan 32 thread. Pada instans inti DIMACS, percepatannya jauh lebih besar: 6,26\times secara sekuensial dan 127\times dengan 32 thread. Hasil ini dirangkum dalam tabel berikut: | Jenis Instans | Percepatan Sekuensial | Percepatan 32-Thread | |---------------|-------------------|-------------------| | k-core dunia nyata | 1,28\times | 1,63\times | | Instans inti DIMACS | 6,26\times | 127\times | Instans inti DIMACS sangat menantang dan sering digunakan sebagai benchmark untuk algoritma minimum cut. Percepatan 127\times dengan 32 thread menunjukkan bahwa agen menemukan optimasi yang sangat meningkatkan skalabilitas paralel. Percepatan sekuensial 6,26\times pada instans ini juga luar biasa, mengingat algoritma asli sudah sangat dioptimalkan. Perubahan agen kemungkinan melibatkan peningkatan struktur data, rutin kontraksi paralel, atau reduksi berbasis batas. Sifat pasti dari optimasi tidak dirinci dalam abstrak, tetapi h

Masalah minimum cut untuk graf berbobot sisi tak berarah berupaya mempartisi himpunan simpul menjadi dua blok sambil meminimalkan jumlah berbobot sisi yang melintasi cut. Secara formal, diberikan graf G = (V, E) dengan bobot sisi w : E \to R^{+}, minimum cut adalah:

S \subset V min e \in δ (S) \sum w (e)

Hasilnya menunjukkan bahwa agentic algorithm engineering dapat menghasilkan peningkatan substansial bahkan untuk algoritma yang sudah sangat disetel. Percepatan pada instans inti DIMACS sangat mencolok, menunjukkan bahwa agen menemukan optimasi non-obvious yang terlewat oleh insinyur manusia. Percepatan yang lebih besar dalam pengaturan paralel menunjukkan bahwa agen mungkin telah meningkatkan penyeimbangan beban, mengurangi overhead sinkronisasi, atau meningkatkan rutin kontraksi paralel. Metodologi AAE bersifat umum dan dapat diterapkan pada algoritma dan domain lain. Namun, beberapa pertanyaan masih tersisa: Bagaimana agen menghasilkan hipotesis? Apa peran data pelatihan LLM? Seberapa transferable optimasi tersebut ke instans lain? Penulis memperkenalkan AAE sebagai metodologi, dan karya ini berfungsi sebagai proof of concept. Pekerjaan selanjutnya dapat mengeksplorasi integrasi AAE ke dalam alur kerja rekayasa algoritma standar, pengembangan strategi prompting yang lebih baik, dan penerapan pada domain masalah lain. Sifat open-source VieCut memfasilitasi reproduktibilitas dan eksperimen lebih lanjut. Temuan makalah ini menunjukkan bahwa agen LLM dapat memperkuat keahlian manusia dalam rekayasa algoritma, berpotensi mempercepat pengembangan algoritma berperforma tinggi.

Praktisi dan peneliti ilmu komputer

Membuka konten member…