Skip to content

[BUG] Brute-force kNN can return nonzero distances for identical vectors #2883

Open

Description

@viclafargue

#2841 removed a rule that forced small distances to zero when two vectors had equal squared lengths. This addressed a real problem: distinct nearby vectors could incorrectly receive zero distance, affecting neighbor ordering and clustering.

As discussed in the PR, removing that rule also exposes underlying rounding errors when comparing a vector with itself. Negative errors are still clamped to zero, while positive errors remain. Taking the square root makes these errors more visible with the Euclidean metric. The PR documents this tradeoff and adjusts the Go brute-force test tolerance accordingly.

Observed behavior :
In a float32 test with 800 vectors of 32 dimensions, searching an independently allocated copy of the dataset returned nonzero self-distances for 256 vectors:

  • Maximum squared Euclidean self-distance: approximately 0.000732.
  • Maximum Euclidean self-distance: approximately 0.0271.

This occurred with both k=8 and k=65. The correct self-neighbor IDs were returned. Similar behavior occurs with dataset slices, column-major inputs, and filtered searches.

Expected behavior :
Identical finite vectors should have zero distance, including when queries are copies or slices of the dataset.
Could we preserve this behavior while retaining the improvements from #2841? This would complement the diagonal correction already added for certain pairwise-distance calls, extending support to brute-force kNN.

Activity

  1. aamijar commented on Oct 26, 2026

    @aamijar
    Member

    Yes this is expected when using L2SqrtExpanded metric because of rounding errors. Ideally, we could avoid those somehow. We might be moving to TopK kernels soon, so it would be interesting to see if this still happens with that path @dantegd.
    On the user side, you could write a post-processing step to check if the returned indices are the same as queries (identical vectors) then manually set the distance to be zero.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions