[FEA] Optimize Vamana index build kernels
Open
@bkarsin is already working on this.
Since Jan 29, 2026.
feature request
- Dominant language
- Cuda
- Stars
- 854
- Forks
- 236
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 62
Description
There are a number of perf optimizations that can improve the GPU Vamana index build in cuVS. This issue tracks these optimizations that may be applied with several PRs to limit scope and maintain stability. Perf estimates for each optimization are rough and attempt to be conservative.
Note: speedups are speculative and should not be relied on until optimizations are tested
High Impact / Priority Optimizations
- Increase blockDim of
GreedySearchandRobustPrunekernels from 32 to 128-256. Block size limits theoretical occupancy to 50%, estimated 1.2x-1.5x kernel perf improvement - got 0% to 38% kernel speedup - Parallelize all distance computations in
enqueue_all_neighborsfor improved parallelism. Could significantly reduce sync overheads on method thatGreedySearchspends 30-40% of runtime on. Expected 1.4-1.6x GreedySearch improvement - Optimization unsuccessful, no speedup achieved - Reduce syncthreads required during merge loop of
RobustPrune. Can reduce syncs by 10x during merge loop.RobustPrunespends 20% of time here, so estimate 1.3-1.4x improvement ofRobustPrune. - Achieved 0% to 28% kernel spedup - Replace serial prefix sum execution with CUB parallel prefix sums. Minimal time is spent here, so roughly 5% E2E build time improvement. - Achieved 2-5% E2E speedup
- Optimize the
check_visiteddata structure ofRobustPrune(hash set or bitset). Currently a linear search, estimate a 1.2x speedup toGreedySearch.
Overall perf gain estimate
- 2-2.5x speedup of
GreedySearch - 1.5-2.2x speedup of
RobustPrune
Depending on the dataset, the time breakdown can vary between these kernels. On narrow vectors,GreedySearchdominates, whileRobustPruneis more costly for wide vectors.
Expected E2E perf gains: 1.6x-2.4x
E2E perf achieved thus far: 1x-1.4x
Additional more challenging / speculative optimizations
- Try to improve cache reuse of candidate-candidate distances computed during
RobustPrune. Shared memory is a major occupancy limiter for these kernels, so this may not be feasible. - Reduce synchronizations used by
PriorityQueuestructure by replacing them with warp primitives.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.