Revisiting Multi-Codebook Quantization
Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Therefore, MCQ theoretically has the potential to achieve the best performance because solutions of other codebook-based quantization methods are all covered by MCQ's solution space under the same codebook size setting. However, finding the optimal solution to MCQ is proved to be NP-hard due to its encoding process, \textit{i.e.}, converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions, or employ heuristic algorithms which are still time-consuming for encoding. Different from previous approaches, this paper takes the first attempt to find a deep solution to MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of-the-art performance. Notably, our method is 11×-38× faster than heuristic algorithms for encoding, which makes it more practical for real scenery of large-scale retrieval. Our code is publicly available: https://github.com/DeepMCQ/DeepQ.
Code (0)
등록된 구현이 없습니다.
Tasks
QuantizationRetrievalSimilar Papers 제목 키워드 기반
Soft Convex Quantization: Revisiting Vector Quantization with Convex Optimization
Vector Quantization (VQ) is a well-known technique in deep learning for extracting informative discrete latent representations. VQ-embedded models have shown impressive results in a range of applications including image …
Image ReconstructionQuantizationAnd the Bit Goes Down: Revisiting the Quantization of Neural Networks
In this paper, we address the problem of reducing the memory footprint of convolutional network architectures. We introduce a vector quantization method that aims at preserving the quality of the reconstruction of the ne…
CPUQuantizationGraph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning
Vector Quantization (VQ) has recently emerged as a promising approach for learning compressed and discrete representations for graph-structured data. However, a fundamental challenge, i.e., codebook collapse, remains und…
Graph Representation LearningRQ-MoE: Residual Quantization via Mixture of Experts for Efficient Input-Dependent Vector Compression
Vector quantization is a fundamental tool for compressing high-dimensional embeddings, yet existing multi-codebook methods rely on static codebooks that limit expressiveness under heterogeneous data geometry. While recen…
Revisiting Adaptive Rounding with Vectorized Reparameterization for LLM Quantization
Adaptive Rounding has emerged as an alternative to round-to-nearest (RTN) for post-training quantization by enabling cross-element error cancellation. Yet, dense and element-wise rounding matrices are prohibitively expen…