Siklus Claude [PDF]

 (www-cs-faculty.stanford.edu)
4 poin oleh GN⁺ 2026-03-04 | 1 komentar | Bagikan ke WhatsApp
  • Claude Opus 4.6 milik Anthropic berhasil menyelesaikan masalah dekomposisi siklus Hamiltonian terarah yang telah diteliti Donald Knuth selama beberapa minggu
  • Masalahnya adalah mencari dekomposisi menjadi tiga siklus Hamiltonian pada graf berarah dengan (m^3) simpul, dan Claude berhasil menyelesaikannya secara lengkap untuk m ganjil
  • Claude menjalankan berbagai strategi pencarian secara bertahap, termasuk dekomposisi fiber, pola serpentine 3D, penelusuran mendalam (DFS), dan simulated annealing
  • Pada akhirnya, Claude menurunkan solusi umum dalam bentuk program Python, dan Filip Stappers memverifikasinya untuk m ganjil dari 3 hingga 101, mengonfirmasi dekomposisi lengkap
  • Knuth menilai hasil ini sebagai kemajuan terobosan dalam penalaran otomatis dan pemecahan masalah kreatif, sambil menegaskan bahwa kasus m genap masih belum terpecahkan

Latar belakang dan definisi masalah

  • Topik penelitian ini berkaitan dengan siklus Hamiltonian terarah (directed Hamiltonian cycles), dan dijadwalkan akan dimasukkan ke jilid mendatang dari The Art of Computer Programming karya Knuth
  • Graf terdiri dari (m^3) simpul (ijk), dan dari setiap simpul ada tiga sisi: (i+jk), (ij+k), (ijk+)
  • Tujuannya adalah menemukan solusi umum yang, untuk semua (m>2), mendekomposisi sisi-sisi tersebut menjadi tiga siklus terarah (m^3)-siklus

Proses eksplorasi Claude

  • Claude Opus 4.6 adalah model hybrid reasoning dari Anthropic; Filip Stappers memberikan masalah ini dan mengarahkan agar proses pengerjaannya didokumentasikan
  • Pada tahap awal, Claude merumuskan ulang masalah ini sebagai graf fungsional dan masalah penugasan permutasi, lalu mencoba pendekatan fungsi linear dan kuadratik, tetapi gagal
  • Setelah itu Claude bereksperimen berturut-turut dengan pencarian DFS, analisis pola serpentine 2D, dan pola berbasis Gray code 3D
  • Dengan memperkenalkan pendekatan dekomposisi fiber, Claude menganalisis struktur berlapis berdasarkan (s = (i+j+k) \mod m), lalu menemukan solusi parsial melalui simulated annealing (SA)

Penemuan solusi dan verifikasi

  • Pada langkah eksplorasi ke-31, Claude menghasilkan program Python yang memakai aturan ketergantungan satu koordinat per fiber
  • Program ini menghasilkan tiga siklus Hamiltonian lengkap untuk m=3,5,7,9,11
  • Filip Stappers mengujinya untuk semua m ganjil dari 3 hingga 101 dan mengonfirmasi dekomposisi lengkap
  • Knuth kemudian menyederhanakannya ke dalam kode C dan membuktikan secara matematis bahwa tiap siklus memang memiliki panjang (m^3)

Generalisasi dan analisis matematis

  • Dikonfirmasi bahwa sebagian siklus Hamiltonian pada m=3 dapat digeneralisasi ke semua m ganjil
    • Dari 11.502 siklus pada (m=3), sebanyak 1.012 dapat digeneralisasi ke (m=5), dan 996 di antaranya tetap berlaku hingga (m=7)
    • Ke-996 ini dapat digeneralisasi ke semua m ganjil > 1
  • Dekomposisi "mirip Claude" didefinisikan oleh aturan sederhana yang hanya bergantung pada nilai batas i, j, s (0 atau m−1)
  • Teorema: agar dekomposisi "mirip Claude" valid untuk semua m ganjil > 1, tiga siklus pada m=3 harus merupakan siklus Hamiltonian yang dapat digeneralisasi
  • Hasil komputasi menunjukkan bahwa 760 dekomposisi mirip Claude valid untuk semua m ganjil

Ketakterpecahan m genap dan kesimpulan

  • Untuk m genap, masalah ini masih terbuka (open)
    • Ketidakmungkinan untuk (m=2) telah dibuktikan dalam penelitian sebelumnya
    • Claude menemukan solusi parsial pada (m=4,6,8), tetapi gagal menggeneralisasikannya
  • Saat mengeksplorasi kasus m genap, Claude menunjukkan kesalahan dan perilaku abnormal sehingga pencarian dihentikan
  • Knuth menilai ini sebagai pencapaian bersejarah dalam penalaran otomatis berbasis AI, dan menyebutnya sebagai kemajuan yang sepadan dengan nama Claude Shannon

Lampiran: aturan untuk dua siklus lainnya

  • Siklus kedua (c=1):
    • Jika (s=0), maka j bertambah; jika (0<s<m−1), maka i bertambah; saat (s=m−1), jika i>0 maka k bertambah, dan jika i=0 maka j bertambah
  • Siklus ketiga (c=2):
    • Pada (s=0), jika j<m−1 maka i bertambah, jika j=m−1 maka k bertambah
    • Pada (0<s<m−1), jika i<m−1 maka k bertambah, jika i=m−1 maka j bertambah
    • Pada (s=m−1), maka i bertambah
  • Urutan simpul pada s=0 untuk tiap siklus dijelaskan secara eksplisit, dan dari sana struktur keseluruhan siklus dapat dibuktikan

Bacaan terkait

1 komentar

 
GN⁺ 2026-03-04
Komentar Hacker News

  • Menarik memikirkan area masalah tempat skalabilitas RL bisa diterapkan
    Dulu harus bergantung pada kognisi manusia, tetapi sekarang pola seperti ini sudah terinternalisasi dalam distribusi probabilitas sehingga siapa pun bisa mengaksesnya
    Namun tetap ada pertanyaan apakah model akan mampu mengejar ketika batas ilmu pengetahuan terus meluas
    Agar Anthropic bisa menjaga Claude tetap mutakhir pada 2030, mereka akan membutuhkan (a) pembelajaran berkelanjutan pada model tetap atau (b) pelatihan berkelanjutan, dan keduanya tidak mudah

    • Model open-weight terasa seperti semacam kapsul waktu
      Setelah titik cutoff pengetahuan, model itu akan selamanya tertahan di momen tersebut
    • Jika berbagi data diizinkan, hasil penalaran hari ini bisa menjadi data pelatihan untuk besok
      Bisa dibayangkan model yang memberi inferensi gratis kepada peneliti, lalu memakai jejak proses berpikir (trace) mereka sebagai data pelatihan
    • Dari yang belakangan dikatakan para peneliti, arsitektur model tampaknya akan berkembang ke arah perluasan besar-besaran context window
      Model seperti Qwen3-next, Qwen3.5, dan Nemotron 3 Nano mendukung window sejuta token sambil mengurangi biaya memori lewat hybrid attention
    • Sebagian besar riset dan pembelajaran sudah berlangsung melalui LLM dan agen coding
      Loop umpan balik real-time dari verifikasi manusia, eksekusi kode, dan pencarian berfungsi sebagai sinyal pembelajaran bagi model
    • Pada 2030, bisa jadi justru Claude yang menjaga Anthropic tetap mutakhir
      Setengah bercanda, tapi bukan sesuatu yang sepenuhnya mustahil

  • Ini mengingatkan pada percakapan GPT-4 antara Wolfram dan Knuth yang pernah ada
    Knuth saat itu skeptis, tetapi setelah melihat model seperti Opus 4.6 belakangan ini, tampaknya sikapnya melunak
    Sikap mau mengubah pandangan berdasarkan bukti baru itu keren
    Percakapan terkait bisa dilihat di sini

    • Memperbarui probabilitas prior berdasarkan bukti baru memang inti daya tarik statistika Bayesian
      Itu juga inti dari cara berpikir ilmiah

  • Rasanya pengantar tulisan Knuth agak berpotensi menyesatkan
    Seolah Claude yang langsung menyelesaikan masalahnya, padahal sebenarnya Claude membuat contoh dan Knuth yang menggeneralisasikannya menjadi pembuktian

    • Saya juga pernah mencoba eksperimen serupa dengan Claude, dan sinergi antara manusia dan LLM memang besar
      LLM lemah dalam menentukan arah, tetapi begitu arahnya diberikan, ia sangat bagus dalam eksplorasi mendalam
      Jika dibiarkan sendiri ia bisa melenceng, tetapi bila dipandu manusia ia menjadi partner yang hebat
    • Saya tidak merasa Knuth melebih-lebihkan
      Claude memang berperan menembus inti masalah, dan manusia hanya merapikannya
    • Bisa juga dianggap Claude memang melakukan ‘penyelesaian’ seperti yang dimaksud Knuth
      Penataan pembuktian hanyalah pekerjaan sekunder
    • Kemampuan untuk kembali ke percobaan sebelumnya lalu merefleksikan dan memperbaiki tampak jelas sebagai tanda kecerdasan

  • Menarik bahwa Claude berhenti pada kasus genap
    Mungkin ia dipakai lewat claude.ai atau claude code, dan masuk ke kelebihan konteks (dumb zone)

    • Akan bagus jika dumb zone ini bisa divisualisasikan
      Misalnya seperti Copilot yang menampilkan grafik penggunaan konteks, sehingga pengguna bisa menyadarinya
    • Pada akhirnya, tanpa pemadatan konteks (compacting) hasilnya akan berantakan
    • Dari penyebutan ‘plan document’, tampaknya ia memakai dokumen manajemen sesi
    • Ada juga yang penasaran apa sebenarnya dumb zone itu

  • Ada yang mencoba menyuruh Claude menyelesaikan teka-teki pentomino yang dipopulerkan Arthur C. Clarke
    Setelah merepresentasikan papan dan potongan sebagai integer 64-bit, ia membuat program C# yang menyelesaikannya dengan cepat, tetapi pada kasus 20x3 ia memberi jawaban salah karena mapping yang keliru
    Menarik karena itu terasa seperti jenis kesalahan yang juga bisa dilakukan manusia

  • Singkatnya, Knuth mengajukan masalah dan temannya melakukan sekitar 30 kali eksplorasi dengan Claude
    Claude membuat program Python yang menyelesaikan kasus ganjil, lalu Knuth membuktikan pendekatan tersebut
    Kasus genap masih tetap menjadi masalah yang belum terpecahkan

    • Namun, frasa Knuth “careful human guidance” terasa agak berlebihan
      Dalam praktiknya, Claude sering berhenti atau membuat kesalahan, dan manusia hanya sesekali mengingatkan
    • Yang tampaknya ingin ditekankan Knuth adalah bahwa pembuktian formal tetap merupakan tugas manusia
      Siapa yang pertama menghasilkan ide inti masih belum jelas

  • Sekarang benar-benar masa yang menyenangkan untuk menangani masalah yang belum terpecahkan
    Rasanya ingin kembali mengeksplorasi riset dari 10 tahun lalu bersama Claude

  • Kekuatan LLM tampaknya ada pada tiga hal: pengetahuan yang sangat luas, kemampuan membuat koneksi, dan trial-and-error yang tak kenal lelah
    Jika tiga hal ini digabungkan, kadang hasilnya mengejutkan
    Mungkin pembuktian P≠NP pun ada pada mata rantai samar yang belum terlihat manusia

    • Poin terakhir itu sebenarnya mungkin bukan sifat LLM itu sendiri, melainkan sifat loop agen
      LLM hanyalah satu komponen di dalamnya
    • Meski begitu, eksplorasi berulang yang tak pernah lelah tetap menjadi keunggulan besar dibanding manusia
      Jika faktor lain sama, inilah perbedaan yang menentukan
    • Saya sepenuhnya setuju bahwa menggabungkan tiga hal itu bisa menghasilkan sesuatu yang hebat
    • Tetapi terasa menakutkan bahwa kemampuan seperti ini bisa dipakai untuk sistem pengawasan
    • ‘Kemampuan membuat koneksi’ tampaknya sebenarnya terbatas pada koneksi yang sudah ada dalam data pelatihan
      Membentuk koneksi yang sepenuhnya baru masih sulit

  • Saya ragu apakah benar “LLM hanyalah mesin yang memprediksi kata berikutnya”
    Kalau begitu, bagaimana menjelaskan pemecahan masalah seperti ini? Apakah ini bisa disebut ‘berpikir’?

    • Jika kita bisa memprediksi dengan sempurna kata berikutnya yang akan diucapkan Einstein, itu sendiri sudah berarti mengimplementasikan kecerdasan
      Ungkapan “kata yang paling mungkin” adalah penjelasan yang terlalu disederhanakan
    • Penjelasan itu cocok untuk base model, tetapi model seperti Opus 4.6 memiliki RLHF dan pelatihan tambahan di atasnya
      Pada akhirnya, “kemampuan memprediksi apa yang akan terjadi berikutnya dengan baik” mungkin justru merupakan definisi kecerdasan
    • Base model belajar pola “Answer:” dari web, sehingga secara alami juga mempelajari pola pemecahan masalah
      Berkat RLHF, model tidak sekadar diberi imbalan untuk prediksi, tetapi untuk memberikan jawaban yang membantu
      Itulah sebabnya ekspresi seperti “delve” muncul terlalu sering
      Lihat dokumen AI SIGNS terkait hal ini
    • Pada akhirnya model tetap mengambil kata dari distribusi probabilitas, tetapi distribusi itu sendiri adalah inti kecerdasan
      LLM sedang mempelajari distribusi itu
    • Mekanisme sederhana berupa “kata yang paling mungkin” menjadi sangat kuat ketika digabungkan dengan seluruh pengetahuan umat manusia
      Menyederhanakannya untuk mengejek hanya berarti melewatkan inti teknologinya

  • Menarik bahwa ini adalah laporan dari Knuth sendiri
    Sudah waktunya membaca dan memahaminya langsung tanpa bantuan LLM

    • Karena tidak punya waktu, ada yang malah mencari tautan ringkasan yang dibuat orang lain