Distance Metrics

What this page covers

Basis is hard-coded to L2 (Euclidean) distance in the current build. This page explains why, how the distance is encoded for HNSW, and how to normalize inputs when your model emits cosine-similar embeddings.

The Point type

Point is the unit the HNSW graph stores:

struct Point {
    id: Uuid,
    vec: Vec<f32>,
}

impl MetricPoint for Point {
    type Metric = u32;

    fn distance(&self, other: &Self) -> u32 {
        let mut sum = 0.0f32;
        for i in 0..self.vec.len() {
            let diff = self.vec[i] - other.vec[i];
            sum += diff * diff;
        }
        sum.sqrt().to_bits()
    }
}

Two properties matter:

1. L2 distance, computed without SIMD or BLAS in the reference build. The loop is the bottleneck for high-dimensional vectors; if you need faster inserts/queries, swap in a SIMD-backed distance function and rebuild.
2. f32.to_bits() as the metric type. The HNSW crate requires Ord on the metric type. Casting a non-negative f32 to u32 via to_bits preserves the natural ordering because the IEEE-754 representation of non-negative floats is monotonic in u32 space.

Why this works for non-negative distances

For f32 values in [0, +∞):

The mapping is strictly monotonic, so HNSW's smaller-is-closer comparisons remain correct.

Negative distances would break this — they are not possible from L2 by construction, so the encoding is safe here.

Adapting to cosine similarity

The L2 distance between two unit-normalized vectors a and b is related to cosine similarity by:

||a - b||^2 = 2 - 2·cos(a, b)

So if your embedding model already emits unit vectors (CLIP, sentence-transformers normalize=True, OpenAI text-embedding-3-*), L2 nearest-neighbor on those vectors is exactly cosine nearest-neighbor.

fn normalize(v: &mut [f32]) {
    let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt();
    if norm > 0.0 {
        for x in v.iter_mut() {
            *x /= norm;
        }
    }
}

let mut emb = embed("hello world"); // your embedding pipeline
normalize(&mut emb);
basis.add(Uuid::new_v4(), &emb).await?;

Dimensionality

Basis does not check that inserted vectors share a dimensionality — the HNSW graph will silently accept mismatched lengths and produce meaningless distances. Validate on the caller side:

const EMBED_DIM: usize = 768;

if vector.len() != EMBED_DIM {
    return Err(format!("expected dim {EMBED_DIM}, got {}", vector.len()).into());
}
basis.add(id, &vector).await?;

Performance characteristics

When to pre-quantize

For corpora above 10 M vectors, scalar quantization (f32 → i8) before insertion reduces memory by 4× and speeds the inner loop. Basis does not perform this automatically; apply it before calling add and to query vectors before calling search.