Mailing List Archive

Hi Lucene developers,

I work for Amazon Retail Product search and we are using Lucene KNN for
semantic search of products. We index product embeddings (vectors) into
lucene (hnsw graph) and search them by generating query embedding at
runtime. The product embeddings also receive regular updates and the index
geometry keeps changing because of merges.
We recently noticed that the hnsw graphs generated are not always strongly
connected and in worst case scenario some products may be undiscoverable.
Connectedness of Hierarchical graph can be complicated, so below I am
mentioning my experiment details.

- Experiment:
I took the Lucene indexes from our production servers and for each segment
(hnsw graph) I did following test.
At each level graph I took the same entry point, the entry point of HNSW
graph, checked how many nodes are reachable from this entrypoint. Note that
connectedness at each level was checked independently of other levels.
Sample code attached. My observations are as below.

- Observation :
1. Of all the graphs across all the segments, across 100s of indexes that I
considered, one graph for each "level" of HNSW, almost 18% of the graphs
had some disconnectedness.
2. Disconnectedness was observed at all the levels of HNSW graphs. We have
at most 3 levels in HNSW graphs.
3. percentage disconnectedness ranged from small fractions 0.000386% (1
disconnected out of 259342) to 3.7% (eg. 87 disconnected out of 2308).
In some extreme case the entry-point in zeroth level graph was disconnected
from rest of the graph making the %age disconnected as high as 99.9% (65
reachable nodes from EP out of 252275). But this does not necessarily mean
that the 99.9% of nodes were not discoverable, it just means that if
unluckily we end up on EP in the 0th level graph for a query, there can at
max be 65 nodes that can be reached. But had we diverted our path from EP
to some other node in the upper level graphs then may be more nodes be
discoverable via that node.

- What I Not Checked :
What I have not checked till now is the connectedness for the whole HNSW
graph including edges of all the levels.
Also, I have not checked the number of disconnected components in a graph.
I have just checked the number of connected nodes to the entry-point.

But irrespective of that, I think graphs should be strongly connected at
each level and disconnectedness if at all should be very very rare.

Thanks Kaival Parikh for discovering the issue in the first place and the
script for checking connectedness.

What do others think about this?

public class CheckHNSWConnectedness {
private static int getReachableNodes(HnswGraph graph, int level)
throws IOException {
Set<Integer> visited = new HashSet<>();
Stack<Integer> candidates = new Stack<>();
candidates.push(graph.entryNode());

while (!candidates.isEmpty()) {
int node = candidates.pop();

if (visited.contains(node)) {
continue;
}

visited.add(node);
graph.seek(level, node);

int friendOrd;
while ((friendOrd = graph.nextNeighbor()) != NO_MORE_DOCS) {
candidates.push(friendOrd);
}
}
return visited.size();
}

public static void checkConnected(String index, String hnswField)
throws IOException, NoSuchFieldException, IllegalAccessException {
try (FSDirectory dir = FSDirectory.open(Paths.get(index));
IndexReader indexReader = DirectoryReader.open(dir)) {
for (LeafReaderContext ctx : indexReader.leaves() ) {
KnnVectorsReader reader =
((PerFieldKnnVectorsFormat.FieldsReader) ((SegmentReader)
ctx.reader()).getVectorReader()).getFieldReader(hnswField);

if (reader != null) {
HnswGraph graph = ((Lucene95HnswVectorsReader)
reader).getGraph(hnswField);
for (int l = 0; l < graph.numLevels(); l++){
int reachableNodes = getReachableNodes(graph, l);
// int graphSize = graph.size(); // this gives
nodes at 0th level
int graphSize = graph.getNodesOnLevel(l).size();
System.out.printf("Level: %d, Actual Size:
%d, Reachable: %d, Not Reachable : %d\n", l, graphSize,
reachableNodes, (graphSize - reachableNodes));
}
}
}
}
}

public static void main(String[] args) throws IOException,
NoSuchFieldException, IllegalAccessException {
String index = args[0];
String field = args[1];
System.out.println("For index " + index + " field : " + field);
checkConnected(index, field);
}




--
Regards,
Nitiraj