Lagra och hitta vektorer effektivt

Att hitta de närmaste vektorerna till en fråga är enkelt om du har tusen vektorer: jämför med alla.

Med tio miljoner vektorer à 768 dimensioner blir det 7,7 miljarder multiplikationer per fråga. Det går, men inte hundra gånger per sekund.

Approximativa index byter exakthet mot hastighet. De hittar oftast rätt grannar, ibland inte, och gör det tusen gånger snabbare.

Index	Idé	Bra på
Flat	jämför med alla	exakt, små samlingar
IVF	dela upp i kluster, sök i de närmaste	stora samlingar, justerbar
HNSW	navigerbar graf av grannar	låg latens, hög recall
PQ	komprimera vektorerna	minnesbegränsning

Måttet som räknas heter recall@k: av de $k$ verkliga närmaste grannarna, hur många hittade indexet? 0,95 betyder att en av tjugo missas — vilket i ett RAG-system oftast är helt acceptabelt, eftersom flera dokument ändå hämtas.

HNSW (hierarchical navigable small world) bygger ett skiktat grannskapsnätverk. Översta lagret har få noder med långa hopp; nedersta har alla noder med korta hopp. Sökningen börjar högst upp, greedy-vandrar mot frågan, och går ner ett lager i taget.

Det är samma idé som en hoppa-lista: långa hopp först, sedan finjustering.

Parameter	Betyder	Effekt
M	grannar per nod	högre → bättre recall, mer minne
efConstruction	sökbredd vid bygget	högre → bättre index, längre byggtid
efSearch	sökbredd vid fråga	justeras i drift: högre → bättre recall, högre latens

Den sista är den viktigaste i praktiken: den låter dig flytta dig längs recall/latens-kurvan utan att bygga om indexet.

IVF klustrar vektorerna (k-means) och söker bara i de nprobe närmaste klustren. Enkelt, minnessnålt och lätt att förstå — men recall faller vid klustergränser, eftersom en granne kan ligga precis på andra sidan.

Produktkvantisering (PQ) delar vektorn i delar och ersätter varje del med närmaste kodbokspost. En 768-dimensionell float32-vektor på 3 072 byte blir 96 byte — 32× mindre. Kostnaden är precision, och PQ kombineras därför nästan alltid med en omrankning: hämta 10× fler kandidater med PQ, räkna exakta avstånd på dem.

Avståndsmåttet måste matcha embeddingmodellen:

Mått	Används när
Cosinus	textembeddingar (nästan alltid)
Inre produkt	när vektorerna är normaliserade — samma som cosinus
Euklidiskt	bild- och ljudembeddingar ibland

Att använda euklidiskt avstånd på onormaliserade textembeddingar är ett vanligt och svårupptäckt fel: det fungerar «nästan», och recall blir lägre utan att något går sönder.

Mät alltid recall mot exakt sökning på ett urval av frågor innan du litar på ett index. Det är en halvtimmes arbete och det enda sättet att veta var på kurvan du befinner dig.

import numpy as np, time

rng = np.random.default_rng(0)
N, D = 200_000, 128
X = rng.normal(size=(N, D)).astype("float32")
X /= np.linalg.norm(X, axis=1, keepdims=True)      # normalisera → inre produkt = cosinus
fragor = X[:100] + 0.1 * rng.normal(size=(100, D)).astype("float32")
fragor /= np.linalg.norm(fragor, axis=1, keepdims=True)

def exakt(q, k=10):
    return np.argsort(-(X @ q))[:k]

t = time.perf_counter()
facit = [exakt(q) for q in fragor]
print(f"exakt: {(time.perf_counter() - t) / len(fragor) * 1000:.1f} ms/fråga")

# IVF för hand: klustra, sök bara i de nprobe närmaste klustren
from collections import defaultdict

K = 256
centroider = X[rng.choice(N, K, replace=False)]
for _ in range(8):                                  # enkel k-means
    tillhor = np.argmax(X @ centroider.T, axis=1)
    for c in range(K):
        m = tillhor == c
        if m.any():
            centroider[c] = X[m].mean(0)
    centroider /= np.linalg.norm(centroider, axis=1, keepdims=True)

listor = defaultdict(list)
for i, c in enumerate(np.argmax(X @ centroider.T, axis=1)):
    listor[int(c)].append(i)

def ivf_sok(q, k=10, nprobe=8):
    naraste = np.argsort(-(centroider @ q))[:nprobe]
    kandidater = np.array([i for c in naraste for i in listor[int(c)]])
    if len(kandidater) == 0:
        return np.array([], dtype=int)
    poang = X[kandidater] @ q
    return kandidater[np.argsort(-poang)[:k]]

def recall(nprobe):
    traff = 0
    t0 = time.perf_counter()
    for q, f in zip(fragor, facit):
        traff += len(set(ivf_sok(q, 10, nprobe)) & set(f))
    ms = (time.perf_counter() - t0) / len(fragor) * 1000
    return round(traff / (10 * len(fragor)), 3), round(ms, 2)

for nprobe in (1, 4, 16, 64, 256):
    r, ms = recall(nprobe)
    print(f"  nprobe={nprobe:>3}: recall@10 {r:.3f}  {ms:>6.2f} ms/fråga")
#  ↑ kurvan mellan recall och latens — välj punkt efter krav, mät alltid själv

Loopen längst ner är det viktigaste i hela noden: recall och latens är en kurva, inte ett värde. Att välja nprobe eller efSearch utan att ha ritat den kurvan för sin egen data är att gissa.