PaperlayerView exact revision on arXiv

Source-linked AI summary

Spreading vectors for similarity search

Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Hervé Jégou

arXiv:1806.03198v3stat.MLcs.LG

TL;DR

Multi-dimensional indexing must discretize data effectively, but jointly optimizing learned representations and coding remains largely unresolved. The paper adapts data to fixed quantizers using a neural mapping that promotes spherical uniformity while preserving neighborhoods, achieving competitive accuracy and practical encoding speed; training without quantization also produces a generic catalyzer.

  • Problem

    Jointly optimizing a coding stage and neural network for similarity search remains essentially unsolved, while multi-dimensional indexing needs mappings that support effective discretization.

  • Method

    The method learns a neural mapping that adapts data to a subsequent quantizer, combining a Kozachenko–Leonenko-based entropy regularizer for spherical uniformity with a locality-aware triplet loss.

  • Results

    The catalyzer reduces the nearest-neighbor uniformity probability from 20.8% to 5.0%, while the Catalyst + Lattice variant is 14× faster than LSQ at competitive or higher accuracy.

  • Takeaways & Limitations

    The learned mapping can serve as a plug-in before standard quantizers, and spherical lattice quantizers offer competitive quantization properties with efficient algebraic encoding.

Abstract

from arXiv · show

Discretizing multi-dimensional data distributions is a fundamental step of modern indexing methods. State-of-the-art techniques learn parameters of quantizers on training data for optimal performance, thus adapting quantizers to the data. In this work, we propose to reverse this paradigm and adapt the data to the quantizer: we train a neural net which last layer forms a fixed parameter-free quantizer, such as pre-defined points of a hyper-sphere. As a proxy objective, we design and train a neural network that favors uniformity in the spherical latent space, while preserving the neighborhood structure after the mapping. We propose a new regularizer derived from the Kozachenko--Leonenko differential entropy estimator to enforce uniformity and combine it with a locality-aware triplet loss. Experiments show that our end-to-end approach outperforms most learned quantization methods, and is competitive with the state of the art on widely adopted benchmarks. Furthermore, we show that training without the quantization step results in almost no difference in accuracy, but yields a generic catalyzer that can be applied with any subsequent quantizer.

1 INTRODUCTION

The paper adapts data to fixed quantizers by learning a mapping that preserves neighborhoods while making outputs uniform, addressing difficult joint optimization of neural networks and discretization. Its catalyzer supports competitive indexing and can improve subsequent coding stages.

  • Motivation and approach: The approach generalizes learned one-dimensional CDF indexing by mapping vectors to a uniform distribution over a d-dimensional sphere for fixed discretization.Candidate quantizers include fixed binary encodings and regular lattice quantizers.
  • Motivation and approach: Jointly optimizing coding and neural networks is difficult because discretization functions are hard to optimize through, especially for powerful codes such as product quantization.Existing binary-code methods use soft binarization or stochastic relaxation, while product-quantization solutions require complex optimization procedures.
  • Method: The method reverses conventional adaptation by learning a mapping whose output distribution makes a subsequent binary or general quantizer perform better.Rather than adapting the indexing structure to the data, it adapts the data to the index.
  • Method: The loss combines neighborhood preservation through a ranking objective with a differential-entropy-derived regularizer that favors a uniform continuous output.The two criteria are explicitly treated as competing objectives.
  • Results and contributions: The approach reports a reduced discrepancy between near-neighbor and nearest-neighbor search, while its learned mapping also supports compact coding with fixed discretization structures.The paper frames this discrepancy reduction as a result of the technique and highlights compact coding as a contribution.
  • Results and contributions: The paper presents the learned mapping as a neural-network adapter for later similarity-search methods and evaluates the strategy with lattice assignment for compact codes.The workflow is organized around learning the mapping first and applying a subsequent coding stage.

2 RELATED WORK

Related work spans generative modeling, nonlinear dimensionality reduction, learned indexing and quantization, lattice-based discretization, and entropy regularization. The paper distinguishes its approach by mapping empirical inputs to a uniform spherical output for indexing.

  • Generative modeling: Generative models map between latent distributions and empirical data, whereas this work maps an empirical input distribution to a uniform spherical output space.The paper also distinguishes its encoder-focused mapping from GAN decoders and VAE encoder-decoder mappings.
  • Dimensionality reduction and representation learning: Self-organizing maps, stochastic neighbor embedding, and t-SNE represent nonlinear dimensionality-reduction methods that preserve neighborhood structure in the output space.The cited t-SNE line of work is described as tailored to low-dimensional visualization.
  • Learning to index and quantize: Learned indexing and quantization research includes locality-sensitive hashing, iterative quantization, and product compact codes, addressing the limitations of non-adaptive indexing.The paper positions its data-adaptation strategy within this literature.
  • Lattices: Lattices are discrete Euclidean subsets valued for space covering, sphere packing, and efficiently computable closest points under algebraic structure.These properties motivate lattice-based quantization in indexing applications.
  • Entropy regularization: Entropy regularization has been used for output regularization, optimal-transport computation, moment matching, and spreading representations.The paper relates its uniformity objective to this broader family of techniques.

3 OUR APPROACH: LEARNING THE CATALYZER

The catalyzer maps inputs to a hypersphere while balancing neighborhood preservation against uniform output distribution. A Kozachenko–Leonenko regularizer spreads points, while a triplet loss preserves neighbors; intermediate weighting gives useful trade-offs.

  • The neural network maps vectors from the input space to a higher-dimensional hypersphere.
  • 3.1 KOLEO: DIFFERENTIAL ENTROPY REGULARIZER: The Kozachenko–Leonenko regularizer pushes closest points apart with diminishing marginal effect as distances increase.
  • The method combines a triplet loss for neighborhood preservation with a differential-entropy regularizer favoring uniform outputs.The triplet loss uses input-space nearest neighbors as positives and output-space distant neighbors as negatives.
  • 3.3 DISCUSSION: The trade-off parameter λ balances ranking quality and output uniformity, so intermediate values avoid both neighbor collapse and poor neighborhood preservation.Without regularization, neighboring points can collapse and leave quantizer cells empty; relying only on entropy harms neighbor preservation.
  • 3.3 DISCUSSION: The catalyzer reduces the probability that a nearest-neighbor distance exceeds another point’s 100th-neighbor distance from 20.8% to 5.0%.The corresponding nearest- and 100th-neighbor distance distributions overlap less after mapping.
  • 3.3 DISCUSSION: Increasing regularization makes projected output distributions more uniform, resembling a uniform distribution at λ = 1.The visualizations use random two-dimensional projections of the higher-dimensional output distribution.

4 CATALYZER WITH DISCRETIZATION

The catalyzer enables fixed parameter-free discretization by mapping data toward distributions suited to binary or spherical lattice coding. At search time, database vectors are quantized while queries remain unquantized for asymmetric distance comparison.

  • The method supports parameter-free binarization and fixed spherical lattice quantization.
  • Lattice quantizers are effective for uniform distributions, and the regularizer makes the catalyzed output closer to that setting.Rigid lattice partitions are suboptimal for arbitrary distributions but offer strong quantization properties for uniform data.
  • 4.2 LATTICES: The spherical lattice consists of integer points with fixed norm, and each catalyzed feature is assigned to its nearest lattice point.
  • Queries remain unquantized while database vectors use lattice codes, enabling asymmetric approximate similarity comparisons.The approximation replaces the database feature with its normalized quantized code.
  • During training, the quantization layer returns quantized features forward and passes gradients backward through a straight-through estimator.

5 EXPERIMENTS

Experiments evaluate compressed similarity search on Deep1M, BigAnn1M, and billion-scale datasets using recall@k, comparing lattice-based indexing with PQ, OPQ, and binary hashing methods. The lattice quantizer generally outperforms PQ and OPQ, while the catalyzer improves multiple downstream quantizers and hashing methods.

  • Experimental setup: The evaluation encodes vectors through transformation followed by quantization or binarization, then exhaustively scans codes to return top-k neighbors.Training, validation, and evaluation vectors are separated for the reported experiments.
  • Experimental setup: Experiments use Deep1M and BigAnn1M, each with 1M reference vectors and 10k queries, plus full billion-vector datasets.Methods are evaluated with recall@k for k ∈ {1, 10, 100}.
  • Lattice quantization: On both datasets, the lattice quantizer strongly outperforms PQ and OPQ for most code sizes.The lattice experiments vary radius r and output dimension dout to generate performance curves.
  • Hyperparameters: For low bitrates, small dout performs better, whereas higher bitrates favor larger dout because representation quality becomes dominant.The choice of dout trades representation capacity against compressibility and quantization error.
  • Large-scale experiments: At billion-vector scale with 64-bit codes, recall@10 is 37.8% for the lattice quantizer versus 26.1% for OPQ on Deep1B.On BigAnn, the corresponding recalls are 36.5% and 21.3%.
  • Comparison to the state of the art: Catalyst + Lattice is 14× faster than LSQ while achieving competitive or higher accuracy, but its 1M asymmetric-distance search takes 7.5 ms versus 4.9 ms for PQ.The lattice scheme does not require external metadata after compact-code production.
  • Ablation study: Training without the quantization layer has limited impact at 64 bits, and catalyzed features improve OPQ recall@10 from 63.6 to 71.1.Replacing the catalyzer with PCA significantly decreases lattice-quantizer performance.
  • Binary hashing: The catalyzer improves binary-hashing performance by 2–9 percentage points from 32 to 128 bits.The comparison includes LSH and ITQ, with a simple sign function applied to catalyzed features.

6 CONCLUDING REMARKS

The paper adapts data distributions to fixed quantizers by mapping inputs onto a uniform unit hypersphere, improving indexing accuracy while retaining practical advantages.

  • The neural network maps input features to a uniform distribution on a unit hypersphere for indexing.
  • The approach is competitive with rigid lattice quantizers and trivial binary encoding.
  • Rigid quantizers provide fast encoding and allow vector decoding without codebooks or auxiliary tables.

APPENDIX A VALUES OF THE REGULARIZATION PARAMETER

The appendix reports the regularization settings selected for Deep1M with a fixed hypersphere radius of 10.

  • The optimal regularization parameter λ decreases as the dimension increases.
  • Table 3 reports optimal λ values for Deep1M.
  • The reported λ values use a fixed radius of r = 10.

APPENDIX B FAST DISCRETIZATION WITH A LATTICE ON THE SPHERE.

The appendix describes a lattice quantizer on a hypersphere, including atom-based enumeration and compact encoding of permutations and signs.

  • Lattice on the sphere: The quantizer uses integer lattice points lying on a hypersphere, with radius selected for the desired representation.
  • Atoms: Atoms are normalized vectors formed by taking coordinate absolute values and sorting them in decreasing order.
  • Encoding and enumerating: Quantization normalizes the input, applies the corresponding permutation and sign structure, and selects a lattice vector.
  • Encoding and enumerating: The encoding stores an atom range, a permutation, and signs of non-zero elements, while decoding reverses these steps.
  • Encoding and enumerating: Encoding 1M vectors takes about 0.5 s, compared with 1.9 s for PQ.

APPENDIX C EPSILON-SEARCH

On Deep1M, the transformed space produces closer agreement between range search and nearest-neighbor search, requiring fewer returned results for comparable recall.

  • The transformed space shows better agreement between range search and k-nearest-neighbor search.
  • Without mapping, the number of returned results varies substantially for a given ε; after mapping, the agreement improves.
  • For 80% recall, transformed-space search returns 200 results per query at ε = 0.38, versus 700 at ε = 0.54 in the original space.
Loading 1806.03198v3…