[QST] kmeans performance cuVS vs. FAISS

Background

I'm developing a Postgres extension that runs kmeans clustering (on GPU) in order to accelerate index build times for vector indexes. The code can be found here: https://github.com/EnterpriseDB/pgpu

The code is written in Rust and the initial implementation used FAISS/rust for GPU accelerated kmeans since cuVS rust bindings didn't expose kmeans until recently.

We've now switched to cuVS and our benchmarks show very similar clustering time performance and clustering quality/accuracy.

I'm opening this issue because we were expecting performance gains from cuVS based on https://developer.nvidia.com/blog/enhancing-gpu-accelerated-vector-search-in-faiss-with-nvidia-cuvs/

implementations being used

With FAISS, I used the faiss-rs crate from https://github.com/Enet4/faiss-rs and built the FAISS C library faiss_c from source with version v1.13.0 (faiss-rs says they only support v1.7.2 but I had no issues using the latest version)

This setup ^^^ did not use the cuVS backend in FAISS.

With cuVS, I used the rust bindings from version 25.10: https://github.com/rapidsai/cuvs/tree/branch-25.10/rust and used the native kmeans implementation from cuVS. FAISS is not used at all in our new cuVS implementation

In both cases I used CUDA 12.9 with an L40S GPU and driver 580.105.08 on an aws ec2 g6e.xlarge instance.

Our tests vs. NVIDIA blog referenced above

Our tests compared:

• FAISS "non-cuVS" GPU
• cuVS kmeans

Your blog above compares

• FAISS "non-cuVS" GPU
• FAISS cuVS

So there are some differences...

kmeans implementation FAISS

this is how we configured/called FAISS: https://github.com/EnterpriseDB/pgpu/blob/v1.0.0/vectorchord-indexing/src/clustering_gpu_impl.rs#L22

    params.set_niter(kmeans_iterations); // this was set to 10
    params.set_nredo(kmeans_nredo); // set to 1
    params.set_verbose(true); // print progress
    params.set_update_index(true); // update the index after each iteration for better results
    params.set_spherical(spherical_centroids); // set to "true"; 

...

    let mut index = index_factory(vector_dims, "Flat", index_metric_type) // metric was InnerProduct
        .unwrap()
        .into_gpu(&gpu_res, 0)
        .expect("Flat index creation failed");

we did not set max_points_per_centroid but it defaults to 256 and we never supplied more samples than that. --> so FAISS should not have "benefited" from processing fewer samples.

kmeans implementation cuVS

here is the cuVS code: https://github.com/EnterpriseDB/pgpu/blob/82f33a47672606638595cc1482f7c22c81eac2d6/vectorchord-indexing/src/clustering_gpu_impl.rs#L44

    let kmeans_params = kmeans::Params::new()
        .expect("kmeans params create failed")
        .set_n_clusters(num_clusters as i32) // same as FAISS; see below
        .set_max_iter(kmeans_iterations as i32) // 10
        .set_n_init(kmeans_nredo as i32) // 1
        .set_metric(distance_operator_cuvs) // InnerProduct
        .set_hierarchical(true)
        .set_hierarchical_n_iters(kmeans_iterations as i32); // also 10

so we attempted to use identical configurations.

Benchmarking / reproducing

We use an internal database benchmarking tool that I can't share unfortunately. The tool loads data, runs the index creation (using the PGPU extension mentioned above) and then runs queries to assess the index/clustering quality.

I can explain the process but it might be easier is you just run clustering on its own; focusing on clustering performance.

We used the LAION dataset; a reduced version with just 5M records. It used to be available here (https://myscale-datasets.s3.ap-southeast-1.amazonaws.com/laion-5m-test-ip.hdf5) but this link is now dead.

1. load dataset into a table on PG; using the "vector" datatype for the embeddings
2. run PGPU to cluster the data and call index creation:

            select pgpu.create_vector_index_on_gpu(
              table_name => 'public.{table_name}',
              column_name => 'embedding',
              cluster_count => 8192,
              sampling_factor => 256,
              batch_size => 5000000,
              kmeans_nredo =>1,
              kmeans_iterations=>10,
              distance_operator=> 'ip',
              spherical_centroids => 'true'

PGPU will read cluster_count*sampling_factor vectors from the table; in this case ~2 million and supply these to the kmeans functions as the training dataset.
batch_size will control a custom batching implementation you can find in the code above. I tested with and without. If the batch size is large as in this example here, then only one kmeans training call will be made. So we're not introducing any other sources of "noise".
3) PGPU will write the centroids into a new table and then call vectorchord index creation
4) we then query the database like this: SELECT id FROM {table_name} ORDER BY embedding {metric_ops} %s LIMIT {top} with vectors we know to be present in the dataset and check if the query returns this vector.

Results we're seeing

Below you can see some of the results. The single run datapoints are most relevant since they purely execute a single "kmeans" call on FAISS and cuvs.

We can see the clustering times (in seconds) are very similar between FAISS and cuVS."index build time" isn't relevant here; this is the phase where postgres sorts the vectors into the clusters.

When we look at recall / qps rates, these are very similar again. So the clustering quality of both implementations is similar. This tells me that FAISS did not "cheat" by e.g. subsampling. The recall results would be worse in this case; I saw that in other tests I did.

Compare the FAISS and cuVS implementations in the linked vectorchord-indexing/src/clustering_gpu_impl.rs revisions, starting with the shown kmeans parameters and benchmark setup. Focus on reproducing clustering performance if the dataset or an equivalent test is available; done means identifying a supported explanation for the similar timings or documenting the missing reproduction data.