Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix IndexIVFFastScan reconstruct_from_offset method #4095

Open
wants to merge 4 commits into
base: main
Choose a base branch
from

Conversation

alisafaya
Copy link

Resolves issue #4089 - IndexIVFPQFastScan crashes with certain nlist values

The reconstruct_from_offset method in IndexIVFFastScan was incorrectly reconstructing vectors, causing crashes when the nlist parameter was not byte-aligned (e.g. 100 instead of 256).

The root cause was that the list_no (Voronoi cell number) was not being properly encoded into the code vector before passing it to the sa_decode function. This resulted in invalid list_no values being read in sa_decode, triggering the assertion failure 'list_no >= 0 && list_no < nlist' when nlist in some cases.

This PR fixes the issue with the following changes to reconstruct_from_offset:

  1. Encode the list_no into the beginning of the code vector using the existing encode_listno method
  2. Start the BitstringWriter after the coarse code portion of code (shifted by coarse_code_size() bytes)
  3. Remove the residual centroid addition logic, as it is already handled in sa_decode

After these changes:

  • Crashes no longer occur for any nlist value
  • Reconstruction is now correct, matching the output of IndexIVFPQ

Fixes #4089

Please review and let me know if any changes are needed. Thanks!

@asadoughi
Copy link
Contributor

Thanks for the contribution! Can you add unit tests, in Python should be sufficient, for the two cases you referenced?

  • Crashes no longer occur for any nlist value
  • Reconstruction is now correct, matching the output of IndexIVFPQ

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

IndexIVFPQFastScan crashes with certain nlist values
5 participants