A semantic search engine can compare a query embedding with every document embedding, but that becomes slow as the collection grows. Approximate nearest neighbor (ANN) search instead retrieves vectors likely to be close to the query, leaving a smaller set to score. It trades some accuracy for faster retrieval and lower resource costs. section 13.5.3
A practical ANN search pipeline has three parts:
- Generate document embeddings ahead of time and add them to a searchable index. HNSW organizes nearby vectors in a multilayer graph; an inverted file index is another option. section 13.5.3
- Encode the query, search the index for a configurable number of candidates, and filter or rank the returned matches. For cosine-based matching, normalize document and query vectors so dot products can supply similarity scores. section 13.5.4 section 13.2.2
- Check both speed and result quality. Semantically related results are not necessarily the most relevant results for a short, ambiguous query. section 13.6.2
Listing 13.14 ANN search using NMSLIB
import nmslib
concepts_index = nmslib.init(method="hnsw", #1
space="negdotprod") #1
normalized_embeddings = list(map(normalize_embedding, embeddings))
concepts_index.addDataPointBatch(normalized_embeddings) #2
concepts_index.createIndex(print_progress=True) #3
ids, _ = concepts_index.knnQuery( #4
normalized_embeddings[25], k=10) #4
matches = [labels[phrases[i]].lower() for i in ids] #5
display(matches)
The Python listing initializes an NMSLIB HNSW index, adds normalized embeddings as a batch, builds the index, and requests ten neighbors. section 13.5.4
Semantic autocomplete
An autocomplete index holds embeddings for 12,375 terms. Searching for “bag” returns related terms such as “bag cover,” “bag liner,” and “paper bag” without comparing the query against every term at search time. The query helper also sets a candidate count and minimum similarity; queries such as “mountain hike” can then surface related suggestions. section 13.5.4 section 13.5.3
Listing 13.15 Encoding a query and returning the k-nearest-neighbor concepts
def embedding_search(index, query, phrases, k=20, #1
min_similarity=0.75): #1
matches = []
query_embedding = transformer.encode(query) #2
query_embedding = normalize_embedding(query_embedding)
ids, distances = index.knnQuery(query_embedding, k=k)
for i in range(len(ids)):
similarity = distances[i] * -1 #3
if similarity >= min_similarity: #4
matches.append((phrases[ids[i]], similarity))
if not len(matches):
matches.append((phrases[ids[1]], distances[1] * -1)) #5
return matches
def semantic_suggest(prefix, phrases):
matches = embedding_search(concepts_index, prefix, phrases)
print_labels(prefix, matches)
semantic_suggest("mountain hike", phrases)
semantic_suggest("dehyd", phrases)
The query helper shows encoding, normalization, k-neighbor retrieval, conversion of returned distances to similarity scores, and a minimum-similarity filter. section 13.5.4
ANN is one part of a larger performance trade-off. Quantization can shrink embeddings, Matryoshka Representation Learning can reduce the dimensions used for initial retrieval, and reranking can improve the final candidates. In one combined inverted-file-index example, search was about 99% faster and the index about 98% smaller than full-precision search, while reranked recall remained above 72%; those figures describe that configuration, not an ANN guarantee. section 13.7.5
