Metraipolis › archive › dc_e9d263be417e

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search — arXiv:2608.30384

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.30384
License (as archived)
CC0-1.0
Archived
2026-10-17T08:39:11.751Z
SHA-256 of the archived text
fdb8d62e5ecd947ec6750fd98b79210b2a800532fa900ae002fb6f77c8bc8d82
Stable URL of this page
https://metraipolis.com/documento/dc_e9d263be417e

How to cite

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search — arXiv:2608.30384 — arXiv (en), https://arxiv.org/abs/2608.30384 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e9d263be417e (Metraipolis archive dc_e9d263be417e, sha256 fdb8d62e5ecd947ec6750fd98b79210b2a800532fa900ae002fb6f77c8bc8d82)
BibTeX
@misc{dce9d263be417e,
  title = {RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search — arXiv:2608.30384},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30384},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e9d263be417e; sha256 fdb8d62e5ecd947ec6750fd98b79210b2a800532fa900ae002fb6f77c8bc8d82},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30384. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the $L_2$ norms of quantized vectors. Our major innovation is that we correct the $L_2$ norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-01 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Information Retrieval (cs.IR).
Pagina del lavoro: https://arxiv.org/abs/2608.30384 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T08:13:26.813Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).