ordvec 0.2.0

Training-free ordinal & sign quantization for vector retrieval
Documentation

ordvec

CI License: MIT OR Apache-2.0 MSRV OpenSSF Scorecard OpenSSF Best Practices codecov

Crates.io docs.rs

Training-free ordinal & sign quantization for vector retrieval.

ordvec is a small, dependency-light Rust crate for compressed nearest-neighbour search over high-dimensional embeddings.

What's different

Compressed-retrieval libraries usually either fit a codebook to your data (product / scalar quantization) or wrap vectors in a graph (HNSW). ordvec does neither — it quantizes the ordinal structure of each vector on its own:

  • Training-free, data-oblivious. No codebook, no learned rotation, no fit step. Encoding is a per-vector rank (or sign) transform — index the very first vector with no prior data, and never refit when the corpus drifts.
  • Zero system dependencies. Pure Rust — no BLAS / LAPACK / ndarray / faer. Builds and cross-compiles cleanly, including to aarch64 and wasm32.
  • Ordinal + sign quantization. Compresses the rank order of coordinates (1/2/4 bits each) and their signs — a different lever from the product / scalar / binary quantization most crates use.
  • Predictable footprint. Exactly dim * bits / 8 bytes per document — known before you see any data (256 B at dim = 1024, 2-bit), with bits ∈ {1, 2, 4} the size/recall knob.
  • Two-stage retrieval, built in. A cheap bitmap / sign-popcount prefilter feeds an exact rerank — the coarse→fine pipeline ships as library primitives.

ordvec is a compressed flat-scan substrate (optionally two-stage): small codes scored by fast SIMD — AVX-512/AVX2 runtime-dispatched on x86_64, baseline NEON on aarch64, and simd128 on wasm32. It is the code-and-scan layer, not a navigable-graph index — but the codes are small and index-agnostic, so they compose under an ANN or sharding layer for large-scale serving rather than competing with one.

Ordinal index family

  • Rank — full-precision rank vectors (u16 per coordinate).
  • RankQuant — ranks bucketed into 1 << bits equal-width bins, bits bits per coordinate (dim * bits / 8 bytes/doc). Both a symmetric (Spearman) and asymmetric (float-query LUT) scorer.
  • Bitmap — a top-bucket bitmap per document (one bit per coordinate); scoring is popcount(Q AND D), a coarsened rank overlap.
  • SignBitmap — a sign bitmap per document for sign-cosine candidate generation, feeding an exact rerank stage.

Two further paths, for callers who need them:

  • RankQuantFastscan (#[doc(hidden)] — reachable as ordvec::RankQuantFastscan, but the API is not yet stable) — an optional b=2 FastScan kernel (block-32 PQ-LUT) for absolute-minimum scan latency, at 2× the RankQuant b=2 footprint (dim/2 bytes/doc). Surfaced here so latency-critical callers know it exists.
  • MultiBucketBitmap (behind --features experimental) — the multi-bucket bilinear-overlap probe behind the research-side decomposition; a scaffold for the theory, not a production path.

The bitmap prefilter has a closed-form null

The Bitmap prefilter scores candidates by popcount(Q AND D) over each document's fixed-size top-bucket set. Two unrelated documents — modelled as independent uniform top-bucket sets — overlap hypergeometrically, H(dim, n_top, n_top), with expected overlap n_top² / dim (e.g. 16 at dim = 256, n_top = 64). So the filter's selectivity — how often an unrelated document clears a given overlap threshold — is closed-form and data-independent, not a tuned cutoff. (Whether true neighbours clear the bar is empirical; this is an exact candidate-generation null, not a retrieval-optimality theorem.) The invariance underneath it — that the rank transform is unchanged by any strictly monotone reparametrisation of the coordinates — is separately machine-checked in Lean, with the formalisation accompanying the paper. Details in docs/RANK_MODES.md.

Quickstart

[dependencies]
ordvec = "0.2"

# Or, to track unreleased `main`, use a git dependency instead:
# ordvec = { git = "https://github.com/Fieldnote-Echo/ordvec" }

use ordvec::RankQuant;

let dim = 1024;
let mut index = RankQuant::new(dim, 2);   // 2 bits/coord → 256 bytes/doc

// `add` takes a flat, row-major buffer of `dim * n_docs` f32s.
index.add(&doc_embeddings);               // &[f32], len = dim * n_docs

// Asymmetric scan: full-precision queries vs bucketed docs (recommended).
let results = index.search_asymmetric(&query_embeddings, 10); // len = dim * n_queries

let top_ids = results.indices_for_query(0);     // top-10 doc ids for query 0
let top_scores = results.scores_for_query(0);

For the two-stage compressed-scan path (Bitmap / SignBitmap candidate generation → RankQuant rerank) and the full mode comparison, see docs/RANK_MODES.md.

Python

The same Rank / RankQuant / Bitmap / SignBitmap API is available from Python — the bindings ship to PyPI as ordvec:

pip install ordvec

Wheels target CPython 3.10+ (abi3); to build from source instead, see ordvec-python/.

Documentation

Reproducible benchmark

The head-to-head benchmark generates a seeded synthetic corpus in-process, so the quality numbers (R@10, candidate-recall, bytes/vec) are deterministic and regenerable from a clean checkout with no external corpus file:

cargo run --release --example bench_rank

A few operating points from the committed run (benchmarks/rank_modes_results.txt):

Mode bytes/vec p50 (ms) Mdocs/s R@10
Rank asym (full-precision reference) 512 3.71 8 0.845
RankQuant b=4 asym 128 0.31 96 0.806
RankQuant b=2 asym 64 0.24 126 0.572
RankQuant b=2 FastScan 128 0.09 333 0.570
Two-stage b=2 (M=500, CR=1.000) 96 0.11 275 0.572

One representative run on a synthetic corpus (dim=256, n=30k, seed=1), AMD Ryzen 9 9950X (AVX-512), 32 threads, single-thread scan. R@10 is deterministic run-to-run; throughput/latency vary with hardware and run. R@10 is measured against FP32 brute-force cosine on this synthetic corpus — the broader real-corpus evaluation lives in the paper (in progress).

Scope

ordvec is a library and substrate, not a turnkey service: small ordinal/sign codes, fast SIMD scoring, and a built-in two-stage prefilter — the code-and-scan layer of a retrieval system. It is not a navigable-graph index (HNSW) on its own — yet — and not a serving tier at all: ordvec is the substrate other systems build on, so its small, index-agnostic codes slot under an ANN or sharding layer for large-scale serving rather than replacing it. Encoding is training-free and data-oblivious by design — no codebook fit — so you index the first vector with no prior data and never refit as the corpus grows.

Quality evidence in this repo is the reproducible synthetic benchmark above; the broader real-corpus evaluation is in the paper (in progress).

Security: index-file trust

The on-disk formats (.tvr / .tvrq / .tvbm / .tvsb) carry no built-in checksum, MAC, or signature — by design. The loaders validate structure (magic, version, bounds, exact-length payload) but not origin: a structurally valid file can still be untrusted. If an index file crosses a trust boundary (network transfer, shared storage), verifying it is the caller's responsibility — e.g. a SHA-256 manifest, artifact-store integrity, or Sigstore attestation. No in-format crypto is shipped because it would add key management the library can't own. See docs/INDEX_PROVENANCE.md and THREAT_MODEL.md.

Provenance

ordvec was developed within turbovec, factored out into this standalone, zero-system-dependency crate. turbovec (MIT, by Ryan Codrai) is credited as the project it grew within, with thanks; ordvec's development history is in this repository's git log.

Acknowledgements

Thanks to Todd Baur (@toadkicker) for the sign-cosine intuition and engineering polish.

Thanks to Mike Singleton (@singleton2787) for mathematical assistance and mentorship.

Research collaboration

ordvec is the reference implementation for an in-progress paper on ordinal retrieval — using the rank and sign structure of embeddings, rather than their floating-point magnitudes, as the retrieval signal. The repository is open specifically to grow a group of collaborators, including potential named co-authorship where contributions meet the paper's authorship bar — a different invitation than "send a PR." Collaboration we're actively seeking:

  • Real-corpus evaluation — running the modes against public corpora (GloVe, MTEB / BEIR, OpenAI embedding dumps) beyond the synthetic benchmark.
  • Theory — formalising the hypergeometric candidate-generation null and the rank-cosine invariants.
  • Independent reproduction — re-running the benchmark on other hardware and reporting the numbers.

If that's your area, see GOVERNANCE.md and open an issue or a discussion.

Contributing

Contributions to the code, the docs, and the paper are all welcome — see CONTRIBUTING.md.

Minimum supported Rust version

ordvec's MSRV is Rust 1.89 — the release that stabilized the specific AVX-512 intrinsics the SIMD kernels compile against (it also clears the 1.87 floor from is_multiple_of). Because the kernels are built against those intrinsics, this is a hard compile floor, not just a convenience pin: a toolchain below 1.89 won't build the crate. Raising the MSRV is treated as a minor-version change.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.