- Rangkaian algoritme kuantisasi yang secara mendasar menyelesaikan masalah overhead memori pada vektor berdimensi tinggi, dan dapat diterapkan baik untuk kompresi cache key-value LLM maupun pencarian vektor
- Arsitektur kompresi dua tahap: data terlebih dahulu dikompresi dengan kualitas tinggi menggunakan PolarQuant, lalu galat sisa dihilangkan hanya dengan 1 bit melalui algoritme QJL
- Dapat menguantisasi cache key-value hingga 3 bit tanpa pelatihan atau fine-tuning serta tanpa kehilangan akurasi model, sambil mencapai peningkatan kinerja hingga 8x pada GPU H100
- Dalam pencarian vektor, juga mencatat rasio recall optimal tanpa codebook besar atau tuning per-dataset, melampaui metode state-of-the-art yang ada
- Kontribusi algoritmis yang fundamental dengan efisiensi yang dapat dibuktikan dan mendekati batas bawah teoretis, sehingga diharapkan berperan penting untuk model seperti Gemini dan infrastruktur pencarian semantik skala besar
Latar belakang vektor dan kuantisasi
- Vektor adalah cara mendasar model AI memahami dan memproses informasi, dan vektor berdimensi tinggi merepresentasikan informasi kompleks seperti fitur gambar, makna kata, dan atribut dataset
- Vektor berdimensi tinggi mengonsumsi memori sangat besar, sehingga menimbulkan bottleneck pada cache key-value (lembar referensi digital berkecepatan tinggi yang menyimpan informasi yang sering digunakan dengan label sederhana agar bisa segera diambil kembali)
- Kuantisasi vektor adalah teknik kompresi data klasik untuk mengecilkan ukuran vektor berdimensi tinggi, yang membantu meningkatkan kecepatan pencarian vektor dan mengatasi bottleneck cache key-value
- Kuantisasi vektor tradisional memiliki overhead memori internal karena harus menghitung dan menyimpan konstanta kuantisasi dengan presisi penuh untuk setiap blok data kecil, menambah biaya 1–2 bit per angka dan sebagian meniadakan tujuan kuantisasi
Cara kerja TurboQuant
- TurboQuant adalah metode kompresi yang mencapai pengurangan ukuran model tinggi tanpa kehilangan akurasi, serta mendukung baik kompresi cache key-value maupun pencarian vektor
- Terdiri dari dua tahap inti:
Tahap 1: kompresi berkualitas tinggi (metode PolarQuant)
- Vektor data diputar secara acak untuk menyederhanakan struktur geometris data, lalu quantizer standar berkualitas tinggi diterapkan secara terpisah pada tiap bagian vektor
- Tahap ini menggunakan sebagian besar bit untuk menangkap konsep utama dan intensitas dari vektor asli
Tahap 2: menghilangkan galat tersembunyi
- Pada galat halus yang tersisa dari tahap 1, algoritme QJL diterapkan hanya dengan daya kompresi residual 1 bit
- QJL berperan sebagai pemeriksa galat matematis yang menghilangkan bias sehingga menghasilkan skor attention yang lebih akurat
QJL: teknik 1 bit tanpa overhead
- Memanfaatkan transformasi Johnson-Lindenstrauss untuk mereduksi data berdimensi tinggi sambil mempertahankan jarak dan hubungan penting antartitik data
- Setiap angka dalam vektor hasil direduksi menjadi satu bit tanda (+1 atau -1), sehingga overhead memori menjadi nol
- Untuk menjaga akurasi, digunakan estimator khusus yang secara strategis menyeimbangkan query presisi tinggi dengan data tersederhanakan presisi rendah
- Dengan ini, model dapat menghitung skor attention secara akurat untuk menentukan bagian input mana yang penting dan mana yang bisa diabaikan
PolarQuant: "sudut" baru terhadap kompresi
- Pendekatan yang menyelesaikan masalah overhead memori dengan cara yang sepenuhnya berbeda
- Alih-alih koordinat standar (X, Y, Z), vektor diubah ke koordinat polar — mirip mengganti "3 blok ke timur, 4 blok ke utara" menjadi "5 blok ke arah 37 derajat"
- Hasil transformasi terdiri dari dua informasi: radius yang menunjukkan intensitas data inti, dan sudut yang menunjukkan arah serta makna data
- Karena pola sudut sudah diketahui dan sangat terkonsentrasi, data dapat dipetakan ke grid melingkar tetap dengan batas yang sudah diketahui, alih-alih grid "persegi" dengan batas yang terus berubah, sehingga langkah normalisasi data yang mahal dapat dihilangkan
- Pada vektor berdimensi d, pasangan koordinat dikelompokkan lalu dipetakan ke sistem koordinat polar, kemudian radius dikumpulkan berpasangan dan transformasi polar rekursif diulangi hingga akhirnya disuling menjadi satu radius dan sekumpulan sudut deskriptif
Eksperimen dan hasil
Kinerja benchmark konteks panjang
- Dievaluasi dengan LLM open-source (Gemma, Mistral) pada benchmark konteks panjang standar seperti LongBench, Needle In A Haystack, ZeroSCROLLS, RULER, dan L-Eval
- TurboQuant mencapai skor optimal pada distorsi inner product (dot product distortion) dan recall sekaligus meminimalkan footprint memori key-value
- Pada model Llama-3.1-8B-Instruct, menunjukkan kinerja yang tangguh dibanding baseline KIVI di berbagai tugas seperti tanya jawab, pembuatan kode, dan ringkasan
Tugas Needle-in-Haystack
- Dalam pengujian mencari informasi spesifik di antara teks dalam jumlah besar, TurboQuant mencapai hasil downstream sempurna di seluruh benchmark
- Ukuran memori key-value diperkecil setidaknya lebih dari 6x
- PolarQuant juga hampir lossless pada tugas ini
Kinerja runtime
- Dapat menguantisasi cache key-value ke 3 bit tanpa pelatihan atau fine-tuning, tanpa kompromi terhadap akurasi model
- Mencapai runtime yang lebih cepat daripada LLM asli, dengan implementasi yang sangat efisien dan overhead runtime yang nyaris dapat diabaikan
- TurboQuant 4 bit mencatat peningkatan kinerja hingga 8x dalam perhitungan attention logit dibanding key tidak terkuantisasi 32 bit pada GPU H100, diukur terhadap baseline yang dioptimalkan dengan JAX
Kinerja pencarian vektor
- Dievaluasi pada pencarian vektor berdimensi tinggi dibanding metode mutakhir seperti PQ dan RabbiQ
- Menggunakan rasio recall 1@k yang mengukur seberapa sering algoritme menangkap hasil inner product terbaik sebenarnya di antara perkiraan top-k
- Dibanding baseline yang memakai codebook besar yang tidak efisien dan tuning per-dataset, TurboQuant mencatat rasio recall yang konsisten lebih unggul
- Pada dataset GloVe (d=200), mencapai rasio recall 1@k terbaik dibanding berbagai baseline kuantisasi mutakhir
- Dengan pendekatan data-oblivious, memberikan tingkat distorsi yang nyaris optimal, sehingga menjaga presisi model yang jauh lebih berat dengan efisiensi sistem 3 bit
Prospek ke depan
- TurboQuant, QJL, dan PolarQuant bukan sekadar solusi rekayasa praktis, tetapi juga kontribusi algoritmis fundamental yang didukung bukti teoretis yang kuat
- Memiliki efisiensi yang dapat dibuktikan dan bekerja mendekati batas bawah teoretis, sehingga kokoh dan dapat diandalkan untuk sistem inti berskala besar
- Selain mengatasi bottleneck cache key-value pada model utama seperti Gemini, dampak kuantisasi vektor online yang efisien dapat meluas ke area yang lebih luas
- Seiring pencarian modern berevolusi dari berbasis kata kunci menjadi pemahaman niat dan makna, pencarian vektor menjadi esensial untuk menemukan item yang paling mirip secara semantik dalam database berisi miliaran vektor
- TurboQuant memungkinkan pembangunan dan kueri indeks vektor skala besar dengan memori minimum, waktu prapemrosesan nyaris nol, dan akurasi mutakhir, sehingga mewujudkan pencarian semantik berskala Google yang lebih cepat dan efisien
4 komentar
"Rotasi adalah kekuatan tanpa batas. Percayalah pada itu."
Hormat saya.
Saya sampai login gara-gara komentar ini.
Komentar Hacker News
Riset kompresi cache KV benar-benar perkembangan yang menarik
Namun cukup disayangkan karena tidak ada sitasi terhadap mekanisme matematis inti dalam riset terkait
Teknik yang menerapkan rotasi geometris untuk menangani geometri berdimensi tinggi lalu melakukan kuantisasi ekstrem pertama kali diusulkan dalam makalah tim kami di NeurIPS 2021, “DRIVE”
Melalui pendekatan berbasis rotasi ini dan mekanisme koreksi bias, kami mencapai estimasi rata-rata varians yang optimal
Setelah itu, isi ini juga dipresentasikan dalam seminar undangan Google, dan mengingat kemiripan teoretis antara TurboQuant dan PolarQuant, kami berharap versi berikutnya akan mencantumkan sitasi terhadap riset terdahulu
Maksud saya, apakah caranya dengan menyimpan matriks diagonal dan basis baru agar bisa dikompresi lebih jauh?
Tolong jelaskan apa hubungan riset ini dengan MHLA
Ide seperti ini memang sering ditemukan ulang tiap beberapa tahun; misalnya, ada pendekatan serupa dalam makalah 2017
Tetapi ada juga kemungkinan penelitinya secara independen memikirkan ide serupa ketika risetnya sudah cukup jauh berjalan
Ide bagus memang sering menjadi sesuatu yang secara alami dicapai oleh orang yang memahami masalahnya secara mendalam
Saya tidak paham penjelasan “TurboQuant memutar data secara acak untuk menyederhanakan geometri”
Tidak ada jaminan bahwa rotasi selalu menghasilkan bentuk yang lebih sederhana, kan?
Dan bagian “mengurangi data berdimensi tinggi dengan transformasi Johnson–Lindenstrauss lalu merepresentasikan tiap vektor dengan bit tanda” juga sulit diterima; bagaimana mungkin satu nilai boolean dapat mempertahankan informasi relasional?
Muncul aktivasi outlier pada beberapa dimensi, dan karakteristik optimizer Adam memperkuat fenomena ini
Untuk bacaan terkait, lihat SmoothQuant dan Privileged Basis
Dengan begitu, pembelajaran pola yang tidak perlu bisa dikurangi dan optimisasi menjadi lebih stabil
Artinya, model tidak belajar aturan sepele seperti “kalau digit tertentu pada dimensi tertentu bernilai 5 maka itu kucing”
Dengan mengalikan matriks rotasi, data menjadi lebih merata distribusinya sehingga kuantisasi bisa dilakukan lebih efisien
Setelah itu, algoritma Lloyd–Max mengoptimalkan batas dan nilai rekonstruksi, lalu bias yang tersisa dikoreksi dengan 1 bit
Dengan cara ini, presisi tinggi tetap bisa dipertahankan meski memakai sedikit bit
Misalnya, jika nilai floating-point diubah ke satuan lain (bel → desibel), nilainya dapat dinyatakan dengan lebih seragam sehingga lebih mudah dikompresi
Dengan kata lain, data yang jauh dipindahkan kembali mendekati pusat
Selain itu, tiap dimensi dikodekan secara terpisah, jadi seluruh vektor tidak direduksi menjadi satu boolean tunggal
Tulisan blog ini berkualitas rendah
Grafiknya memiliki sumbu yang salah label, dan visualisasi videonya juga sama sekali tidak menyampaikan konsep Polar Quantization
Grafik yang lain bahkan memulai sumbu dari 48 sehingga melebih-lebihkan perbedaan sebenarnya
Secara keseluruhan, keandalan materi visual dan kualitas komunikasinya rendah
Seseorang sudah mulai mengimplementasikannya di llama.cpp
Lihat commit terkait
Teorema Johnson–Lindenstrauss diharapkan tetap berlaku sehingga kuantisasi independen tiap koordinat tetap sah secara teoretis
Pengetahuan domain saya kurang, tetapi strukturnya tampak jelas
Kemungkinan besar akan digabung ke branch utama dalam 4~6 minggu
Ada animasi yang menjelaskan TurboQuant secara intuitif
Ini ringkasan yang saya susun di tingkat sarjana
Intinya adalah mengkuantisasi cache KV sambil meminimalkan kehilangan informasi
Karena sebagian besar vektor berkumpul di sekitar ekuator bola berdimensi tinggi, distribusinya dibuat lebih merata lewat rotasi untuk meningkatkan pelestarian entropi
PolarQuant mencoba ini lewat transformasi koordinat polar, tetapi TurboQuant menyederhanakannya dan menambahkan koreksi bias QJL
Pada akhirnya, kompresi efisiensi tinggi dicapai lewat gabungan PolarQuant + QJL + koreksi praktis
Tulisan blognya penuh kesalahan dan membingungkan
Codebook koordinat hyperpolar dari PolarQuant juga masih tersisa sebagian di TurboQuant
Tulisan ini termasuk salah satu yang terburuk dalam menjelaskan komponen AI
Hampir tidak ada konteks teknis
Teorema Johnson–Lindenstrauss disebut, tetapi koneksi konkretnya tidak dijelaskan
Misalnya, menjelaskan “3 blok ke timur, 4 blok ke utara” sebagai “bergerak 5 blok pada sudut 37 derajat”, sehingga terasa seperti analogi tingkat SMP
Sebuah implementasi PyTorch independen sudah dirilis
turboquant-pytorch
Blognya memang baru dipublikasikan belakangan ini, tetapi makalahnya sudah diajukan ke arXiv hampir setahun lalu
Saya penasaran apakah ini sudah diterapkan pada model seperti Gemini, dan kalau ya, semoga biaya RAM untuk penggunaan pribadi juga bisa turun
Saya terkesan dengan cepatnya riset kompresi berujung pada aplikasi nyata
Seperti format gambar AVIF dan JPEG XL yang berkembang dari riset codec video, teknik kuantisasi AI juga tampaknya akan segera diterapkan di lingkungan inferensi nyata
Beberapa konsep seperti ruang warna XYB memang sama, dan saya menduga LLM juga akan memerlukan rekayasa khusus serupa