ivfq

package module
v0.17.0 Latest Latest
Warning

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

Go to latest
Published: Nov 10, 2026 License: MIT Imports: 14 Imported by: 0

README

ivfq

go get github.com/axiomhq/ivfq

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

package what it holds
ivfq sizing rule (HoodK, DefaultNprobe), Policy, split and merge rules, the centroid trees (FloatTree; Tree[B] over any EmbeddingBatch, such as Dense[T]), the centroid codec, and the distance vocabulary (Metric, Embedding, EmbeddingBatch, Score, Dot, L2Sq, CosineSim)
kmeans Config.Fit: sampled greedy k-means++ with one parallel assignment pass, two-level above kmeans.TwoLevelK centroids; Config.FitBalanced for splits
rabitq 1-bit RaBitQ codes, one bit per dimension plus two float32 per row: Quantize, Quantizer, Scorer, Rotation, and Block for ivfq.Tree
rank top-k selection
codec f16 and int8 row storage
vector Slice: flat float32, f16, int8 or uint8 rows, read as [][]float32
bench Big ANN corpus readers and recall@k

No I/O anywhere but bench.

Build an index

k := ivfq.HoodK(len(vectors)) // clusters of about ivfq.HoodTarget (196) rows
centroids, assign, err := kmeans.Config{K: k, Iters: 11, Seed: 1}.Fit(ctx, vectors)
tree, err := ivfq.Build(ctx, centroids, 32)
rot := rabitq.NewRotation(rabitq.Seed("index", "field"), dims)
codes, err := rabitq.Quantize(rowsOfCluster, rabitq.Options{Metric: ivfq.L2, Rotation: rot})

Fit trains on a sample of at most kmeans.SampleSize(k) rows and assigns every row in one parallel pass; the result is bit-identical whatever GOMAXPROCS is. Above kmeans.TwoLevelK (512) it fits √k coarse centroids, then k fine ones under them, and each row searches only its 16 nearest coarse centroids' fine ones: about 17·√k distances per row, not k. To route rows later, s := tree.NewSearcher() then s.Assign(row, beam), one Searcher per goroutine.

Build returns a FloatTree: exact float32 centroids, Leaf, Upsert and a wire format. For a smaller immutable router, BuildTree builds the same hierarchy and stores every node's rows in a block you choose:

small, err := ivfq.BuildTree(ctx, centroids, 32, ivfq.NewDense[int8])
bits, err := ivfq.BuildTree(ctx, centroids, 32, func(rows [][]float32) (rabitq.Block, error) {
	return rabitq.NewBlock(rows, rot)
})
q, err := ivfq.NewDense[float32]([][]float32{query}) // a dense query
probe, err := bits.Nearest(q.At(0), beam, ivfq.DefaultNprobe(k))

Every block is an EmbeddingBatch: ScoreAll(query, metric, dst) scores a dense query (DenseEmbedding of any scalar) against all its rows, higher is better, and At(i) is row i as an Embedding. Dense scores L2, cosine and inner product of its decoded rows; rabitq.Block holds L2 codes and scores only the L2 estimate. A tree always routes by L2.

Dense[float32] routes exactly as FloatTree, except that a score overflowing to infinity, which FloatTree ranks last, is an error. float16, int8 and uint8 blocks round (integer blocks on one affine scale per block), and rabitq.Block ranks by 1-bit estimates, so it misses some exact neighbours and a dropped branch cannot be reranked back. A Tree keeps no float32 copy of the centroids: keep your own if you need them.

Query

probe := tree.Nearest(query, ivfq.DefaultNprobe(k))
sc := codes.Scorer(rabitq.NewQuery(query, ivfq.L2, rot))
score, bound := sc.ScoreAndBound(row)   // estimate and upper bound
exact := ivfq.Score(ivfq.L2, query, raw) // rerank the shortlist

A row may be skipped by an exact top-k cutoff only when its bound is below the cutoff. The bound is probabilistic; Query.Exact drops it.

For two-pass reranking, Scorer.ScoreAllLazy(scores) collects a BoundHint while scoring. After exactly reranking the shortlist, call Scorer.RefineBounds(scores, bounds, cutoff, hint) to avoid tight bounds for obvious losers. Packed global L2 scoring uses this shortcut; other bindings compute the original bounds. Keep the column unchanged and the cached scores in the current query's row order. Refined bounds support a rising cutoff; preserve the original rescue order and use strict bound < cutoff rejection. ScoreAll still returns every original score and bound bit for bit. See the executable ExampleScorer_RefineBounds in rabitq/quant_test.go.

Splits and merges keep the clusters at their size as rows arrive: a split is kmeans.Config{K: 2, Iters: kmeans.SplitIters}.FitBalanced, which keeps each child at least a quarter of the parent, and Policy, MergeTargets, SplitAbove and MergeBelow decide when, reading only per-cluster counts, radii and centroids. No rule ever touches every row.

Rank

rank orders hits by score descending, NaN last, ties by id ascending. Ids are ints: row or leaf numbers, as the rest of ivfq returns them.

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.

Benchmark data

bench reads the Big ANN corpora and scores recall. Stdlib only.

  1. Read a corpus: b, err := bench.OpenBin(path), defer b.Close(), then b.Next(n) in batches for .u8bin/.i8bin/.fbin. A sample cut from a corpus keeps the corpus header; read the rows you need, since reading past its end reports a truncation.
  2. Read the ground truth: bench.ReadGroundTruth(path) for .ibin.
  3. Score: bench.RecallAtK(got, truth, 10).
  4. CPU time: bench.CPUSeconds() before and after a run.

Kernels

Every SIMD kernel lives in internal/simd beside a pure Go reference and a test that pins it to that reference; amd64 picks the kernel at run time from golang.org/x/sys/cpu, and every other architecture runs the reference.

Dot, L2Sq and CosineSim keep several float32 accumulator lanes, so they can differ from a float64 loop by about 1e-7 relative. That can reorder near ties, and a narrow beam that breaks a tie differently reaches different leaves, so rankings and 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 ./rabitq

License

MIT, see LICENSE.

Documentation

Overview

Package ivfq is the clustering half of an IVF index in the FAISS sense ("IVF + quantizer"): the sizing rule that keeps clusters at about HoodTarget vectors, the centroid trees a query probes, the split and merge rules that hold cluster sizes between rebuilds, the Policy that names the next cluster to split, and a binary codec for centroid sets and their deltas. It also holds the distance vocabulary every subpackage shares: Metric, Score, Dot, L2Sq and CosineSim.

The sizing rule is the package's central claim: k = HoodK(N) = ceil(N/HoodTarget), so clusters hold about HoodTarget vectors whatever N is and cluster COUNT carries the growth. A default query probes DefaultNprobe(k) clusters, which is not constant in N and cannot be: flat IVF recall tracks the fraction of the corpus scanned, and no sizing changes that. What fixed-size clusters buy is a better index at whatever budget is chosen, and a far cheaper build, because kmeans fits them on a sample. After the build nothing here asks for a pass over N: Policy and MergeTargets read only per-cluster counts, radii and centroids, which an index already holds, and rebuilding an index is a caller's explicit decision.

The other halves are subpackages: kmeans fits the centroids, rabitq gives every cluster a 1-bit candidate column with a scorer and an error bound, rank selects hits by int id, codec stores rows at f16 and int8, vector reads flat float32, f16, int8 or uint8 input as float32 rows, and bench reads the standard ANN corpora. No I/O anywhere but bench.

Index

Examples

Constants

View Source
const (
	MergeMax = 3

	// HoodTarget is the vectors-per-neighborhood the sizing rule aims at,
	// the one constant that keeps hood size 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 (98 KiB at 128 dims: one object read and the unit a cache
	// evicts), and the centroid set both the query and the build must scan
	// is N/HoodTarget.
	//
	// The sizing rule aims at 196 rows, a soft target with headroom under
	// MaxHoodRows: a hood born at the hard cap splits again at its first
	// growth, and that churn was half the rows a backlog ingested.
	HoodTarget = 196

	// MaxHoodRows is the hard ceiling on live rows in a published dense
	// hood (DefaultPolicy.MaxHoodRows); the caller's capacity pass enforces it
	// beyond the geometric splits.
	MaxHoodRows = 256

	// 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

View Source
var ErrCorrupt = errors.New("ivfq: corrupt")

ErrCorrupt wraps every decode failure of a centroid set or delta.

Functions

func ApplyCentroidDeltas added in v0.4.0

func ApplyCentroidDeltas(base [][]float32, deltas ...[]CentroidUpsert) ([][]float32, error)

ApplyCentroidDeltas folds deltas, oldest first, over a base set. The base slice is not mutated; its vectors are shared. A slot past the end of the set (a gap) is corruption: appends are contiguous by construction.

func Centroid added in v0.4.0

func Centroid(vecs [][]float32, dims int, spherical bool) ([]float32, float64)

Centroid is the mean of the dims-wide vectors (spherical: normalized) and their mean distance to it; nil for none. Vectors of another width are skipped.

func CosineSim

func CosineSim(a, b []float32) float32

CosineSim returns cosine similarity (higher = more similar). Zero vectors score 0, and so do vectors so small that their float32 squared norms underflow (coordinates about 1e-23 or below), with growing error on the way there; Dense's cosine sums such vectors in float64 instead.

func DecodeCentroids added in v0.4.0

func DecodeCentroids(data []byte, dims int) ([][]float32, error)

DecodeCentroids reads what EncodeCentroids wrote, every centroid dims wide.

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 index. It is also where a recall controller starts and what its ceiling is a multiple of, 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 makes the default an EXACT scan just below its own size: a 100,000-vector index has 511 hoods and the budget asks for 511, so the default would read every one, for recall the index does not need. The ceiling reads 127 there. Above ~400,000 vectors the ceiling is never the binding bound. Below 64 hoods it floors at 16, so an index of up to 16 hoods (3,136 vectors) 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, in one call.

func EncodeCentroidDelta added in v0.4.0

func EncodeCentroidDelta(entries []CentroidUpsert) []byte

EncodeCentroidDelta writes upserts as: magic, dims, count, then per entry the slot and the vector. The dims are carried so a delta applied to the wrong field fails on its header, not on a misaligned float.

func EncodeCentroids added in v0.4.0

func EncodeCentroids(cs [][]float32) []byte

EncodeCentroids writes a little-endian uint32 count, then each centroid's float32 values.

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. Under round(sqrt(total)) both count and size grow as sqrt(N), and candidates per query therefore grow linearly in N. The two rules agree up to 272 vectors; HoodK is no larger up to HoodTarget² (38,416) and larger above it, by design.

func HoodSize

func HoodSize(total int) int

HoodSize is the per-hood target HoodK implies at this total: HoodTarget once the index 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-index 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.

func MeanDistance added in v0.4.0

func MeanDistance(vecs [][]float32, c []float32) float64

MeanDistance is the mean Euclidean distance from c to the vectors as wide as c; 0 for none.

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 singleton hoods merge at any size.

func MergeOwed added in v0.4.0

func MergeOwed(stats []ClusterStat) bool

MergeOwed reports an empty cluster (reclaim) or a tiny one with room somewhere to merge into. MergeTargets refuses a merge past the split trigger, so a tiny no cluster has room for owes nothing: counting it would buy a rebalancing cycle that declines every time.

func MergeTargets added in v0.9.0

func MergeTargets(stats []ClusterStat, centroids [][]float32, busy func(i int) bool, n int) [][2]int

MergeTargets plans up to n merges at once: pairs of a tiny cluster and the nearest cluster to absorb it, the smallest tinies first, each tiny merging into its nearest neighbour when that neighbour stays at or under the split trigger with its rows. A merge past the trigger undoes the split that made the tiny, and the next cycle splits the host again: a lopsided 2-means split leaves a child under MergeBelow, the child's nearest cluster is its sibling, and the layout alternates split and merge on every cycle, forever. A tiny with no such neighbour stays until it grows. The size trigger is the one mirrored: a merge can still widen a host past the radius trigger.

No cluster is in two pairs, and none busy reports (nil: none) is in any: a tiny whose nearest neighbour is busy or already paired waits for a later call rather than taking its second nearest. centroids[i] is stats[i]'s centroid; pairs index stats as {tiny, host}. At most mergeTries distance scans (k × dims each) per pair wanted; they run on GOMAXPROCS goroutines, a batch of tinies per pass over the centroids.

func Normalize

func Normalize(v []float32)

Normalize scales v to unit length in place. A zero-norm v is left as is.

func RoundSqrt

func RoundSqrt(total int) int

RoundSqrt is round(√total), the k rule HoodK replaced: about √N neighborhoods of about √N vectors. HoodK keeps it as its small-index floor.

func Score

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

Score is q against v under metric as a "higher is better" score: the negated squared distance for L2, the similarity for Cosine, the inner product for InnerProduct. An unknown Metric is a programming error and panics.

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 rewrite that leaves a hood above this may split 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. 273 at a million vectors.

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.

Types

type CentroidUpsert added in v0.4.0

type CentroidUpsert struct {
	ID  int
	Vec []float32
}

CentroidUpsert is one entry of a centroid delta: the vector now at slot ID, which is either an existing slot (a recentred cluster) or one past the last (a cluster a split added), or, with a nil Vec, the set cut to its first ID slots (the last entry of a delta, after its upserts). A caller that drops a cluster moves the last one into its slot and cuts the end, so a merge is two entries and not a full set.

func CentroidDelta added in v0.4.0

func CentroidDelta(prev, next [][]float32, limit int) ([]CentroidUpsert, bool)

CentroidDelta reports the upserts that turn prev into next when next keeps every slot of prev in place and only replaces or appends at most limit slots. Callers pass max(2, len(prev)/16): small enough that a delta stays cheap to apply on every load, and at least two so a split always qualifies. ok=false means write a full set: slots moved or vanished, or more than limit changed.

func DecodeCentroidDelta added in v0.4.0

func DecodeCentroidDelta(data []byte, dims int) ([]CentroidUpsert, error)

DecodeCentroidDelta reads what EncodeCentroidDelta wrote. Like DecodeCentroids it grows with bytes actually read, so a lying count dies on its first truncated entry instead of sizing an allocation.

type ClusterStat

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

ClusterStat is one hood as its index records it. Count is the number of vectors the hood holds and Radius the mean distance from those members to its centroid, both measured by whatever last rewrote the hood, so both are exact 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 DefaultPolicy

type DefaultPolicy struct{}

DefaultPolicy is the one shipped Policy. SplitTarget answers with one hood, chosen by size and then by radius.

func (DefaultPolicy) Bootstrap

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

func (DefaultPolicy) MaxHoodRows added in v0.16.0

func (DefaultPolicy) MaxHoodRows() int

MaxHoodRows opts this policy into a hard publication cap (MaxHoodRows). Engines without capacity enforcement may still temporarily exceed it.

func (DefaultPolicy) SplitTarget

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

type Dense added in v0.17.0

type Dense[T vector.Scalar] struct {
	// contains filtered or unexported fields
}

Dense is an EmbeddingBatch of rows stored as T and decoded to float32 to score. NewDense[T] is its encoder for BuildTree.

float32 rows are kept exactly. float16 rows are rounded to the nearest IEEE binary16 value; a coordinate that rounds past ±65504 (|x| ≥ 65520) is an error, not an infinity. int8 and uint8 rows are codes on one affine scale per block, because tree means are fractional: the block's [min, max] coordinate range maps onto all 256 codes, scale = (max-min)/255 and offset = min - scale*(T's minimum), a coordinate x is stored as round((x-offset)/scale), halves away from zero, clamped to T's range, and decodes to offset + scale*code, within scale/2 of x up to float32 rounding. A block whose coordinates are all equal decodes them exactly.

Scores are of the decoded rows, not the coordinates before encoding, exactly as a Dense[float32] of the decoded rows would score them: -(‖q‖² + ‖row‖² - 2·q·row) for L2, from float32 q·row and squared norms combined in float64 (FloatTree's ranking distance negated); q·row for InnerProduct; and q·row/(‖q‖‖row‖) from the same terms for Cosine, except that a row or query whose squared norm is under 2⁻⁶⁰ is summed wholly in float64, so a tiny nonzero vector is not mistaken for zero. Cosine is 0 when either vector is exactly zero.

func NewDense added in v0.17.0

func NewDense[T vector.Scalar](rows [][]float32) (Dense[T], error)

NewDense encodes rows, which must be nonempty, equally wide, at least one-dimensional and finite, and each row as encoded must have a finite float32 squared norm (FloatTree's rule: no coordinate past about 1.8e19). It copies them and keeps no float32 copy unless T is float32.

func (Dense[T]) At added in v0.17.0

func (d Dense[T]) At(i int) Embedding

At implements EmbeddingBatch.

func (Dense[T]) Dims added in v0.17.0

func (d Dense[T]) Dims() int

Dims is the width of every row.

func (Dense[T]) Len added in v0.17.0

func (d Dense[T]) Len() int

Len is the number of rows.

func (Dense[T]) ScoreAll added in v0.17.0

func (d Dense[T]) ScoreAll(query Embedding, metric Metric, dst []float32) error

ScoreAll implements EmbeddingBatch for a dense query, a DenseEmbedding of any scalar, under L2, Cosine or InnerProduct. It reads a float32 query in place and decodes any other, and a non-float32 block a row at a time, into scratch of its own. A finite query far from a row can overflow to an infinite score, which is an error.

type DenseEmbedding added in v0.17.0

type DenseEmbedding[T vector.Scalar] struct {
	// contains filtered or unexported fields
}

DenseEmbedding is row i of a Dense[T], from Dense.At: a read-only view that keeps the block, with its scale and offset, alive. It is also the dense query every Score and ScoreAll in this module takes; to score a []float32 q, use NewDense[float32]([][]float32{q}) and At(0), once per query: At allocates its interface value on every call.

func (DenseEmbedding[T]) Decode added in v0.17.0

func (e DenseEmbedding[T]) Decode(dst []float32) error

Decode copies the row's Dims decoded coordinates into dst, which must be at least that long, and leaves dst[Dims:] as it was. The values are what the block scores: float16 decoded as IEEE binary16, int8 and uint8 as offset + scale*code. Decode keeps nothing of dst, and dst never aliases the block.

func (DenseEmbedding[T]) Dims added in v0.17.0

func (e DenseEmbedding[T]) Dims() int

Dims is the row's width.

func (DenseEmbedding[T]) Score added in v0.17.0

func (e DenseEmbedding[T]) Score(query Embedding, metric Metric) (float32, error)

Score implements Embedding as Dense.ScoreAll scores this row.

type DenseEncoder added in v0.17.0

type DenseEncoder[S, T vector.Scalar] struct{}

DenseEncoder is the Encoder from rows of S to Dense[T] blocks. Encode reads S's values as float32 (float16 decoded as IEEE binary16), then encodes them as NewDense[T] does, a row at a time: it borrows rows only for the call, keeps nothing of them, and never builds a float32 copy of the whole input.

func (DenseEncoder[S, T]) Encode added in v0.17.0

func (DenseEncoder[S, T]) Encode(rows vector.Slice[S]) (Dense[T], error)

Encode implements Encoder.

type Embedding added in v0.17.0

type Embedding interface {
	Dims() int
	Score(query Embedding, metric Metric) (float32, error)
}

Embedding is one vector in some representation: a row of a Dense block (DenseEmbedding), of a rabitq.Block, or of any other EmbeddingBatch.

Score is query scored against the receiver, the stored target, under metric, higher is better: the negated squared distance for L2 (up to rounding, so a row equal to the query may score just above 0), the similarity for Cosine (0 when either vector is zero), the inner product for InnerProduct. A representation may score an estimate (RaBitQ does). It returns an error for a query of another width, a query representation or metric the receiver does not score, or a non-finite result. Every receiver in this module takes a dense query (DenseEmbedding of any scalar, the value At returns, not a pointer to it) and no other; none asks the query to score itself instead. Score neither changes nor retains query.

type EmbeddingBatch added in v0.17.0

type EmbeddingBatch interface {
	Len() int
	Dims() int
	At(i int) Embedding
	ScoreAll(query Embedding, metric Metric, dst []float32) error
}

EmbeddingBatch is Len embeddings of one width held together, scored together.

At returns row i as an Embedding: a read-only view that keeps the batch (and how to read it) alive, never shared scratch. It panics, as slice indexing does, when i is not a row.

ScoreAll sets dst[i], for every i < Len(), in row order, to what At(i).Score(query, metric) returns, up to float rounding, and never writes dst[Len():]. It fails as Score does, and when dst is shorter than Len(); after an error dst[:Len()] may be partly written and means nothing. It does not change query, retains neither query nor dst, and dst must not overlap query's or the batch's storage. A batch does not change once built: concurrent ScoreAll calls are safe, each with its own dst.

type Encoder added in v0.17.0

type Encoder[S vector.Scalar, B EmbeddingBatch] interface {
	Encode(rows vector.Slice[S]) (B, error)
}

Encoder encodes rows of S into a block B: DenseEncoder[S, T] makes Dense[T] blocks, rabitq.BlockEncoder[S] rabitq.Blocks, from any source scalar S. Encode borrows rows read-only for the call and returns a block that owns its data, rows in input order; rows must not change during the call.

BuildTree does not take an Encoder: a tree's internal rows are fractional means held as [][]float32, so its encoder is NewDense[T] or a closure over rabitq.NewBlock.

type FloatTree added in v0.17.0

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

FloatTree is a deterministic hierarchy over a set of float32 leaf centroids, kept exactly: it is the tree with Leaf, Upsert, Truncate, Clone and a wire format (MarshalBinary, UnmarshalTree). Tree is the immutable one whose nodes hold caller-encoded centroid blocks.

func Build

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

Build constructs a fanout-ary hierarchy. Its fixed seeds make identical inputs deterministic; fanout values below two are promoted to two. Every centroid must have the first one's length and a finite squared norm, as Upsert requires, or Build returns an error. A cancelled ctx returns its error and no tree.

Example

Route a query to its nearest cluster centroids.

package main

import (
	"context"
	"fmt"

	"github.com/axiomhq/ivfq"
)

func main() {
	centroids := [][]float32{{0, 0}, {10, 0}, {0, 10}, {10, 10}}
	tree, err := ivfq.Build(context.Background(), centroids, 2)
	if err != nil {
		panic(err)
	}
	fmt.Println(tree.Nearest([]float32{9, 1}, 1))
}
Output:
[1]

func UnmarshalTree

func UnmarshalTree(data []byte) (FloatTree, 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 (*FloatTree) ApplyCentroidDeltas added in v0.17.0

func (t *FloatTree) ApplyCentroidDeltas(deltas [][]CentroidUpsert) error

ApplyCentroidDeltas upserts deltas, oldest first, into t in place. An error leaves t with the entries before it applied, so apply to a Clone when t must survive a bad delta.

func (FloatTree) Clone added in v0.17.0

func (t FloatTree) Clone() FloatTree

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 (FloatTree) Dims added in v0.17.0

func (t FloatTree) Dims() int

Dims is the width of every centroid in the tree.

func (FloatTree) EvaluationsBeam added in v0.17.0

func (t FloatTree) EvaluationsBeam(q []float32, beam, probe int) ([]int, int)

EvaluationsBeam is Nearest with the number of centroid distance evaluations and the beam set apart from probe (Nearest's beam is probe): the search keeps beam nodes per level and ranks every leaf under them, so it scans every leaf only once beam covers every level's width. Leaves are ranked exactly; a narrower beam can only miss a leaf under a node it dropped. beam may be smaller than probe, and the result is still the probe nearest leaves the beam reached.

func (FloatTree) EvaluationsBeamI8Work added in v0.17.0

func (t FloatTree) EvaluationsBeamI8Work(q []float32, beam, probe int) ([]int, TreeWork)

EvaluationsBeamI8Work is EvaluationsBeam, the same leaves in the same order, with the leaf scan read through the holders' int8 copies (QuantizeI8). The beam over internal nodes is EvaluationsBeam's own, in float32, so it visits the same holders. Each scanned leaf gets an int8 distance and an exact bound on its error,

|<q,c> - <q~,c~>| <= ||q|| ||c - c~|| + ||q - q~|| ||c~||

and its float32 distance is computed, as EvaluationsBeam computes it, only for the probe nearest by int8 and for any other leaf whose lower bound is within the probe-th float32 distance so far. TreeWork counts both kinds of distance. A tree without its int8 copies (not quantized, or changed since) is searched by EvaluationsBeam.

func (FloatTree) Height added in v0.17.0

func (t FloatTree) Height() int

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

func (FloatTree) Leaf added in v0.17.0

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

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

func (FloatTree) Leaves added in v0.17.0

func (t FloatTree) Leaves() int

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

func (FloatTree) MarshalBinary added in v0.17.0

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

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

func (FloatTree) Nearest added in v0.17.0

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

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

func (*FloatTree) NewSearcher added in v0.17.0

func (t *FloatTree) NewSearcher() *Searcher

NewSearcher returns a Searcher over t. t must not change while the Searcher is in use.

func (*FloatTree) QuantizeI8 added in v0.17.0

func (t *FloatTree) QuantizeI8()

QuantizeI8 gives every leaf holder an int8 copy of its leaves for EvaluationsBeamI8Work: a quarter of the bytes the leaf scan reads, which at 768 dimensions was 12.7 MB a query. It is derived, never serialized, and dropped by Clone and by any change to the tree (Upsert, Truncate), after which EvaluationsBeamI8Work reads the float32 leaves until QuantizeI8 runs again. It writes t, so call it before t is shared.

func (*FloatTree) Truncate added in v0.17.0

func (t *FloatTree) Truncate(n int) error

Truncate cuts the tree to its first n leaves, each later leaf detached from its holder. Internal centroids stay, as they do under Upsert, and a holder may be left empty; the next Build rebalances.

func (*FloatTree) Upsert added in v0.17.0

func (t *FloatTree) 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, and so is a vector whose squared norm is not a finite float32 (a NaN or infinite coordinate, or a huge one). The height never changes and the result round-trips through MarshalBinary and UnmarshalTree.

A replace moves the leaf to the holder nearest to v (replace), so a slot refilled with a far centroid stays reachable. Internal centroids are deliberately not recomputed: 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 Metric

type Metric int

Metric is the distance a field is scored with. The zero value is L2.

const (
	L2           Metric = iota // squared euclidean distance, negated by Score
	Cosine                     // cosine similarity
	InnerProduct               // inner product
)

func ParseMetric added in v0.5.0

func ParseMetric(s string) (Metric, error)

ParseMetric is the inverse of Metric.String: "l2", "cosine" or "ip".

func (Metric) MarshalText added in v0.5.0

func (m Metric) MarshalText() ([]byte, error)

MarshalText implements encoding.TextMarshaler, so a Metric reads and writes as its name in JSON and other text configs.

func (Metric) String added in v0.5.0

func (m Metric) String() string

func (*Metric) UnmarshalText added in v0.5.0

func (m *Metric) UnmarshalText(text []byte) error

UnmarshalText implements encoding.TextUnmarshaler.

type Policy

type Policy interface {
	// Bootstrap: no index exists and total is the live vector count.
	// ok=false leaves the index unbuilt this cycle. The build that follows
	// 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: per-cluster counts and radii are what an index already holds, so consulting the policy costs O(k) arithmetic and no pass over the vectors. There is deliberately NO whole-index trigger: nothing a Policy answers can ask for a pass over every vector. Split, merge and reclaim are the whole vocabulary, and rebuilding an index is a caller's explicit decision.

type Searcher added in v0.5.0

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

Searcher is Nearest, Assign and TwoStageAssign with scratch that survives between calls: a warm Searcher allocates nothing per query, where FloatTree.Nearest allocates its result. It belongs to one goroutine; a bulk caller makes one per worker.

func (*Searcher) Assign added in v0.5.0

func (s *Searcher) Assign(q []float32, beam int) int

Assign is the leaf a beam-wide search ranks first, or -1 when the tree is empty or q is the wrong width: the same leaf Nearest(q, beam)[0] names.

func (*Searcher) Nearest added in v0.5.0

func (s *Searcher) Nearest(q []float32, probe int) []int

Nearest is FloatTree.Nearest: up to probe leaf ids, nearest first, in the same order. The slice is the Searcher's own and the next call overwrites it.

func (*Searcher) TwoStageAssign added in v0.5.0

func (s *Searcher) TwoStageAssign(q []float32, top int) int

TwoStageAssign ranks one leaf in two exact stages: a distance for every child of the root, then a distance for every leaf under the top subtrees, then returns the nearest such leaf, or -1.

On large trees the stage-two scan is the whole cost and Assign's beam pruning wins. Small trees are where this wins: with a narrow root fan a few subtrees cover nearly the whole set (at k = 977, a top-4 two-stage reached 99.1% agreement at 2.5x less wall per row on BIGANN). Choose by measured wall time, not by the evaluation count.

type Tree

type Tree[B EmbeddingBatch] struct {
	// contains filtered or unexported fields
}

Tree is FloatTree's hierarchy with every node's rows (child means for an internal node, leaf centroids for a leaf holder) held as one encoded block B: Tree[Dense[float32]], Tree[Dense[float16.Float16]], Tree[Dense[int8]], Tree[Dense[uint8]] or Tree[rabitq.Block]. A search scores each node's rows with B.ScoreAll under L2, whatever metric the field uses, and compares scores across blocks, so every block of one tree must score L2 on one scale. The tree keeps the topology and, per row, the child node or original leaf id; the blocks keep everything else. There is no float32 copy beside the blocks, so a lossy B cannot return a leaf's original centroid; a caller that needs them keeps its own.

A Tree is immutable and safe for concurrent searches.

func BuildTree added in v0.17.0

func BuildTree[B EmbeddingBatch](ctx context.Context, centroids [][]float32, fanout int, encode func(rows [][]float32) (B, error)) (Tree[B], error)

BuildTree builds the hierarchy Build builds over centroids, from the same float32 working coordinates (each internal row is the mean of the leaves beneath it), then calls encode once per node with that node's rows and keeps only the blocks it returns. The rows are read-only and valid only during the call: a block copies what it keeps. Centroids follow Build's rules and must be at least one-dimensional. An encoder error, or a block whose Len or Dims disagrees with its rows, fails the build; so does a ctx cancelled at any point before BuildTree returns, even over no centroids.

func (Tree[B]) Dims

func (t Tree[B]) Dims() int

Dims is the width of every centroid in the tree.

func (Tree[B]) Leaves

func (t Tree[B]) Leaves() int

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

func (Tree[B]) Nearest

func (t Tree[B]) Nearest(q Embedding, beam, probe int) ([]int, error)

Nearest returns up to probe leaf ids, nearest first, ties by lower id. It keeps the beam best nodes per level by their blocks' L2 scores and ranks every leaf of the holders it reaches, as FloatTree.EvaluationsBeam does; with B = Dense[float32] and no score overflowing, the result is EvaluationsBeam's. An empty tree, or a beam or probe below one, returns nil, nil without looking at q. Otherwise the first error a block's ScoreAll returns (a q of the wrong width or representation, an infinite score) is Nearest's, with no ids.

type TreeWork added in v0.16.0

type TreeWork struct {
	Float32, Quantized int
}

TreeWork is a tree search's centroid work: Float32 is the float32 distances it computed, internal nodes included, and Quantized the int8 leaf distances it computed beside them. Every centroid a search scores is in one of the two.

Directories

Path Synopsis
Package bench reads Big ANN benchmark corpora and ground truth (.u8bin/.i8bin/.fbin/.ibin), scores recall@k, and reads process CPU time.
Package bench reads Big ANN benchmark corpora and ground truth (.u8bin/.i8bin/.fbin/.ibin), scores recall@k, and reads process CPU time.
Package codec stores float32 rows at reduced precision: IEEE binary16 (round to nearest even) and int8 (round half away from zero, saturating).
Package codec stores float32 rows at reduced precision: IEEE binary16 (round to nearest even) and int8 (round half away from zero, saturating).
internal
simd
Package simd holds the numeric kernels every ivfq package scores with: the float32 distances, the block dot product the centroid tree ranks with, the 1-bit popcount products, the Walsh-Hadamard rotation and the quantizers behind rabitq, and the int8 codec.
Package simd holds the numeric kernels every ivfq package scores with: the float32 distances, the block dot product the centroid tree ranks with, the 1-bit popcount products, the Walsh-Hadamard rotation and the quantizers behind rabitq, and the int8 codec.
Package kmeans fits centroids for an IVF index: sampled greedy k-means++ with one parallel assignment pass, two-level above TwoLevelK, and the size-floored 2-means a cluster split uses.
Package kmeans fits centroids for an IVF index: sampled greedy k-means++ with one parallel assignment pass, two-level above TwoLevelK, and the size-floored 2-means a cluster split uses.
Package rabitq is the 1-bit candidate codec of an IVF index: RaBitQ (Gao & Long, SIGMOD 2024, arXiv:2405.12497).
Package rabitq is the 1-bit candidate codec of an IVF index: RaBitQ (Gao & Long, SIGMOD 2024, arXiv:2405.12497).
Package rank orders scored hits: score descending, NaN last, ties by id ascending.
Package rank orders scored hits: score descending, NaN last, ties by id ascending.
Package vector is the typed input shape for dense rows: one flat, row-major buffer of a supported scalar type and its width.
Package vector is the typed input shape for dense rows: one flat, row-major buffer of a supported scalar type and its width.

Jump to

Keyboard shortcuts

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