Mencari jutaan halaman Wikipedia secara ‘vibe’ dalam mode offline

• Mewujudkan pencarian embedding real-time offline di dalam browser tanpa server, sehingga 6 juta dokumen English Wikipedia dapat dijelajahi secara interaktif secara lokal
• Embedding asli 384-dimensi float32 berukuran sekitar 9GB sehingga tidak cocok untuk aplikasi browser, jadi ukurannya diperkecil berdasarkan all-minilm-l6-v2 dan embedding rata-rata potongan halaman
• Dengan menerapkan Product Quantization pada subruang 8 dimensi, ukuran dataset diperkecil menjadi sekitar 288MB, dan sekitar 2 juta embedding dapat dimuat dalam 96MB
• Pencarian melakukan perhitungan jarak di domain terkompresi tanpa dekompresi, dan dengan memperbaiki hasil konversi melalui opcode GatherElements di ONNX, perhitungan menjadi sekitar 4 kali lebih cepat
• Pada perangkat modern, inferensi MiniLM dan perhitungan jarak untuk 100k embedding selesai dalam waktu singkat, sehingga UI React dapat memperbarui hasil setiap 100–300ms

---

Pencarian vektor offline yang berjalan di dalam browser

• Tujuannya adalah menunjukkan bahwa jutaan halaman Wikipedia dapat dicari secara real-time di browser tanpa infrastruktur pencarian server yang rumit
• Desain intinya diringkas menjadi tiga hal
  • Pencarian vektor bisa cukup cepat hanya dengan Product Quantization dan pemindaian linear
  • Menggunakan ONNX Runtime, tetapi inefisiensi yang muncul dari konversi PyTorch dapat diperbaiki di tingkat opcode
  • Browser cukup cepat untuk menjalankan inferensi real-time dengan WASM, dan WebGPU juga tetap menjadi kemungkinan ke depan
• Kondisi pencarian menggunakan kemiripan vektor dari embedding isi sekaligus kondisi kesetaraan pada huruf pertama judul
  • Ini lebih dekat dengan kasus kueri basis data yang mencari sebagian kolom dengan kemiripan vektor dan kolom lain dengan kondisi kesetaraan
• Karena dibatasi sebagai aplikasi browser offline, embedding harus kecil, model embedding harus open source, dan ukuran model serta beban komputasinya juga harus ringan
  • Pada 2023, model ringan umumnya berarti di bawah 100MB

Data English Wikipedia dan ukuran embedding

• Dataset yang digunakan adalah English Wikipedia, dan embedding dibuat dengan model all-minilm-l6-v2
• Dokumennya berjumlah sekitar 6 juta, dan embedding halaman dibuat dengan membagi halaman menjadi beberapa potongan lalu merata-ratakan embedding tiap potongan
• Halaman diurutkan mulai dari yang paling panjang
  • Saat basis data dimuat secara bertahap, ini dimaksudkan agar halaman panjang yang kemungkinan mendapat lebih banyak usaha dari manusia ditampilkan lebih dulu
• Dimensi embedding adalah 384 dimensi
  • Jika disimpan sebagai float32, ukurannya menjadi 6M * 384 * 4 = 9GB
  • Dalam 96MB hanya dapat disimpan sekitar 64k embedding
• Encoding float32 asli terlalu besar untuk pencarian offline berbasis browser

Kompresi embedding dengan Product Quantization

• Product Quantization adalah metode yang tidak menyimpan nilai floating-point secara langsung, melainkan membuat beberapa palet lalu mengganti nilai input dengan indeks palet
• Karena palet biasanya memiliki maksimal 256 nilai, tiap indeks dapat berukuran paling besar 1 byte
  • Palet implisit digunakan dengan menggeser dan menskalakan garis bilangan seperti -127~127 atau 0~255
  • Palet eksplisit menyimpan 256 angka secara berurutan
  • Product Quantization menggunakan palet eksplisit
• Dengan konfigurasi minimum, jika masing-masing dari 384 dimensi diubah menjadi indeks 1 byte, dataset menjadi 6M * 384 = 2.25GB
  • Dalam 96MB dapat disimpan sekitar 256k embedding
  • Metode ini pun masih tidak efisien untuk target yang diinginkan
• Jika dikuantisasi dalam satuan titik 2 dimensi, embedding 384 dimensi dapat direpresentasikan sebagai 192 indeks sehingga menghemat ruang 2 kali
• Konfigurasi yang dipakai sebenarnya menggunakan satuan titik 8 dimensi
  • 384 dimensi direpresentasikan menjadi 48 indeks
  • Ukuran palet tetap di sekitar 384KB
  • Ukuran dataset menjadi 6M * 48 = 288M
  • Dalam 96MB dapat disimpan sekitar 2 juta embedding
• Precision dan recall dapat dievaluasi pada tingkat kuantisasi apa pun

Mencari langsung tanpa dekompresi

• Keunggulan Product Quantization adalah pencarian dapat dilakukan dalam keadaan terkompresi tanpa dekompresi
• Jika n dimensi dikelompokkan menjadi n/2 titik 2 dimensi, jarak antara tiap titik palet dan titik 2 dimensi yang sesuai dari kueri dapat dihitung sebelumnya
• Setelah itu, tiap embedding menghitung jarak total dengan mengambil nilai jarak melalui indeks palet lalu menjumlahkannya
  • Ini membutuhkan kerja lebih sedikit dibanding memulihkan seluruh titik n dimensi terlebih dahulu lalu menghitung jarak tiap dimensi
• Pada konfigurasi titik 8 dimensi yang sebenarnya, perhitungan jarak dapat dilakukan dengan beban kerja sekitar 1/8 dari embedding yang tidak dikompresi

Menggunakan Arrow sebagai format pertukaran data

• Karena biaya pemindahan dan transformasi data besar, lebih menguntungkan jika embedding terkompresi diserialisasikan dalam format yang siap dipakai
• Arrow adalah format berorientasi kolom yang cocok untuk tujuan ini
  • Embedding dan judul halaman disimpan sebagai tabel Arrow
  • Indeks palet diperlakukan seperti array 2 dimensi, sedangkan judul seperti array string 1 dimensi
  • Fokusnya adalah menyalin bit ke posisi yang tepat, bukan parsing atau loading yang berat
• Format array Arrow hanya menyimpan data 1 dimensi, jadi dua skema digunakan untuk menangani 48 dimensi embedding
  • Skema metadata menggunakan unit 100 ribu baris
  • Skema embedding menggunakan unit 100 ribu * 48 baris
  • Saat dimuat, embedding dibentuk ulang kembali
• safetensors juga mengikuti prinsip desain yang sama
• JSON menserialisasikan array 48 elemen sebagai karakter ASCII panjang variabel sehingga tahap loading menjadi lebih rumit
• Protocol Buffers menggunakan integer lebar variabel base 128 untuk integer di bawah 32 bit, dan format integer ini saat ini belum didukung baik oleh compute kernel

Parsing Wikipedia dan pembuatan embedding

• Untuk parsing markup Wikipedia digunakan mediawiki parser from hell, yaitu mwparserfromhell
• Wikipedia dataset dari OLM mengambil dump data terbaru Wikipedia untuk bahasa tertentu lalu mem-parsingnya menjadi baris seperti judul dan isi
  • Dataset ini lebih mirip kode yang perlu dijalankan daripada data serialisasi yang aman dan tidak berbahaya, sehingga memerlukan kepercayaan saat eksekusi
• Parsing dijalankan di semua core pada satu mesin
  • Mesin modern memiliki puluhan core, sehingga cocok untuk skala di bawah 100 juta dokumen seperti English Wikipedia yang saat ini berukuran 6 juta halaman
• Model embedding yang digunakan adalah all-minilm-l6-v2
  • Ini adalah sentence transformer ringan dengan performa baik untuk bahasa Inggris
  • Kueri dan dokumen di-embedding ke ruang yang sama
  • Dengan 22 juta parameter, model ini sangat ringan
• Untuk eksekusi JavaScript di browser, versi kuantisasi 8-bit melalui ONNX dan transformers.js juga digunakan
• Model dilatih dengan sekuens 128 token, sehingga jendela konteksnya jauh lebih pendek daripada rata-rata panjang halaman
  • Halaman dibagi menjadi beberapa potongan, lalu embedding tiap potongan dirata-ratakan untuk membuat embedding rata-rata halaman

Pencarian facet berbasis pq.js dan pemindaian linear

• Saat mencari jutaan dokumen secara lokal, sistem pengindeksan yang rumit tidak selalu diperlukan
• Tujuannya adalah mendapatkan beberapa hasil teratas yang paling dekat dengan titik tertentu, misalnya 12 jarak teratas
• Jika ada 10 juta array jarak, 10 juta kolom facet, dan satu nilai facet, pemfilteran dapat dilakukan dengan menambahkan 0 jika cocok dan Infinity jika tidak, lalu mencari top-k
  • Di ponsel modern, 100 hasil teratas dapat ditemukan dalam kurang dari 10ms
  • Implementasinya ada di filtered-topk dan pq.js
• Perhitungan jarak untuk embedding terkompresi Product Quantization dapat ditulis dengan PyTorch
  • Ada palet sebanyak subspaceCount, dan tiap palet memiliki codewordCount titik berdimensi subspaceDim
• Pengindeksan pada model ONNX yang diekspor dari PyTorch menjadi agak canggung
  • Opcode GatherElements di ONNX melakukan langsung pekerjaan yang dibutuhkan
  • Dengan alat seperti ONNX-modifier, node pada graf aliran data model ONNX hasil ekspor dapat ditambah atau dihapus
• Jika beberapa tahap pengindeksan diganti menjadi satu opcode yang tepat, perhitungan jarak menjadi sekitar 4 kali lebih cepat

Komputasi streaming dan UI interaktif

• Jumlah embedding yang menjadi target perhitungan jarak tidak tetap
  • Jarak antara kueri dan sebagian embedding dapat dihitung secara streaming
  • Setelah cukup waktu berlalu, top-k dijalankan berdasarkan jarak yang telah dihitung sejauh itu untuk memperbarui hasil pencarian
• Karena semua embedding berada secara lokal, latensi menuju infrastruktur pencarian pada dasarnya 0ms
• Target respons UI adalah hasil terlihat dalam 100–300ms setelah interaksi
  • MiniLM dapat dijalankan dalam kurang dari 100ms
  • Pada perangkat edge tertentu bahkan bisa kurang dari 15ms
  • Perhitungan jarak untuk 100k embedding dapat dijalankan dalam sekitar 10ms
• Jika dataset diurutkan dari artikel panjang ke pendek, sebagian besar hasil pencarian teratas pada akhirnya akan muncul lebih cepat di hasil streaming awal
  • Ini karena artikel panjang sering kali melibatkan perhatian dan usaha penulisan yang lebih besar, dan lebih cocok dengan kueri pencarian dibanding banyak artikel stub
• Karena jarak dihitung secara global lalu facet filter dan top-k diterapkan, saat nilai facet atau jumlah hasil pencarian diubah untuk kueri yang sama, hanya pemfilterannya yang perlu dijalankan ulang
  • Pemfilteran ini kurang dari 10ms sehingga terasa seketika

Komponen pq.js yang dapat digunakan kembali

• Banyak fungsi pustaka dari seluruh Wikipedia search app dapat dipindahkan menjadi komponen pq.js yang dapat digunakan kembali
• Saat ini banyak shape ONNX yang sudah dipatok sebelumnya
• Dukungan untuk berbagai tingkat kuantisasi dan berbagai dimensi embedding akan memungkinkan penggunaan ulang yang lebih luas

[GN⁺]

Komentar Hacker News

• Jelas menarik, tetapi ketika saya mencoba menjelaskan beberapa istilah filsafat dan psikologi, semua entri yang saya cari hanya muncul di sekitar peringkat 20
  Entri yang lebih terkenal tetapi kurang akurat berada di atas; misalnya, apa pun yang saya ketik untuk mendefinisikan suatu modalitas psikoterapi tertentu, “psychotherapy” selalu menjadi peringkat 1
  Sebaliknya, saya pernah memakai ChatGPT untuk mencari subbidang yang sempit yang namanya tidak saya ingat, dan setiap kali jawabannya tepat
  Ide layanan AI yang mencarikan nama benda berdasarkan deskripsi itu bagus, tetapi saya tidak yakin apakah membatasinya ke Wikipedia atau judul artikel Wikipedia adalah pendekatan yang tepat, dan model bahasa besar serbaguna tampaknya sudah cukup baik dalam hal ini
  Meski begitu, sebagai bukti konsep, dan fakta bahwa ini bisa berjalan lokal di browser, benar-benar keren

  • Tujuannya adalah menampilkan mesin database dan mendemokan bahwa setelah browser mengunduh semuanya, ia bisa berjalan bahkan di lingkungan yang sepenuhnya terisolasi
    Sepertinya ada banyak parameter yang bisa disetel. Misalnya apakah hanya memakai paragraf pertama artikel atau keseluruhan artikel, apakah mencari dalam rentang yang dekat dengan artikel tertentu, dan hal-hal semacam itu, tetapi belum saya utak-atik
    Wikipedia adalah dataset demo yang sangat bagus, dan saya ingin mencoba menambahkan dataset lain. Misalnya seperti saat mencari “mountain” di iPhoto lalu muncul foto yang berisi gunung, akan menarik jika bisa mencari di berbagai dataset dengan model multimodal seperti CLIP
  • Saya pernah memakainya dengan cara menjelaskan ide dan tujuan, lalu mendapatkan kembali nama bidang atau kata kunci yang layak dicari
    Model bahasa besar terlihat seperti mesin pencari fuzzy terbaik, dan bekerja dengan cara yang cukup unik namun saling melengkapi dibanding mesin pencari tradisional

• Saya suka konsepnya, tetapi hasilnya kurang bagus
  Saya mengetik “weird looking monkey” dan berharap mendapat hasil seperti bekantan atau monyet hidung pesek emas, tetapi yang muncul hanya artikel seperti “Pet monkey”, “List of individual monkeys”, “Ethnoprimatology”, “Monkey”
  Ketika kueri yang sama dimasukkan ke Google, hasilnya persis seperti yang saya harapkan, jadi ini mengecewakan; saya ingin menemukan monyet-monyet berpenampilan aneh yang belum saya ketahui

  • Ini memakai begitu saja model sentence-transformer siap pakai yang sudah berusia lebih dari setahun
    Fokus demo ini adalah menunjukkan database embedding, tetapi embedding-nya sendiri juga masih sedikit berguna
    Saya sama sekali tidak menyimpan data analitik tentang apa yang ditemukan dan tidak ditemukan orang di halaman itu, jadi belum siap untuk memperbaiki hasil pencariannya
  • Editor dan panduan Wikipedia umumnya tidak menyukai kata sifat subjektif, dan “weird looking” dalam kueri terdengar seperti ungkapan yang akan dihindari dalam artikel Wikipedia
    Karena itu, menjadi sulit mendapatkan hasil yang bagus dari korpus pengetahuan ini

• Implementasinya sangat bagus, dan keren bahwa ini bisa dilakukan secara offline. Namun kualitas embedding-nya tampaknya masih kurang
  Salah satu kiat yang mungkin membantu adalah membuat embedding bukan dari keseluruhan artikel Wikipedia, melainkan dari kalimat yang mendekati definisi, atau biasanya kalimat pertama/paragraf pertama saja. Saya tidak yakin bagian mana yang dipakai sekarang
  Situs saya, OneLook, juga sejak 2003 telah menyediakan fitur serupa untuk mencari kata dan konsep lewat deskripsi di https://onelook.com/thesaurus/
  Awalnya itu murni pencarian kamus terbalik, tetapi selama 20 tahun terakhir kami telah mencoba embedding kata, embedding kalimat, dan belakangan model bahasa besar; sekarang GPT menghasilkan kandidat untuk input yang tidak bisa kami jawab sendiri
  Dalam tugas ini, model bahasa besar jauh lebih unggul daripada pendekatan lama, sehingga motivasi saya untuk memperbaiki bagian OneLook ini agak berkurang. Saya sering melihat orang mengatakan bahwa pencarian definisi terbalik adalah alasan utama mereka memakai ChatGPT

• Saya agak terlambat melihat ini, tetapi embedding teks, setidaknya untuk yang digunakan dalam tulisan ini, biasanya tidak terlalu bagus untuk mencari berdasarkan nuansa
  Pada umumnya lebih mirip membandingkan kata yang tumpang tindih atau mencari konten yang mirip dengan kueri
  Namun ada makalah terbaru yang benar-benar mencoba masalah ini: “Retrieving Texts based on Abstract Descriptions” (Ravfogel et al., 2023) https://arxiv.org/abs/2305.12517
  Makalah itu memiliki banyak contoh pencarian dengan deskripsi abstrak seperti “arsitek yang merancang bangunan”, “perusahaan yang merupakan bagian dari perusahaan lain”, “buku yang memengaruhi perkembangan genre”
  Embedding tersebut tampaknya mendukung pencarian seperti ini dengan jauh lebih baik, jadi akan menarik jika pencarian Wikipedia offline pada artikel yang ditautkan itu dicoba ulang dengan jenis embedding baru ini

• Saat ini halamannya tidak berfungsi di lingkungan saya; model_quantized.onnx tidak termuat
  Saat saya mengetik, file itu sudah terunduh hingga 19,2MB dengan kecepatan sekitar 50KB/dtk, dan jika ini terjadi pada setiap pengunjung, mungkin sedang melakukan hal yang mengerikan pada biaya bandwidth Lee Butterman

  • Ini disajikan sebagai file statis dari satu t2.nano, jadi saya tidak tahu apa yang akan terjadi

• Hal yang dikerjakannya sendiri sangat mengesankan, tetapi kualitas hasil pencarian tampaknya tidak bagus
  Dari pengalaman, saya tahu bahwa menilai kualitas hasil pencarian secara manual itu benar-benar sulit. Hasilnya bisa sangat dekat dengan hasil yang sangat bagus, tetapi tetap mengembalikan kecocokan yang jauh lebih buruk dari itu

  • Benar. Kualitasnya mungkin tidak sebagus Similar Website Finder https://explore2.marginalia.nu/ ;)
    Saya rasa hasilnya akan membaik jika memakai embedding kalimat yang lebih baru, dan saya perlu mengumpulkan lebih banyak data

• Teknologinya sangat mengesankan, tetapi hasilnya tidak demikian
  Saat mencari “pointy building in Paris”, yang muncul adalah Tourism in Paris, Bourse de commerce (Paris), Grands Projets of François Mitterrand, List of tallest buildings and structures in the Paris region, List of tourist attractions in Paris, Palais des congrès de Paris, Landmarks in Paris, Palais de la Bourse, Lyon, Outline of Paris, Architecture of Paris
  Bangunan runcing paling terkenal di Paris sama sekali tidak terlihat
  Untuk aplikasi semacam ini, sentence embedding dari keseluruhan dokumen mungkin bukan pilihan terbaik

  • Setidaknya 5 di antaranya sepertinya memuat jawaban yang dicari
  • Kalau yang dimaksud Eiffel Tower, itu bukan bangunan
    Saya baru saja memeriksa artikelnya; kata “building” muncul 19 kali, tetapi sebagian besar sebagai kata kerja, lalu berikutnya adalah “Chrysler Building”
    Maksudnya, kecuali ada bangunan runcing terkenal lain yang tidak terpikir oleh saya

• Sebagian keajaiban mesin pencari terletak pada pencampuran embedding dari halaman-halaman yang menaut ke halaman tersebut, atau kata kunci information retrieval tradisional, dengan pembobotan berdasarkan jumlah klik dan skor otoritas
  Tanpa sinyal ini, banyak informasi berguna terabaikan, dan hasilnya tidak terasa ajaib
  Meski begitu, ini demo yang mengesankan dan menarik

• Saya ingin menyukainya, tetapi dalam pencarian yang saya coba, hampir tidak ada hasil yang relevan
  “The wizard in The Lord of the Rings” tidak menampilkan Gandalf atau Saruman, hanya buku-buku terkait LOTR
  “Protagonist of Scorsese's Taxi Driver” tidak menampilkan Travis Bickle
  “A person that plants trees for a living” entah kenapa tidak memasukkan gardener dalam daftar
  “Curly-haired painter on TV” sama sekali tidak menampilkan Bob Ross
  Untuk “Unusually shaped modern art museum in Spain”, Bilbao memang muncul di posisi ke-4, tetapi sisanya bukan bangunan berbentuk unik
  Untuk “Dog shaped like a sausage”, dachshund seharusnya ada di hasil teratas

  • Perlu dicatat bahwa semua hasil yang diharapkan di sini memang memiliki artikel Wikipedia
    Kalau artikelnya tidak ada, absennya hasil itu tidak akan terlalu aneh, tetapi kenyataannya semuanya ada

• “Vibes” terasa jauh lebih mengena daripada “sentence embeddings”. Mungkin saya juga harus mulai memakai istilah itu :)

  • Alih-alih “mengena”, istilah itu mengorbankan banyak presisi
    Penulis aslinya tidak menjelaskan mengapa memilih kata itu, dan tidak cocok dengan penggunaan “vibe” mana pun yang saya tahu
    Saya jadi bertanya-tanya apakah “gist” kurang terdengar seperti buzzword