Skip to content

The index factory

Matthijs Douze edited this page Sep 2, 2024 · 35 revisions

The index_factory function interprets a string to produce a composite Faiss index. The string is a comma-separated list of components. It is intended to facilitate the construction of index structures, especially if they are nested. The index_factory argument typically includes a preprocessing component, and inverted file and an encoding component. This page summarizes the index_factory components and arguments.

A formal definition of the factory strings in Backus–Naur form can be found here: factory_string.bnf.

Examples:

index = index_factory(128, "PCA80,Flat"): produces an index for 128D vectors that reduces them to 80D by PCA then does exhaustive search.

index = index_factory(128, "OPQ16_64,IMI2x8,PQ8+16"): takes 128D vectors, applies an OPQ transform to 16 blocks in 64D, uses an inverted multi-index of 2x8 bits (= 65536 inverted lists), and refines with a PQ of size 8, then 16 bytes.

The numbers we indicate are examples, and d is the input dimension.

Prefixes

String Class name Comments
IDMap IndexIDMap Used to enable add_with_ids on indexes that do not support it, mainly the flat indexes.
IDMap2 IndexIDMap2 Same, but in addition supports reconstruct.

Vector transforms

These strings map to VectorTransform objects that can be applied on vectors before they are indexed

String Class name Output dimension Comments
PCA64, PCAR64, PCAW64, PCAWR64 PCAMatrix 64 Applies a PCA transform to reduce the number of dimensions. W = follow with whitening, R = follow with random rotation. The PCAR is especially useful as pre-processing with a Flat or scalar quantizer.
OPQ16, OPQ16_64 OPQMatrix d, 64 Rotates the vectors so that they can be encoded efficiently by a PQ to 16 subvectors. 64 is the output dimension, because it is often beneficial to also reduce the number of dimensions. If the output dimensions not specified, it is the same as the input dimension.
RR64 RandomRotation 64 Random rotation on the input data. The dimension can increase or decrease wrt. the input
L2norm NormalizationTransform d L2-normalizes the input vectors
ITQ256, ITQ ITQMatrix 256, d Applies an ITQ transformation to the input vectors, see "Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval" by Gong et al.. This is useful when the vectors are encoded with LSH.
Pad128 RemapDimensionsTransform 128 Pad the input vectors with 0s to 128 dim

Non-exhaustive search components

Inverted file indexes

Inverted files all inherit from IndexIVF. The non-exhaustive component specifies what the coarse quantizer (first parameter of the constructor) should be. The factory strings start with IVF or IMI, followed systematically by a comma and an encoding (see below)

String Quantizer class Number of centroids Comments
IVF4096 IndexFlatL2 or IndexFlatIP 4096 Constructs one of the IndexIVF variants, with a flat quantizer.
IMI2x9 MultiIndexQuantizer 2^(2 * 9) = 262144 Constructs an IVF with many more centroids, possibly less balanced.
IVF65536_HNSW32 IndexHNSWFlat 65536 The quantizer is trained as a flat index but indexed with a HNSW. This makes quantization a lot faster
IVF65536(PQ16x4) arbitrary 65536 Use the string in parenthesis to construct the coarse quantizer.
IVF1024(RCQ2x5) ResidualCoarseQuantizer 1024 This is a special case of the previous. The coarse quantizer is a residual quantizer.

Graph-based indexes

HNSW and NSG are graph based indexes. They inherit from IndexHNSW and IndexNSG. Both rely on a flat storage IndexFlatCodes that stores the actual vectors.

String Storage class Comment
HNSW32, HNSW IndexFlatL2 Arguably the most useful HNSW variant, because when the links are stored, it does not make much sense to compress the vectors. 32 (the number of links per vertex) is the default and can be omitted.
HNSW32_SQ8 IndexScalarQuantizer SQ8 scalar quantizer
HNSW32_PQ12 IndexPQ PQ12x8 index
HNSW32_16384+PQ12 Index2Layer 1st layer is a flat index, the PQ encodes the residual of the quantizer
HNSW32_2x10+PQ12 Index2Layer 1st layer is an IMI index, the PQ encodes the residual of the quantizer

The NSG variants are the same, except that HNSW is replaced with NSG.

Memory overheads

Memory overheads:

  • In HNSW32, 32 encodes the number of links, the lowest level that uses most memory has 32 * 2 links, or 32 * 2 * 4 = 256 bytes per vector. So the overhead is quite significant.

  • In NSG32, 32 encodes the number of links per vertex directly so 32 means 32 * 4 = 128 bytes per vector.

  • For the IVF and IMI indexes, the main overhead is that the 64-bit id of each vector is stored as well (ie. an overhead of 8 bytes per vector)

Encodings

String Class name (Flat/IVF) code size (bytes) Comments
Flat IndexFlat, IndexIVFFlat 4 * d The vectors are stored as is, without any encoding
PQ16, PQ16x12 IndexPQ, IndexIVFPQ 16, ceil(16 * 12 / 8) Uses Product Quantization codes with 16 codes of 12 bits each. When the number of bits is omitted, it is set to 8. With suffix "np" does not train the Polysemous permutation, which can be slow.
PQ28x4fs, PQ28x4fsr, PQ28x4fs_64 IndexPQFastScan, IndexIVFPQFastScan 28 / 2 Same as PQ above, but uses "fast scan" version of the PQ that relies on SIMD instructions for distance computations. Supports only nbits=4 for now. The suffix _64 indicates the bbs factor used (must be a multiple of 32). The suffix fsr (only for IVF) indicates that the vectors should be encoded by residual (slower, more accurate)
SQ4, SQ8, SQ6, SQfp16 IndexScalar Quantizer, IndexIVF ScalarQuantizer 4*d/8, d, 6*d/8, d*2 Scalar quantizer encoding
Residual128, Residual3x10 Index2Layer ceil(log2(128) / 8), ceil(3*10 / 8) Residual encoding. Quantizes the vectors into 128 centroids or 3x10 MI centroids. Should be followed by PQ or SQ to actually encode the residual. Only for use as a codec.
RQ1x16_6x8 IndexResidualQuantizer (16 + 6*8) / 8 Residual quantizer codec. The vector is first encoded with a 2^16-centroid quantizer, then the residuals are refined in 6 stages with 256 centroids each.
RQ5x8_Nqint8 IndexResidualQuantizer 5+1 Residual quantizer index with norms quantized to 8 bits (other options are Nqint4 and Nfloat)
LSQ5x8_Nqint8 IndexLocalSearchQuantizer 5+1 Same, with local search quantizer
PRQ16x4x8 IndexProductResidualQuantizer 16*4 The vector is sliced into 16 sub-vectors and each sub-vector is encoded into a residual quantizer of size 4x8.
PLSQ16x4x8 IndexProductResidualQuantizer 16*4 Same, with a LSQ quantizer
ZnLattice3x10_6 IndexLattice ceil((3*log2(C(d/3, 10)) + 6) / 8) Lattice codec. The vector is first split into 3 segments, then each segment is encoded as its norm (6 bits) and as a direction on the unit sphere in dimension d/3, quantized by the Zn lattice of radius^2 = 10. C(dim, r2) is the number of points on the sphere of radius sqrt(r2) that have integer coordinates (see here for more details, and this Gist on how to set the radius).
LSH, LSHrt, LSHr, LSHt IndexLSH ceil(d / 8) Binarizes the vectors by thresholding them. At search time, the query vectors are also binarized (symmetric search). Suffix r = rotate vectors prior to binarization, t = train thresholds to balance 0s and 1s. Useful in combination with ITQ.
ITQ90,SH2.5 IndexIVFSpectralHash ceil(90 / 8) Only an IVF version. Transforms the vector to encode with ITQ (PCA and PCAR also supported), reducing to 90 dim. Then encode each component, with [0, 2.5] giving bit 0 and [2.5, 5] giving bit 1, modulo 5. SH2.5g uses a global threshold, SH2.5c just uses the centroid as threshold. SH without an argument just keeps the sign of the vector components as the bit.

Suffixes

String Storage class Comment
RFlat IndexRefineFlat Re-order the search results with exact distance computations
Refine(PQ25x12) IndexRefine Same, but the refine index can be any index.

Example

Let's walk trough one of the most complex factory strings OPQ16_64,IVF262144(IVF512,PQ32x4fs,RFlat),PQ16x4fsr,Refine(OPQ56_112,PQ56):

  • OPQ16_64: OPQ pre-processing

  • IVF262144(IVF512,PQ32x4fs,RFlat): IVF index with 262k centroids. The coarse quantizer is an IVFPQFastScan index with an additional refinement step.

  • PQ16x4fsr: the vectors are encoded with PQ fast-scan (which takes 16 * 4 / 8 = 8 bytes per vector)

  • Refine(OPQ56_112,PQ56): the re-ranking index is a PQ with OPQ pre-processing that occupies 56 bytes.

Clone this wiki locally