Wie funktioniert Approximate Nearest Neighbor Search, und was gibst du für die Geschwindigkeit auf?

Exakte Suche vergleicht die Query mit jedem Vektor, das ist linear in der Korpusgröße. ANN-Indizes wie HNSW oder IVF bauen eine Struktur (einen navigierbaren Graphen oder eine Menge von Clustern), die nur eine kleine Kandidatenmenge besucht, und liefern damit sublineare Query-Zeit. Du gibst exakten Recall auf: manche echten nächsten Nachbarn werden verfehlt. Parameter wie efSearch oder nprobe schieben dich auf der Kurve zwischen Recall und Latenz.

Exakte Suche heißt, die Query gegen jeden Vektor zu vergleichen, das ist bei hunderttausend in Ordnung und bei hundert Millionen aussichtslos. ANN-Indizes verkleinern die Kandidatenmenge. HNSW baut einen geschichteten Nachbarschaftsgraphen und läuft ihn gierig von einer dünnen obersten Schicht zu einer dichten unteren, du berührst also ein paar tausend Knoten statt des ganzen Korpus. IVF clustert den Raum vorher und durchsucht nur die nächstgelegenen paar Cluster. In beiden Fällen gibst du Recall auf: manchmal liegt der echte nächste Nachbar knapp außerhalb der Region, die du erkundet hast. Wichtig ist, dass es ein Regler ist. In HNSW steuert efSearch, wie breit der Beam ist; in IVF steuert nprobe, wie viele Cluster du öffnest. Ich baue immer eine kleine Ground-Truth-Menge, ein paar tausend Queries per Brute Force gescort, sweepe dann diesen Parameter und plotte Recall at 10 gegen p99-Latenz. Beim letzten System, das ich getunt habe, hat der Weg von 95 auf 99 Prozent Recall die Latenz verdreifacht und die Klickrate downstream fast nicht bewegt, also sind wir bei 95 geblieben. Ich monitore Recall außerdem, weil er nach großen Index-Rebuilds still degradiert.