Struct faiss::ResidualQuantizer

struct ResidualQuantizer : public faiss::AdditiveQuantizer

Residual quantizer with variable number of bits per sub-quantizer

The residual centroids are stored in a big cumulative centroid table. The codes are represented either as a non-compact table of size (n, M) or as the compact output (n, code_size).

Public Types

using train_type_t = int


enum Search_type_t

Encodes how search is performed and how vectors are encoded.


enumerator ST_decompress

decompress database vector

enumerator ST_LUT_nonorm

use a LUT, don’t include norms (OK for IP or normalized vectors)

enumerator ST_norm_from_LUT

compute the norms from the look-up tables (cost is in O(M^2))

enumerator ST_norm_float

use a LUT, and store float32 norm with the vectors

enumerator ST_norm_qint8

use a LUT, and store 8bit-quantized norm

enumerator ST_norm_qint4
enumerator ST_norm_cqint8

use a LUT, and store non-uniform quantized norm

enumerator ST_norm_cqint4
enumerator ST_norm_lsq2x4

use a 2x4 bits lsq as norm quantizer (for fast scan)

enumerator ST_norm_rq2x4

use a 2x4 bits rq as norm quantizer (for fast scan)

Public Functions

ResidualQuantizer(size_t d, const std::vector<size_t> &nbits, Search_type_t search_type = ST_decompress)
ResidualQuantizer(size_t d, size_t M, size_t nbits, Search_type_t search_type = ST_decompress)
virtual void train(size_t n, const float *x) override

Train the residual quantizer.

void initialize_from(const ResidualQuantizer &other, int skip_M = 0)

Copy the M codebook levels from other, starting from skip_M.

float retrain_AQ_codebook(size_t n, const float *x)

Encode the vectors and compute codebook that minimizes the quantization error on these codes

  • x – training vectors, size n * d

  • n – nb of training vectors, n >= total_codebook_size


returns quantization error for the new codebook with old codes

virtual void compute_codes_add_centroids(const float *x, uint8_t *codes, size_t n, const float *centroids = nullptr) const override

Encode a set of vectors

  • x – vectors to encode, size n * d

  • codes – output codes, size n * code_size

  • centroids – centroids to be added to x, size n * d

void refine_beam(size_t n, size_t beam_size, const float *residuals, int new_beam_size, int32_t *new_codes, float *new_residuals = nullptr, float *new_distances = nullptr) const

lower-level encode function

  • n – number of vectors to hanlde

  • residuals – vectors to encode, size (n, beam_size, d)

  • beam_size – input beam size

  • new_beam_size – output beam size (should be <= K * beam_size)

  • new_codes – output codes, size (n, new_beam_size, m + 1)

  • new_residuals – output residuals, size (n, new_beam_size, d)

  • new_distances – output distances, size (n, new_beam_size)

void refine_beam_LUT(size_t n, const float *query_norms, const float *query_cp, int new_beam_size, int32_t *new_codes, float *new_distances = nullptr) const
size_t memory_per_point(int beam_size = -1) const

Beam search can consume a lot of memory. This function estimates the amount of mem used by refine_beam to adjust the batch size


beam_size – if != -1, override the beam size

void compute_codebook_tables()

Cross products used in codebook tables used for beam_LUT = 1

uint64_t encode_norm(float norm) const

encode a norm into norm_bits bits

uint32_t encode_qcint(float x) const

encode norm by non-uniform scalar quantization

float decode_qcint(uint32_t c) const

decode norm by non-uniform scalar quantization

void set_derived_values()

Train the norm quantizer.

void train_norm(size_t n, const float *norms)
inline virtual void compute_codes(const float *x, uint8_t *codes, size_t n) const override

Quantize a set of vectors

  • x – input vectors, size n * d

  • codes – output codes, size n * code_size

void pack_codes(size_t n, const int32_t *codes, uint8_t *packed_codes, int64_t ld_codes = -1, const float *norms = nullptr, const float *centroids = nullptr) const

pack a series of code to bit-compact format

  • codes – codes to be packed, size n * code_size

  • packed_codes – output bit-compact codes

  • ld_codes – leading dimension of codes

  • norms – norms of the vectors (size n). Will be computed if needed but not provided

  • centroids – centroids to be added to x, size n * d

virtual void decode(const uint8_t *codes, float *x, size_t n) const override

Decode a set of vectors

  • codes – codes to decode, size n * code_size

  • x – output vectors, size n * d

virtual void decode_unpacked(const int32_t *codes, float *x, size_t n, int64_t ld_codes = -1) const

Decode a set of vectors in non-packed format

  • codes – codes to decode, size n * ld_codes

  • x – output vectors, size n * d

template<bool is_IP, Search_type_t effective_search_type>
float compute_1_distance_LUT(const uint8_t *codes, const float *LUT) const
void decode_64bit(idx_t n, float *x) const

decoding function for a code in a 64-bit word

virtual void compute_LUT(size_t n, const float *xq, float *LUT, float alpha = 1.0f, long ld_lut = -1) const

Compute inner-product look-up tables. Used in the centroid search functions.

  • xq – query vector, size (n, d)

  • LUT – look-up table, size (n, total_codebook_size)

  • alpha – compute alpha * inner-product

  • ld_lut – leading dimension of LUT

void knn_centroids_inner_product(idx_t n, const float *xq, idx_t k, float *distances, idx_t *labels) const

exact IP search

void compute_centroid_norms(float *norms) const

For L2 search we need the L2 norms of the centroids


norms – output norms table, size total_codebook_size

void knn_centroids_L2(idx_t n, const float *xq, idx_t k, float *distances, idx_t *labels, const float *centroid_norms) const

Exact L2 search, with precomputed norms

Public Members

train_type_t train_type = Train_progressive_dim

Binary or of the Train_* flags below.

int niter_codebook_refine = 5

number of iterations for codebook refinement.

int max_beam_size = 5

beam size used for training and for encoding

int use_beam_LUT = 0

use LUT for beam search

ApproxTopK_mode_t approx_topk_mode = ApproxTopK_mode_t::EXACT_TOPK

Currently used mode of approximate min-k computations. Default value is EXACT_TOPK.

ProgressiveDimClusteringParameters cp

clustering parameters

ProgressiveDimIndexFactory *assign_index_factory = nullptr

if non-NULL, use this index for assignment

std::vector<float> codebook_cross_products

dot products of all codebook entries with the previous codebooks size sum(codebook_offsets[m] * 2^nbits[m], m=0..M-1)

std::vector<float> cent_norms

norms of all codebook entries (size total_codebook_size)

size_t M

number of codebooks

std::vector<size_t> nbits

bits for each step

std::vector<float> codebooks


std::vector<uint64_t> codebook_offsets
size_t tot_bits = 0

total number of bits (indexes + norms)

size_t norm_bits = 0

bits allocated for the norms

size_t total_codebook_size = 0

size of the codebook in vectors

bool only_8bit = false

are all nbits = 8 (use faster decoder)

bool verbose = false

verbose during training?

bool is_trained = false

is trained or not

IndexFlat1D qnorm

store and search norms

std::vector<float> norm_tabs

store norms of codebook entries for 4-bit fastscan search

size_t max_mem_distances = 5 * (size_t(1) << 30)

norms and distance matrixes with beam search can get large, so use this to control for the amount of memory that can be allocated

Search_type_t search_type

Also determines what’s in the codes.

float norm_min = NAN

min/max for quantization of norms

float norm_max = NAN
size_t d

size of the input vectors

size_t code_size

bytes per indexed vector

Public Static Attributes

static const int Train_default = 0

regular k-means (minimal amount of computation)

static const int Train_progressive_dim = 1

progressive dim clustering (set by default)

static const int Train_refine_codebook = 2

do a few iterations of codebook refinement after first level estimation

static const int Train_top_beam = 1024

set this bit on train_type if beam is to be trained only on the first element of the beam (faster but less accurate)

static const int Skip_codebook_tables = 2048

set this bit to not autmatically compute the codebook tables after training