Editorial ilmu komputer
Open AccessOA2026
Laporan Teknis Aperon: Pencarian Tetangga Terdekat Aproksimatif Berdimensi Tinggi dengan Hierarchical No-Pointer Tangent-Local Search
HNTL: Kerangka Block-SoA tanpa pointer yang mencapai percepatan 3,61x dan recall sempurna dengan C=20 kandidat pada data manifold anisotropik
Yong Fu· 2026· DOI 10.48550/arXiv.2606.08813
Masalah inti
Pencarian tetangga terdekat aproksimatif (ANN) di ruang berdimensi tinggi adalah primitif dasar bagi sistem memori vektor, retrieval-augmented generation, dan pencarian semantik. Metode graf kedekatan seperti HNSW mendominasi bidang ini karena trade-off recall-latensi yang kuat, tetapi metode tersebut menanggung **pointer tax** yang berat: setiap node menyimpan banyak pointer ke tetangga, sehingga membengkakkan overhead memori, dan penelusuran graf memicu akses memori tak teratur yang menghambat pipeline CPU dan mengalahkan prefetcher perangkat keras. Sistem memori vektor Aperon mengatasi hal ini dengan **HNTL (Hierarchical No-pointer Tangent-Local)**, kerangka pengindeksan vektor dan pembangkitan kandidat yang menghilangkan pointer sepenuhnya. HNTL mempartisi ruang berdimensi tinggi menjadi butir lokal yang koheren, merepresentasikan vektor sebagai koordinat berdimensi rendah pada ruang tangen lokal, dan memindainya secara sekuensial menggunakan tata letak **Block-SoA (Structure-of-Arrays)** tanpa pointer. Digest ini menyajikan struktur IMRAD dari laporan teknis tersebut, mencakup metodologi, hasil profiling perangkat keras, dan implikasinya bagi pencarian ANN berdimensi tinggi.
Inovasi
Laporan ini mengevaluasi HNTL pada data manifold anisotropik dengan dan . Temuan utama:
- **Recall**: HNTL mencapai **Rerank Recall@10 final sebesar 1,0000** dengan ukuran kumpulan kandidat hanya vektor. Artinya, recall sempurna diperoleh setelah reranking hanya 20 kandidat, pengurangan dramatis dibandingkan metode berbasis graf yang biasanya memerlukan ratusan kandidat.
- **Kecepatan**: Profiling perangkat keras melalui penghitung Apple kperf CPU Performance Monitoring Unit (PMU) menunjukkan **percepatan 3,61x** untuk mesin pemindaian C++ Block-SoA yang di-auto-vectorize NEON dibandingkan penelusuran graf pointer-chasing standar: **4,137 ns/vektor** versus **14,951 ns/vektor**.
- **Efisiensi mikroarsitektural**: Percepatan ini didorong oleh peningkatan **IPC (Instructions Per Cycle) sebesar 3,59x** dan cache miss data L1/L2 yang mendekati nol, mengonfirmasi bahwa tata letak tanpa pointer menghilangkan stall memori yang membebani penelusuran graf.
Hasil-hasil ini dirangkum dalam tabel di bawah ini:
| Metrik | HNTL (Block-SoA) | Graf Pointer-Chasing |
|--------|------------------|-----------------------|
| Waktu per vektor | 4,137 ns | 14,951 ns |
| Per
Pencarian tetangga terdekat aproksimatif (ANN) di ruang berdimensi tinggi adalah primitif dasar bagi sistem memori vektor, retrieval-augmented generation, dan pencarian semantik. Metode graf kedekatan seperti HNSW mendominasi bidang ini karena trade-off recall-latensi yang kuat, tetapi metode tersebut menanggung **pointer tax** yang berat: setiap node menyimpan banyak pointer ke tetangga, sehingga membengkakkan overhead memori, dan penelusuran graf memicu akses memori tak teratur yang menghambat pipeline CPU dan mengalahkan prefetcher perangkat keras. Sistem memori vektor Aperon mengatasi hal ini dengan **HNTL (Hierarchical No-pointer Tangent-Local)**, kerangka pengindeksan vektor dan pembangkitan kandidat yang menghilangkan pointer sepenuhnya. HNTL mempartisi ruang berdimensi tinggi menjadi butir lokal yang koheren, merepresentasikan vektor sebagai koordinat berdimensi rendah pada ruang tangen lokal, dan memindainya secara sekuensial menggunakan tata letak **Block-SoA (Structure-of-Arrays)** tanpa pointer. Digest ini menyajikan struktur IMRAD dari laporan teknis tersebut, mencakup metodologi, hasil profiling perangkat keras, dan implikasinya bagi pencarian ANN berdimensi tinggi.
HNTL beroperasi dalam tiga tahap: (1) **Partisi ruang** menjadi butir lokal melalui clustering atau pemisahan rekursif, memastikan setiap butir menangkap wilayah yang koheren dari manifold data. (2) **Embedding ruang tangen**: untuk setiap butir, PCA lokal dihitung, dan vektor diproyeksikan ke ruang tangen berdimensi rendah. Pada data manifold anisotropik dengan dimensi dan , PCA lokal menangkap **96,3% varians**, memungkinkan reduksi dimensi yang agresif sekaligus mempertahankan struktur ketetanggaan. (3) **Pemindaian Block-SoA tanpa pointer**: vektor dalam suatu butir disimpan dalam tata letak Block-SoA, di mana koordinat dikelompokkan berdasarkan dimensi, bukan berdasarkan vektor. Hal ini memungkinkan pemindaian sekuensial yang ramah cache dan auto-vectorization. Pembangkitan kandidat berlangsung dengan memindai butir dalam urutan hierarkis, menghitung jarak aproksimatif di ruang tangen, dan memilih kumpulan kandidat kecil untuk reranking eksak. Seluruh pipeline menghindari pointer chasing, dan mengandalkan blok memori yang bersebelahan serta loop yang ramah SIMD.
Mengapa penting
Hasil HNTL menyoroti trade-off fundamental dalam pencarian ANN: metode berbasis graf mencapai recall tinggi melalui konektivitas tetapi membayar harga mahal dalam ketidakteraturan memori dan overhead pointer. HNTL menghindari hal ini dengan memanfaatkan **struktur lokal berdimensi rendah** pada data berdimensi tinggi. Varians 96,3% yang ditangkap oleh PCA lokal pada data manifold anisotropik menunjukkan bahwa embedding dunia nyata sering kali terletak pada atau dekat manifold berdimensi rendah, sehingga aproksimasi ruang tangen sangat efektif. Tata letak Block-SoA tanpa pointer adalah kunci percepatan 3,61x: dengan menyimpan koordinat berdasarkan dimensi, mesin pemindaian dapat menggunakan instruksi NEON SIMD dan prefetching sekuensial, mencapai IPC 3,59x dan cache miss mendekati nol. Recall sempurna dengan menunjukkan bahwa aproksimasi ruang tangen mempertahankan cukup informasi untuk memberi peringkat tinggi pada tetangga sejati, sehingga reranking eksak dapat memulihkannya. Batasan meliputi ketergantungan pada asumsi manifold dan biaya pembangunan model PCA lokal, yang dapat diamortisasi pada indeks statis atau yang berkembang lambat. Pekerjaan selanjutnya dapat mengeksplorasi ukuran butir adaptif, pembaruan daring, dan integrasi dengan product quantization untuk kompresi lebih lanjut. Secara keseluruhan, HNTL menawarkan alternatif yang menarik dibandingkan graf kedekatan yang sarat pointer untuk ANN berdimensi tinggi, khususnya pada sistem memori vektor yang terbatas memori atau sensitif terhadap latensi.
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten member…