Vectors: distance kernels, HNSW and exact search

This note is normative for the vector part of a segment: what the kernels compute, how closeness becomes a score, how the graph is built and searched, what the two files contain and how a merge treats them. Measured results are at the end.

Metrics and scores

A vector field has a metric, chosen in the schema ([Vector(Metric = ...)] or FieldDefinition.Metric) and stored with it.

• The query of a cosine field is scaled the same way. A vector of length 0 stays all zeros (its cosine with anything is taken as 0, score 0.5). The stored source keeps the original vector; the vectors file keeps the scaled one, which is what TryGetVector returns.
• Documents with a NaN or an infinity in a vector are rejected when added (ArgumentException), and so are such queries.
• A document may lack a vector. A vector field holds one vector per document (no multi-valued vector fields yet).
• Scores are monotone in the distance, so ranking by score is ranking by distance. Ties break towards the smaller document id.

Distance kernels

OneIndex.Kernels.VectorKernels (internal, no dependency on the rest of the engine) computes dot product, squared Euclidean distance and sum of squares over float, and dot product and squared distance over sbyte.

• One result on every machine. The float order of additions is fixed by the kernel, not by the instruction set: element i goes to lane i mod 16, in index order, with a separate multiply and add (never a fused multiply-add); the sixteen lanes are folded by halves (j with j+8, then j+4, j+2, j+1). A 512-bit register is those sixteen lanes, 256-bit code keeps two registers, 128-bit code four, scalar code sixteen variables. A tail shorter than 16 is padded with zeros, which adds exactly zero. All widths, and x64 and arm64, therefore return the same bits, so a graph built on one machine is the graph built on any other. The tests assert bit equality against the scalar path for lengths 0 to 300 and compare with a double-precision sum.
• Special values. No flushing or clamping: denormals take part at full precision, infinities follow IEEE 754, a NaN input gives a NaN result (payload unspecified). Indexed data and queries are checked finite before they reach a kernel.
• Width. Vector512, Vector256 or Vector128 is chosen once from IsHardwareAccelerated (false for 512 bits on processors where the runtime judges it slower); Vector128 is also the WebAssembly SIMD path and the arm64 AdvSimd path. The scalar path is the fallback and the reference.
• Integer kernels widen to 16 bits, multiply, widen to 32 bits and add; integer sums are exact so every width agrees. Dot product accepts up to 131,071 elements and squared distance up to 32,768 without overflowing int; longer inputs throw.
• Files with unsafe constructs, Unsafe.*, MemoryMarshal or intrinsics: Kernels/VectorKernels.cs (loads through Vector128/256/512.LoadUnsafe behind a length check made once per call, and fixed 16-float stackalloc tail buffers), Kernels/QuantizedKernels.cs (the same loads for the 4-bit dot product, and a byte-to-signed-byte reinterpretation), Codecs/VectorPartReader.cs and Codecs/VectorSegmentCodec.cs and Codecs/VectorFiles.cs (MemoryMarshal.Cast between the bytes of a checked block and the floats or ints in it; bounds are those of the block), Vectors/HnswBuilder.cs is entirely safe code.

Exact search

FlatSearch compares the query with every accepted vector and keeps the best k in a bounded heap. It serves segments below the field's flat threshold (default 1,000 vectors; they get no graph), is used when a filter is selective (below), and is the ground truth that the recall measurements and the durability checks use. FlatSearch.SearchBatch answers many queries in one pass over the vectors, a tile of 128 vectors at a time against all queries, which is the shape of a matrix product.

HNSW

Implemented from Malkov and Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", IEEE TPAMI 42(4), 2020 (arXiv:1603.09320): algorithm 1 (INSERT), 2 (SEARCH-LAYER), 4 (SELECT-NEIGHBORS-HEURISTIC, no extended candidates; connections dropped by pruning are not refilled, which is the default of an internal switch) and 5 (K-NN-SEARCH).

• Parameters per field: M (default 16; layer 0 allows 2M, the paper's Mmax0; see the deviation below), efConstruction (default 100), flat threshold (default 1,000). Search breadth ef is a query parameter (KnnQuery.Ef); 0 uses max(k, 100).
• Layer 0 keeps up to 2M links chosen at insertion (the paper chooses M and lets reverse links grow a list to Mmax0). Measured on the 384-dimension set (150,000 vectors) at the same build time, recall 0.90 is reached at ef 220 instead of 270. The upper layers choose M.
• Software prefetch was tried and dropped. Collecting a node's unvisited neighbours and reading the first cache line of each before scoring (which overlaps the memory reads without any intrinsic) changed the throughput at ef 220 by -3 to +7 percent across five settings, which is inside the noise of repeated runs on a shared host (medians 1035 to 1141 queries per second, minima 812 to 969), so the plain loop stays.
• Layer assignment draws the number of times in a row a 64-bit hash of (field seed, node number) is divisible by M: the same distribution as the paper's floor(-ln(uniform) * 1/ln M) (P(level >= l) = M^-l) without a logarithm, whose last bit could differ between platforms. The field seed is a fixed constant xor the CRC-32C of the field name. Levels stop at 24.
• Deterministic build. One thread, no clock, no random generator: the same vectors in the same order give the same graph on every machine (kernels above). Tests build twice and compare every link.
• Deletes. A deleted document stays in the graph, because removing it can cut paths. Search walks through it and leaves it out of the results. A segment with many deletes is rebuilt by the merge policy like any other.
• Filters. A query may carry a filter (a query whose matches are the allowed documents). The segment turns it into a bit set, and the search is described under "Filtered search" below.

Merge

A merge builds the merged segment's graph over the live vectors of the sources in their merged order. When the source with the most vectors has a graph with the same M and none of its vectors is deleted, its graph is copied (node numbers moved up by the number of vectors before it) and only the other sources' vectors are inserted, in order (the paper's incremental construction; the starting graph is just a valid state to continue from). Otherwise all vectors are inserted. Both are deterministic functions of the merge inputs; the first differs from flushing the same documents in one segment, which is documented, not a defect. The benchmark runner times both.

Files

Both files have the common header (magic, version) and footer (CRC-32C of the file), and both are read through the storage interface by range. Vectors and level-0 links are read in blocks of about 64 KB holding whole records; each block has its own CRC-32C in a table that is checked when the block is first loaded, so opening a segment does not read its vectors and damage is found by the first read that touches it, raising CorruptIndexException with the file name. Loaded blocks stay cached for the life of the reader; reading a cached vector or link neither allocates nor waits. The little-endian layout is read in place, so big-endian platforms are rejected.

vectors (magic OIXV, version 1) after the header: u32 document count of the segment; for each field, in name order: the vectors (count * dims * 4 bytes, float little endian, ordinal order, in blocks), for a segment where not every document has a vector the table of the document of each ordinal (count * 4 bytes, strictly increasing), and the block CRC table (4 bytes per block). Then the directory: field count, and per field the name, dimensions, metric, encoding (0: 32-bit floats; later compressed copies add parts of their own and rerank from this file), count, flags (bit 0: sparse), offsets of the three sections, vectors per block and the CRCs of the document table and of the CRC table. Trailer: directory offset (u64), CRC-32C of the directory (u32).

hnsw (magic OIXH, version 1) after the header: u32 document count; for each field with a graph, in name order: layer 0 as fixed-size records of 2M + 1 ints (link count, then the links, unused slots zero), in blocks with a CRC table; then the upper layers as one checked blob: node count, then for each node above layer 0 its number (as the gap from the previous), its level and, for each layer from 1, the link count and the links (varints). Directory per field: name, node count, M, top level, entry point, offsets, records per block, CRC of the CRC table, offset, length and CRC of the upper-layer blob.

Readers check, before trusting an offset or count: the sections tile the file exactly; counts are within the segment and the limits object; every link is a node other than the one holding it, with at most 2M links on layer 0 and M above; upper-layer links point to nodes that are in that layer; the entry point is in the top layer; the ordinal-to-document table is strictly increasing and inside the segment. A segment smaller than the field's flat threshold has a vectors part and no hnsw part.

Crash behaviour is that of every part: the files are written, fsynced and listed by the commit; a crash before the commit leaves unreferenced files that are reclaimed.

A field declared with VectorIndexKind.Ivf has no graph: its clustered lists are in part ivf (magic OIXL, version 1) and the vectors part is the rerank source; see ivf.md.

Query surfaces

• Low level: KnnQuery(field, vector, k) with Ef, Filter and Exact. It finds the k nearest documents over all segments (each segment's best k, then the best k overall) and scores them; as a clause of a BooleanQuery it combines with text queries. The filter is applied before choosing neighbours; a Filter clause beside it in a boolean query would cut the neighbours afterwards.
• Happy path: index.SearchVector(x => x.Embedding, vector, neighbors: 20) returns a SearchQuery; Where(...) restricts the candidates (before the nearest are chosen), Take/Skip page within the neighbors found.
• Query JSON: {"type":"knn","field":"Embedding","vector":[...],"k":10,"ef":100,"exact":false,"filter":{...},"boost":1}; the tool schema adds one such node per indexed vector field with the vector length fixed.
• A field with a compressed copy is searched on the copy and reranked exactly (next section). Hybrid fusion and reranking by models are separate.

Compressed copies

A vector field may ask for a compressed copy of its vectors ([Vector(Quantization = ...)], FieldDefinition.Quantization). The graph is built on the full-precision vectors, as always; the copy is what a search walks it with. The full-precision vectors stay in the segment and reorder the candidates, so a result's score is always the exact one, whatever the codec.

• Scalar codecs (Veasey, "Understanding optimized scalar quantization", Elasticsearch Labs, 2024). Each vector gets its own interval [a, b]; component x becomes the code round((2^n - 1)(clamp(x, a, b) - a) / (b - a)). The interval starts at the vector's mean plus or minus a fixed number of standard deviations (the normal-distribution optimum: 2.514 for 4 bits, 3.611 for 8) clipped to its min and max, and is refined by up to five rounds of coordinate descent on the paper's anisotropic error with lambda 0.1 (an error parallel to the vector counts ten times an error perpendicular to it): for fixed codes the best (a, b) solves a 2 by 2 linear system, which is solved in closed form, and a round that does not lower the error is discarded. The record keeps the codes, then a, the step (b - a) / (2^n - 1), the sum of the codes and the squared length of the original vector (little-endian float, float, int, float). Expanding (a_x + s_x X)(a_y + s_y Y) over the d components gives the dot product from the integer X . Y, the two sums and the intervals; for the Euclidean metric the squared distance is |x|^2 + |y|^2 - 2 x . y. The query is compressed to 8 bits with the same procedure whatever the document codec (the paper quantizes the query with at least 4). Int8 codes are stored as code - 128 so the signed-byte kernel applies (a moves by 128 * step). Int4 codes are packed so that byte j holds component j in its low nibble and component ceil(d/2) + j in its high nibble, which lets the kernel split a register into two halves without shuffling. Vectors are not centred by a corpus mean, a deviation from the paper that keeps each record self-contained (a merge copies nothing).
• Sign bit keeps one bit per component, set when the component is above zero, and compares by Hamming distance. It needs the cosine or dot-product metric (a Euclidean field with it is a schema error). It is deliberately plain: no per-vector correction, no centering.
• Oversample. A quantized search walks the graph with width = max(ef, ceil(oversample * k)) and keeps the best width candidates by compressed distance; every candidate is then measured against its full-precision vector and the best k are returned (ties towards the smaller ordinal). oversample is a field setting (Oversample, 1 to 100; 0 means the codec default above) and ef is the query's (KnnQuery.Ef; 0 means max(k, 100)), so at the default ef the oversample binds only when oversample * k exceeds 100.
• Exact and small cases use floats. Exact searches, segments below the flat threshold (no graph, so no compressed copy is written), selective filters that fall back to scanning, and walks that exceed their visit limit all use the full-precision vectors.
• Files. Part vecq (magic OIXQ, version 1) beside vectors and hnsw, with the same header, footer and 64 KB blocks with per-block CRC-32C. After the header: u32 document count; for each quantized field with a graph, in name order, its records in blocks and the block CRC table. Directory per field: name, dimensions, codec, record count, record bytes, records per block, data offset, CRC table offset and the CRC of the table. A reader checks that the sections tile the file, that the counts equal the vectors file's, that record and block sizes follow from the codec, and validates each block as it loads (finite correction factors, code sums within range for scalar codecs, zero padding bits after the last dimension for sign bits). Damage raises CorruptIndexException naming the file.
• Schema. Section 4 of the schema record (after section 3): a count, then for each vector field with a codec or an oversample, in ascending field index, the field index, the codec byte and the oversample as the bits of a float. A schema without codecs is written byte for byte as before; a reader that does not know section 4 skips it and searches the full-precision vectors, which is correct, only slower.
• Evolution. Changing the codec or the oversample re-indexes the field from stored source in the background like a metric change. A segment whose compressed copy does not match the schema's codec (written before the change) is searched on full-precision vectors until it is rebuilt.
• Merge writes the compressed copy of the merged segment from its full-precision vectors; nothing is copied from the sources.
• Determinism. Interval selection uses IEEE double arithmetic in a fixed order and integer codes; the integer kernels are exact at every width. The records are therefore the same bytes on every machine (a test hashes 100 records of each codec and passes on x64 and arm64).

Filtered search

A KnnQuery with a Filter (a keyword term, a numeric or date range over a column or point, any query) turns the filter into a bit set of documents per segment and then chooses between two ways of answering. The choice is made per segment, on the number of documents the filter admits.

• Filtered graph walk. After Patel, Kraft, Guestrin and Zaharia, "ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data", SIGMOD 2024 (section 5, search over the predicate subgraph). The upper layers are walked greedily without the filter, as for an unfiltered query. On layer 0 only documents that pass the filter are scored, queued and kept. Where a neighbour fails the filter, its own neighbours are looked at instead (neighbours of neighbours), so a rejected node costs a list read and no distance, and the walk is not cut off from the accepted nodes behind it. A node stops looking through rejected neighbours once it has collected 2M accepted neighbours (32 by default), the length of an unfiltered layer-0 list. The walk ends as the unfiltered one does, when the nearest unexpanded candidate is farther than the ef-th best accepted result. If it finds fewer than min(k, accepted) results (a filter that splits the graph into pieces) the segment scans.
• Exact scan. Below the switch the segment compares the query with every accepted vector (FlatSearch); the result is exact.
• The switch. The scan is taken when the filter admits at most 20 * max(ef, k) documents in the segment. The walk's cost depends on ef and hardly on the selectivity (measured, below), while the scan's cost is proportional to the number of accepted vectors. On 150,000 vectors of 384 dimensions at ef 100 they cost the same at about 1,500 accepted documents (15 times ef), and at ef 40 at about 650, so the break-even is close to linear in ef with a factor of 15. The scan is exact and the walk is not (recall 0.83 to 0.91 at ef 100 where the walk alone is used at 1%), so the scan is taken a little past break-even, where it costs up to 1.3 times the walk. At the default ef of 100 the scan serves segments with up to 2,000 accepted documents, and a larger ef widens that range (a caller asking for more recall gets the exact scan sooner). Compressed copies use the same rule; the scan reads the full-precision vectors.
• Compressed copies. The filtered walk runs on the int8, int4 or sign-bit codes with the same filter, keeps max(ef, oversample * k) accepted candidates, and reranks them with the full-precision vectors, exactly as the unfiltered search does. Deleted documents are rejected nodes in the same way.
• Deviations from the paper. The graph is the ordinary graph. The paper builds ACORN-gamma with a denser neighbour list (expansion factor gamma) so a predicate subgraph stays connected, and describes ACORN-1 with the ordinary degree, which is the variant used here. The second hop is taken only through rejected neighbours (the paper expands every neighbour). The switch to the exact scan is the paper's own fallback for very selective predicates, with a threshold measured here rather than derived.
• Hybrid, facets and sort. The filter belongs to the vector arm (HybridQuery.Vector.Filter), as text filters belong to the text arm. A filtered knn clause is an ordinary query, so facets, sorts and aggregations see the same K documents.

Measured

Method: tools/vector_filtered_rows.sh (bench --mode filtered). The embedding sets above, one segment, ef 100 (the default) and the ef that reaches 0.95 unfiltered (450 at 384 dimensions, 270 at 768, float graph). Recall@10 is against the exact top 10 over the passing documents (brute force). Two filters over the same documents: uncorrelated, a hash of the document number (a keyword term, or a range over a number assigned at random, selects the same way), and correlated, the lowest slice of the projection of the vector on one fixed random direction (a range over a column that follows the vectors' position in space, so a query's neighbours are mostly inside the filter or mostly outside it). Selectivities 50%, 10%, 1% and 0.1%. Keyword, column and point filters reach the search as the same bit set (tests/OneIndex.Tests/FilteredVectorTests.cs runs a keyword term, two numeric ranges and a correlated range through KnnQuery.Filter). Post-filter is the naive alternative: an unfiltered search for ceil(40 / selectivity) neighbours (at most 10,000, with ef at least that), keeping those that pass. Timings are indicative: they ran as queued jobs on a shared 32-core host (x64, AMD Ryzen 9 7950X3D) whose load average was above 15 during the runs; an earlier run on a quiet host (load 4) gave 1.5 to 3 times the queries per second shown. Compare rows with each other, not with the unfiltered table. Recall does not depend on load.

Recall@10 / queries per second, 384 dimensions, 150,000 vectors, float graph, ef 100 (the default):

At ef 450 (384 dimensions): uncorrelated 50% 0.966 / 304 (post-filter 0.954 / 406), 10% 0.984 / 305 (0.938 / 460), 1% and 0.1% 1.000 (exact scan); correlated 50% 0.969 / 303 (0.950 / 361), 10% 0.980 / 282 (0.881 / 455), 1% and 0.1% 1.000 (exact scan; post-filter 0.801 and 0.164).

768 dimensions, 75,000 vectors, float graph, ef 100: uncorrelated 50% 0.905 / 640 (post-filter 0.886 / 1100), 10% 0.938 / 719 (0.948 / 404), 1% 1.000 / 7515 (0.995 / 61), 0.1% 1.000 / 13843 (0.234 / 36); correlated 50% 0.903 / 770 (0.871 / 1100), 10% 0.930 / 971 (0.901 / 309), 1% 1.000 / 5839 (0.859 / 57), 0.1% 1.000 / 12474 (0.158 / 33). At ef 270: 50% 0.961 and 0.962, 10% 0.980 and 0.982, 1% and 0.1% 1.000.

int4 copy (oversample 3, float rerank), 384 dimensions, ef 100: uncorrelated 50% 0.862 / 1029, 10% 0.905 / 1511, 1% 1.000 / 3493, 0.1% 1.000 / 6738; correlated 0.870 / 1196, 0.889 / 2395, 1.000 / 3326, 1.000 / 7060. At ef 450 the recalls are 0.962, 0.981, 1.000, 1.000 (uncorrelated) and 0.967, 0.979, 1.000, 1.000 (correlated). 768 dimensions, ef 100: uncorrelated 0.907 / 1228, 0.938 / 2330, 1.000 / 6882, 1.000 / 13564; correlated 0.903 / 1200, 0.932 / 1499, 1.000 / 7037, 1.000 / 13618; at ef 270: 0.963, 0.983, 1.000, 1.000 and 0.961, 0.980, 1.000, 1.000.

What the rows say:

• Filtered recall at a given ef is about the unfiltered recall at that ef (0.86 to 0.91 at 100, 0.96 to 0.98 at 450 or 270) from 50% down to 10%, and exact below the switch.
• Post-filtering is acceptable only for mild filters. At 50% it is as accurate as the walk at the same ef and faster (it asks for 80 neighbours, hardly more than the walk visits). At 10% it is comparable (uncorrelated) or worse (correlated, 0.87 against 0.90 at ef 100, 0.88 against 0.98 at 450). Below 10% it fails (correlated 1%: 0.80; 0.1%: 0.16 to 0.21, where the 10,000-neighbour cap stops it) or is 30 to 100 times slower than the scan (uncorrelated 1%: 74 against 4,123 queries per second). Post-filtering does not guarantee a full page of k; the walk and the scan return min(k, accepted).
• The walk alone loses recall at 1% (0.83 to 0.91 at ef 100): few accepted nodes are near a query and the second hop is capped. The switch removes that range.
• The second-hop target (2M) was chosen on a sweep from 12 to 64 on the 384-dimension set at 50%, 10% and 4%: a smaller target is faster per ef and loses recall, and at matched recall the curves are close, so 32 stays (it is the length of an unfiltered list).

Information rows (no managed comparator implements a filtered graph search, so there is nothing to gate against): queries per second at the smallest swept ef that reaches the recall, filtered walk with switch, float graph, 384 dimensions at 0.90 / 0.95 recall: uncorrelated 50% 808 (ef 140) / 418 (300), 10% 860 (100) / 607 (200), 1% and 0.1% exact (2621, 5995); correlated 50% 688 / 376, 10% 1064 / 538, 1% and 0.1% exact (3457, 5893). 768 dimensions: uncorrelated 50% 793 (100) / 438 (200), 10% 1677 (70) / 671 (140); correlated 50% 685 / 461, 10% 1414 / 666; exact below. int4, 384 dimensions: uncorrelated 50% 1328 (140) / 352 (450), 10% 3252 / 1055; correlated 50% 1055 / 629, 10% 2005 / 716. Peak resident memory of the 384-dimension process was 980 MB for the float index and 982 MB for the int4 index (150,000 vectors; the process also holds the data and the truth sets).

Method of the measurements

• Embedding sets: tools/embeddings.py (the Wikipedia abstracts of the text benchmarks, BAAI/bge-small-en-v1.5 at 384 and BAAI/bge-base-en-v1.5 at 768 dimensions, text cut to 128 tokens, queries are held-out article titles with the model's query instruction); ground truth is the exact top 100 by dot product computed with numpy.
• Recall: bench/OneIndex.VectorBench (--engine oneindex|oneindex-segment|hnswnet|curiosity), single-threaded build and search, recall@10 against the exact top 10, queries/second as the median of three passes over the query set, ef swept over a grid; the reported row for a target is the smallest ef that reaches it. Hnsw.Net 0.1.4 and curiosity-ai HNSW 26.9.5494 run through their public API (the two cannot be referenced together, so bench/OneIndex.VectorBench.Curiosity is the same runner for the second).
• Compressed copies: tools/vector_codec_table.sh (the oneindex-segment engine with --quant and --oversample); float rows against the comparators: tools/vector_bench_group.sh.
• Kernels: bench/OneIndex.Bench KernelBenchmarks.
• Durability: tests/Durability carries a vector field (flat threshold 3, so merges of tiny segments build and continue graphs); every recovered snapshot is checked for the vector of every live document and for exact nearest neighbours against brute force.
• Filtered search: tools/vector_filtered_rows.sh. The durability workload also runs filtered nearest-neighbour queries (a keyword term and a numeric range) after every recovery and requires every hit to pass the filter and the exact result to equal brute force.
• Fuzz: fuzz target vectors (it includes a filtered walk).

Measured

Embedding sets (BAAI/bge-small-en-v1.5 at 384 dimensions, 150,000 base vectors; BAAI/bge-base-en-v1.5 at 768 dimensions, 75,000 base vectors; 1,000 held-out title queries; the first abstracts of the Wikipedia dump; manifests with SHA-256 are written by tools/embeddings.py). The sets are generated, never committed. M=16, efConstruction=100, one thread for build and search, recall@10 against exact search, ef on a grid (the row for a target is the smallest ef that reaches it, so a row can overshoot its target). Queries per second are the median of three passes. The graph builder takes 1.5 x efConstruction candidates per insertion on layer 0 (see HNSW above).

Float graph against the managed comparators

tools/vector_bench_group.sh, one engine after another on an otherwise idle machine. Hnsw.Net 0.1.4 and curiosity-ai HNSW 26.9.5494 run through their public API.

Machines: x64 is a Ryzen 9 7950X3D (32 threads), .NET 10.0.402, load 3.7 before and 2.9 to 6.7 during; arm64 is an Apple M2 (8 cores), .NET 10.0.403, load about 2 to 4 throughout. Index files are 250.6 MB (384) and 240.5 MB (768) for the vectors file plus the graph; Hnsw.Net's saved index is 253.4 MB and 241.9 MB.

Throughput at matched recall against Hnsw.Net, the faster managed comparator at every target both reach (curiosity-ai's graph only reaches 0.90 at ef 900 on 384 and 450 on 768, and never reaches 0.95 on 384, so it is far behind at matched recall). The ratio is ours over Hnsw.Net, with queries per second linearly interpolated between grid points to the target recall; neither engine reaches 0.99 on 384, so the last 384 row is the best recall both reach (0.98).

Build time against curiosity-ai is 1.57x (384) and 1.71x (768) on x64: its graph builds faster and is much worse (recall 0.933 at ef 1300 on 384).

Native libraries, information only (hnswlib 0.8.0, faiss-cpu 1.15.1 through tools/native/vector_rows.py, run on a busy host, so their throughput is not comparable to the rows above): 384 hnswlib builds in 127 s (contended) and reaches 0.90 at ef 270, 0.95 at 640; faiss builds in 36.5 s and reaches 0.90 at 270, 0.95 at 540. 768: hnswlib 30.9 s, 0.90 at 180, 0.95 at 450, 0.99 at 1800; faiss 24.3 s, 0.90 at 180, 0.95 at 380, 0.99 at 1800.

The first version of this graph needed a larger ef than Hnsw.Net for the same recall. The changes (layer-0 neighbours chosen up to the paper's Mmax0, and a wider candidate list on layer 0 during insertion) follow the paper's parameters and were judged only by recall-against-ef curves of the comparator's public API. The curves (150,000 x 384; recall@10 at ef 140, 220, 450, 1300) were Hnsw.Net .8825, .9138, .9462, .9806; this the first version of this graph reached 0.90 at ef 220 to 270 and 0.95 at 640, and with the changes now in place .8878, .9206, .9543, .9839 (0.90 at 180, 0.95 at 450). On 768 dimensions, factors 1.0, 1.25 and 1.5 reached 0.95 at ef 380, 320 and 270, and cost 64.8 s, 94.0 s and 107.2 s to build on a loaded host (Hnsw.Net 135.7 s in the same job); the factor of 1.5 is the one that keeps the 384-dimension build time at or below Hnsw.Net's (0.98x). Topping connections up with pruned candidates (HnswBuilder.KeepPruned) raised recall at a fixed small ef but lowered throughput at matched recall (50,000 vectors, 0.90: 1540 against 1756 qps; 0.95: 853 against 1048), so it stays off.

Compressed copies

tools/vector_codec_table.sh, segment engine (files on disk, rerank from the full-precision file), k = 10. The search width is max(ef, 10 x oversample), so the ef = 10 column shows each oversample on its own (width 10, 20, 30, 50, 100) and from ef = 100 the oversample no longer binds. Recall is deterministic; queries per second come from a run on a host at load 10 to 25 and are indicative only (single runs vary by a factor of two between neighbouring grid points).

Recall@10 by search width (ef for the float and the bit-o1 rows):

(A quantized row at a width below its oversample times 10 shows the oversample's width: int8 at ef 10 is width 20, int4 width 30.)

The sign-bit codec by oversample, with the default ef of 100 and with ef = k (so the oversample alone sets the width):

What it costs, in words:

• Memory. The graph and the full-precision vectors are in every row; the copy is extra and is read while walking. Per 150,000 x 384 vectors: float vectors 225,014 KB, graph 19,752 KB, int8 copy 58,597 KB, int4 copy 30,470 KB, sign-bit copy 7,031 KB. For 75,000 x 768: int8 57,425 KB, int4 29,298 KB, sign-bit 7,031 KB. Total index bytes: 384: 250.6 MB float, 310.6 MB int8, 281.8 MB int4, 257.8 MB sign-bit; 768: 240.5, 299.3, 270.5, 247.7 MB. Peak process memory while building was 844 to 918 MB for every codec (the build holds the float vectors). The compressed copy buys speed and a smaller working set for the walk, not a smaller index: the float file stays for the rerank.
• Recall. int8 and int4 follow the float curve within 0.01 from a width of 100. The sign bit does not: at width 100 it reaches 0.665 (384) and 0.795 (768), and 0.95 needs a width of about 450 on 768 dimensions (0.944) to 640 (0.962 at ef 640 in the earlier run), while on 384 dimensions it reaches 0.926 at 900 and 0.948 at 1300 and not 0.95. The cause is not established (the sign of an uncentred component carries little when the vectors share a large common offset is a guess; centring on a corpus mean would test it, and this codec deliberately does not centre). Because the oversample only matters while 10 x oversample exceeds ef, the default of 5 binds only at ef below 50; callers who want the high-recall region of this table raise ef (or the oversample, to 45 for width 450).
• Speed. Hamming over 384 bits is 4.5 ns and over 768 bits 8.6 ns per pair against 42 and 74 ns for the float dot product, so a walk is much cheaper per visited node; at equal recall the extra width eats most of it (the sign bit needs a width of 900 for 0.926 on 384 dimensions where the float graph needs 220, so the saving per node is spent on visiting more nodes). int4 at a width of 100 to 450 is about 1.5x to 2.2x the float throughput in the same run.

Kernels

BenchmarkDotNet, in-process short job, mean per call over one pair of vectors, 0 bytes allocated. Width 0 is the scalar path, 1 Vector128, 2 Vector256, 3 Vector512.

The Hamming kernel is population counts over 64-bit words, which the runtime compiles to the hardware instruction on both machines; it has no vector path. All widths give bit-identical results; VectorKernelTests and QuantizedVectorTests pass on both machines.

Code that uses unsafe-class APIs (Unsafe., MemoryMarshal, stackalloc) is limited to Kernels/VectorKernels.cs and Kernels/QuantizedKernels.cs (the SIMD kernels; the 4-bit dot product at 768 dimensions goes from 273 ns scalar to 26.6 ns with Vector256 on x64 and from 281 ns to 49.8 ns with Vector128 on the M2), Codecs/VectorPartReader.cs and Codecs/VectorFiles.cs (bulk conversion of file blocks to floats and integers) and Codecs/VectorSegmentCodec.cs (the same conversions at merge time); each states its bounds where it is used.

Schema record and evolution

The dimension of a vector field is part of its field record. Its other settings (metric, M, efConstruction, flat threshold) are written in schema section 3 (schema format 2: sections are an ascending id and a length-prefixed payload; a reader that does not know a section skips it). Section 3 is a varint count, then per vector field whose settings differ from the defaults, in ascending field index: the field index, the metric byte, M, efConstruction and the flat threshold as varints. A schema whose vector fields all use the defaults is written as format 1, byte for byte what it was before settings existed. Reading rejects a section that names a field that is not a vector, is out of order, is empty, or holds an unknown metric.

On open, a changed metric, M, efConstruction or flat threshold rebuilds the vectors from stored source in the background like an analyzer change (the graph and the scores both change). A changed dimension is a schema evolution error naming the field.

Embedding set hashes

SHA-256 of the files written by tools/embeddings.py (the sets are not committed).