Documentation
¶
Overview ¶
Package ann is the dense (semantic) retriever. v1 is a flat brute-force cosine scan — the "vicinity" equivalent in docs/DESIGN.md §1. HNSW lands later behind this same Hit/Query shape; flat is exact and fine at repo scale.
Invariants the rest of the codebase depends on:
- **Input vectors are L2-normalized.** embed.StaticModel.Encode normalizes its output before returning, so cosine similarity is just the dot product — Query computes that, not a full ‖a‖‖b‖-divided cosine. Passing non-normalized vectors silently produces incorrect rankings; the precision contract lives at the embed boundary, not here.
- **Scores are float32-precision.** Query scores each vector with the SIMD dot kernel (linalg.Dot, float32 accumulation), not a float64 scalar sum. For unit-norm float32 inputs the per-element error is bounded and recall is unaffected; only sub-ULP near-ties may order differently than an exact float64 scan would. The ascending-Index tie-break still makes the result deterministic.
- **Similarity, not distance.** semble's dense backend (vicinity) returns cosine *distance* (1 − sim) and search.py flips it back to similarity; ken skips the round-trip and scores similarity directly, with "higher = better." Anything reading the Score field must treat it that way.
- **Goroutine-safety.** A built *Flat is read-only — Query takes no locks and is safe to call concurrently across goroutines. New is not thread-safe (single builder); Query is.
- **No mutation.** *Flat is immutable after New, by design. v0.3's incremental indexing (internal/search/watch.go, ADR-012) does not mutate an existing *Flat — instead the writer builds a brand-new *Flat alongside a new *bm25.Index + chunks slice, wraps them in a new *search.Index snapshot, and publishes the pointer atomically. Readers load the snapshot pointer once at query entry. So Flat stays goroutine-safe-by-immutability; what changes is that the containing search.Index can be swapped wholesale between queries.
Example ¶
Exact cosine search over a set of L2-normalized vectors (the normalization contract lives at the embed boundary; ann assumes unit vectors and scores by dot product, higher = better).
package main
import (
"fmt"
"github.com/townsendmerino/aikit/ann"
)
func main() {
vecs := [][]float32{
{1, 0}, // 0
{0, 1}, // 1
{0.6, 0.8}, // 2 — unit length
}
idx := ann.New(vecs)
for _, h := range idx.Query([]float32{1, 0}, 2) {
fmt.Printf("%d %.2f\n", h.Index, h.Score)
}
}
Output: 0 1.00 2 0.60
Example (BaseDeltaFusion) ¶
Serving a changing corpus WITHOUT mutating an index (design rule 4): keep a big immutable base index plus a small, frequently-rebuilt delta of recent docs, query both, and fuse the rankings. Each index's local Hit.Index is mapped to a global doc id; fuse.RRF merges them into one ranking. Periodically fold the delta into a fresh base and swap.
package main
import (
"fmt"
"github.com/townsendmerino/aikit/ann"
"github.com/townsendmerino/aikit/fuse"
)
func main() {
base := ann.New([][]float32{ // global ids 0..2 (the established corpus)
{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0},
})
const baseN = 3
delta := ann.New([][]float32{ // global ids 3..4 (just added)
{0, 0, 0, 1}, {0.7071, 0.7071, 0, 0},
})
q := []float32{0, 1, 0, 0}
fused := fuse.RRF(60,
fuse.Keys(base.Query(q, 10), func(h ann.Hit) int { return h.Index }),
fuse.Keys(delta.Query(q, 10), func(h ann.Hit) int { return baseN + h.Index }),
)
fmt.Printf("fused %d docs from base+delta; top global id %d\n", len(fused), fused[0].Key)
}
Output: fused 5 docs from base+delta; top global id 1
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrFormat = errors.New("ann: malformed or unsupported serialized index")
ErrFormat is returned (wrapped) by every index-loading path — Load (HNSW), LoadFlatI8, and LoadFlatI8Mmap — when the input is not a valid serialized index: a bad magic, an unsupported format version, or a truncated / internally inconsistent blob. Test for it with errors.Is rather than string-matching:
idx, err := ann.LoadFlatI8(blob)
if errors.Is(err, ann.ErrFormat) {
// the bytes are not a usable FlatI8 index (corrupt, or a newer format)
}
I/O failures from LoadFlatI8Mmap (open/mmap) are NOT wrapped with ErrFormat — only the blob's own format errors are.
Functions ¶
This section is empty.
Types ¶
type Config ¶ added in v0.2.0
type Config struct {
// M is the max neighbors per node per layer above 0; layer 0 uses
// 2*M (the standard M0). Higher M ⇒ better recall, more memory and
// slower build. Default 16.
M int
// EfConstruction is the candidate-list size during insertion. Higher
// ⇒ better graph quality (recall) at higher build cost. Default 200.
EfConstruction int
// EfSearch is the default candidate-list size during Query; the
// effective value is max(EfSearch, k). Higher ⇒ better recall, slower
// query. Default 64. Override per-query with QueryEf.
EfSearch int
// Seed seeds the level-assignment RNG for reproducible builds.
Seed uint64
// SimpleNeighbors opts into plain M-nearest neighbor selection (paper
// Algorithm 3) instead of the DEFAULT diversity heuristic (Algorithm 4). The
// heuristic spreads each node's edges across directions rather than piling
// them into one cluster, which sharply improves recall on CLUSTERED data — on
// a real Model2Vec code corpus it lifted recall@10 from 0.68 to 1.00 — at
// roughly 2× build cost (query cost unchanged). Set this only to trade that
// recall for a faster build. See selectHeuristic.
SimpleNeighbors bool
// Int8 stores the vectors as int8 (per-vector symmetric quantization) instead
// of float32 — ¼ the vector memory, and the persisted/embedded blob shrinks to
// match. Build, search, and persistence all run in the integer domain. Recall
// is essentially unchanged on real embeddings (the int8 quantization is the
// same that FlatI8 uses; see TestHNSW_int8RecallGate). Experimental.
Int8 bool
}
Config tunes the graph. Zero values fall back to the documented defaults, so Config{} is a sensible build.
type Flat ¶
type Flat struct {
// contains filtered or unexported fields
}
Flat is an exhaustive cosine index over a fixed set of unit vectors.
func (*Flat) Query ¶
Query returns the k highest cosine-similarity vectors to q, descending, ties broken by ascending index for determinism. k<=0 or k>=Len returns all, sorted.
Two paths by design:
- k<=0 || k>=Len: full sort over every dot-product result. Preserves the documented "return all, sorted" semantic for callers that want the complete ranked list.
- 0 < k < Len: min-heap of size K via internal/topk. O(N log K) vs the full-sort path's O(N log N) — at medium scale (~378k chunks, k=10) this was 30.88% of hybrid search CPU per ADR-025. Final sort.SliceStable imposes the ascending-Index tie-break the doc comment promises, which the heap on its own doesn't guarantee (heap only sorts by score; ties within result come out in heap-internal order). The K-sized stable sort is O(K log K) — cheap at K=10.
func (*Flat) QueryFilter ¶ added in v1.2.0
QueryFilter is Query restricted to documents for which keep(id) is true — a logical-delete / live-set filter applied at query time, so the index stays immutable. Exact for Flat (it scores every vector and filters before selecting), unlike the approximate HNSW.QueryFilter. A nil keep is exactly Query.
type FlatI8 ¶ added in v1.2.0
type FlatI8 struct {
// contains filtered or unexported fields
}
FlatI8 is the int8-quantized sibling of Flat: it stores each indexed vector as int8 codes plus a per-vector float32 scale — a quarter of Flat's float32 footprint — and scores a query by int8×int8 dot product. It exposes the same Hit / Query(q, k) shape as Flat, so it drops into the same fuse.RRF flow and is a swap-in where memory matters more than the last fraction of recall.
The win is exactly aikit's niche: embedded, single-binary, RAM-constrained retrieval (and a 4× smaller blob to //go:embed). The cost is a small recall hit from quantization — tiny for the L2-normalized embeddings this index is built for, since every component lands in a bounded range and gets ~1/127 resolution.
Scoring reuses linalg's W8A8 kernel: the query is dynamically quantized to int8, dotted against the stored int8 vectors in the integer domain (SIMD, parallel over the corpus), and rescaled by the query and per-vector scales. So this is W8A8 at M=1 — the same math the quantized decode path uses.
Like Flat, a built *FlatI8 is read-only and Query is safe to call concurrently; NewFlatI8 is the single-threaded builder.
Example ¶
FlatI8 is a drop-in for Flat that stores vectors as int8 (¼ the memory) and scores via the int8 W8A8 kernel — for embedded / RAM-constrained retrieval, at a small recall cost. Same Hit / Query(q, k) shape, so it also feeds fuse.RRF.
package main
import (
"fmt"
"github.com/townsendmerino/aikit/ann"
)
func main() {
vecs := [][]float32{
{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1},
}
ix := ann.NewFlatI8(vecs) // stored as int8 + per-vector scales
hits := ix.Query([]float32{0.1, 0.2, 0.95, 0.1}, 1)
fmt.Println("nearest doc:", hits[0].Index)
}
Output: nearest doc: 2
func LoadFlatI8 ¶ added in v1.3.0
LoadFlatI8 reconstructs an index from MarshalBinary's output, copying the codes into the Go heap. The returned *FlatI8 is query-ready and read-only-safe for concurrent Query; the bytes are not retained. Returns an error for a bad magic, an unsupported version, or any truncated/inconsistent blob — never a panic. Use LoadFlatI8Mmap to avoid the copy for a large embedded index.
func LoadFlatI8Mmap ¶ added in v1.3.0
LoadFlatI8Mmap loads a FlatI8 index by memory-mapping path and ALIASING the int8 codes directly from the mapping — zero-copy. So a large embedded index is query-ready instantly (no parse-and-copy of the n×dim codes into the heap) and its bytes live in the shared OS page cache rather than the Go heap. Only the small scales block (n floats) is copied. On non-unix platforms the file is heap-read instead (identical result, no page-cache benefit). For a plain in-memory copy from a byte slice, use LoadFlatI8.
Lifetime: the returned *FlatI8 aliases the mapping, so keep it reachable for as long as you Query it; a finalizer unmaps it once it becomes unreachable. Close releases the mapping eagerly — and Query after Close panics, so only Close when you are done:
// WRONG — released while still in use.
f, _ := ann.LoadFlatI8Mmap("index.bin")
f.Close()
f.Query(q, 10) // panics: codes unmapped
// RIGHT — Close (or just let GC unmap it) only after the last query.
f, _ := ann.LoadFlatI8Mmap("index.bin")
defer f.Close()
hits := f.Query(q, 10)
func NewFlatI8 ¶ added in v1.2.0
NewFlatI8 builds an int8 index by quantizing vecs (each assumed L2-normalized, the package invariant) to int8 + per-vector scales. The float32 inputs are not retained — only the int8 codes and scales — so the index holds ~¼ the bytes. All vectors are treated as dimension len(vecs[0]); a shorter vector is zero-padded and a longer one truncated (the embed pipeline yields a uniform dimension, so this is just defensive).
func (*FlatI8) Close ¶ added in v1.3.0
Close releases the mapping of a LoadFlatI8Mmap index. It is a no-op (and leaves the index queryable) for an in-memory index from NewFlatI8 / LoadFlatI8, and is idempotent. After Close on a mapped index the codes are unmapped, so Query panics — Close only once you are done querying. Not safe to call concurrently with Query (coordinate the handoff, as with any teardown).
func (*FlatI8) MarshalBinary ¶ added in v1.3.0
MarshalBinary serializes the int8 index (codes + per-vector scales + shape) into a versioned blob that LoadFlatI8 / LoadFlatI8Mmap turn back into a query-ready *FlatI8. It implements encoding.BinaryMarshaler, so the index also round-trips through gob.
The point is the //go:embed pattern: quantize the corpus once offline, embed the bytes, and Load at startup — no float32 vectors, no re-quantization per process.
func (*FlatI8) Query ¶ added in v1.2.0
Query returns the k highest int8-cosine vectors to q, descending, ties broken by ascending index for determinism — the same contract as Flat.Query. k <= 0 or k >= Len returns all, sorted. A query of the wrong dimension returns nil.
func (*FlatI8) QueryFilter ¶ added in v1.2.0
QueryFilter is Query restricted to documents for which keep(id) is true — a logical-delete / live-set filter applied at query time, so the index stays immutable. Exact over the int8 scores. A nil keep is exactly Query.
type HNSW ¶ added in v0.2.0
type HNSW struct {
// contains filtered or unexported fields
}
HNSW is an approximate cosine index. Build with NewHNSW + Add (or BuildHNSW); query with Query. See the type doc for thread-safety.
func BuildHNSW ¶ added in v0.2.0
BuildHNSW builds an index over vecs (used by reference, not copied), added in order. Equivalent to NewHNSW + a loop of Add.
func Load ¶ added in v1.2.0
Load reconstructs an index from MarshalBinary's output — the //go:embed-an-index entry point. The returned *HNSW is query-ready and, like a freshly built one, read-only-safe for concurrent Query. The bytes are not retained (vectors are copied). Returns an error for a bad magic, an unsupported version, or any truncated/inconsistent blob — never a panic.
func NewHNSW ¶ added in v0.2.0
NewHNSW creates an empty index. Add vectors with Add, or use BuildHNSW to bulk-load.
func (*HNSW) Add ¶ added in v0.2.0
Add inserts vec (by reference) and returns its assigned index. Not safe for concurrent use. Panics on a dimension mismatch with vectors already added (a programmer error, like topk's negative-k panic).
func (*HNSW) MarshalBinary ¶ added in v1.2.0
MarshalBinary serializes the built index — graph, vectors, and config — into a versioned byte blob that Load turns back into a query-ready *HNSW. It implements encoding.BinaryMarshaler, so the index also round-trips through gob and friends.
The point is the //go:embed pattern: build the graph once offline, embed the bytes in the binary, and Load them at startup instead of rebuilding per process.
Example ¶
Persist a built HNSW index and reload it — the //go:embed-an-index pattern: build the graph once offline, write MarshalBinary's bytes to a file (or embed them in the binary), and Load them at startup instead of rebuilding per process.
package main
import (
"fmt"
"github.com/townsendmerino/aikit/ann"
)
func main() {
vecs := [][]float32{
{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1},
}
ix := ann.BuildHNSW(vecs, ann.Config{Seed: 1})
blob, err := ix.MarshalBinary() // os.WriteFile("index.hnsw", blob, 0o644), or //go:embed
if err != nil {
panic(err)
}
loaded, err := ann.Load(blob)
if err != nil {
panic(err)
}
hits := loaded.Query([]float32{0.1, 0.1, 0.9, 0.1}, 1)
fmt.Println("nearest doc:", hits[0].Index)
}
Output: nearest doc: 2
func (*HNSW) Query ¶ added in v0.2.0
Query returns the k highest-cosine-similarity vectors to q, descending, ties broken by ascending index — matching Flat.Query's contract. Uses the configured EfSearch (effective ef = max(EfSearch, k)). Returns nil for an empty index or a dimension-mismatched q.
func (*HNSW) QueryEf ¶ added in v0.2.0
QueryEf is Query with an explicit ef (candidate-list size) for this call, the recall/latency knob: larger ef ⇒ higher recall, slower. Effective ef is max(ef, k).
func (*HNSW) QueryFilter ¶ added in v1.2.0
QueryFilter is Query restricted to the documents for which keep(id) is true — a logical-delete / live-set filter applied at query time, so the index stays immutable (the cornerstone). Filtered-out nodes still ROUTE the search, so graph connectivity is intact and live recall holds; they're simply not returned. Under heavy deletion the live result can fall short of k (the search runs out of live nodes within ef) — rebuild the index to purge tombstones when that bites. A nil keep is exactly Query.
Source Files