kNN-Suche für semantische Ähnlichkeit: Approximate kNN mit HNSW verstehen

1. Wo klassische Textsuche bei Bedeutungsähnlichkeit an Grenzen stößt

BM25-basierte Textsuche bewertet Dokumente danach, wie oft und wie selten die Suchbegriffe im Dokument und im Gesamtindex vorkommen. Das funktioniert hervorragend, solange Kunden dieselben Begriffe verwenden wie das Produktkatalogsystem. Sobald aber ein Synonym, eine Umschreibung oder eine andere Formulierung ins Spiel kommt, etwa eine Suche nach leiser Küchenmaschine statt geräuscharmer Standmixer, liefert reine Textsuche schlicht keine Treffer, obwohl inhaltlich exakt das passende Produkt existiert.

Synonymlisten können einen Teil dieser Lücke schließen, skalieren aber schlecht, weil jede neue Formulierung manuell gepflegt werden muss. Vektorsuche geht das Problem grundsätzlich anders an: Ein Embedding-Modell wandelt Text in einen numerischen Vektor um, der die Bedeutung des Textes im Raum codiert. Zwei Texte mit ähnlicher Bedeutung erzeugen Vektoren, die im hochdimensionalen Raum nah beieinander liegen, unabhängig davon, welche konkreten Wörter verwendet wurden.

2. Von Embeddings zum Vektorraum: wie Ähnlichkeit gemessen wird

Ein Embedding-Modell bildet Text typischerweise auf einen Vektor mit mehreren hundert bis mehreren tausend Dimensionen ab, etwa 384, 768 oder 1536 Werte pro Vektor. Elasticsearch speichert solche Vektoren im Feldtyp dense_vector und bietet mehrere Similarity-Metriken an, um die Distanz oder Ähnlichkeit zwischen zwei Vektoren zu berechnen: cosine misst den Winkel zwischen zwei Vektoren unabhängig von deren Länge, dot_product ist rechnerisch günstiger und eignet sich für normalisierte Vektoren, und l2_norm misst den euklidischen Abstand.

Die Wahl der Metrik hängt vom verwendeten Embedding-Modell ab: Die meisten modernen Sentence-Transformer-Modelle sind für Cosine-Similarity trainiert und liefern damit die verlässlichsten Ergebnisse, während manche Modelle explizit für dot_product optimiert sind, um Rechenzeit zu sparen. Die Similarity-Metrik wird direkt im Mapping des Feldes festgelegt und lässt sich nach dem Anlegen des Index nicht mehr ändern, ohne den Index neu aufzubauen.

PUT products
{
  "mappings": {
    "properties": {
      "description_embedding": {
        "type": "dense_vector",
        "dims": 768,
        "index": true,
        "similarity": "cosine"
      }
    }
  }
}

3. Exaktes kNN gegen Approximate kNN: der grundlegende Kompromiss

Exaktes kNN, in Elasticsearch über eine script_score-Query mit einer Vektordistanzfunktion umgesetzt, vergleicht die Anfrage mit jedem einzelnen Vektor im Index und liefert garantiert die tatsächlich nächsten Nachbarn. Der Rechenaufwand wächst dabei linear mit der Anzahl der Dokumente, was bei wenigen tausend Kandidaten problemlos in Millisekunden erledigt ist, bei mehreren Millionen Vektoren aber schnell mehrere Sekunden pro Anfrage kostet und damit für eine Live-Suche im Shop unbrauchbar wird.

Approximate kNN verzichtet auf die Garantie exakter Ergebnisse zugunsten von Geschwindigkeit. Statt jeden Vektor zu prüfen, navigiert der Algorithmus durch eine vorab aufgebaute Graphstruktur und findet dabei mit hoher, aber nicht absoluter Wahrscheinlichkeit die tatsächlich nächsten Nachbarn. Für die allermeisten Anwendungsfälle in der Produktsuche ist dieser kleine Genauigkeitsverlust vollkommen akzeptabel, weil ohnehin selten nur ein einziges perfekt passendes Ergebnis existiert, sondern eine Menge ähnlich guter Treffer.

4. Der HNSW-Algorithmus: Funktionsweise der Graphnavigation

HNSW steht für Hierarchical Navigable Small World und baut beim Indexieren einen mehrschichtigen Graphen auf, in dem jeder Vektor ein Knoten ist und Kanten zu seinen jeweils nächsten Nachbarn führen. Die oberste Schicht enthält nur wenige Knoten mit weitreichenden Verbindungen, während untere Schichten immer dichter werden und schließlich alle Vektoren enthalten. Eine Suche startet auf der obersten, dünnen Schicht, springt grob in Richtung des Zielbereichs und steigt Schicht für Schicht ab, wobei die Suche in jeder Schicht präziser wird.

Dieses Prinzip ähnelt einer Landkarte mit mehreren Zoomstufen: Man beginnt mit der groben Übersichtskarte, um die richtige Region zu finden, und wechselt dann zu immer detaillierteren Karten, um die genaue Position zu bestimmen. Weil jede Schicht nur wenige Sprungschritte bis zum Zielbereich benötigt, wächst die Suchzeit nur logarithmisch mit der Anzahl der Vektoren, nicht linear wie bei exaktem kNN. Das ist der eigentliche Grund, warum HNSW auch bei zig Millionen Vektoren noch Antwortzeiten im einstelligen Millisekundenbereich liefert.

5. Praktische Konfiguration: index_options im dense_vector Mapping

Die Struktur des HNSW-Graphen lässt sich beim Anlegen des Mappings über index_options steuern. Der Parameter m legt fest, wie viele Kanten jeder Knoten maximal zu seinen Nachbarn hält, ein höherer Wert verbessert die Suchqualität, erhöht aber Speicherbedarf und Indexierungszeit. Der Parameter ef_construction bestimmt, wie gründlich beim Aufbau des Graphen nach den besten Nachbarn gesucht wird, und wirkt sich ausschließlich auf die Indexierungsgeschwindigkeit und die spätere Suchqualität aus, nicht auf die Suchgeschwindigkeit selbst.

Für die meisten Produktkataloge sind die Standardwerte von Elasticsearch ein solider Ausgangspunkt, und Anpassungen lohnen sich erst, wenn konkrete Recall-Messungen zeigen, dass zu viele relevante Treffer fehlen. Eine Erhöhung von m oder ef_construction sollte immer mit einem erneuten Voll-Reindex einhergehen, da bestehende Graphstrukturen nicht nachträglich verdichtet werden können.

PUT products
{
  "mappings": {
    "properties": {
      "description_embedding": {
        "type": "dense_vector",
        "dims": 768,
        "index": true,
        "similarity": "cosine",
        "index_options": {
          "type": "hnsw",
          "m": 16,
          "ef_construction": 100
        }
      }
    }
  }
}

6. Die Suchanfrage: der knn-Query-Block mit k und num_candidates

Eine kNN-Anfrage in Elasticsearch besteht aus dem Anfragevektor, dem Parameter k, der die Anzahl der letztlich gewünschten Ergebnisse angibt, und dem Parameter num_candidates, der bestimmt, wie viele Kandidaten pro Shard während der Graphnavigation betrachtet werden, bevor die besten k davon zurückgegeben werden. Diese zweistufige Konstruktion ist der Schlüssel dazu, Approximate kNN in der Praxis steuerbar zu machen.

Ein höherer num_candidates-Wert bedeutet, dass der Algorithmus mehr mögliche Nachbarn prüft, bevor er die endgültige Auswahl trifft, was die Wahrscheinlichkeit erhöht, tatsächlich die nächsten Nachbarn zu finden, gleichzeitig aber auch mehr Rechenzeit kostet. Elasticsearch empfiehlt als Faustregel, num_candidates mindestens doppelt bis dreifach so groß wie k zu wählen, wobei sich der optimale Faktor je nach Datensatz und Anforderung an Genauigkeit deutlich unterscheiden kann.

GET products/_search
{
  "knn": {
    "field": "description_embedding",
    "query_vector": [0.021, -0.153, 0.402, "..."],
    "k": 10,
    "num_candidates": 100
  },
  "_source": ["sku", "name", "price"]
}

7. num_candidates Tuning: der Trade-off zwischen Recall und Latenz

In der Praxis empfiehlt sich ein iteratives Vorgehen beim Tuning von num_candidates: Man startet mit einem konservativen Wert, misst die Antwortzeit unter realistischer Last, und vergleicht die zurückgegebenen Ergebnisse stichprobenartig mit einer exakten kNN-Referenzsuche auf einer Teilmenge der Daten, um den tatsächlichen Recall zu bestimmen. Recall bezeichnet dabei den Anteil der tatsächlich nächsten Nachbarn, die die Approximate-Suche tatsächlich gefunden hat.

Bei sehr großen Produktkatalogen mit mehreren Millionen Einträgen lohnt es sich, num_candidates nicht global, sondern je nach Anwendungsfall unterschiedlich zu wählen: Für eine interaktive Live-Suche im Shop-Frontend ist eine niedrige Latenz meist wichtiger als hundertprozentiger Recall, während für eine Batch-Verarbeitung, etwa das Vorschlagen ähnlicher Produkte für Cross-Selling, ein höherer Recall bei etwas längerer Rechenzeit vertretbar ist.

8. Hybrides Filtern: kNN mit klassischen Filtern kombinieren

In einem realen Shop soll eine semantische Suche fast nie über den kompletten Katalog laufen, sondern innerhalb einer Kategorie, eines Preisbereichs oder unter Berücksichtigung der Verfügbarkeit. Elasticsearch unterstützt dafür einen filter-Parameter direkt innerhalb des knn-Blocks, der vor der Graphnavigation angewendet wird. Dieses sogenannte Pre-Filtering sorgt dafür, dass die HNSW-Suche nur innerhalb der gefilterten Teilmenge nach Nachbarn sucht, statt erst global zu suchen und danach herauszufiltern.

Der Unterschied ist bei stark einschränkenden Filtern erheblich: Ohne Pre-Filtering könnte eine globale Suche theoretisch alle k Ergebnisse liefern, die anschließend durch den Filter komplett verworfen werden, sodass am Ende zu wenige oder gar keine Treffer übrig bleiben. Mit Pre-Filtering navigiert der Graph gezielt nur durch die relevante Teilmenge, was bei stark selektiven Filtern zwar mehr Rechenaufwand innerhalb dieser Teilmenge bedeutet, aber verlässlich vollständige Ergebnismengen liefert.

GET products/_search
{
  "knn": {
    "field": "description_embedding",
    "query_vector": [0.021, -0.153, 0.402, "..."],
    "k": 10,
    "num_candidates": 100,
    "filter": {
      "bool": {
        "filter": [
          { "term": { "category_id": 42 } },
          { "range": { "price": { "lte": 150 } } }
        ]
      }
    }
  }
}

9. Grenzen und Monitoring: Recall messen, Indexgröße, Rebuild-Kosten

Der HNSW-Graph liegt vollständig zusätzlich zu den eigentlichen Vektoren im Speicher, was bei großen Katalogen mit hochdimensionalen Embeddings einen erheblichen Speicherbedarf pro Node bedeutet. Vor der Produktivnahme sollte deshalb realistisch abgeschätzt werden, wie viel zusätzlicher Heap- und Off-Heap-Speicher für den Graphen benötigt wird, insbesondere wenn mehrere Vektorfelder pro Dokument oder mehrere Sprachen parallel indiziert werden.

Da sich index_options nachträglich nicht ändern lassen, ohne den betroffenen Index komplett neu aufzubauen, sollte jede Änderung an Graphparametern zunächst auf einem Testindex mit einer repräsentativen Teilmenge der Produktdaten validiert werden. Ein regelmäßiges Monitoring, das Recall-Stichproben gegen eine exakte Referenzsuche zieht und die tatsächliche Antwortzeitverteilung unter Produktionslast beobachtet, verhindert, dass sich die Suchqualität unbemerkt verschlechtert, wenn der Katalog wächst und die relative Genauigkeit bei gleichbleibendem num_candidates tendenziell sinkt.

10. Zusammenfassung

11. FAQ: kNN-Suche für semantische Ähnlichkeit: Das Wichtigste auf einen Blick