Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks

• URL: http://arxiv.org/abs/2501.03078v1
• Date: Mon, 06 Jan 2025 15:20:22 GMT
• Title: Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks
• Abstract summary: We introduce QINCo2, which improves the state-of-the-art reconstruction MSE by 34% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.<n>We conduct experiments on four datasets to evaluate QINCo2 for vector compression and billion-scale nearest neighbor search.
• Score: 23.598010051403225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vector quantization is a fundamental technique for compression and large-scale nearest neighbor search. For high-accuracy operating points, multi-codebook quantization associates data vectors with one element from each of multiple codebooks. An example is residual quantization (RQ), which iteratively quantizes the residual error of previous steps. Dependencies between the different parts of the code are, however, ignored in RQ, which leads to suboptimal rate-distortion performance. QINCo recently addressed this inefficiency by using a neural network to determine the quantization codebook in RQ based on the vector reconstruction from previous steps. In this paper we introduce QINCo2 which extends and improves QINCo with (i) improved vector encoding using codeword pre-selection and beam-search, (ii) a fast approximate decoder leveraging codeword pairs to establish accurate short-lists for search, and (iii) an optimized training procedure and network architecture. We conduct experiments on four datasets to evaluate QINCo2 for vector compression and billion-scale nearest neighbor search. We obtain outstanding results in both settings, improving the state-of-the-art reconstruction MSE by 34% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.

Related papers

• RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search [0.4077787659104315]
  RSLM is a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension.<n>We reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system.<n>Our major innovation is that we correct the $L$ norm of the final reconstructed vector rather than just the residual.
  arXiv  Detail & Related papers  (2026-08-31T07:40:57Z)
• Q2D2: A Geometry-Aware Audio Codec Leveraging Two-Dimensional Quantization [8.458339111154585]
  We introduce Two Dimensional Quantization (Q2D2), a quantization scheme in which feature pairs are projected onto structured 2D grids.<n>Despite its simple geometric formulation, Q2D2 improves audio compression efficiency, with low token rates and high codebook utilization.
  arXiv  Detail & Related papers  (2025-12-01T11:06:38Z)
• Reducing Storage of Pretrained Neural Networks by Rate-Constrained Quantization and Entropy Coding [56.066799081747845]
  The ever-growing size of neural networks poses serious challenges on resource-constrained devices.<n>We propose a novel post-training compression framework that combines rate-aware quantization with entropy coding.<n>Our method allows for very fast decoding and is compatible with arbitrary quantization grids.
  arXiv  Detail & Related papers  (2025-05-24T15:52:49Z)
• Quantum-enhanced belief propagation for LDPC decoding [0.0]
  We introduce the quantum-enhanced belief propagation algorithm, which acts as a pre-processing step to belief propagation. We study the possibility of having shared variational parameters between syndromes and, in this case, code lengths.
  arXiv  Detail & Related papers  (2024-12-11T18:14:18Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Residual Quantization with Implicit Neural Codebooks [40.021284158234344]
  We propose QINCo, a neural RQ variant that constructs specialized codebooks per step that depend on the approximation of the vector from previous steps. Experiments show that QINCo outperforms state-of-the-art methods by a large margin on several datasets and code sizes.
  arXiv  Detail & Related papers  (2024-01-26T09:42:51Z)
• Soft Convex Quantization: Revisiting Vector Quantization with Convex Optimization [40.1651740183975]
  We propose Soft Convex Quantization (SCQ) as a direct substitute for Vector Quantization (VQ) SCQ works like a differentiable convex optimization (DCO) layer. We demonstrate its efficacy on the CIFAR-10, GTSRB and LSUN datasets.
  arXiv  Detail & Related papers  (2023-10-04T17:45:14Z)
• Deep Equilibrium Object Detection [24.69829309391189]
  We present a new query-based object detector (DEQDet) by designing a deep equilibrium decoder. Our experiments demonstrate DEQDet converges faster, consumes less memory, and achieves better results than the baseline counterpart.
  arXiv  Detail & Related papers  (2023-08-18T13:56:03Z)
• Mixed-Precision Quantization with Cross-Layer Dependencies [6.338965603383983]
  Mixed-precision quantization (MPQ) assigns varied bit-widths to layers to optimize the accuracy-efficiency trade-off. Existing methods simplify the MPQ problem by assuming that quantization errors at different layers act independently. We show that this assumption does not reflect the true behavior of quantized deep neural networks.
  arXiv  Detail & Related papers  (2023-07-11T15:56:00Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  Cross-encoder models are prohibitively expensive for direct k-nearest neighbor (k-NN) search. We propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors.
  arXiv  Detail & Related papers  (2023-05-04T17:01:17Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Nearest neighbor search with compact codes: A decoder perspective [77.60612610421101]
  We re-interpret popular methods such as binary hashing or product quantizers as auto-encoders. We design backward-compatible decoders that improve the reconstruction of the vectors from the same codes.
  arXiv  Detail & Related papers  (2021-12-17T15:22:28Z)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization. We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming. This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• Permute, Quantize, and Fine-tune: Efficient Compression of Neural Networks [70.0243910593064]
  Key to success of vector quantization is deciding which parameter groups should be compressed together. In this paper we make the observation that the weights of two adjacent layers can be permuted while expressing the same function. We then establish a connection to rate-distortion theory and search for permutations that result in networks that are easier to compress.
  arXiv  Detail & Related papers  (2020-10-29T15:47:26Z)
• APQ: Joint Search for Network Architecture, Pruning and Quantization Policy [49.3037538647714]
  We present APQ for efficient deep learning inference on resource-constrained hardware. Unlike previous methods that separately search the neural architecture, pruning policy, and quantization policy, we optimize them in a joint manner. With the same accuracy, APQ reduces the latency/energy by 2x/1.3x over MobileNetV2+HAQ.
  arXiv  Detail & Related papers  (2020-06-15T16:09:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.