Menelaah varian linear attention keluarga DeltaNet

• Dimulai dari softmax attention, diturunkan secara bertahap hingga linear attention yang memakai state berukuran tetap, DeltaNet yang hanya mencatat error, Gated DeltaNet yang meredam seluruh state, dan Kimi Delta Attention (KDA) yang meredam per kanal
• Linear attention dasar menyimpan jumlah outer product key-value masa lalu ke dalam state (S_t) sehingga berjalan linear terhadap panjang sekuens, tetapi muncul interferensi penulisan aditif karena nilai baru tidak ditetapkan melainkan ditambahkan ke asosiasi yang sudah ada
• DeltaNet mencatat selisih antara nilai yang diprediksi dari key saat ini dan target value, dikalikan dengan (\beta_t); tiga interpretasi—kondisi rekonstruksi langsung, gradient descent online, dan pembaruan state rank-1—berujung pada rumus yang sama
• Gated DeltaNet terlebih dulu meredam seluruh state dengan skalar (\alpha_t), dan KDA memperluasnya menjadi matriks diagonal (D_t=\operatorname{Diag}(\alpha_t)) agar tiap kanal key dapat mempertahankan atau menghapus informasi dengan rasio berbeda
• Rekurensi KDA yang sama dijalankan dengan kernel Triton rekuren terpadu untuk decode dan metode chunk untuk training serta prefill panjang; metode chunk memulihkan dependensi intra-token dengan penyelesaian segitiga lalu menyusunnya kembali sebagai perkalian matriks

---

Notasi dan urutan pembahasan

• Dalam notasi bra-ket, (\lvert q\rangle) adalah vektor kolom, (\langle k\rvert) adalah vektor baris, (\langle k\vert q\rangle) adalah skalar, dan (\lvert v\rangle\langle k\rvert) adalah matriks
• Diasumsikan satu head attention kausal dan vektor riil digunakan, key DeltaNet dinormalisasi, dan state memetakan dari ruang key ke ruang value
• Urutan pembahasan adalah softmax attention → linear attention → DeltaNet → Gated DeltaNet → KDA, lalu diakhiri dengan implementasi Triton rekuren dan chunk
• Di antara keluarga DeltaNet, dua varian dipakai pada keluarga model Qwen dan Kimi terbaru

Dari attention berkompleksitas kuadratik ke state linear

• Softmax attention kausal umum menghitung kemiripan key dan query, menormalkan skor terhadap semua key masa lalu menjadi distribusi, lalu mengeluarkan jumlah berbobot dari vektor value
• Untuk sekuens dengan panjang (T), ada (T^2) pasangan key-query
  • Dalam inferensi autoregresif, key dan value bisa di-cache, tetapi ukuran cache tumbuh bersama sekuens
  • Query baru juga harus memeriksa seluruh masa lalu
• Penyebut softmax bergantung bersama pada query saat ini dan semua key sebelumnya, sehingga urutan perhitungan sulit diatur ulang secara sederhana
• Jika softmax dihapus, output bisa dikelompokkan sebagai jumlah outer product key-value masa lalu
  • (S_t=\sum_{i\le t}\lvert v_i\rangle\langle k_i\rvert)
  • (S_t=S_{t-1}+\lvert v_t\rangle\langle k_t\rvert)
  • (\lvert o_t\rangle=S_t\lvert q_t\rangle)
• Identitas kuncinya adalah ((\lvert v\rangle\langle k\rvert)\lvert q\rangle=\langle k\vert q\rangle\lvert v\rangle); alih-alih menyimpan semua key dan value masa lalu, outer product yang sudah dijumlahkan disimpan dalam state berukuran tetap (d_v\times d_k)
• Karena token dilalui satu kali, metode ini berjalan linear terhadap panjang sekuens, tetapi sebagai gantinya kehilangan normalisasi dan selektivitas softmax
  • Linear attention yang lebih canggih memakai feature map dan suku normalisasi

Masalah penulisan aditif pada linear attention

• Tepat setelah mencatat (\lvert v_t\rangle\langle k_t\rvert) untuk key saat ini yang telah dinormalisasi, jika dibaca lagi dengan key yang sama maka (S_t\lvert k_t\rangle=S_{t-1}\lvert k_t\rangle+\lvert v_t\rangle)
• Penulisan baru tidak membuat memori mengembalikan (v_t) lewat penetapan, melainkan menambahkan dengan gaya += ke nilai yang sudah dikembalikan sebelumnya
• Jika state sebelumnya sudah mengembalikan nilai yang benar, value yang sama menjadi terduplikasi, dan karena key tidak saling ortogonal, setiap penulisan dapat saling mengganggu dengan penulisan sebelumnya
• Linear attention menyediakan memori asosiatif terkompresi, tetapi melakukan pembaruan aditif alih-alih pembaruan yang lebih mendekati = yang sebenarnya dibutuhkan

DeltaNet: menulis error prediksi, bukan nilai

• DeltaNet terlebih dulu membaca prediksi lama untuk key baru, (\widehat v_t=S_{t-1}k_t), lalu hanya mencatat selisihnya, bukan seluruh value
  • (e_t=\beta_t(v_t-S_{t-1}k_t))
  • (S_t=S_{t-1}+e_tk_t^\mathsf T)
  • Kekuatan penulisan terlatih (\beta_t) berada pada rentang ([0,1])
• Jika langsung dibaca lagi dengan key yang sama, hasilnya menjadi ((1-\beta_t)S_{t-1}k_t+\beta_tv_t)
  • Jika (\beta_t=1), hasilnya tepat (v_t)
  • Nilai yang lebih kecil hanya menggeser sebagian prediksi lama ke arah target
• Pembaruan ini lokal di ruang key
  • Pada arah query yang ortogonal terhadap key saat ini, pembaruan outer product bernilai 0 sehingga respons tidak berubah
  • Hanya asosiasi pada arah key saat ini yang diganti secara selektif

• Menurunkannya dari loss rekonstruksi

  • Jika state (S) dipandang sebagai pemetaan linear dan loss untuk pasangan key-value saat ini didefinisikan sebagai (\frac12\lVert Sk_t-v_t\rVert_2^2), maka gradiennya adalah ((Sk_t-v_t)k_t^\mathsf T)
  • Jika dari (S_{t-1}) dilakukan satu langkah gradient descent dengan besar (\beta_t), hasilnya persis sama dengan rumus pembaruan DeltaNet
  • Pembaruan yang sama bisa diinterpretasikan dengan tiga cara
    • Dalam operasi memori, (\beta_t) adalah kekuatan penggantian asosiasi lama
    • Dalam pembelajaran online, (\beta_t) adalah learning rate
    • Dalam aljabar linear, ini adalah outer product rank-1 dari error prediksi dan key

• Transisi state terstruktur

  • Jika pembaruan dikembangkan, diperoleh (S_t=S_{t-1}(I-\beta_tk_tk_t^\mathsf T)+\beta_tv_tk_t^\mathsf T)
  • Untuk key satuan, (I-\beta_tk_tk_t^\mathsf T) memiliki eigenvalue (1-\beta_t) pada arah key saat ini, dan eigenvalue 1 pada semua arah ortogonal
  • Asosiasi pada arah key lama lebih dulu dihapus lalu asosiasi baru ditambahkan, tetapi pengelolaan usia seluruh state masih belum terselesaikan

Gated DeltaNet: lebih dulu melupakan seluruh state

• Saat seluruh masa lalu dikompresi ke dalam satu matriks, token individual yang sudah tergabung di dalam state tidak lagi bisa dipilih dan dilewati secara selektif
• DeltaNet memang mengoreksi area sekitar key saat ini, tetapi informasi lama di arah lain tetap tinggal dan terus bisa berkontribusi pada pembacaan berikutnya
• Gated DeltaNet menerapkan gerbang retensi skalar terlatih (\alpha_t\in[0,1])
  1. Melupakan dengan (\widetilde S_t=\alpha_tS_{t-1})
  2. Memprediksi dengan (\widehat v_t=\widetilde S_tk_t)
  3. Mengoreksi dengan (e_t=\beta_t(v_t-\widehat v_t))
  4. Mencatat dengan (S_t=\widetilde S_t+e_tk_t^\mathsf T)
• Urutan melupakan → memprediksi → mengoreksi → menulis itu penting
  • Jika memprediksi sebelum peredaman, memori yang dipakai untuk menghitung error akan berbeda dari memori yang benar-benar diperbarui
• Aturan delta menangani penggantian pada key target, sedangkan gerbang skalar menangani penghapusan global; keduanya menyelesaikan masalah yang berbeda
• Namun karena satu (\alpha_t) diterapkan ke seluruh matriks, semua kanal key harus dipertahankan atau dilupakan dengan rasio yang sama

Kimi Delta Attention: peredaman per kanal

• Kimi Delta Attention mengubah skalar (\alpha_t) menjadi vektor berdimensi (d_k) dan membentuk (D_t=\operatorname{Diag}(\alpha_t))
• Karena state memetakan dari ruang key ke ruang value, kanal key bersesuaian dengan kolom-kolom (S), dan perkalian kanan (S_{t-1}D_t) menerapkan laju retensi berbeda pada tiap kolom
• KDA bekerja dalam urutan berikut
  1. Meredam tiap kanal key dengan (\widetilde S_t=S_{t-1}D_t)
  2. Memprediksi dengan (\widehat v_t=\widetilde S_tk_t)
  3. Mengoreksi dengan (e_t=\beta_t(v_t-\widehat v_t))
  4. Mencatat dengan (S_t=\widetilde S_t+e_tk_t^\mathsf T)
  5. Membaca dengan (o_t=S_t(d_k^{-1/2}q_t))
• Perubahan konseptual dari Gated DeltaNet ke KDA hanyalah menaikkan (\alpha_t) menjadi (D_t), tetapi kini satu kanal bisa dihapus sementara kanal lain dipertahankan

• Transisi diagonal-rank-rendah

  • Jika KDA dikembangkan, diperoleh (S_t=S_{t-1}A_t+\beta_tv_tk_t^\mathsf T), dengan (A_t=D_t(I-\beta_tk_tk_t^\mathsf T))
  • Ini bisa ditulis sebagai (A_t=D_t-b_ta_t^\mathsf T), (b_t=D_tk_t), (a_t^\mathsf T=\beta_tk_t^\mathsf T), sehingga menjadi transisi diagonal-plus-low-rank (DPLR)
  • DPLR berarti transisi (d_k\times d_k) yang bekerja di ruang key, sedangkan state memori sendiri tetap berupa matriks (d_v\times d_k)
  • Tiap anggota keluarga menambahkan fungsi berikut
    • Linear attention: memori rekuren berukuran tetap
    • DeltaNet: penggantian selektif pada arah target
    • Gated DeltaNet: peredaman seluruh state
    • KDA: peredaman per kanal key
  • Implementasi biasanya menyimpan (g_t=\log\alpha_t\le0) lebih dulu, lalu memperoleh laju retensi dengan (\exp(g_t))
  • Implementasi referensi 5 langkah dengan layout transpos (d_k\times d_v) dapat dilihat di naive_recurrent_kda

Kernel Triton rekuren terpadu untuk decode

• KDA memiliki dua cara eksekusi utama
  • Metode rekuren terpadu: cocok untuk decode, sekuens pendek, dan serving yang mempertahankan state
  • Metode chunk: cocok untuk training dan prefill panjang
• fused_recurrent_kda_fwd menjalankan satu program Triton per sekuens, per value head, dan per tile value selebar 32
  • BK mencakup dimensi key pada konfigurasi dukungan umum
  • Setiap program memiliki tile state transpos [BK, BV] dan melintasi token secara berurutan
  • Tile value, head, dan sekuens yang berbeda dieksekusi secara independen
• Kernel menjalankan peredaman state, reduksi prediksi terhadap key, perhitungan residual, penulisan outer product, dan reduksi pembacaan query persis sesuai rekurensi
• Ini cocok untuk decode ketika hanya satu token baru masuk tiap kali, tetapi operasi vektor tidak bisa diubah menjadi perkalian matriks besar yang efisien bagi Tensor Core, sehingga kurang menguntungkan untuk training dan prefill panjang

Chunkwise KDA: menyusun ulang rekurensi menjadi perkalian matriks

• Chunkwise KDA harus memproses (C) token sekaligus sambil menghasilkan state dan output yang persis sama dengan metode rekuren per token
• Setiap chunk menghitung dua hasil
  • (S_{c+1}) setelah memproses seluruh chunk dari state masuk (S_c)
  • Output kausal untuk semua token di dalam chunk
• Kesulitan utamanya adalah error delta tiap token bergantung pada penulisan sebelumnya dalam chunk yang sama

• Peredaman kumulatif dan error sementara

  • Misalkan peredaman diagonal token (i) adalah (D_i), dan peredaman kumulatif dari batas chunk hingga token (i) adalah (D_{0:i}=D_0D_1\cdots D_i)
  • Saat penulisan token (j) diteruskan sampai token (i), yang diterapkan adalah (D_{j+1:i}); karena matriks diagonal saling komutatif, matriks peredaman dapat dipertukarkan
  • Mula-mula dihitung secara paralel error sementara yang mengabaikan penulisan lain dalam chunk
    • (\bar e_i=\beta_i(v_i-S_cD_{0:i}k_i))
  • Untuk semua token selain token pertama, error sementara ini belum memasukkan pengaruh penulisan sebelumnya di chunk yang sama, sehingga tidak bisa dipakai apa adanya

• Memulihkan dependensi kausal

  • Koefisien pengaruh token sebelumnya (j) terhadap error token saat ini (i) didefinisikan sebagai (\rho_{ij}=\beta_i k_j^\mathsf TD_{j+1:i}k_i)
  • Error sebenarnya memiliki dependensi berurutan berbentuk (e_i=\bar e_i-\sum_{j<i}\rho_{ij}e_j)
  • Jika (\rho_{ij}) ditempatkan ke dalam matriks bawah-segitiga ketat (R_c), maka matriks error yang ditumpuk dapat dihitung sebagai (E_c=\bar E_c(A_c^{kk})^\mathsf T), dengan (A_c^{kk}=(I+R_c)^{-1})
  • Tidak diperlukan invers matriks dense umum
    • (I+R_c) adalah matriks segitiga dengan elemen diagonal 1
    • Cukup lakukan penyelesaian segitiga kausal untuk setiap kanal value

• Menghitung state akhir chunk

  • State yang masuk melewati semua peredaman dalam chunk, dan tiap penulisan di dalam chunk hanya melewati peredaman yang berada setelahnya
  • Jika key yang telah diredam hingga akhir chunk ditumpuk per baris dalam (K_c^{\mathrm{end}}), state dapat diringkas menjadi perkalian matriks berikut
    • (S_{c+1}=S_cD_{0:C-1}+E_cK_c^{\mathrm{end}})
  • Banyak penulisan outer product rank-1 digabung menjadi satu perkalian matriks untuk memajukan seluruh state chunk sekaligus

• Menghitung semua output di dalam chunk

  • KDA membaca setelah menulis token saat ini, sehingga output token (i) juga mencakup penulisannya sendiri
  • Koefisien pengaruh penulisan sebelumnya (j) terhadap query (i) didefinisikan sebagai (\chi_{ij}=s,k_j^\mathsf TD_{j+1:i}q_i), (j\le i)
  • Koefisien ini ditempatkan ke dalam matriks pembacaan bawah-segitiga (A_c^{qk})
    • Nol pada segitiga atas memblok kontribusi token masa depan
    • Elemen diagonal mencerminkan perilaku token saat ini yang membaca setelah menulis dirinya sendiri
  • Jika vektor yang telah diredam dari batas hingga tiap query ditumpuk dalam (Q_c^{\mathrm{boundary}}), maka seluruh output menjadi
    • (O_c=sS_cQ_c^{\mathrm{boundary}}+E_c(A_c^{qk})^\mathsf T)
  • Perkalian matriks pertama membaca state masuk chunk yang telah diredam, dan perkalian kedua menambahkan kontribusi penulisan kausal dari dalam chunk

Pipeline Triton chunkwise

• Implementasi chunk bukan satu kernel raksasa, melainkan pipeline yang terdiri dari beberapa pemanggilan kernel
• Pertama, dihitung log peredaman kumulatif di dalam chunk
  • Selisih dua prefix sum dipakai untuk merepresentasikan (D_{j+1:i}) tanpa perlu mengalikan vektor retensi yang panjang
• Berikutnya dibuat matriks interaksi kausal (A^{qk}) dan (A^{kk}), lalu dengan (A^{kk}) dibentuk bentuk WY untuk penulisan terkoreksi chunk tersebut
• Kernel state melakukan satu-satunya lintasan antarchunk
  • Menghasilkan state yang masuk ke tiap chunk
  • Menyelesaikan error delta chunk
• Setelah state masuk dihitung, kernel output dapat memproses token dari chunk dan tile berbeda secara paralel
• Implementasi aktual mula-mula menghitung blok interaksi diagonal 16-token, lalu menjalankan kernel terpadu untuk bagian non-diagonal dan penyelesaian segitiga
• chunk_kda_fwd mengorkestrasi langkah-langkah tersebut, dengan titik masuk utama chunk_kda_fwd_intra, chunk_gated_delta_rule_fwd_h, dan chunk_gla_fwd_o_gk
  • v_new dalam kode adalah error yang telah diselesaikan
  • h adalah state masuk chunk
  • kg adalah key yang telah diredam hingga akhir chunk
• Metode rekuren dan metode chunk bukan attention yang berbeda, melainkan dua jadwal eksekusi dari rekurensi KDA yang sama
  • Metode rekuren adalah operasi vektor serial untuk decode berlatensi rendah
  • Metode chunk adalah operasi matriks untuk training dan prefill yang berpusat pada Tensor Core

[GN⁺]

Opini Hacker News

• Selama 15 tahun terakhir, machine learning membutuhkan notasi matematika yang seragam, dan mungkin memang akan terus membutuhkannya. Dulu malah lebih parah karena tiap makalah dari peneliti di berbagai penjuru dunia memakai notasi yang aneh-aneh
  Jika notasi berbeda di setiap makalah, akan muncul hambatan dalam memahami isinya. Setidaknya tulisan ini menjelaskan notasinya secara eksplisit sejak awal, dan makalah yang melakukan ini tergolong jarang. Awalnya saya bahkan tidak menyadari ada fitur pengalihan notasi, tetapi ternyata sangat berguna

  • Saya tidak paham alasan orang lebih menyukai notasi matematika tradisional seperti ∣q⟩ alih-alih simbol satu huruf atau tipe data yang eksplisit. Memang lebih ringkas, tetapi menurut saya rumus akan jauh lebih mudah dipahami jika ditulis sebagai pseudocode atau bahasa pemrograman nyata seperti Python
  • Tulisan ini hanya menjelaskan satu aspek dari notasi, tetapi tidak memberikan definisi variabel yang dipakai. Jika pernah belajar machine learning, Anda mungkin tahu atau bisa menebak apa itu k, q, dan S, tetapi tanpa pengetahuan latar yang relevan, sebagian besar isi tulisan ini jadi sulit dipahami
  • Dulu saya juga berpikir begitu, tetapi karena waktu yang dihabiskan untuk melihat rumus jauh lebih banyak daripada melihat kode, setelah memahami arti simbolnya, notasi yang ringkas justru jauh lebih mudah dibaca. Kita juga jadi tidak perlu pusing dengan penamaan, yang memang terkenal sulit jika ditulis dengan kata-kata

• Dibilang “bisa saja dipikirkan sendiri…”, tetapi membuat atau menggabungkan sesuatu yang sebelumnya belum ada itu sangat sulit
  Begitu seseorang akhirnya mempublikasikan hasil dari pekerjaan sulit, reaksi seperti “ternyata tidak sulit”, “saya juga bisa melakukannya” langsung muncul, dan semuanya mulai terlihat sederhana. Sering juga saat sedang mengembangkan sesuatu dan merasa telah menemukan hal baru, belakangan baru sadar bahwa itu sudah dibuat pada tahun 1970-an dan dipakai luas. Kita hanya tidak tahu karena belum pernah berpapasan dengannya di jalur kita sendiri

• Bagi saya, notasi bra-ket membuat seluruh isi menjadi sederhana dan intuitif. Dalam notasi vektor, saya sering bingung mana yang horizontal dan mana yang vertikal, lalu hanya mengikuti bentuk besarnya sampai kehilangan fokus, tetapi dengan bra-ket semuanya terasa sangat intuitif
  Sepertinya saya mungkin telah melewatkan banyak tulisan bagus, jadi saya ingin mencoba mengubah tulisan lain ke notasi ini. Sebagai konteks, saya seorang doktor fisika dan punya disleksia ringan

• Saat melihat gaya penulisan seperti “perkalian luar adalah matriks dan perkalian dalam adalah angka. Alih-alih menyimpan semua key dan value masa lalu, kita menyimpan jumlah perkalian luar dalam state berukuran tetap S_t”, saya langsung yakin ini adalah tulisan yang dibuat LLM

  • Mungkin dimulai dari meminta judul yang mengandung istilah yang sedang tren
  • Jika Anda memberi prompt ke Claude agar tidak memakai dash (–), hasilnya akan seperti ini

• Ada juga tutorial yang divisualisasikan: https://snowchord.com/blog/linear-attention-visualized/

• Setiap kali melihat tulisan dan judul seperti ini, saya merasakan rasa syukur yang mendalam dan kerendahan hati terhadap begitu banyak orang yang jauh lebih pintar daripada saya. Saat SMA dan kuliah S1 saya dikenal sangat pintar dan memang di atas rata-rata, tetapi pasti ada jutaan orang yang bisa membuat saya tampak seperti pemula
  Yang saya maksud pintar di sini adalah kemampuan menyimpan konsep dan sistem yang besar serta kompleks di kepala lalu menalar darinya, dan ini tampaknya merupakan bakat yang sangat penting terutama bagi matematikawan

  • Bahkan jika alat AI terus mempercepat pekerjaan, saya rasa sumber utama sebagian besar ide baru akan tetap manusia
    Sebuah eksperimen pikiran yang pernah saya bahas sambil minum dengan teman adalah membesarkan anak-anak dengan mengisolasi mereka dari konten populer yang disuplai layar dan algoritma, lalu menempatkan mereka dalam lingkungan ramah belajar dengan kualitas media dan materi yang dikontrol ketat, seperti saat melatih model mutakhir. Semacam biara untuk anak-anak, dengan cara mengajarkan pengetahuan terbaru tentang realitas melalui matematika, teknik, ilmu komputer, deep learning, dan sebagainya
    Pada akhirnya, untuk memanfaatkan alat AI canggih demi memperluas batas pengetahuan, tetap dibutuhkan orang yang sangat cerdas dan pola pikirnya belum terlalu terkontaminasi. Gagasan bahwa AI akan sepenuhnya menggantikan manusia adalah arah yang keliru

• Sebagai catatan, nama notasi bra-ket memang benar-benar berasal dari kata bracket
  https://en.wikipedia.org/wiki/Bra-ket_notation

• Awalnya saya ragu, tetapi saya jadi menyukainya karena notasi ket membuat operasinya jauh lebih jelas. Meski begitu, akan lebih baik jika ada ulasan singkat tentang beberapa variabel seperti d_k pada attention kuadratik

• Awalnya saya merasa kecil hati karena tidak terpikir solusi ini, tetapi begitu sadar bahwa menulis binary search sendiri dalam JavaScript saja saya masih kesulitan, saya langsung merasa lebih tenang. Tidak ada kemungkinan saya bisa memikirkan Kimi Delta Attention sendiri

  • Ada sisi di mana kode aljabar linear justru mengejutkan mudah untuk ditulis. Tidak seperti kode ilmu komputer umum yang rekursinya saling terjalin rumit, semua variabel di sini punya hubungan matematis, dan konsep matematika yang umum biasanya sudah bisa memakai library yang terimplementasi dengan baik
    Loop juga jarang perlu lebih dari dua atau tiga tingkat kedalaman, dan kalau lebih rumit dari itu, biasanya memang lebih baik diserahkan ke library saja