ivfq

package module
v0.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 27, 2026 License: MIT Imports: 17 Imported by: 0

README

ivfq

go get github.com/axiomhq/ivfq

Inverted-file clustering plus 1-bit quantization for approximate nearest neighbour search, in pure Go with AVX2 kernels. The FAISS "IVF + quantizer" pair, without the storage: you keep the rows, this package gives you the clusters, the codes and the scan.

Build an index

  1. Train centroids on a sample: centroids, _, err := ivfq.RunSampledBudget(ctx, vectors, k, iters, seed, bytes). k := ivfq.HoodK(n) sizes clusters at about 1,024 rows.
  2. Put them in a tree: tree, err := ivfq.Build(ctx, centroids, fanout).
  3. Route every row to its cluster: tree.Nearest(row, beam)[0].
  4. Quantize each cluster's rows: q, err := ivfq.Quantize(rows, ivfq.Options{Dims: dims, Seed: seed}). One bit per dimension plus two float32 per row.

Query

  1. Probe the nearest clusters: tree.Nearest(query, ivfq.DefaultNprobe(k)).
  2. Score every probed row on its codes: s := q.Scorer(ivfq.NewQuery(query, "l2")); s.ScoreAndBound(row) returns an estimate and a bound.
  3. Rerank the shortlist on the raw vectors with ivfq.Score(metric, query, row).

Splits and merges keep the clusters at their size as rows arrive: Split, SplitAbove, MergeBelow, Tree.Upsert. No verb ever touches every row; the policy (Policy, DefaultPolicy) only reads per-cluster counts and radii.

What is in it

area names
clustering RunSampled, RunSampledSpherical, RunSampledBudget, SampleSize, Split, SplitSpherical, SplitAbove, MergeBelow
centroid tree Build, Tree, Tree.Nearest, Tree.Upsert, MarshalBinary, UnmarshalTree
sizing HoodK, DefaultNprobe, Policy, DefaultPolicy
quantizer Quantize, Quantizer, Code, Query, Scorer, Scorer.ScoreAndBound, Rotation
codecs AppendF16, DecodeF16Into (round to nearest even), AppendI8, DecodeI8Into (half away from zero, saturating)
kernels Dot, L2Sq, CosineSim, Score, Dots
scoring LateInteractionScore, ValidateLateInteraction
types Vector[T], Rows[T], Sparse[T], Metric (L2, Cosine, InnerProduct)
recall tuning (recall) New, Controller, Offer, Due, Measure, Tuned, Set, Source, Knobs, Depth, Overlap
rank (rank) Hit, TopK, Select, Fusion, RRF

Rank

github.com/axiomhq/ivfq/rank orders hits by score descending, ties by id ascending.

  1. Select the top k as you score: sel := rank.NewTopK(k), sel.Push(id, score) per candidate, then sel.Hits(). rank.Select(hits, k) does the same for a slice.
  2. Fuse ranked legs: rank.RRF(k, legs...), or rank.Fusion{RankConstant: c, Weights: w}.RRF(k, legs...) after Validate(len(legs)).
  3. Late interaction: ivfq.LateInteractionScore(metric, queryTokens, docTokens) sums, over query tokens, the best document-token score. Check inputs with ValidateLateInteraction first.

Tune recall

github.com/axiomhq/ivfq/recall holds an index at a recall@k target by moving two knobs from a sample of live queries.

  1. Build one controller: c := recall.New(recall.Config{}) (target 0.95, 1 in 100 queries, 30 s between measurements).
  2. Run each query at c.Tuned(recall.Key{Index: name, Field: field}).
  3. After it, if c.Offer(name) and c.Due(name), call c.Measure(ctx, key, src), in the background if you like.

What it tunes:

knob range order
Knobs.Probes MinProbes (16) to 2 × DefaultNprobe spent first, bought back second
Knobs.Depth, clusters the bound-pruned rerank reads None, 8, 16, 32, 64, Unbounded bought back first, spent second

What src (a recall.Source, one sampled query on one view) gives it:

method returns
Clusters() cluster count, and how many are cached
Search(ctx, knobs) top-k ids at those knobs, and whether it answered exactly anyway
Exact(ctx) the true top-k ids
Reranked() rows live queries' rerank read since the last call

Guarantees:

  • Never below the floor: probes stay at or above 16, and a move that drops recall more than 0.02 under the target is undone and its value pinned as a floor for good.
  • Only tunes on warm data: under 99% of clusters cached, Measure returns ErrCold before either arm runs.
  • One knob per move, at least MoveSamples (5) samples apart, so each sample measures one change.
  • Filtered queries tune probes on their own and keep an unbounded depth.
  • No I/O, no goroutines. State lives in memory; Set restores it.

K-means seeds with greedy k-means++ and assigns in one parallel pass; the result is bit-identical whatever GOMAXPROCS is.

Kernels

Every SIMD kernel has a pure Go reference and a test that pins it. amd64 picks the kernel at run time from golang.org/x/sys/cpu; every other architecture, and amd64 without the flags, runs the Go reference.

kernel amd64 path needs claim test
Dots dotsAVX2FMA AVX2 + FMA each out[r] equals Dot(q, row r) bit for bit TestDotsMatchesDot
1-bit scan bitProductAVX2 AVX2 + POPCNT popcounts identical to the Go loop TestBitProductMatchesGeneric
rotation rotatePairsAVX2 AVX2 no FMA, so equal to the Go loop bit for bit TestRotatePairsMatchesApply
i8 codec decodeI8AVX2, encodeI8AVX2 AVX2 same bytes and floats as the scalar codec TestI8CodecsMatchScalar

Dot, L2Sq and CosineSim keep several float32 accumulator lanes, so they can differ from a float64 loop by about 1e-7 relative. Rankings do not change, but centroids are only reproducible against a fixed kernel: treat a kernel change like a seed change.

Benchmark

BenchmarkBitScore, 10,000 rows of 128 dimensions, AMD EPYC 7502P (AVX2), Go 1.27, n=10:

per 10k rows per row
1-bit scan, estimate and bound 427.6 µs ± 1% 43 ns
f32 L2Sq over raw rows 258.9 µs ± 2% 26 ns

Test

go test -race ./...
go test -run '^$' -bench BitScore -count 10 .

License

MIT, see LICENSE.

Documentation

Overview

Package ivfq is inverted-file clustering plus quantization: the two halves of an IVF index in the FAISS sense ("IVF + quantizer").

The clustering half partitions vectors into hoods: k-means (plain, spherical, and sample-trained), the centroid Tree and its Nearest lookup, splits and merges, and the rebalancing Policy. The quantization half gives every hood a candidate column and an exact rerank: Vector[T], Rows, Sparse, Rotation, Quantizer, the 1-bit RaBitQ Code and its Scorer, and the SIMD kernels under them (Dot, L2Sq, CosineSim, Dots, the bit products). LateInteractionScore scores multi-vector documents token by token; package rank selects and fuses the results. No I/O.

Index

Constants

View Source
const (
	MergeMax = 3

	// HoodTarget is the vectors-per-neighborhood the sizing rule aims at.
	// It is the ONE constant that makes a query's cost constant in N: three
	// things are proportional to it and they pull opposite ways — candidates
	// scored per query is nprobe x HoodTarget, pack bytes per hood is
	// HoodTarget x dims x 4 (512 KiB at 128 dims, one S3 GET's worth and the
	// unit the byte cache evicts), and the centroid set both the query and
	// the build must scan is N/HoodTarget.
	//
	// 1024 was CHOSEN, not swept: it makes the 1M index 977 hoods against the
	// 1,000 the old rule gave, so the 1M measurements are a controlled A/B on
	// one corpus rather than a comparison of two different indexes. A sweep
	// over {512, 2048, 4096} at 1M is the obvious follow-up and has not been
	// run. The reasoning: fixed-size neighborhoods.
	HoodTarget = 1024

	// CandidateBudget is how many candidates a default query is allowed to
	// score. 100,000 is what the sqrt-sized index spent at 1M for recall
	// 0.968, so the default is the old default, made constant in N.
	CandidateBudget = 100_000
)

Variables

This section is empty.

Functions

func AppendF16

func AppendF16(dst []byte, v []float32) []byte

AppendF16 appends EncodeF16(v) to dst.

func AppendI8

func AppendI8(dst []byte, v []float32) []byte

AppendI8 appends EncodeI8(v) to dst.

func CosineSim

func CosineSim(a, b []float32) float32

CosineSim returns cosine similarity (higher = more similar). Zero vectors score 0.

func DecodeF16

func DecodeF16(b []byte) []float32

func DecodeF16Into

func DecodeF16Into(dst []float32, b []byte)

DecodeF16Into decodes len(dst) values of b into dst.

func DecodeI8

func DecodeI8(b []byte) []float32

func DecodeI8Into

func DecodeI8Into(dst []float32, b []byte)

DecodeI8Into decodes len(dst) values of b into dst.

func DefaultNprobe

func DefaultNprobe(k int) int

DefaultNprobe is how many hoods a query probes when the caller does not name a number and no recall controller has tuned the namespace. It is also where the controller starts and what its ceiling is a multiple of (engine/recall_tune.go), so it is a starting point rather than the last word. Two bounds, and the smaller wins:

max(budgetNprobe, k/32)  the FLOOR: a constant candidate budget, raised
                         to a fixed fraction of the index once that is
                         bigger, because a constant budget does not hold
                         recall (see recallProbeDiv).
max(16, k/4)             the CEILING: never read more than a quarter of
                         the hoods by default once there are enough of
                         them to matter.

The ceiling exists because the budget alone made the default an EXACT scan just below its own size: a 100,000-vector index has 98 hoods and the budget asks for 98, so the default read every one — 4.42 ms measured, for recall the index did not need. The quarter it now reads there is 24 hoods: recall@10 1.000 at 1.12 ms, 24,641 candidates against 100,000. Above ~400,000 vectors the ceiling is never the binding bound and 1M and 10M are untouched. Below 64 hoods it floors at 16, which is at or above k for every namespace the bootstrap threshold allows, so a small namespace still probes everything and answers exactly.

func Dot

func Dot(a, b []float32) float32

Dot returns the inner product. With precomputed squared norms it gives a squared distance without the sqrt L2Sq pays: |a-b|^2 = |a|^2 + |b|^2 - 2 a.b. The subtraction loses a few low bits when a and b are much longer than their difference, so callers rank with it; they do not report it.

func Dots

func Dots(q, block, out []float32)

Dots sets out[r] to Dot(q, block[r*len(q):(r+1)*len(q)]) for every row of block, bit for bit — the same kernel sequence go-simd runs per row — in one call: a centroid tree ranks a node's hundred children at a time, and at 16 dimensions the call per child cost more than the arithmetic.

func EncodeF16

func EncodeF16(v []float32) []byte

EncodeF16 stores v as little-endian IEEE binary16, round-to-nearest-even; out-of-range values become ±Inf (callers validate with float16.Fromfloat32(x).IsInf(0) before storing).

func EncodeI8

func EncodeI8(v []float32) []byte

EncodeI8 rounds to the nearest integer, ties away from zero, and saturates to [-128,127]. This is an implementation choice because the public docs do not prescribe conversion of floating-point inputs to i8 storage.

func HoodK

func HoodK(total int) int

HoodK is the sizing rule: k = ceil(total / HoodTarget), so hood size is constant in N and hood COUNT carries the growth. It replaces round(sqrt(total)), under which both count and size grew as sqrt(N) and candidates per query therefore grew linearly in N. Identical to the old rule for total <= 256; larger for everything above, by design.

func HoodSize

func HoodSize(total int) int

HoodSize is the per-hood target HoodK implies at this total: HoodTarget once the namespace is big enough to want more than hoodFloor hoods, and total/k below that. Split and merge are stated against THIS, not against HoodTarget directly, so the small-namespace floor does not make every hood look tiny and merge the index into one pack.

func L2Sq

func L2Sq(a, b []float32) float32

L2Sq returns squared euclidean distance. Squared preserves ranking and skips the sqrt. (floats has no squared form, so the sqrt is paid and undone — still 2.4x the scalar loop it replaced.)

func LateInteractionScore added in v0.3.0

func LateInteractionScore(metric string, query, document [][]float32) float32

LateInteractionScore sums each query token's best document-token score. Inputs must be validated nonempty matrices of the same width. In particular, a negative best match contributes its negative score, not zero.

func MaxTrainN

func MaxTrainN() int

MaxTrainN reports that count. ResetMaxTrainN zeroes it.

func MergeBelow

func MergeBelow(total int) int

MergeBelow is the hood size under which a hood is a wasted probe slot and should be absorbed by its nearest neighbor. Never below MergeMax, so the pre-existing "singleton hoods merge" behavior survives at any size.

func Nearest

func Nearest(centroids [][]float32, v []float32) int

Nearest returns the index of the L2-nearest centroid.

func Normalize

func Normalize(v []float32)

Normalize scales v to unit length in place. A zero-norm v (degenerate antipodal cluster mean) is left unnormalized.

func ResetMaxTrainN

func ResetMaxTrainN()

func RoundF16

func RoundF16(v []float32) []float32

RoundF16 is DecodeF16(EncodeF16(v)), except that it returns v itself, allocating nothing, when every value already is an f16 value.

func RoundI8

func RoundI8(v []float32) []float32

RoundI8 is DecodeI8(EncodeI8(v)), except that it returns v itself, allocating nothing, when every value already is an i8 value — as every row read back from an i8 column is. -0 is not: it decodes as +0.

func RoundSqrt

func RoundSqrt(total int) int

RoundSqrt is the k heuristic: about √N neighborhoods of about √N vectors.

func RunSampled

func RunSampled(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)

RunSampled fits k centroids on a deterministic random sample of at most SampleSize(k) vectors, then assigns EVERY vector in one parallel pass (assignAll). This is the only k-means the build runs at scale: with fixed-size hoods k = N/HoodTarget, so global Lloyd's would be O(N^2/S) per iteration — eleven passes of it at 10M is hours. Sampling collapses the iterated term to the sample and leaves exactly one O(N x k) pass.

Identical to Run when the sample covers the corpus, so small namespaces (and every existing test) get the full fit unchanged.

func RunSampledBudget

func RunSampledBudget(ctx context.Context, vecs [][]float32, k, iters int, seed int64, bytes int) ([][]float32, []int, error)

func RunSampledSpherical

func RunSampledSpherical(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)

RunSampledSpherical is RunSampled for cosine namespaces.

func RunSampledSphericalBudget

func RunSampledSphericalBudget(ctx context.Context, vecs [][]float32, k, iters int, seed int64, bytes int) ([][]float32, []int, error)

func SampleSize

func SampleSize(k int) int

SampleSize is the training-set bound: NOTHING in a build may call Lloyd's with more vectors than this. It is the property that makes the build linear-ish in N — training is O(SampleSize(k) x k x dims) whatever N is, and the only pass that touches all N vectors is one assignment.

func SampleSizeForBudget

func SampleSizeForBudget(k, dims, bytes int) int

SampleSizeForBudget additionally caps the training vectors by their raw float32 footprint. It never returns zero for a non-empty build.

func Score

func Score(metric string, q, v []float32) float32

Score converts a metric into a uniform "higher = better" score.

func Seed

func Seed(parts ...string) uint64

Seed is the rotation seed a namespace's field uses: FNV-1a over the namespace and field names. Deriving it rather than drawing it keeps every hood of a field in ONE frame, so a query rotates once per hood and the cache above holds one entry — while two different fields, and two different namespaces, still get independent rotations. The value is written into every codes part anyway, so a reader never re-derives it and changing this function cannot strand existing packs.

func Split

func Split(ctx context.Context, vecs [][]float32, seed int64) ([][]float32, []int, error)

Split is 2-means: the cluster-split primitive. A cancelled ctx returns its error and no result, as Run.

func SplitAbove

func SplitAbove(total int) int

SplitAbove is the band's MAXIMUM: the hood size past which the policy owes a split (SplitTarget's size trigger, 1.4x the target). It is stated here rather than inlined at the trigger because a hood no longer has to wait for a verb to learn it: a rewrite that leaves a hood above this splits it inside the rewrite, the way SPFresh's LIRE splits a posting inside the insert that overflowed it, and both readers of the rule have to agree on the same number. 1,432 at a million vectors.

func SplitSpherical

func SplitSpherical(ctx context.Context, vecs [][]float32, seed int64) ([][]float32, []int, error)

SplitSpherical is Split's spherical counterpart.

func TotalCount

func TotalCount(stats []ClusterStat) int

TotalCount sums a stats slice — the live vector count the split and merge thresholds are stated against. Both triggers are relative to the size the sizing rule wants at THIS total, so neither needs the policy to be told N.

func ValidateLateInteraction added in v0.3.0

func ValidateLateInteraction(tokens [][]float32, dims int) error

ValidateLateInteraction checks a nonempty matrix of finite, fixed-width tokens.

Types

type ClusterStat

type ClusterStat struct {
	ID, Count int
	Radius    float64
	Hits      int
}

ClusterStat is one hood as the manifest records it. Count is the number of vectors the hood's PACK holds and Radius the mean distance from those members to its centroid, both written by whichever verb last rewrote the hood — so both are exact, delete-aware by construction (a deleted id is removed from its pack in the cycle that deletes it), and free to read. Radius == 0 means either "every member is the same point" or "emptied, awaiting reclaim"; either way it is not splittable evidence. Hits is query heat since the last cycle, and is 0 on a detached cycle.

type Code

type Code struct {
	// Words is rows x ceil(dims/64) little-endian bit rows: bit j of row i
	// is word[i*w + j/64] >> (j%64).
	Words []uint64
	// Centroid is the hood's own mean, in the ORIGINAL frame, subtracted
	// before rotation. It is the codec's, not the manifest's: a patched
	// hood's members drift from the centroid set they were filed under, and
	// the estimator's accuracy is a function of how short the residuals
	// are, so the codec carries the centroid it actually encoded against.
	Centroid []float32
	// Norms is ||o - c|| per row, and Aligns is <x_b, x> per row: the two
	// scalars the estimator needs. Aligns is zeroRowAlign for a row whose
	// vector has no direction at all (a zero vector in a cosine namespace),
	// which scores 0 the way CosineSim scores it.
	Norms  []float32
	Aligns []float32
	// Seed is the rotation the bits live in (rotate.go). Stored rather than
	// derived so a reader never has to agree with the writer about how a
	// seed is computed.
	Seed uint64
	// Unit says the rows are unit vectors: cosine namespaces quantize the
	// residual of the NORMALIZED vector, so the estimator's squared
	// distance maps to cosine as 1 - d^2/2.
	Unit bool
	// contains filtered or unexported fields
}

Code is the 1-bit payload of a Codes. Rows are indexed the same way the int8 payload's are: by the hood's row order, which is the ids column's order, which is what the candidate pass labels a score with.

func (*Code) Rows

func (b *Code) Rows() int

Rows is how many code rows the payload holds.

type Codes

type Codes = Quantizer

Codes keeps the name existing importers already use.

type DefaultPolicy

type DefaultPolicy struct{}

DefaultPolicy is the one production policy. The Policy interface exists so tests can substitute a stub that names a verb unconditionally; there is no second shipped policy. SplitTarget is answered by a verb bounded by a single hood:

  • SplitTarget: size, then radius, for the hood one verb from the band.

func (DefaultPolicy) Bootstrap

func (DefaultPolicy) Bootstrap(total int) (int, bool)

func (DefaultPolicy) SplitTarget

func (DefaultPolicy) SplitTarget(clusters []ClusterStat) (int, bool)

type Metric

type Metric int

Metric names a Distance.

const (
	L2 Metric = iota
	Cosine
	InnerProduct
)

type Number

type Number interface {
	~float32 | ~float64 | ~int8 | ~int16 | ~int32 | ~uint8 | ~uint16
}

Number is every element type a Vector may hold.

type Options

type Options struct {
	Dims   int
	Metric string
	Seed   uint64
}

Options is what Encode needs beyond the vectors: the field's declared width (an empty hood still publishes a shaped column), the metric (cosine hoods encode unit vectors), and the rotation seed.

type Policy

type Policy interface {
	// Bootstrap: no index exists; total = live vector count from the winner
	// scan. ok=false leaves the namespace unindexed this cycle. This is the
	// ONE pass over all N vectors the design allows.
	Bootstrap(total int) (k int, ok bool)
	// SplitTarget: consulted AFTER the append pass with post-append counts.
	SplitTarget(clusters []ClusterStat) (id int, ok bool)
}

Policy implementations must be safe for concurrent use; the shipped policies are stateless.

Every trigger past Bootstrap is stated on []ClusterStat and nothing else, and that is the point: a ClusterStat slice is read straight out of the manifest, so consulting the policy costs O(k) arithmetic and no pass over the vectors. There is deliberately NO whole-index trigger any more — the drift-gated full recluster this interface used to carry (ReclusterK, with its IndexStats of additive and live counts) was the last thing in the engine that could decide, on its own, to touch all N vectors. It is gone, and so is the regional re-fit that briefly replaced it; split, merge and reclaim are the whole vocabulary, and an explicit recluster is the only verb that still rebuilds a whole index when a human asks for it.

type Quantizer

type Quantizer struct {
	Dims int
	// Code is the payload. Non-nil for anything UnmarshalBinary returned.
	Code *Code
}

Codes is one hood's candidate column: the bytes the probe wave moves and the kernel scores. There is ONE codec — RaBitQ 1-bit residuals (rabitq.go), dims BITS plus 8 bytes per row, with a bound that holds at boundConfidence — and this type is the seam the engine sees.

Until 2026-09-15 there were two, selected by Config.CandidateCodes, and a hood's payload said which one it held so mixed generations read. The per-vector symmetric int8 codec (DQC2) is gone: it cost dims BYTES plus 16 a row against 1-bit's dims bits plus 8, which on SIFT1M was 105.3 stored bytes a row against 27.8, and the one thing it bought — a bound that cannot be exceeded — is bought back where it is actually wanted by Query.Exact.

func AppendRows

func AppendRows(c Quantizer, vectors [][]float32) (Quantizer, error)

AppendRows returns a copy of the column with one freshly encoded row per vector, appended in order, encoded against the column's OWN centroid, seed and metric frame. The zero-vector rule carries over: a zero vector appended to a cosine column becomes a zeroRowAlign row.

It is the other half of copying codes between packs: the few rows that move INTO a split's new hood from a neighbouring one are re-encoded against the copied column's centroid, so the whole column stays one frame without re-quantizing the rows that were copied verbatim.

func Empty

func Empty(centroid []float32, opts Options) (Quantizer, error)

Empty returns a column with no rows around centroid, in opts' frame: what AppendRows grows one block at a time, so every block of a cluster is encoded against the cluster's own centroid rather than the mean of whichever rows happened to start the block.

func Quantize

func Quantize(vectors [][]float32, opts Options) (Quantizer, error)

Quantize is the ONE door a hood's codes are written through. vectors are the hood's rows in id order, already at the precision the exact rerank will read them at.

func UnmarshalBinary

func UnmarshalBinary(data []byte) (Quantizer, error)

UnmarshalBinary decodes MarshalBinary output. Everything a row's score and bound rest on is checked there (rabitq.go, unmarshalBits), because the candidate pass prunes the exact rerank with these values before any full vector is read.

func UnmarshalBinaryBorrowed

func UnmarshalBinaryBorrowed(data []byte) (Quantizer, error)

UnmarshalBinaryBorrowed validates codes like UnmarshalBinary, but keeps scalar and bit rows in data. The caller must keep data immutable and alive.

func (Quantizer) MarshalBinary

func (c Quantizer) MarshalBinary() ([]byte, error)

func (Quantizer) Retained

func (c Quantizer) Retained() int

Retained is what a decoded column holds in memory, for the byte cache's accounting.

func (Quantizer) Rows

func (c Quantizer) Rows() int

Count is how many code rows this column holds — one per vector the manifest counted, which is what CheckParts holds it to.

func (*Quantizer) SameFrame

func (c *Quantizer) SameFrame(o *Quantizer) bool

SameFrame reports whether o's rows were encoded exactly as c's.

func (Quantizer) Score

func (c Quantizer) Score(q Query, row int) float32

Score is the one-off form of Scorer.Score: it binds the query for a single row. Tests and oracles use it; the candidate pass does not, because the binding is O(dims).

func (Quantizer) ScoreAndBound

func (c Quantizer) ScoreAndBound(q Query, row int) (score, bound float32)

ScoreAndBound is the one-off form of Scorer.ScoreAndBound.

func (*Quantizer) Scorer

func (c *Quantizer) Scorer(q Query) Scorer

Scorer prepares q against this column.

func (Quantizer) Select

func (c Quantizer) Select(rows []int) (Quantizer, error)

Select returns a column holding only the rows at the given indexes, in that order, sharing the source column's centroid, seed and metric frame. Every per-row scalar and bit is copied verbatim, so a copied row decodes, scores and bounds exactly as it did in the source column.

This is the read-and-reassemble half of copying codes between packs: a split writes each half's rows out of the source hood's column instead of quantizing them again. A column is self-consistent around the ONE centroid its rows are residuals to, so rows may only be combined with rows of a column carrying that same centroid — that is what AppendRows is for.

func (Quantizer) UpperBound

func (c Quantizer) UpperBound(q Query, row int) float32

UpperBound is the one-off form of ScoreAndBound's bound.

type Query

type Query struct {
	Vector []float32
	Metric string
	// Exact drops the bound: every row's bound is +Inf, so the bound-pruned
	// pass reads every row and the answer is exactly the top k over the
	// probed hoods. It is how a caller buys back the certainty the 1-bit
	// codec's probabilistic bound trades away.
	Exact bool
	// Sigmas overrides boundSigmas for the 1-bit codec (0 = the default).
	// Tests measure coverage against it; the query path sets it from
	// search.Config.BoundSigmas, which the bound-width sweep varies.
	Sigmas float64
	// contains filtered or unexported fields
}

Query is a vector prepared for scoring many rows: the cosine query norm is computed once here rather than per candidate.

func NewQuery

func NewQuery(q []float32, metric string) Query

type Rotation

type Rotation struct {
	// contains filtered or unexported fields
}

The rotation RaBitQ's error bound assumes: a uniformly random orthogonal transform, applied to every residual before it is sign-quantized. It is what makes the quantization error independent of the data's own axes — without it, a corpus whose energy sits in a few dimensions quantizes to a handful of distinct codes and the estimator's variance is whatever the corpus says it is, not O(1/sqrt(D)).

A materialized D x D matrix is out of the question at the dimensions this engine serves: building one is O(D^3) (3.6 GFLOP at 1536 dims), storing it is 9 MB, and applying it to every row of every hood at build time is D^2 per vector. So the rotation is a BUTTERFLY of Givens rotations: a few rounds, each one a random pairing of all D coordinates and a random angle per pair. Every factor is exactly orthogonal, so the product is exactly orthogonal at any D (no power-of-two padding, no code bits spent on a pad), it costs O(D log D) to apply, and it is reproducible from a seed — the pack stores the seed, not the matrix.

rounds is 3 + ceil(log2(D)): each round mixes disjoint pairs, so after log2(D) rounds of random pairings every coordinate has had a path to every other, and the three extra rounds are the mixing margin. The coverage test (TestBitBoundCoversAtItsConfidence, including its axis-aligned corpus) is what actually holds this number honest. Rotation is the butterfly of Givens rotations RaBitQ applies.

func (*Rotation) Apply

func (r *Rotation) Apply(v []float32)

apply rotates v in place. v must be r.dims long.

type Rows

type Rows[T Number] []Vector[T]

Rows is a late-interaction matrix: one Vector per token.

type Scorer

type Scorer struct {
	// contains filtered or unexported fields
}

Scorer binds one column to one query: the per-hood work the paper's estimator needs — the query's residual to THIS hood's centroid, rotated and quantized to four bit planes — which is O(dims) once per probed hood rather than once per row. The candidate pass builds one per hood and scores its rows through it.

A Scorer belongs to the goroutine that made it.

func (Scorer) Rebind

func (s Scorer) Rebind(c *Quantizer, q Query) Scorer

Rebind is Scorer for a column in the same frame as the one s was built on (same centroid, rotation and metric): the query-side work is reused and only the rows change. A cluster of the LSM tier is many 64-row blocks encoded against one centroid, so a probe binds the query once per cluster rather than once per block. A column in another frame is bound afresh.

func (Scorer) Score

func (s Scorer) Score(row int) float32

Score is ScoreAndBound's estimate alone.

func (Scorer) ScoreAndBound

func (s Scorer) ScoreAndBound(row int) (score, bound float32)

ScoreAndBound is the candidate kernel: a higher-is-better estimate of the exact score, and a conservative upper bound on it. A row may be skipped by an exact top-k cutoff only when its bound is below the cutoff.

The bound is boundSigmas standard deviations of the RaBitQ estimator's error and holds at boundConfidence, so "exact within the probed hoods" is a recall guarantee rather than a certainty — unless Query.Exact is set, which is how a caller buys the certainty back.

func (Scorer) With

func (s Scorer) With(c *Quantizer) Scorer

With is Rebind without the frame check, for a caller that has verified the columns share one frame (tier.ClusterView.SameFrame).

type Sparse

type Sparse[T Number] struct {
	Index []uint32
	Value []T
}

Sparse is a coordinate-sparse vector. Index is sorted and unique.

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree is a deterministic hierarchy over a set of leaf centroids.

func Build

func Build(ctx context.Context, centroids [][]float32, fanout int) (Tree, error)

Build constructs a fanout-ary hierarchy. Its fixed seeds make identical inputs deterministic; fanout values below two are promoted to two. A cancelled ctx returns its error and no tree.

func UnmarshalTree

func UnmarshalTree(data []byte) (Tree, error)

UnmarshalTree decodes MarshalBinary output. Counts are checked against the bytes remaining before they size an allocation, and indices against the encoder's invariants: in range, the root is node zero, every child numbered after its parent (Build appends a node before recursing into its children, which is what makes traversal finite), every other node referenced by exactly one parent, every leaf owned by one node, and no node both branches and holds leaves.

func (Tree) Assigner

func (t Tree) Assigner(beam int) func([]float32) int

Assigner ranks one leaf with the same beam traversal as Nearest. Each concurrent caller borrows its own reusable scratch; no per-row tree-sized allocations or unused top-k leaf sort are needed by bulk assignment.

func (Tree) Clone

func (t Tree) Clone() Tree

Clone returns a deep copy of the tree: every centroid, child and leaf list, scan block, and norm slice is duplicated, and the clone's leaves address the clone's blocks. Neither tree can observe the other's Upsert: a decoded tree sits in a shared cache behind concurrent searches, so a caller that means to mutate clones first and swaps the result in.

func (Tree) Dims

func (t Tree) Dims() int

Dims is the width of every centroid in the tree.

func (Tree) Evaluations

func (t Tree) Evaluations(q []float32, probe int) ([]int, int)

Evaluations is Nearest with the number of centroid distance evaluations.

func (Tree) Height

func (t Tree) Height() int

Height returns the number of node levels, including the root and leaves.

func (Tree) Leaf

func (t Tree) Leaf(id int) []float32

Leaf returns leaf id's centroid, aliasing the tree's own storage: read only.

func (Tree) Leaves

func (t Tree) Leaves() int

Leaves is the number of leaf centroids the tree ranks over.

func (Tree) MarshalBinary

func (t Tree) MarshalBinary() ([]byte, error)

MarshalBinary encodes the hierarchy and leaf vectors in a versioned format.

func (Tree) Nearest

func (t Tree) Nearest(q []float32, probe int) []int

Nearest returns up to probe leaf centroid indices, nearest first.

func (Tree) Ranker

func (t Tree) Ranker(probe int) func(q []float32, visit func(id int))

Ranker is Nearest for bulk callers: each call visits the same leaves in the same order as Nearest(q, probe), on scratch borrowed from a pool the concurrent callers share. Nearest allocates its candidate buffer per call; a fold re-routing every member of its moved hoods through it allocated about 45 KB per row, 200 GB for one 4,096-hood fold (measured on a 4,096-cluster re-route).

func (Tree) TwoStageAssigner

func (t Tree) TwoStageAssigner(top int) func([]float32) int

TwoStageAssigner ranks one leaf in two exact stages: a distance for every child of the root, then a distance for every leaf under the best top of them. The beam search prunes at every level, so on a tree deeper than the fan — k-means grouping is never balanced enough to keep one level under the fanout — a miss at any level loses the true centroid for good, and recall only comes back with the beam wide enough to be most of a brute scan. The two-stage search spends its whole budget on the one decision that can miss, which subtree, and is exact everywhere else: 3.2x fewer centroid evaluations than beam 16 at k = 9,766.

Measured, it is a wash for bulk routing: on real BIGANN rows the stage-two subtree scans gather their holders cold and give back the evaluation savings (97.0% exact agreement at top 8 against the beam's 96.8% at the same nanoseconds per row — BenchmarkAssignerBeam in tree_bench_test.go), so the maintainer's router keeps the beam. Small trees are where this wins: at k = 977 a top-4 two-stage reached 99.1% agreement at 2.5x less wall per row than beam 16, because the stage-one fan there is 10 wide and four subtrees cover nearly the whole set. Choose by the benchmark, not by the evaluation count.

func (Tree) TwoStageNearest

func (t Tree) TwoStageNearest(q []float32, top int) ([]int, int)

TwoStageNearest is TwoStageAssigner's search with the picked leaf ids, nearest first, and the number of centroid distance evaluations returned — the pairing Nearest and Evaluations give the beam search.

func (*Tree) Upsert

func (t *Tree) Upsert(id int, v []float32) error

Upsert replaces leaf id's centroid with v, or appends v as a new leaf when id equals the number of leaves; any other id is an error, since appends must stay contiguous. The height never changes and the result round-trips through MarshalBinary and UnmarshalTree.

A replace writes v into the slot the leaf's reference already aliases — index() made t.leaves[id] a sub-slice of the owning holder's block, so one copy serves both views — and refreshes that holder's norm. Internal centroids are deliberately not recomputed: a re-centred hood moves by a fraction of its radius, the beam walks a handful of candidates per level, and holders are ranked by their means, which drift negligibly over a run of upserts. Recentring is what the next full Build is for.

An append descends the hierarchy the way Nearest does (beam = fanout) to find the holder whose centroid is nearest to v, appends the leaf there, and gives that holder a fresh block — holder blocks are sub-slices of the one leaf arena, so growing in place would trample a neighbouring hood — while re-pointing the holder's leaves at the new block. A holder is allowed to grow past the fanout: search scans every leaf of a visited holder, so correctness holds and quality degrades slowly; rebuild once enough upserts have accumulated.

type Vector

type Vector[T Number] []T

Vector is a dense row. Methods type-switch on the instantiation: float32 accumulates in float32 (the SIMD kernels in kernels.go), integers in int32.

Directories

Path Synopsis
Package rank orders scored hits: score descending, ties by id ascending.
Package rank orders scored hits: score descending, ties by id ascending.
Package recall tunes an IVF index's two query knobs, the probe count and the rerank depth, from a sample of live queries.
Package recall tunes an IVF index's two query knobs, the probe count and the rerank depth, from a sample of live queries.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL