- Dalam situasi ketika biaya self-attention menjadi bottleneck pada Transformer berkonteks panjang, SPECTRE menurunkan kompleksitas per layer dari O(L²) menjadi O(L log L) dengan token mixer berbasis FFT
- Setiap attention head diganti dengan kombinasi real FFT cepat, spectral gate adaptif terhadap konten, dan inverse FFT, sambil mempertahankan struktur Transformer yang ada
- Pada generasi autoregresif, Prefix-FFT cache mengurangi beban perhitungan ulang FFT di setiap langkah, dan modul wavelet opsional dapat melengkapi hilangnya fitur lokal
- Pada backbone Llama-3.2-1B, SDPA, FlashAttention-2, dan SPECTRE dibandingkan, dengan throughput dan latensi pemrosesan 512~128k token diukur pada NVIDIA A100-80GB
- SPECTRE menunjukkan kinerja setara atau lebih tinggi daripada baseline pada PG-19 dan ImageNet-1k, serta menargetkan pemrosesan konteks panjang di GPU umum dengan tambahan parameter kurang dari 6%
Cara mengurangi biaya kuadratik self-attention dengan FFT
- Transformer berkonteks panjang dibutuhkan untuk tugas yang menangani puluhan ribu token, seperti dialog multi-turn, peringkasan sepanjang buku, dan visi beresolusi tinggi
- Self-attention konvensional memiliki biaya O(n²d), sehingga latensi inferensi dan penggunaan memori meningkat seiring bertambahnya panjang konteks
- SPECTRE adalah pendekatan pengganti drop-in yang mengganti layer self-attention dengan token mixer di domain frekuensi
- Memproyeksikan token ke basis Fourier ortonormal
- Menerapkan gate diagonal adaptif terhadap konten dan gate low-rank opsional
- Mengembalikannya ke ruang token dengan inverse transform
- Kuncinya adalah menurunkan kompleksitas per layer menjadi O(n log n) tanpa mengubah arsitektur jaringan di sekitarnya
Komposisi token mixer dan dukungan generasi
- Komposisi pengganti attention head pada SPECTRE adalah fast real FFT, spectral gate, dan inverse FFT
- Spectral gating bekerja pada n/2 + 1 koefisien frekuensi, dirancang untuk mengurangi komputasi dan penggunaan memori sambil mempertahankan daya representasi
- Prefix-FFT cache berperan mirip KV-cache standar untuk mendukung decoding streaming
- Mengurangi kelemahan spectral mixer sebelumnya yang harus menghitung ulang FFT di setiap time step pada generasi autoregresif
- Merupakan struktur yang memungkinkan generasi efisien dalam anggaran memori tetap
- Wavelet Refinement Module opsional melengkapi detail lokal yang bisa hilang pada pendekatan spectral murni, dengan overhead komputasi yang kecil
Cara menerapkannya ke Transformer yang ada
- SPECTRE dapat langsung menggantikan layer multi-head attention tanpa memerlukan perombakan arsitektur terpisah
- Model pra-pelatihan yang ada dapat di-fine-tune dengan layer SPECTRE
- Parameter yang diperbarui adalah parameter yang baru diperkenalkan
- Parameter tambahan kurang dari 6% dari total bobot
- Berbeda dari pendekatan yang memerlukan optimisasi khusus atau arsitektur nonstandar, struktur Transformer di sekitarnya tetap dipertahankan
Eksperimen berbasis Llama-3.2-1B
- Tiga kernel attention diterapkan pada backbone Llama-3.2-1B yang sama untuk dibandingkan
- standard softmax-dot-product attention(SDPA)
- FlashAttention-2
- SPECTRE mixer
- Lingkungan pengukuran adalah NVIDIA A100-80GB, dan panjang sekuens adalah L ∈ {512, 1k, 4k, 8k, 32k, 128k}
- Metriknya adalah throughput tokens-per-second dan single-batch latency
- Semakin tinggi throughput, semakin baik
- Semakin rendah latency, semakin baik
- SPECTRE menunjukkan waktu eksekusi yang mendekati O(n log n) sambil mempertahankan akurasi backbone
- Hingga 32k token, waktu eksekusinya tetap hampir datar
- Berdasarkan abstrak, pada konteks 128k-token, hingga 7× lebih cepat daripada FlashAttention-2
- Berdasarkan daftar contribution di isi utama, pada 32k token, menunjukkan inferensi hingga 7× lebih cepat daripada FlashAttention-2
Hasil benchmark dan cakupan praktis
- SPECTRE menunjukkan hasil yang setara atau lebih tinggi daripada baseline pada language modeling PG-19 dan klasifikasi ImageNet-1k
- Tetap mempertahankan pencampuran konteks global sambil menghindari biaya kuadratik self-attention pada pemrosesan konteks panjang
- Metode percepatan attention berbasis sparse pattern, kernel approximation, dan struktur low-rank dapat memiliki keterbatasan seperti mengorbankan exactness, memerlukan optimisasi nonstandar, atau tidak mendukung streaming generation
- SPECTRE menggunakan pendekatan domain frekuensi di mana FFT mendiagonalisasi circular convolution dan mengubah global mixing menjadi perkalian element-wise
- Dengan membatasi parameter tambahan di bawah 6%, pendekatan ini menargetkan pemrosesan konteks ratusan ribu token pada commodity GPU tanpa hardware khusus
1 komentar
Komentar Hacker News
Pada dasarnya ini adalah cara yang memanfaatkan teorema konvolusi: konvolusi yang mahal di ruang asal menjadi perkalian sederhana di ruang dual, dan sebaliknya juga berlaku
Jika ada operasi konvolusi pada data, cukup ubah ke domain konjugat lalu ganti menjadi perkalian
Dengan kata lain, kerjakan pada domain yang alami bagi data
https://en.wikipedia.org/wiki/Convolution_theorem
Untuk optimasi, optimalkan tiap tahap, dan lakukan sebanyak mungkin pekerjaan di ruang yang paling efisien
Bukankah itu cerita yang berbeda dari sekadar lebih mudah dihitung?
Selain itu, komputasinya harus memakai bilangan kompleks, dan secara numerik juga kurang stabil. Sepanjang yang saya tahu, FFT tidak menguntungkan untuk konvolusi umum
Untuk self-attention atau penggunaan di makalah ini, n bisa jauh lebih besar. Saya belum membaca makalahnya. Meski begitu, masalah bilangan kompleks tetap ada
Google memperkenalkan ide ini pada 2022 melalui FNet: Mixing Tokens with Fourier Transforms
Setelah itu mereka mengetahui bahwa dalam sebagian besar situasi, performa perkalian matriks TPU lebih cepat daripada FFT
https://arxiv.org/abs/2105.03824
“Secara keseluruhan, pendekatan seperti FNet, Performer, dan sparse transformer menunjukkan bahwa pencampuran token tetap atau aproksimatif dapat mengurangi beban komputasi, tetapi strategi adaptive spectral filtering kami secara unik menggabungkan efisiensi FFT dengan filter spektral yang dapat dipelajari dan bergantung pada input. Ini memberikan kombinasi kuat antara skalabilitas dan adaptivitas yang penting untuk tugas pemodelan sekuens yang kompleks.”
Ada juga bagian perbandingan setelah itu
Tapi, apakah pada DSP ada perangkat keras khusus untuk membantu FFT? Saya benar-benar penasaran. Belum pernah memakainya, tetapi rasanya mungkin membantu
“TPU sangat tidak efisien untuk transformasi Fourier sehingga para peneliti memilih implementasi transformasi Fourier dengan skala kuadratik yang menggunakan matriks DFT yang telah dihitung sebelumnya, alih-alih memakai algoritma FFT, untuk sekuens di bawah 4096.”
“Pada GPU Nvidia Quadro P6000, transformasi Fourier menyumbang hingga 30% dari waktu inferensi dalam arsitektur FNet.”
Perusahaan ini pada 2021 mengklaim bahwa jika Google memakai chip optik mereka pada TPU, waktu inferensi bisa berkurang 40%. Jika FFTNet menangani lebih banyak pekerjaan, mungkin bisa turun lebih jauh lagi
https://scribe.rip/optalysys/attention-fourier-transforms-a-...
Transformasi Fourier diterapkan sepanjang dimensi “token”. Namun pada banyak aplikasi, dimensi ini tidak punya makna. Karena itu transformer menjadi pilihan yang baik untuk menangani data yang invarian terhadap permutasi
Saya ingin melihat eksperimen tambahan yang menggunakan transformasi Fourier pada grup hingga yang kurang dikenal. Ini bersifat invarian terhadap permutasi sambil tetap berbagi banyak sifat dengan transformasi Fourier standar
Saya juga penasaran, jika ini menjadi gelombang besar berikutnya di LLM, seberapa mudah mesin inferensi seperti vLLM atau llama.cpp dapat mengintegrasikannya
https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...
Sepanjang yang saya tahu, llama menerapkan rotasi pada vektor sesuai posisinya dalam input
Matematika ini benar-benar lewat di atas kepala saya, dan saya pun cuma nyaris paham penjelasan di sekitar rumusnya. Bisa tolong ada yang jelaskan dengan bahasa sederhana bagaimana ini setara dengan mekanisme attention?
Apa yang dimaksud dengan frekuensi di sini, dan bagaimana relasi posisi antar token dikodekan?
Dalam analisis sinyal atau gambar, ini yang paling intuitif: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
Ruang frekuensi pada dasarnya adalah ruang “kompleks” yang direpresentasikan dengan bilangan kompleks. Frekuensi punya keunggulan karena melihat masalah secara global
Mekanisme ini tidak setara dengan mekanisme attention, dan jelas ada trade-off. Namun, ada kemungkinan ia menangkap cukup banyak relasi penting yang biasanya ditangkap attention
Untuk modReLU, saya belum punya intuisi yang bagus saat ini, tetapi tampaknya penting karena ia memodifikasi frekuensi sambil tetap mempertahankan invers transformasi Fourier
“Frekuensi” di sini kemungkinan besar cukup abstrak. FFT juga sering dipakai dengan cara yang tidak punya interpretasi frekuensi yang jelas. Sering kali dipakai karena sifat matematisnya yang praktis, seperti teorema konvolusi
Kalau ini benar-benar bekerja dengan baik, itu cukup mengejutkan dan sangat elegan
Artinya setiap vektor keluaran bergantung pada vektor masukan terkait yang telah ditransformasikan oleh suatu fungsi dari semua vektor masukan lainnya
https://medium.com/optalysys/attention-fourier-transforms-a-...
Secara konseptual, bisa dilihat bagaimana ini mirip dengan konvolusi yang agak disederhanakan: https://openreview.net/pdf?id=8l5GjEqGiRG
Konvolusi sering digunakan ketika Anda ingin mempertimbangkan keadaan global dengan suatu cara
Untuk memasukkan causal masking ke dalam kerangka ini, sepertinya perlu melakukan n FFT yang berbeda, dan juga tidak ada penyebutan tentang embedding posisi
Jadi implementasi self-attention pembandingnya tampaknya non-kausal dan NoPE, dan kalau begitu ini mungkin contoh baseline yang sengaja dibuat lemah, jadi tidak terlalu mengesankan
Kalau hasilnya benar-benar mendekati state-of-the-art, rasanya penulis pasti akan menyebutkannya
Ini tampaknya referensi terkait: https://arxiv.org/abs/2111.13587
Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, Bryan Catanzaro
Saya penasaran apakah ada intuisi mengapa melihat ini dalam domain frekuensi membantu
Saya paham komponen DC, tetapi saya tidak berharap data input cukup periodik sehingga frekuensi-frekuensi lain punya makna
Tampaknya tidak menyebut penelitian terdahulu Hyena Operator, yang sudah menunjukkan pencampuran konteks penuh O(n log n) beberapa tahun lalu
https://arxiv.org/abs/2302.10866
https://arxiv.org/abs/2111.00396
Notasi Big-O memberi sedikit gambaran, tetapi seperti kebanyakan hal yang berkaitan dengan ilmu komputer atau teknik elektro, ini juga terasa lewat di atas kepala saya.
Dari sudut pandang seseorang yang benar-benar lemah dalam matematika, saya iri pada orang-orang yang bisa memahami hal seperti ini, atau setidaknya mempelajarinya hingga bisa meraih gelar teknik dan lisensi.
Yang saya tahu tentang FFT cuma sebatas bahwa ia mengubah sinyal, digunakan untuk beberapa jenis pemrosesan sinyal, dan dulu saya pernah dengar bahwa ini merupakan inti dari deteksi ledakan nuklir.
Ide dasarnya seperti ini: hampir semua sinyal yang berguna dapat dinyatakan sebagai penjumlahan gelombang sinus dengan frekuensi dan fase yang berbeda-beda. Misalnya sinyal listrik atau gelombang suara adalah sinyal satu dimensi dengan sumbu x berupa waktu. Bentuknya bisa tampak seperti garis berliku-liku yang rumit dan sulit ditangani.
Dengan transformasi Fourier, Anda bisa memisahkan frekuensi-frekuensi individual dari sinyal berbasis waktu. Lalu Anda bisa mengubah frekuensi tertentu sesuai keinginan. Misalnya jika sinyal memiliki banyak noise acak yang tajam, itu akan muncul sebagai frekuensi tinggi. Untuk membersihkannya, lakukan transformasi Fourier, buang data pada frekuensi di atas ambang tertentu, lalu terapkan invers transformasi Fourier pada data yang tersisa untuk kembali ke versi sinyal asli yang lebih halus. Ini disebut filter lolos-rendah, dan hampir mirip dengan mengambil rata-rata bergerak dari sinyal asli.
Bagian yang menarik adalah bahwa hal ini bisa diperluas secara cukup intuitif ke dimensi yang lebih tinggi. Sinyal dua dimensi dengan sumbu x dan y sama-sama ruang adalah gambar. Kompresi JPEG didasarkan pada konsep ini. Untuk menyimpan gambar dalam ukuran lebih kecil, sinyal frekuensi tinggi dihapus, dengan konsekuensi hilangnya detail halus atau, jika terlalu banyak dibuang, muncul artefak berbentuk cincin. Jika ditambah dimensi ketiga berupa waktu, itu menjadi video, dan masih bisa terus diperluas.
Semua ini enak dipahami secara visual, jadi Anda bisa mendapatkan intuisi yang baik tanpa harus benar-benar mendalami semua matematikanya. Halaman yang bagus dengan banyak visualisasi dan contoh interaktif: https://www.jezzamon.com/fourier/index.html
Video 3Blue1Brown juga menjelaskannya dengan baik: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
Transformasi Fourier, dengan FFT sebagai versi diskretnya, menguraikan sinyal domain waktu 1 dimensi itu menjadi komponen magnitudo dan fase terhadap frekuensi.
Frekuensi pada dasarnya adalah tinggi nada. Gelombang sinus murni atau nada murni mirip dengan suara yang dulu terdengar saat siaran TV berakhir larut malam; dalam kasus ini, sebagian besar nilainya 0 dan muncul satu “lonjakan” pada posisi frekuensi nada tersebut. Semakin besar amplitudo sinyal, semakin besar pula lonjakannya. Jika tinggi nada, yaitu frekuensi, naik atau turun, posisi lonjakan ini bergerak sepanjang sumbu horizontal.
Fase pada dasarnya adalah offset waktu dari sinyal. Nada yang tertunda dengan cara apa pun akan muncul sebagai fase yang berbeda. Namun ini bukan pengukuran absolut, melainkan relatif. Karena satuannya radian, yaitu sudut, setelah satu putaran penuh lingkaran ia akan “reset”, jadi kita tidak bisa tahu apakah sinyal tertunda 1 detik atau 2 detik.
Jadi dari satu sinyal, yaitu amplitudo terhadap waktu, kita sebenarnya mendapatkan dua jenis informasi: magnitudo dan fase terhadap frekuensi.
Jika Anda memahami bilangan imajiner atau variabel kompleks, dua sinyal ini sebenarnya hanyalah magnitudo dan argumen dari keluaran FFT yang merupakan fungsi kompleks.
Di era telemetri, rasanya seperti peluang besar yang terlewat jika FFT tidak diterapkan pada telemetri cloud untuk menemukan anomali periodik dan sistem kuasi-stabil sebelum insiden terjadi, bukan sesudahnya.
Sayangnya, ini masih berada di level yang bisa saya sadari keberadaannya, tetapi belum pada level keterampilan untuk mengimplementasikannya, dan jadwal saya juga sudah penuh.
“SLA paling sering dilanggar 23~25 menit setelah deployment layanan. Hmm, kenapa ya… oh tidak.”
Terlepas dari bercandanya, area yang benar-benar bisa menghasilkan uang di sini adalah memprediksi siklus trafik untuk menaikkan dan menurunkan instance server demi menghemat biaya.
Kalau dikerjakan sebagai proyek sampingan pribadi, perusahaan pasti tidak akan pernah menyetujuinya, tetapi kalau dikemas sebagai produk siap pakai, ini justru jenis pekerjaan yang akan langsung mereka beli.