IVF-SQ#
2026-09-01
11 min read time
The IVF-SQ method is an ANN algorithm. Like IVF-Flat, IVF-SQ splits the points into a number of clusters (also specified by a parameter called n_lists) and searches the closest clusters to compute the nearest neighbors (also specified by a parameter called n_probes), but it shrinks the sizes of the vectors using scalar quantization.
#include <cuvs/neighbors/ivf_sq.hpp>
namespace cuvs::neighbors::ivf_sq
Index build parameters#
-
static constexpr uint32_t kIndexGroupSize = 64
-
struct index_params : public cuvs::neighbors::index_params#
- #include <ivf_sq.hpp>
IVF-SQ index build parameters.
IVF-SQ currently uses 8-bit scalar quantization, storing one
uint8_tcode per vector dimension.Public Members
-
uint32_t n_lists = 1024#
The number of inverted lists (clusters)
-
uint32_t kmeans_n_iters = 20#
The number of iterations searching for kmeans centers (index building).
-
uint32_t max_train_points_per_cluster = 256#
The number of data vectors (per cluster) to use during iterative kmeans building.
-
bool conservative_memory_allocation = false#
By default, the algorithm allocates more space than necessary for individual clusters (
list_data). This allows to amortize the cost of memory allocation and reduce the number of data copies during repeated calls toextend(extending the database).The alternative is the conservative allocation behavior; when enabled, the algorithm always allocates the minimum amount of memory required to store the given number of records. Set this flag to
trueif you prefer to use as little GPU memory for the database as possible.
-
bool add_data_on_build = true#
Whether to add the dataset content to the index, i.e.:
truemeans the index is filled with the dataset vectors and ready to search after callingbuild.falsemeansbuildonly trains the underlying model (e.g. quantizer or clustering), but the index is left empty; you’d need to callextendon the index afterwards to populate it.
-
uint32_t n_lists = 1024#
Index search parameters#
Index#
-
template<typename CodeT>
struct index : public cuvs::neighbors::index# - #include <ivf_sq.hpp>
IVF-SQ index.
In the IVF-SQ index, a database vector is first assigned to the nearest cluster center using an inverted file (IVF) structure, and then compressed using scalar quantization (SQ).
Scalar quantization independently maps each dimension of the per-cluster residual (the input vector minus its assigned centroid) to a fixed-width integer code. For 8-bit quantization (
uint8_t), each residual component is linearly mapped to an integer in [0, 255] using learned per-dimension minimum (sq_vmin) and step-size (sq_delta) values.For a vector component
x_i, centroid componentcentroid_i, residual minimumvmin_i, and quantization stepdelta_i, the stored code is:$$code_i = clamp(round((x_i - centroid_i - vmin_i) / delta_i), 0, 255)$$
The corresponding reconstructed component is:
$$x_i \approx centroid_i + vmin_i + code_i \cdot delta_i$$
This provides a compact representation (1 byte per dimension) while preserving the relative distances between vectors with high fidelity, offering a good trade-off between index size, search speed, and recall compared to flat (uncompressed) and product-quantized (PQ) representations.
Note:
CodeTis the storage type for scalar-quantized residual codes in the inverted lists, not the input dataset type. The public build and search APIs acceptfloatandhalfinput vectors, then store the quantized residual components asCodeTinside the index. Currently, IVF-SQ supports onlyuint8_tcodes, so useCodeT = uint8_t. Each code uses the full 8-bit range [0, 255].- Template Parameters:
CodeT – SQ code storage type. Must be
uint8_tin the current implementation.
Index build#
- auto build(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::index_params &index_params,
- raft::device_matrix_view<const float, int64_t, raft::row_major> dataset
Build the index from the dataset for efficient search.
NB: Currently, the following distance metrics are supported:
L2Expanded
L2SqrtExpanded
InnerProduct
CosineExpanded
Usage example:
using namespace cuvs::neighbors; // use default index parameters ivf_sq::index_params index_params; // create and fill the index from a [N, D] dataset auto index = ivf_sq::build(handle, index_params, dataset);
- Parameters:
handle – [in]
index_params – configure the index building
dataset – [in] a device pointer to a row-major matrix [n_rows, dim]
- Returns:
the constructed ivf-sq index
- auto build(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::index_params &index_params,
- raft::device_matrix_view<const half, int64_t, raft::row_major> dataset
Build the index from the dataset for efficient search.
Usage example:
using namespace cuvs::neighbors; // use default index parameters ivf_sq::index_params index_params; // create and fill the index from a [N, D] dataset auto index = ivf_sq::build(handle, index_params, dataset);
- Parameters:
handle – [in]
index_params – configure the index building
dataset – [in] a device pointer to a row-major matrix [n_rows, dim]
- Returns:
the constructed ivf-sq index
- auto build(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::index_params &index_params,
- raft::host_matrix_view<const float, int64_t, raft::row_major> dataset
Build the index from the dataset for efficient search.
Usage example:
using namespace cuvs::neighbors; // use default index parameters ivf_sq::index_params index_params; // create and fill the index from a [N, D] dataset auto index = ivf_sq::build(handle, index_params, dataset);
- Parameters:
handle – [in]
index_params – configure the index building
dataset – [in] a host pointer to a row-major matrix [n_rows, dim]
- Returns:
the constructed ivf-sq index
- auto build(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::index_params &index_params,
- raft::host_matrix_view<const half, int64_t, raft::row_major> dataset
Build the index from the dataset for efficient search.
Usage example:
using namespace cuvs::neighbors; // use default index parameters ivf_sq::index_params index_params; // create and fill the index from a [N, D] dataset auto index = ivf_sq::build(handle, index_params, dataset);
- Parameters:
handle – [in]
index_params – configure the index building
dataset – [in] a host pointer to a row-major matrix [n_rows, dim]
- Returns:
the constructed ivf-sq index
Index extend#
- void extend(
- raft::resources const &handle,
- raft::device_matrix_view<const float, int64_t, raft::row_major> new_vectors,
- std::optional<raft::device_vector_view<const int64_t, int64_t>> new_indices,
- cuvs::neighbors::ivf_sq::index<uint8_t> *idx
Extend the index with the new data in-place.
Usage example:
using namespace cuvs::neighbors; ivf_sq::index_params index_params; index_params.add_data_on_build = false; // don't populate index on build // train the index from a [N, D] dataset auto index_empty = ivf_sq::build(handle, index_params, dataset); // fill the index with the data std::optional<raft::device_vector_view<const int64_t, int64_t>> no_op = std::nullopt; ivf_sq::extend(handle, new_vectors, no_op, &index_empty);
- Parameters:
handle – [in]
new_vectors – [in] a device matrix view to a row-major matrix [n_rows, idx.dim()]
new_indices – [in] a device vector view to a vector of indices [n_rows]. If the original index is empty (
idx.size() == 0), you can passstd::nullopthere to imply a continuous range[0...n_rows).idx – [inout] pointer to ivf_sq::index
- void extend(
- raft::resources const &handle,
- raft::device_matrix_view<const half, int64_t, raft::row_major> new_vectors,
- std::optional<raft::device_vector_view<const int64_t, int64_t>> new_indices,
- cuvs::neighbors::ivf_sq::index<uint8_t> *idx
Extend the index with the new data in-place.
Usage example:
using namespace cuvs::neighbors; ivf_sq::index_params index_params; index_params.add_data_on_build = false; // don't populate index on build // train the index from a [N, D] dataset auto index_empty = ivf_sq::build(handle, index_params, dataset); // fill the index with the data std::optional<raft::device_vector_view<const int64_t, int64_t>> no_op = std::nullopt; ivf_sq::extend(handle, new_vectors, no_op, &index_empty);
- Parameters:
handle – [in]
new_vectors – [in] a device matrix view to a row-major matrix [n_rows, idx.dim()]
new_indices – [in] a device vector view to a vector of indices [n_rows]. If the original index is empty (
idx.size() == 0), you can passstd::nullopthere to imply a continuous range[0...n_rows).idx – [inout] pointer to ivf_sq::index
- void extend(
- raft::resources const &handle,
- raft::host_matrix_view<const float, int64_t, raft::row_major> new_vectors,
- std::optional<raft::host_vector_view<const int64_t, int64_t>> new_indices,
- cuvs::neighbors::ivf_sq::index<uint8_t> *idx
Extend the index with the new data in-place.
Usage example:
using namespace cuvs::neighbors; ivf_sq::index_params index_params; index_params.add_data_on_build = false; // don't populate index on build // train the index from a [N, D] dataset auto index_empty = ivf_sq::build(handle, index_params, dataset); // fill the index with the data std::optional<raft::host_vector_view<const int64_t, int64_t>> no_op = std::nullopt; ivf_sq::extend(handle, new_vectors, no_op, &index_empty);
- Parameters:
handle – [in]
new_vectors – [in] a host matrix view to a row-major matrix [n_rows, idx.dim()]
new_indices – [in] a host vector view to a vector of indices [n_rows]. If the original index is empty (
idx.size() == 0), you can passstd::nullopthere to imply a continuous range[0...n_rows).idx – [inout] pointer to ivf_sq::index
- void extend(
- raft::resources const &handle,
- raft::host_matrix_view<const half, int64_t, raft::row_major> new_vectors,
- std::optional<raft::host_vector_view<const int64_t, int64_t>> new_indices,
- cuvs::neighbors::ivf_sq::index<uint8_t> *idx
Extend the index with the new data in-place.
Usage example:
using namespace cuvs::neighbors; ivf_sq::index_params index_params; index_params.add_data_on_build = false; // don't populate index on build // train the index from a [N, D] dataset auto index_empty = ivf_sq::build(handle, index_params, dataset); // fill the index with the data std::optional<raft::host_vector_view<const int64_t, int64_t>> no_op = std::nullopt; ivf_sq::extend(handle, new_vectors, no_op, &index_empty);
- Parameters:
handle – [in]
new_vectors – [in] a host matrix view to a row-major matrix [n_rows, idx.dim()]
new_indices – [in] a host vector view to a vector of indices [n_rows]. If the original index is empty (
idx.size() == 0), you can passstd::nullopthere to imply a continuous range[0...n_rows).idx – [inout] pointer to ivf_sq::index
Index search#
- void search(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::search_params ¶ms,
- const cuvs::neighbors::ivf_sq::index<uint8_t> &index,
- raft::device_matrix_view<const float, int64_t, raft::row_major> queries,
- raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,
- raft::device_matrix_view<float, int64_t, raft::row_major> distances,
- const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{}
Search ANN using the constructed index.
See the ivf_sq::build documentation for a usage example.
Note, this function requires a temporary buffer to store intermediate results between cuda kernel calls, which may lead to undesirable allocations and slowdown. To alleviate the problem, you can pass a pool memory resource or a large enough pre-allocated memory resource to reduce or eliminate entirely allocations happening within
search. The exact size of the temporary buffer depends on multiple factors and is an implementation detail. However, you can safely specify a small initial size for the memory pool, so that only a few allocations happen to grow it during the first invocations of thesearch.using namespace cuvs::neighbors; // use default search parameters ivf_sq::search_params search_params; // Use the same allocator across multiple searches to reduce the number of // cuda memory allocations ivf_sq::search(handle, search_params, index, queries1, out_inds1, out_dists1); ivf_sq::search(handle, search_params, index, queries2, out_inds2, out_dists2); ivf_sq::search(handle, search_params, index, queries3, out_inds3, out_dists3);
- Parameters:
handle – [in]
params – [in] configure the search
index – [in] ivf-sq constructed index
queries – [in] raft::device_matrix_view to a row-major matrix [n_queries, index->dim()]
neighbors – [out] raft::device_matrix_view to the indices of the neighbors in the source dataset [n_queries, k]
distances – [out] raft::device_matrix_view to the distances to the selected neighbors [n_queries, k]
sample_filter – [in] an optional device filter function object that greenlights samples for a given query. (none_sample_filter for no filtering)
- void search(
- raft::resources const &handle,
- const cuvs::neighbors::ivf_sq::search_params ¶ms,
- const cuvs::neighbors::ivf_sq::index<uint8_t> &index,
- raft::device_matrix_view<const half, int64_t, raft::row_major> queries,
- raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,
- raft::device_matrix_view<float, int64_t, raft::row_major> distances,
- const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{}
Search ANN using the constructed index with half-precision queries.
See the ivf_sq::build documentation for a usage example.
Note, this function requires a temporary buffer to store intermediate results between cuda kernel calls, which may lead to undesirable allocations and slowdown. To alleviate the problem, you can pass a pool memory resource or a large enough pre-allocated memory resource to reduce or eliminate entirely allocations happening within
search.using namespace cuvs::neighbors; // use default search parameters ivf_sq::search_params search_params; // Use the same allocator across multiple searches to reduce the number of // cuda memory allocations ivf_sq::search(handle, search_params, index, queries1, out_inds1, out_dists1); ivf_sq::search(handle, search_params, index, queries2, out_inds2, out_dists2); ivf_sq::search(handle, search_params, index, queries3, out_inds3, out_dists3);
- Parameters:
handle – [in]
params – [in] configure the search
index – [in] ivf-sq constructed index
queries – [in] raft::device_matrix_view to a row-major matrix [n_queries, index->dim()]
neighbors – [out] raft::device_matrix_view to the indices of the neighbors in the source dataset [n_queries, k]
distances – [out] raft::device_matrix_view to the distances to the selected neighbors [n_queries, k]
sample_filter – [in] an optional device filter function object that greenlights samples for a given query. (none_sample_filter for no filtering)
Index serialize#
- void serialize(
- raft::resources const &handle,
- const std::string &filename,
- const cuvs::neighbors::ivf_sq::index<uint8_t> &index
Save the index to file.
Experimental, both the API and the serialization format are subject to change.
#include <raft/core/resources.hpp> #include <cuvs/neighbors/ivf_sq.hpp> raft::resources handle; // create a string with a filepath std::string filename("/path/to/index"); // create an index with `auto index = ivf_sq::build(...);` cuvs::neighbors::ivf_sq::serialize(handle, filename, index);
- Parameters:
handle – [in] the raft handle
filename – [in] the file name for saving the index
index – [in] IVF-SQ index
- void deserialize(
- raft::resources const &handle,
- const std::string &filename,
- cuvs::neighbors::ivf_sq::index<uint8_t> *index
Load index from file.
Experimental, both the API and the serialization format are subject to change.
#include <raft/core/resources.hpp> #include <cuvs/neighbors/ivf_sq.hpp> raft::resources handle; // create a string with a filepath std::string filename("/path/to/index"); // create an empty index with `ivf_sq::index<uint8_t> index(handle);` cuvs::neighbors::ivf_sq::deserialize(handle, filename, &index);
- Parameters:
handle – [in] the raft handle
filename – [in] the name of the file that stores the index
index – [out] IVF-SQ index