k-NN vector quantization
By default, the k-NN plugin supports the indexing and querying of vectors of type float, where each dimension of the vector occupies 4 bytes of memory. For use cases that require ingestion on a large scale, keeping float vectors can be expensive because Lucenia needs to construct, load, save, and search graphs (for native nmslib and faiss engines). To reduce the memory footprint, you can use vector quantization.
Lucenia supports many varieties of quantization. In general, the level of quantization will provide a trade-off between the accuracy of the nearest neighbor search and the size of the memory footprint consumed by the vector search. The supported types include byte vectors, 16-bit scalar quantization, product quantization (PQ), and Lucene binary quantization (BBQ).
Lucene byte vector
Starting with k-NN plugin version 2.9, you can use byte vectors with the lucene engine in order to reduce the amount of required memory. This requires quantizing the vectors outside of Lucenia before ingesting them into an Lucenia index. For more information, see Lucene byte vector.
Faiss 16-bit scalar quantization
Starting with version 2.13, the k-NN plugin supports performing scalar quantization for the Faiss engine within Lucenia. Within the Faiss engine, a scalar quantizer (SQfp16) performs the conversion between 32-bit and 16-bit vectors. At ingestion time, when you upload 32-bit floating-point vectors to Lucenia, SQfp16 quantizes them into 16-bit floating-point vectors and stores the quantized vectors in a k-NN index.
At search time, SQfp16 decodes the vector values back into 32-bit floating-point values for distance computation. The SQfp16 quantization can decrease the memory footprint by a factor of 2. Additionally, it leads to a minimal loss in recall when differences between vector values are large compared to the error introduced by eliminating their two least significant bits. When used with SIMD optimization, SQfp16 quantization can also significantly reduce search latencies and improve indexing throughput.
SIMD optimization is not supported on Windows. Using Faiss scalar quantization on Windows can lead to a significant drop in performance, including decreased indexing throughput and increased search latencies.
Using Faiss scalar quantization
To use Faiss scalar quantization, set the k-NN vector field's method.parameters.encoder.name to sq when creating a k-NN index:
PUT /test-index
{
"settings": {
"index": {
"knn": true,
"knn.algo_param.ef_search": 100
}
},
"mappings": {
"properties": {
"my_vector1": {
"type": "knn_vector",
"dimension": 3,
"method": {
"name": "hnsw",
"engine": "faiss",
"space_type": "l2",
"parameters": {
"encoder": {
"name": "sq",
},
"ef_construction": 256,
"m": 8
}
}
}
}
}
}
Optionally, you can specify the parameters in method.parameters.encoder. For more information about encoder object parameters, see SQ parameters.
The fp16 encoder converts 32-bit vectors into their 16-bit counterparts. For this encoder type, the vector values must be in the [-65504.0, 65504.0] range. To define how to handle out-of-range values, the preceding request specifies the clip parameter. By default, this parameter is false, and any vectors containing out-of-range values are rejected.
When clip is set to true (as in the preceding request), out-of-range vector values are rounded up or down so that they are in the supported range. For example, if the original 32-bit vector is [65510.82, -65504.1], the vector will be indexed as a 16-bit vector [65504.0, -65504.0].
We recommend setting clip to true only if very few elements lie outside of the supported range. Rounding the values may cause a drop in recall.
The following example method definition specifies the Faiss SQfp16 encoder, which rejects any indexing request that contains out-of-range vector values (because the clip parameter is false by default):
PUT /test-index
{
"settings": {
"index": {
"knn": true,
"knn.algo_param.ef_search": 100
}
},
"mappings": {
"properties": {
"my_vector1": {
"type": "knn_vector",
"dimension": 3,
"method": {
"name": "hnsw",
"engine": "faiss",
"space_type": "l2",
"parameters": {
"encoder": {
"name": "sq",
"parameters": {
"type": "fp16"
}
},
"ef_construction": 256,
"m": 8
}
}
}
}
}
}
During ingestion, make sure each vector dimension is in the supported range ([-65504.0, 65504.0]).
PUT test-index/_doc/1
{
"my_vector1": [-65504.0, 65503.845, 55.82]
}
During querying, the query vector has no range limitation:
GET test-index/_search
{
"size": 2,
"query": {
"knn": {
"my_vector1": {
"vector": [265436.876, -120906.256, 99.84],
"k": 2
}
}
}
}
Memory estimation
In the best-case scenario, 16-bit vectors produced by the Faiss SQfp16 quantizer require 50% of the memory that 32-bit vectors require.
HNSW memory estimation
The memory required for Hierarchical Navigable Small Worlds (HNSW) is estimated to be 1.1 * (2 * dimension + 8 * M) bytes/vector.
As an example, assume that you have 1 million vectors with a dimension of 256 and M of 16. The memory requirement can be estimated as follows:
1.1 * (2 * 256 + 8 * 16) * 1,000,000 ~= 0.656 GB
IVF memory estimation
The memory required for IVF is estimated to be 1.1 * (((2 * dimension) * num_vectors) + (4 * nlist * d)) bytes/vector.
As an example, assume that you have 1 million vectors with a dimension of 256 and nlist of 128. The memory requirement can be estimated as follows:
1.1 * (((2 * 256) * 1,000,000) + (4 * 128 * 256)) ~= 0.525 GB
Faiss product quantization
PQ is a technique used to represent a vector in a configurable amount of bits. In general, it can be used to achieve a higher level of compression as compared to byte or scalar quantization. PQ works by separating vectors into m subvectors and encoding each subvector with code_size bits. Thus, the total amount of memory for the vector is m*code_size bits, plus overhead. For details about the parameters, see PQ parameters. PQ is only supported for the Faiss engine and can be used with either the HNSW or IVF approximate nearest neighbor (ANN) algorithms.
Using Faiss product quantization
To minimize loss in accuracy, PQ requires a training step that builds a model based on the distribution of the data that will be searched.
The product quantizer is trained by running k-means clustering on a set of training vectors for each subvector space and extracts the centroids to be used for encoding. The training vectors can be either a subset of the vectors to be ingested or vectors that have the same distribution and dimension as the vectors to be ingested.
In OpenSeLuceniaarch, the training vectors need to be present in an index. In general, the amount of training data will depend on which ANN algorithm is used and how much data will be stored in the index. For IVF-based indexes, a recommended number of training vectors is max(1000*nlist, 2^code_size * 1000). For HNSW-based indexes, a recommended number is 2^code_size*1000. See the Faiss documentation for more information about the methodology used to calculate these figures.
For PQ, both m and code_size need to be selected. m determines the number of subvectors into which vectors should be split for separate encoding. Consequently, the dimension needs to be divisible by m. code_size determines the number of bits used to encode each subvector. In general, we recommend a setting of code_size = 8 and then tuning m to get the desired trade-off between memory footprint and recall.
For an example of setting up an index with PQ, see the Building a k-NN index from a model tutorial.
Memory estimation
While PQ is meant to represent individual vectors with m*code_size bits, in reality, the indexes consume more space. This is mainly due to the overhead of storing certain code tables and auxiliary data structures.
Some of the memory formulas depend on the number of segments present. This is not typically known beforehand, but a recommended default value is 300.
HNSW memory estimation
The memory required for HNSW with PQ is estimated to be 1.1*(((pq_code_size / 8) * pq_m + 24 + 8 * hnsw_m) * num_vectors + num_segments * (2^pq_code_size * 4 * d)) bytes.
As an example, assume that you have 1 million vectors with a dimension of 256, hnsw_m of 16, pq_m of 32, pq_code_size of 8, and 100 segments. The memory requirement can be estimated as follows:
1.1*((8 / 8 * 32 + 24 + 8 * 16) * 1000000 + 100 * (2^8 * 4 * 256)) ~= 0.215 GB
IVF memory estimation
The memory required for IVF with PQ is estimated to be 1.1*(((pq_code_size / 8) * pq_m + 24) * num_vectors + num_segments * (2^code_size * 4 * d + 4 * ivf_nlist * d)) bytes.
For example, assume that you have 1 million vectors with a dimension of 256, ivf_nlist of 512, pq_m of 32, pq_code_size of 8, and 100 segments. The memory requirement can be estimated as follows:
1.1*((8 / 8 * 64 + 24) * 1000000 + 100 * (2^8 * 4 * 256 + 4 * 512 * 256)) ~= 0.171 GB
Binary quantization
Introduced 0.13.0Lucene BBQ stores one bit per dimension for the HNSW graph walk and keeps the original float32 vectors for rescore. The 32× figure is that graph-walk representation. On-disk size is the quantized graph plus the float32 vectors.
It is the lucene engine, hnsw method, and float data type. Supported spaces are l2,
cosinesimil, and innerproduct. The encoder takes no parameters and needs no training. Ingest is
a float array of length dimension; quantization runs inside Lucenia at flush. Graph connectivity
is Lucene's default (M = 16).
Select it with method.engine: "lucene" and method.parameters.encoder.name: "bbq":
PUT /my-index
{
"settings": {
"index": { "knn": true }
},
"mappings": {
"properties": {
"my_vector": {
"type": "knn_vector",
"dimension": 768,
"method": {
"name": "hnsw",
"engine": "lucene",
"space_type": "l2",
"parameters": {
"encoder": { "name": "bbq" }
}
}
}
}
}
}
compression_level: "32x" with method.engine: "lucene" selects the same encoder. Set either
spelling, or both when they agree. If both are set, compression_level must be "32x". A mismatch
is refused. encoder.name: "bbq" with compression_level omitted is 32x.
PUT /my-index
{
"settings": {
"index": { "knn": true }
},
"mappings": {
"properties": {
"my_vector": {
"type": "knn_vector",
"dimension": 768,
"compression_level": "32x",
"method": {
"name": "hnsw",
"engine": "lucene"
}
}
}
}
}
On the Lucene engine, mode: "on_disk" with no compression_level uses 4x scalar quantization
(7-bit SQ). compression_level: "32x" without method.engine: "lucene" is not Lucene BBQ.
PUT /my-index/_doc/1
{
"my_vector": [ /* 768 floats */ ]
}
Memory and disk sizing
Float32 HNSW memory is estimated as 1.1 * (4 * dimension + 8 * M) bytes per vector (see
HNSW memory estimation).
The 1.1 factor is the overhead convention used throughout these k-NN sizing formulas.
BBQ packed length is ceil(dimension / 8) bytes. .bbqd stores those bits plus 12 bytes per
vector (three float corrections). Estimate the graph page-cache working set (that .bbqd
payload + HNSW neighbor lists) as:
1.1 * (ceil(dimension / 8) + 12 + 8 * M) bytes/vector
Estimate on-disk size (that graph plus float32 rescore vectors) as:
1.1 * (ceil(dimension / 8) + 12 + 8 * M) + 4 * dimension bytes/vector
After the field is decoded, the JVM heap holds 16 bytes per vector (computed setBits and
those three floats); the packed bits stay mapped. With the default hybridfs store, Lucene
maps .bbqd, .bbqm, .vex, and .vec through mmap into the OS page cache. See
mmap file I/O.
Worked example
50 million vectors, dimension 768, M = 16:
Graph page-cache working set: 1.1 * (ceil(768 / 8) + 12 + 8 * 16) * 50_000_000
= 1.1 * 236 * 50_000_000
≈ 12.98 GB
On-disk: (1.1 * 236 + 4 * 768) * 50_000_000
= 3331.6 * 50_000_000
≈ 166.58 GB
Rescore
A BBQ field always runs a rescore pass. Oversample factor:
| Query | Oversample factor |
|---|---|
rescore omitted | 10 |
"rescore": {} | 1.0 |
"rescore": { "oversample_factor": N } | N |
GET /my-index/_search
{
"size": 10,
"query": {
"knn": {
"my_vector": {
"vector": [ /* 768 floats */ ],
"k": 10,
"rescore": { "oversample_factor": 10 }
}
}
}
}
First-pass candidates:
luceneK = max(k, method_parameters.ef_search) if the query sets ef_search, else k
candidates = min(10000, max(luceneK, ceil(k × oversample_factor)))
oversample_factor must be in [1.0, 10000]. A factor outside that range is refused. The walk is
capped at 10,000 candidates. A BBQ query that omits rescore (k: 10, no query ef_search) asks
for 100 candidates. The index setting knn.algo_param.ef_search is not used on Lucene.
Measured recall@10 on 960-dimensional GIST (20k documents), against plain HNSW at 0.993:
| Oversampling | recall@10 |
|---|---|
| 5x | 0.860 |
| 10x (field default) | 0.953 |
| 20x | 0.987 |
| 40x | 1.000 |
Vectors are centred, rotated, and packed to one sign bit per dimension. Rotation uses blocked
Hadamard transforms so packed length stays ceil(dimension / 8). The HNSW graph is built on the
original float32 vectors and scored on the quantized bits at search.
Rescoring quantized results
Quantization trades accuracy for memory. Rescoring buys the accuracy back, and for a
binary-quantized field it is what makes the ranking exact-scored rather than
decided on one bit per dimension: the graph walk is run
wide over the quantized vectors, and the candidates it returns are then scored again against the
full-precision vectors before the top k is chosen.
A rescore is also what makes early termination safe. Stopping a walk early gives up its tail, and
only the rescore's wider first pass keeps that tail reachable — which is why
index.knn.hnsw_early_termination.enabled
costs recall on a field that has no rescore behind it, and earns its keep on one that does.
Add a rescore block to the knn query:
GET /my-index/_search
{
"query": {
"knn": {
"my_vector": {
"vector": [1.5, 2.5, 3.5],
"k": 10,
"rescore": {
"oversample_factor": 2.0
}
}
}
}
}
Parameters
| Parameter | Type | Required/Optional | Description |
|---|---|---|---|
oversample_factor | Float | Optional | How many more candidates the first pass collects than the k finally returned. Default is 1.0 when rescore is present without a factor ("rescore": {}). Valid range 1.0 to 10000. On a BBQ field, omitting rescore uses 10. See Binary quantization. |
How many candidates a factor actually asks for
The factor multiplies k, and ef_search remains the floor it was always meant to be. The result
is bounded at 10,000 candidates:
candidates = min(10000, max(ef_search_floor, ceil(k × oversample_factor)))
So ef_search still guarantees a minimum walk width — it is simply no longer multiplied by the
oversample factor on top of that.
Changed in 0.13.0. The oversample factor used to be multiplied into a candidate count that
already carried ef_search, so the two widenings compounded: at k: 10 with ef_search: 100, an
oversample of 80 asked the graph for 8,000 candidates rather than 800 — a factor of ef_search / k
on every rescored query. Nothing looked wrong, because the results were correct and the only symptom
was the cost. A graph walk pays for candidates in nodes visited, and that is steeply superlinear.
The factor now multiplies k alone, with ef_search kept as a floor rather than a multiplier.
A query tuned against the old behaviour now asks for far fewer candidates than it used to, so
re-check recall on any saved oversample_factor after upgrading.
Also changed in 0.13.0. The upper bound on oversample_factor was raised from 100 to 10,000.
The old bound rejected operating points that were comfortably inside the candidate ceiling — at
k: 10 a factor of 160 asks for 1,600 candidates, well under 10,000, and was refused with a 400.
That removed the top of the recall curve. A factor above 10,000 is refused. A factor that computes
more than 10,000 candidates is accepted and the walk uses 10,000.
When the factor is chosen for you
If shard-level rescoring is turned off with
index.knn.disk.vector.shard_level_rescoring_disabled
on native-engine disk-based vector search, the factor is selected from the field's dimension.
Lucene BBQ uses the Rescore table under Binary quantization.
| Dimension | Oversample factor |
|---|---|
| 1000 and above | 1.0 — no oversampling |
| 768 to 999 | 2.0 |
| Below 768 | 3.0 |
In that path the candidate count is also floored at 100, so a small k still collects enough to
rescore against.