You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "vigyasharma (via GitHub)" <gi...@apache.org> on 2026/01/26 13:41:56 UTC
[I] Cluster Based ANN Vector Search for Lucene [lucene]
vigyasharma opened a new issue, #15612:
URL: https://github.com/apache/lucene/issues/15612
Our current HNSW vector search is great with low latency and high recall, but comes with its own set of challenges. Graph based algos are memory intensive which make them hard to scale. And they don't work well with segment merge. We have to rebuild the graph when merging segments, which is expensive and limiting.
Cluster based vector search algorithms seem to provide a promising alternative. At a high level, they partition vectors into a bunch of clusters, each represented by a centroid. Vectors within the partition are stored as a posting list and queries do an exhaustive search on nearest centroid partition. This has some neat benefits:
1) Only the centroids need to be kept in memory. The postings can be loaded from disk as needed. This scales well for larger than memory indices.
2) Clusters can be merged efficiently across segments.
3) Once you identify the nearest centroid for a query, you only need to look into a single partition. This works well for storage / compute separation use cases where indices live in a remote store (like serverless vector search offerings). The "hot" in-memory part of the index is small (only centroids). Once a nearest centroid is identified, you only need to fetch vectors for that specific partition, which saves network cost and latency.
4) These algos do an exhaustive search within a posting, which works well with filtering. We can order the postings on a specific field (index sort), and skip a bunch of filtered out vectors altogether.
The SPANN paper [1] achieves strong results through two key constraints: bounded partition size and nearest partition assignment (NPA). SPFresh [2] builds on top of it with its 'Lightweight Incremental REbalancing' (LIRE) approach for in-place updates. However, these papers don't map directly to Lucene's segment based architecture. SPANN does an offline index build and SPFresh updates the index in-place.
This issue is to brainstorm how we can adapt insights from these papers into an effective cluster based vector search approach for Lucene's write once segment based architecture. Sharing some initial thoughts to get the ball rolling. Would love to hear from experts in the community.
...
### Technical Proposal
**Basic Setup:** We continue to leverage flat vector format for vector ordinals and raw vectors. Ordinals continue to be unique in segment scope. Indexing simply accumulates vectors in memory and assigns them ordinals (FlatVectorsWriter). At flush, if the no. of vectors are above a threshold, we create our cluster based index. Otherwise, for a small no. of vectors, we only keep the flat format and always do an exhaustive search. This is similar to what we have for HNSW today.
**Segment Flush:** We create the cluster based vector index during segment flush.
1. **Clustering on Vectors:** We cluster the vectors into a configurable no. of partitions, each represented by a centroid. Performance improves with more partitions and the SPANN paper notes that gains plateau once centroids reach ~16% of data points. We can keep the default `min_partitions` value at 12% - 16% of vector corpus size.
I propose we go with simple k-means clustering approach as a first cut. SPANN does Hierarchical Balanced Clustering (HBC) which provides better recall for latency. Similar work by PlanetScale [4] found that randomly selecting centroids works just as well when the corpus is large. Perhaps we start with k-means and follow up with more sophisticated improvements?
2. **Centroid Index:** We need an efficient data structure on centroids to find the nearest partition at query time (and some partition reassignment jobs during indexing). SPANN [1] uses "SPTAG", which is a mix of KD tree and a graph pruned with RNG heuristics.
We can instead leverage Lucene's existing pieces to create an HNSW index on the centroids. This gives an efficient way of finding the nearest partitions (centroids) at query time. Since the HNSW graph is only on centroids, we use < 20% of memory that would otherwise be needed in an hnsw only approach. This seems to have worked well for PlanetScale [4].
3. **Create Postings:** Create posting lists for the vectors assigned to each cluster. The list can be ordered by index-sort to allow efficient filtering and skipping.
4. **Postings Expansion to Improve Recall:** Since real world data shapes are seldom ideal, it's likely that some vectors will violate nearest partition assignment, and get missed when a query scans only the nearest centroid posting. The papers [1],[2] suggest a "postings expansion" step where vectors on the outskirts of the cluster are also assigned to nearby postings to improve recall. We apply this to our approach in the following way:
For each centroid, we find `k` nearby centroids using the hnsw graph and consider these as additional targets for vectors in the posting. A vector is assigned to these centroids (partitions) if its distance from the centroid is almost the same as its distance from the nearest centroid. The small delta of distance allowed will be configurable.
Additionally, we apply Relative Neighborhood Graph (RNG) pruning: if posting A is closer to posting B than to the vector, we only assign the vector to posting B, avoiding redundant assignments to nearby postings. The `k` or no. of postings to replicate the vector in ("postings_replication_factor"?) will be configurable. The paper [1] reports good performance at `postings_replication_factor=8`.
6. **Write Metadata:** We'll need a new vector format for this. It can reuse parts of the hnsw metadata format to store the centroid graph. Additionally, it will store the postings for each centroid.
.
**Query Flow:** For an incoming vector search query, we first find `k` (configurable) nearest centroids using the HNSW graph lookup. Of these, we consider the nearest centroid, and any additional centroids that are within a small distance delta over the nearest centroid. We fetch the postings from the selected centroid partitions and do an exhaustive scan over the vectors. Using posting list order, we can also jump ahead in this step to skip over filtered out documents.
.
**Handling Updates and Deletes:** Deletes and updates are handled as usual per Lucene's segment based architecture. The writes go to the latest segment and deletes flip the `liveDocs` bits. With efficient merging, we can combine segments frequently and keep our search performance in check.
.
**Segment Merges:** We need to adapt the cluster based approach to run effectively with Lucene's write-once segmented architecture. I propose the following goals for our merge design:
1) Efficiency: The approach should leverage the structure of merging segments as much as possible. Idea is to reuse past work done in building those segments.
2) Concurrency friendly: It'll be great if our merge algorithm is easy to parallelize.
3) Correctness: We want the final merged segment to have balanced clusters, postings within size limit, and nearest partition assignment (NPA) for vectors.
#### Potential Approach for Segment Merges
1. **Centroid Selection and Postings Merge:** We cluster existing centroids from input segments. To keep merges fast, we prioritize retaining the centroid of the largest participating posting. Smaller postings are appended to the largest one, combining them into one single partition for each centroid cluster. This minimizes the need to re-calculate distances for the majority of vectors in a new partition. We follow this up with reassignment step on vectors from the deleted centroid postings to maintain the NPA property.
2. **Create Graph for the New Centroids:** Before we split/merge partitions or reassign vectors, we need an efficient way to identify nearest centroids. To do this, we create an HNSW graph for the centroids remaining after postings in each cluster were merged. We may create more centroids if postings are split. These can simply be added to the HNSW graph.
3. **Reassign Vectors in Merged Postings:** Inspired by the SPFresh paper [2], we don't need to touch the vectors that remained in their original posting. Our "candidates vectors" are only the ones that were appended to the largest posting. We pick `k` postings nearest to each centroid as "target postings" for the reassignment. This `k` is a configurable parameter called `reassign_range`. Recall improves as we increase it; SPFresh [2] suggests `reassign_range=64` works well.
4. **Split Large Postings:** Post reassignment, we verify that each posting is within the max configured size limit. This is important to contain tail latency. Larger postings must be split into more partitions. No. of split partitions is determined based on the max allowed posting size, and required no. of centroids are determined using k-means clustering.
Vectors are then reassigned to these centroids. When assigning vectors to the new post-split centroids, we also compare their distance to k `(reassign_range)` nearby postings. This ensures the vectors are assigned to their nearest partition, in case a neighbor was closer than the newly created centroid. All newly created centroids are also added to the centroid HNSW graph.
5. **(Optional) Merge Small Postings:** We now have a new segment with postings that are all within the max allowed partition size. Postings that are too small (`< min_partition_size`), can now be merged into one segment, using the steps described above.
We want to ensure that we don't flip-flop endlessly between split and merge steps. This can be handled with heuristics like only merging if the final posting size is `< max_partition_size`.
...
This outlines my initial thoughts for merging segments. I suspect with benchmarking, we can find incremental improvements, like heuristics that contain the no. of vectors considered for reassignment. I've intentionally skipped details on how to organize and fetch postings from disk, hoping existing Lucene primitives can help us here.
Looking forward to hearing from experts in the community who've thought about or tried similar approaches elsewhere.
**References:**
[1] [SPANN Paper](https://arxiv.org/pdf/2111.08566)
[2] [SPFresh Paper](https://arxiv.org/pdf/2410.14452)
[3] [An older RFC with a SPANN specific proposal](https://github.com/apache/lucene/issues/14997)
[4] [PlanetScale Blog about a similarly inspired setup](https://planetscale.com/blog/larger-than-ram-vector-indexes-for-relational-databases)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "vigyasharma (via GitHub)" <gi...@apache.org>.
vigyasharma commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3823350019
Hi @Vikasht34, thanks for taking a look! I had considered DiskANN, but it has the same fundamental problems of graph based algos. You need to look at the entire graph to find nearest neighbors, which is memory intensive and has an expensive first fetch for cold nodes in storage/compute separated setups. It also comes with all the same problems in segment merge.
We should consider PQ or other types of quantization independent of the algorithm. On that note, Better Binary Quantization (BBQ) seems to report better results than PQ? The postings can be quantized, and we can use PQ if high dimensionality becomes a n/w bottleneck. While posting lookup is brute force, the key is to have small postings that contain tail latency. We'll have to experiment and profile.
I think there is space for these two families of vector search algos in Lucene. The graph based algos, where we should try optimizations like Hnsw + PQ (with disk access for full precision), and single layered Hnsw. And cluster based algos that help with highly selective filters, remote store setups and billion scale use-cases. Quantization applies across the board for both these approaches.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3800085478
Curious enough, I just published this :) :
https://github.com/apache/lucene/pull/15613
@vigyasharma @benwtrent Does that align with the centroid + inverted (ala IVF) approach that you were thinking of?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824752414
> we definitely need int8 (or 4-bit) for the posting lists to keep I/O in check. The trade-off is that once we quantize, we pretty much force a re-ranking phase unless we accept a lower recall ceiling.
Hi @atris that's where we this paper claims that re-call loss is very less like 0.01 , If we cab give access to your repo , i can implement this on top of yours and we can benchmark together
[1] https://arxiv.org/pdf/2509.18471
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824970598
>
> > we need to watch out for centroid drift where the HNSW node stops effectively representing the new combined cluster.
>
> Right, I believe we'll have to adjust based on participating postings? Merging to the largest ensures we only need to reassign vectors from the smaller postings. With a new centroid, we'll have to run reassignment for vectors across all postings in the cluster, to maintain the NPA property. It's a tradeoff b/w re-using structures from existing segments v/s rebuilding them entirely. If postings in the cluster are far away and similarly sized, it'll likely be more optimal to create a new centroid.
Yeah, reusing the centroid saves compute but risks graph quality if the cluster shape shifts significantly.
Given Ben's point about batch building, we probably just eat the cost of full reassignment to keep the graph healthy.
I'll start with the full rebuild for simplicity. If merge latency kills us, we can optimize with the "largest centroid" heuristic later.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "vigyasharma (via GitHub)" <gi...@apache.org>.
vigyasharma commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3801101214
As an incremental next step, I would like to do a small prototype that flushes out a single segment with cluster based format (no merges), and compare its performance with a single segment hnsw index. Would be interesting to see some initial numbers and bottlenecks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824950485
So, the merging and splitting of centroids should fit in nicely with graph updates.
- Merge vectors according to their centroids nearest centroid. Possibly first finding a candidate number of centroids given the vector centroids (centroid to centroid search). Then refine by the vectors and append to the correct centroid
- Then if the centroid gets too large, split it.
- On split, you can use the initial centroid's graph connections as a bootstrapped set of neighbors to search in the graph and update its connections.
- Rinse and repeat
That is likely way faster than doing this one vector at a time and just attempting to add to the graph directly.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "vigyasharma (via GitHub)" <gi...@apache.org>.
vigyasharma commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3800886217
@benwtrent, thanks for the feedback. Lots of insights to unpack here!
> One thing that I think is critical, the vectors in the postings lists must be quantized (I would think significantly so, e.g. 1 or 2 bit). Otherwise we are doubling the index size as to gain disk locality, vectors must be inline with the postings lists.
This peels a critical layer of detail. We certainly want disk locality in postings. A simple first step could be to double store vectors - full precision in flat format and quantized in postings list. We can do full precision vector reordering after collecting hits from postings.
However, it makes me wonder if we really need the flat format in its current form. What if we assign ordinals only to the centroids. And keep raw vectors only in their respective posting lists, optimized for disk locality. Once we identify a posting, we do a full scan. There's no jumping around neighbors to randomly access vectors like graphs, so maybe we don't need ordinals for these vectors?
This implies we'll have a new format for the raw vectors where centroids are assigned ordinals (required by their hnsw graph), and we keep a mapping of centroid ordinals to their posting's address. Raw vectors are only stored in their respective posting lists. This also means we don't get random access on raw vectors, only on the centroids - which is probably okay?
.
> As for using HNSW as the centroid indexing structure, this feels natural. However, one other thing to consider is doing a "hybrid-hnsw", where the higher levels are coarser centroids, and the bottom layer is the finest centroids. But I think that is probably after moving on from regular kmeans (to hierarchical clustering or something).
Agree, we'll learn with experiments.
.
> For postings overspilling, we need to be careful there. Doing it to the naively next nearest has shown to be pretty bad (https://arxiv.org/pdf/2601.07183).
Very interesting, thanks for sharing!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824848517
> The trade-off is that once we quantize, we pretty much force a re-ranking phase unless we accept a lower recall ceiling.
> I would argue this isn't strictly the case. int7/8/4 can provide 95+% recall depending on the data.
>
> Single and double bit, possibly for smaller vectors.
>
> Also, reranking, if done well, isn't that bad. You are talking maybe 100 floating point vectors scored against per Lucene segment vs. many thousands of quantized vector ops.
>
> Also, regarding the "Largest Centroid" merge idea: it’s smart for speed, but we need to watch out for centroid drift where the HNSW node stops effectively representing the new combined cluster. We might need a lightweight re-centering step during merge even if we don't fully re-cluster.
> I think shifting the centroids around will likely be required over time. But I would assume that batch building IVF/Spann/whatever is way faster and easier to do than HNSW over the individual vectors. ;)
Agreed on int8. The random seek overhead on the graph traversal dwarfs the linear scan for re-ranking anyway.
On the merge/rebuild: It definitely solves the drift, but the catch is the shuffle.
We can't stream the merge if we want contiguous posting lists. We have to buffer/group the whole segment by centroid before writing. For large segments, that sort pressure might actually be heavier than the graph build itself.
I'll get the baseline float impl in first to settle the format, then we can tackle that buffer logic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "navneet1v (via GitHub)" <gi...@apache.org>.
navneet1v commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3865037707
Hi @vigyasharma , @atris
Thanks for adding this idea. I see that on this thread we have been discussing mainly on indexing, I would like to add some thoughts for search too.
1. Similar to current HNSW search implementation we should add the concept of minSimilarity score to ensure that within a segment we can start pruning more and more centroids or may be a complete segment.
2. I see this PR: https://github.com/apache/lucene/pull/15676 in Lucene which provides the capability to share the minCompetitive scores across different shards(aka Lucene indices) in distributed vector search envs. I think this cluster based can take benefit from it and can prune more centroids during search.
Some questions on the search quality:
1. In case of filtering/deleted docs do we think with centroids approach we will be able to get high recall? For filters like date range queries it is not necessary that query vector is embedding the meaning of filters in it which then can lead to selection of centroids that can lead to 0 or less than K results.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824741766
> I think there is space for these two families of vector search algos in Lucene. The graph based algos, where we should try optimizations like Hnsw + PQ (with disk access for full precision), and single layered Hnsw. And cluster based algos that help with highly selective filters, remote store setups and billion scale use-cases. Quantization applies across the board for both these approaches.
I totally agree with this, Variants like single-layer HNSW also make sense for faster builds and more merge-friendly segments. In contrast, cluster-based approaches (IVF / partition-first / SPANN-like) are a better fit for billion-scale datasets, highly selective filters, and remote or tiered storage.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "vigyasharma (via GitHub)" <gi...@apache.org>.
vigyasharma commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3800813348
> Curious enough, I just published this :) :
@atris What timing! I'll go through your PR and leave my comments there.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3812411127
@vigyasharma Thanks for detailed Idea, I was wondering Since our goal to server big Indexes which can go along with High Dimension with Image catalogs and build low memory footprint, Do u think we should think of DiskAnn which is tailored for this use case, Cheap PQ codes in Memory, Full precision high quality graphs on Disk. I see couple of hickups with posting based, even though we have coarse Index , eventually we will be doing Brute force on Posting List. When we have higher dimention data , we will have problems with memory bandwidth and lots of IO operations.
On the other side with DiskAnn , It can work well the way HNSW working right now ,Always bring seeded entry points from Graph becuase With PQ we can get those entry points.
[1] https://arxiv.org/pdf/2211.12850
[2]https://suhasjs.github.io/files/diskann_neurips19.pdf
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "arup-chauhan (via GitHub)" <gi...@apache.org>.
arup-chauhan commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3881595459
Hello @atris, this looks very interesting!
I love to contribute in a small-scoped manner
Would it be helpful if I prototyped or benchmarked one focused piece, for example:
• A minimal k-means clustering step at flush for a single segment (no merges), or
• A simple centroid HNSW + exhaustive posting scan baseline for comparison against single-segment HNSW, or
• Some basic LuceneUtil benchmarks to help quantify recall/latency tradeoffs for a clustered layout?
Happy to start with whatever would be most useful to move this forward.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3800009611
I like the idea and agree with the incremental steps for getting it developed. Doing something like this will take time.
One thing that I think is critical, the vectors in the postings lists must be quantized (I would think significantly so, e.g. 1 or 2 bit). Otherwise we are doubling the index size as to gain disk locality, vectors must be inline with the postings lists.
As for SPFresh, I think the algorithm is nice for incremental updates, but for merges in Apache Lucene, we will need to do something that isn't incremental. Likely bulk updates. But I suspect rebuilding from scratch will still end up being way faster than HNSW is now :)
As for using HNSW as the centroid indexing structure, this feels natural. However, one other thing to consider is doing a "hybrid-hnsw", where the higher levels are coarser centroids, and the bottom layer is the finest centroids. But I think that is probably after moving on from regular kmeans (to hierarchical clustering or something).
For postings overspilling, we need to be careful there. Doing it to the naively next nearest has shown to be pretty bad (https://arxiv.org/pdf/2601.07183).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3812685110
@vigyasharma if we have to go about Scann then one of thing I feel we can do to minimize the storage , with less loss in Re-call is to Implement NVQ (Non-Uniform Vector Quantization for Vectors which is getting stored in Posting List) Which will reduce storage by ~4x and while re-scoring there is minor loss in re-call around 0.01.
[1] https://arxiv.org/pdf/2509.18471
Let me know What you think , I can help implementing this on top of @atris PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824744431
> The trade-off is that once we quantize, we pretty much force a re-ranking phase unless we accept a lower recall ceiling.
I would argue this isn't strictly the case. int7/8/4 can provide 95+% recall depending on the data.
Single and double bit, possibly for smaller vectors.
Also, reranking, if done well, isn't that bad. You are talking maybe 100 floating point vectors scored against per Lucene segment vs. many thousands of quantized vector ops.
> Also, regarding the "Largest Centroid" merge idea: it’s smart for speed, but we need to watch out for centroid drift where the HNSW node stops effectively representing the new combined cluster. We might need a lightweight re-centering step during merge even if we don't fully re-cluster.
I think shifting the centroids around will likely be required over time. But I would assume that batch building IVF/Spann/whatever is way faster and easier to do than HNSW over the individual vectors. ;)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824686268
@benwtrent @vigyasharma
Running the baselines on the single-segment flush now (using the PR branch).
One thought while those churn: Ben is spot on about the quantization—we definitely need int8 (or 4-bit) for the posting lists to keep I/O in check. The trade-off is that once we quantize, we pretty much force a re-ranking phase unless we accept a lower recall ceiling. I'm keeping it raw floats in the PR for now just to establish the graph structure, but we can drop a decoder in the SpannVectorsReader pretty easily later.
Also, regarding the "Largest Centroid" merge idea: it’s smart for speed, but we need to watch out for centroid drift where the HNSW node stops effectively representing the new combined cluster. We might need a lightweight re-centering step during merge even if we don't fully re-cluster.
Anyway, let's see what the baseline numbers say first.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "Vikasht34 (via GitHub)" <gi...@apache.org>.
Vikasht34 commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824766087
> Also, reranking, if done well, isn't that bad. You are talking maybe 100 floating point vectors scored against per Lucene segment vs. many thousands of quantized vector ops
@benwtrent I Guess the point is we should not bring even 100 float vectors if 100 quantized vectors would be okay for re-scoring if loss is really less.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3825003504
> So, the merging and splitting of centroids should fit in nicely with graph updates.
>
> - Merge vectors according to their centroids nearest centroid. Possibly first finding a candidate number of centroids given the vector centroids (centroid to centroid search). Then refine by the vectors and append to the correct centroid
> - Then if the centroid gets too large, split it.
> - On split, you can use the initial centroid's graph connections as a bootstrapped set of neighbors to search in the graph and update its connections.
> - Rinse and repeat
>
> That is likely way faster than doing this one vector at a time and just attempting to add to the graph directly.
Bootstrapping from the parent avoids the global entry search, so definitely faster.
The main thing to watch is that the split nodes don't inherit identical neighbor sets, or the graph navigation degrades (we lose the small-world shortcuts). A quick local beam search starting from those parent candidates should solve that.
I'll target that Centroid-first flow for the merge logic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "vigyasharma (via GitHub)" <gi...@apache.org>.
vigyasharma commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3824933968
> Running the baselines on the single-segment flush now (using the PR branch).
@atris Awesome, looking forward to benchmarking numbers.
> we need to watch out for centroid drift where the HNSW node stops effectively representing the new combined cluster.
Right, I believe we'll have to adjust based on participating postings? Merging to the largest ensures we only need to reassign vectors from the smaller postings. With a new centroid, we'll have to run reassignment for vectors across all postings in the cluster, to maintain the NPA property. It's a tradeoff b/w re-using structures from existing segments v/s rebuilding them entirely. If postings in the cluster are far away and similarly sized, it'll likely be more optimal to create a new centroid.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Cluster Based ANN Vector Search for Lucene [lucene]
Posted by "atris (via GitHub)" <gi...@apache.org>.
atris commented on issue #15612:
URL: https://github.com/apache/lucene/issues/15612#issuecomment-3865105584
Currently, the PR post-filters search results during the fine phase, scanning allowed vectors within the selected segments. This avoids zero results for populated partitions but remains sensitive to disjoint query/filter distributions if nprobe is low.
Pruning via minSimilarity (and integrating with/emulating #15676) is a planned optimization to reduce I/O.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org