Mixed results with FINGER for HNSW search

[Jonathan Ellis <jb...@gmail.com>]

Hi all,

FINGER [1] is a recent paper that describes how to accelerate graph-based
ANN search by using a faster, approximate distance measurement for most
query node / graph node comparisons instead of doing full N-dimension
vector calculations.

I've implemented a proof of concept of Finger for Lucene HNSW (in memory),
but I have not been able to replicate the paper's claims of massive
speedup.  Instead I see modest to negligible speedup.  For example, for the
nytimes-256 dataset, at (M, ef) = (16, 100) and topK=10 [2], I get

Vanilla HNSW: 0.72 s to search 10k vectors, recall = 71.5%
HNSW-FINGER: 0.70 s to search 10k vectors, recall = 68.9%

For the same dataset at (M, ef) = (128, 512), I get
Vanilla HNSW: 3.17 s to search 10k vectors, recall = 99.1%
HNSW-FINGER: 1.93 s to search 10k vectors, recall = 97.3%

The FINGER paper does not give exact M/ef, but for recall=70% they show a
speedup of 7000 ops/s -> 17000 ops/s on this dataset in Figure 4, almost
2.5x.

I've looked at this code every way I can think of and I'm stuck, I can't
see what I'm doing wrong or differently.  The approximation code is fairly
straightforward arithmetic, and profiling confirms that the
approximate-similarity function is in fact ~10x faster than the
exact-similarity function.  The problem seems to be that it still needs to
make a significant number of exact-similarity calls.  At (16, 100) it's
making about 2/3 as many exact-similarity calls as vanilla HNSW, and at
(128, 512) it's making about 1/4 as many (hence the performance
improvement). [3]  I believe this is because the approximated similarity
simply isn't high-fidelity enough.

The reason that it's hard to be sure is that there are two key components
to the FINGER approximate distance]:
1. Calculate the optimal basis to project the vectors onto, and
2. Use the signs of the vectors projected onto that basis to estimate the
angle between them.

It's very difficult to rule out bugs in either of these parts since there
are no "known good" values to compare with.  Compounding this challenge, #2
is a probabilistic result so you really have to look at averages over many
calls.

Here are some of the properties of my implementation that I have verified
behave as expected:

1. The basis vectors are orthonormal, and demonstrate that they preserve
more variance and less error than randomly chosen basis vectors
2. For trivial cases, the basis vectors match what an independent numpy
implementation derives
3. As r (the dimension of the basis vectors) increases, the error of the
estimated similarity compared to the actual similarity decreases
4. Using the actual low-basis angle instead of the hamming approximation
improves things, but (it seems to me) not so much that it indicates that
the approximation is broken.

If someone can take a look and see if I missed something, I'd appreciate
that.  Code is at https://github.com/jbellis/lucene/tree/concurrent-finger,
the highlights are

- FingerMetadata: where all the work happens
- TestFingerMetadata: verifies properties 1-3 above
- HnswGraphTestCase.testFinger*: compares Finger and vanilla results on
random data
- HnswSearcher: a cleaned-up HnswGraphSearcher with a Builder that adds
Finger support (search for useFinger)
- VectorMath: utility methods building on Apache Commons Math, which I just
copied into the source tree as hnsw.math package to get it working for now

Finally, the harness I used for testing the nytimes and other datasets is
at https://github.com/jbellis/hnswdemo/tree/finger.  (This code works with
the hdf5 datasets as provided by https://github.com/erikbern/ann-benchmarks/
.)

Much obliged for any ideas you have!

P.S. I'm also available on ASF slack #lucene-dev if you want to discuss
there.

[1] https://dl.acm.org/doi/pdf/10.1145/3543507.3583318
[2] The FINGER paper prefers to measure Recall@10 even though many datasets
offer Recall@100. I did not see a massive difference in Finger's
performance advantage either way.
[3] See Algorithm 2 line 19 in the paper for when exact similarity is
performed, corresponding to line 257 in HnswSearcher.

-- 
Jonathan Ellis
co-founder, http://www.datastax.com
@spyced