Clustering¶
RaBitQ Library provides two implementations of Lloyd's k-means. Both compute centroid means from the original float32 data, accumulate in float64, and require no external clustering package. Choose the class explicitly; neither switches algorithms based on the cluster count.
For installation, see Quick start.
You do not need these classes to build an index: IvfIndex.train and
HnswIndex.train, or the first add, run them for you (see
IVF-RaBitQ training). Use them
directly to inspect assignments, reuse one clustering across several indexes,
or pass the result to set_centroids and add(..., cluster_ids=...). The
indexes train with their own defaults, including sampling at most 256 vectors
per centroid; the classes below default to training on every vector.
Choose a method¶
| Class | Assignment | Recommended use | Cluster count |
|---|---|---|---|
| RaBitQKMeans | Flat RaBitQ scan | Small cluster counts | n >= k >= 1 |
| QGKMeans | SymphonyQG centroid graph | Larger cluster counts | n >= k > max_degree (C++ graph_degree; default 32) |
Python¶
Both classes have the same training and result interface:
from rabitqlib import QGKMeans, RaBitQKMeans
kmeans = RaBitQKMeans(d, 16, niter=25, num_threads=8)
# For larger cluster counts, use instead:
# kmeans = QGKMeans(d, 4096, niter=25, num_threads=8)
last_iteration_obj = kmeans.train(x)
centroids = kmeans.centroids # shape (k, d)
assignments = kmeans.assignments # shape (n,)
distances = kmeans.distances # shape (n,)
final_obj = kmeans.final_obj
# Assign other vectors, shape (m, d), to the trained centroids.
query_assignments, query_distances = kmeans.assign(queries) # shapes (m,), (m,)
x has shape (n, d) and is converted to a C-contiguous float32 array.
C++¶
Clustering belongs to rabitqlib::index, including the flat RaBitQ method.
Link that target; a core-only installation does not include clustering headers.
#include <rabitqlib/clustering/rabitqkmeans.hpp>
#include <rabitqlib/clustering/qgkmeans.hpp>
rabitqlib::rabitqkmeans::RaBitQKMeansParameters parameters;
parameters.niter = 25;
parameters.num_threads = 8;
rabitqlib::rabitqkmeans::RaBitQKMeans kmeans(dimension, 16, parameters);
// For graph assignment, use qgkmeans::QGKMeansParameters and qgkmeans::QGKMeans.
kmeans.train(num_points, data); // row-major float32 input
const auto& centroids = kmeans.centroids;
const auto& assignments = kmeans.assignments;
const auto& distances = kmeans.distances;
const double final_obj = kmeans.final_obj;
// Caller-owned outputs with num_queries elements each.
std::vector<rabitqlib::PID> query_assignments(num_queries);
std::vector<float> query_distances(num_queries);
kmeans.assign(num_queries, queries, query_assignments.data(), query_distances.data());
Complete examples: RaBitQKMeans
(bin/rabitqkmeans) and QGKMeans
(bin/qgkmeans). Run either without arguments for a synthetic demo, or save
clusters for the C++ indexing examples:
./bin/qgkmeans data.fvecs 4096 centroids.fvecs labels.ivecs
./bin/rabitqkmeans data.fvecs 16 centroids.fvecs labels.ivecs
File mode uses exact final assignment and the default training parameters.
Append ip for spherical clustering of normalized input; the default is l2.
sample/run_cpp.sh runs the C++ clustering and indexing workflow without Python.
Parameters and input¶
Set Python keyword arguments or fields of the corresponding C++ parameter type:
| Parameter | Default | Meaning |
|---|---|---|
niter |
25 |
Maximum clustering iterations. |
early_stop_threshold |
0.0 |
Stop from iteration 2 when the absolute relative objective change is at most this value; range [0, 1]. Zero stops only on an unchanged objective. |
num_threads |
0 |
Use detected available logical CPUs, capped by OMP_NUM_THREADS; positive requests are capped at the CPU count. See threading. |
spherical |
false |
Normalize centroids and assign by inner product; input must already be normalized. |
seed |
42 |
Seed for centroid selection and rotation. |
min_points_per_centroid |
39 |
Warn below this training-points-per-centroid ratio when verbose. |
max_points_per_centroid |
0 |
When positive, train on a random sample above k * max_points_per_centroid vectors; 0 trains on all vectors. See sampling. |
verbose |
false |
Print training progress and warnings. |
final_assignment |
'approximate' (C++ Approximate) |
Use the selected method for final labels, or 'exact' (C++ Exact) for nearest-centroid labels. |
num_threads sets an upper limit, not a fixed worker count for every stage.
QGKMeans may use fewer workers to build small centroid graphs. That additional
limit does not apply to training-vector assignment, which uses the thread budget
after capping it to the available CPUs.
Training requires 64 <= d <= 65536, finite coordinates, and
abs(x) <= sqrt(sqrt(FLT_MAX) / (64 * d)); scale larger inputs before training.
Cluster-count requirements are listed above. Training does not normalize or
mutate the input; provide normalized vectors for spherical mode.
Empty clusters are reseeded from distant points; duplicate data can still leave empty clusters in the final assignment. Thread scheduling can affect graph construction and floating-point reductions, so a fixed seed does not guarantee identical multithreaded results.
Training-set sampling¶
Sampling is disabled by default. When max_points_per_centroid is positive
and n > k * max_points_per_centroid, training draws
k * max_points_per_centroid distinct vectors uniformly at random, as Faiss
does; Faiss enables this by default with 256. Centroid initialization and all
Lloyd iterations use only this sample. The final centroids then assign all n
vectors with the selected final_assignment mode, as assign
does, so assignments and distances keep shape (n,) and assignments can be
passed directly to an index's add(..., cluster_ids=...). C++ callers that need
only the centroids can call train_centroids(n, x) instead of train, which
skips this final assignment and leaves assignments, distances and
final_obj empty or zero.
seed selects the sample through a random stream separate from centroid
initialization. Training that does not sample, because the parameter is 0 or
n is at most k * max_points_per_centroid, returns the same results as
before this parameter existed. The selected vectors depend on the
C++ standard library's random distributions, so the same seed can choose a
different sample on another platform.
obj and iteration_stats (and the value returned by Python train()) are
computed on the sampled vectors, while distances and final_obj cover all n
vectors. Their values are not directly comparable. Validation still checks
every input vector, including those outside the sample.
Sampling reduces iteration work but raises peak memory. Training copies the
sample into a contiguous buffer of k * max_points_per_centroid * d float32
values, 4 GiB for k = 4096, max_points_per_centroid = 256 and d = 960,
and briefly holds n 8-byte row indices to select it, in addition to the
caller's input. The final assignment still processes all n vectors.
Method details¶
RaBitQKMeans¶
The flat assignment design is inspired by
SuperKMeans. Training points are rotated
and encoded once around a fixed dataset mean. Each centroid becomes a query
that scans all packed point batches, and each point receives the centroid with
the best estimated distance. The model keeps this mean of the training points
(of the sample, when training samples), and assign
encodes new vectors around it.
Each iteration compares every training point with every centroid. The batch size of 32
is not a cluster-count limit. This method uses one-bit point codes throughout;
it has no graph parameters or nbits (C++ quantization_bits) setting.
QGKMeans¶
QGKMeans builds a SymphonyQG graph over the centroids and uses previous
assignments as search hints. Its additional parameters are below, under their Python
names since 0.8.5. C++ and Python before 0.8.5 name the first three
quantization_bits (with 0 for raw storage), graph_degree and ef_build; in
Python those names still work, with a DeprecationWarning, until 0.9.
| Parameter | Default | Meaning |
|---|---|---|
nbits |
32 |
Graph centroid storage: 32 for raw vectors, or 4/8 bits. |
max_degree |
32 |
A positive multiple of 32, strictly smaller than k. |
ef_construction, ef_search |
240, 16 |
Positive graph construction and search window sizes. |
graph_build_iterations |
1 |
PiPNN initialization followed by one refinement; values ≥2 request that many graph passes, ending in refinement. Independent of niter. |
The seed also controls fallback neighbors; PiPNN uses fixed internal seeds.
QGAssigner in qgkmeans.hpp supports repeated vector-to-centroid assignment
without the clustering loop. To assign vectors with trained QGKMeans centroids,
use assign.
Results and final assignment¶
Python result properties are None until a successful fit; a failed fit
preserves the previous successful results.
distances contains distances to the returned assigned centroids, computed
from the original float32 vectors and centroids. For squared L2, final_obj is
their sum (WCSS); spherical mode sums 1 - inner_product. obj and
iteration_stats record objectives before each centroid update; Python
train() returns the last such objective.
final_assignment='approximate' (default) uses the selected class's assignment
algorithm. Labels need not identify the exact nearest centroids, but reported
distances and WCSS remain exact for those labels. Without sampling, quantized
QGKMeans final assignment retains a point's last-iteration label when it is
closer. After sampling, most points have no such label, so every point uses the
same graph search. Approximate training objectives need not decrease monotonically.
To require exact nearest-centroid final assignments with either class:
from rabitqlib import RaBitQKMeans
kmeans = RaBitQKMeans(d, 16, final_assignment="exact")
kmeans.train(x)
Python takes the strings 'approximate' and 'exact' since 0.8.5. The
FinalAssignmentMode members Approximate, Exact and the legacy alias SymphonyQG
are still accepted until 0.9, and cp.final_assignment reads back as a member
until then; importing FinalAssignmentMode raises a DeprecationWarning.
In C++, set parameters.final_assignment to
rabitqlib::rabitqkmeans::FinalAssignmentMode::Exact or
rabitqlib::qgkmeans::FinalAssignmentMode::Exact; both names refer to the same
enum. Training still uses the selected approximate assignment algorithm.
Exact final assignment screens all centroids with blocked GEMM and refines
possible winners in float64; ties select the smallest centroid index. Returned
distances remain float32. Work is proportional to n * k * d; large coordinate
offsets or near ties can require more refinement.
Assign new vectors¶
After a successful fit, assign(x) returns (assignments, distances) for an
(m, d) array: uint32 centroid IDs and float32 distances to those centroids,
each of shape (m,). It uses final_assignment and the other parameters of the
last successful fit and checks coordinates as training does; m may be 0.
Before the first successful fit, it raises RuntimeError. The C++ method
assign(n, x, assignments, distances) writes to caller-owned buffers. It throws
std::runtime_error until train() succeeds, including when centroids were
written directly, and std::invalid_argument for invalid x or centroids.
assign uses no labels or search hints from training, so each vector's
result is independent of the other vectors in the call. Approximate
RaBitQKMeans encodes vectors around the stored training mean. Approximate
QGKMeans builds a graph over the centroids on first use and reuses it;
C++ callers that change centroids or graph parameters cause one rebuild on
the next call. Each call still validates the k * d centroid coordinates.
For the training vectors, assign reproduces assignments and distances
with exact final assignment, for RaBitQKMeans, and whenever training
sampled the input, because the sampled final pass is the same assignment.
Unsampled approximate QGKMeans training also uses previous labels as graph
search hints, so its final labels can differ.
Compare with Faiss¶
The comparison script
compares both methods with FAISS and requires faiss-cpu. Defaults are one
million 500-dimensional vectors, 4,000 centroids, and up to 25 iterations.
Load data with --input data.npy, or --input data.bin --d D for raw row-major
float32 data. Choose a thread count within the available hardware limit.
All three methods receive the same full dataset, iteration limit, cluster count,
thread budget, and seed values; FAISS subsampling is disabled. This command runs
one fit per method with seed 42. Add --repeats 4 for four fits per method with
rotating order, or --num-seeds N to use consecutive seeds. Different initializers
mean identical seeds need not produce identical centroids.
Only train() is timed, including the library methods' default approximate
final assignment. The script reports actual iterations, timing medians/ranges,
exhaustive nearest-centroid objectives, and both library methods' returned-label
objectives and label mismatches. Equal-distance ties can produce mismatches
without changing the objective. --spherical normalizes the input copy and
compares sums of 1 - inner_product.
Separate worker processes isolate OpenMP runtimes and share a temporary float32
input file; allow about 4 * n * d bytes of temporary disk space. Input staging,
process startup, and exhaustive evaluation are outside training time. For Linux
CPU placement, set OMP_PLACES=threads OMP_PROC_BIND=close; on NUMA systems,
use numactl --cpunodebind=0 --membind=0 with a thread count that fits the node.