HNSW Vector Graph Indexing with AVX2 SIMD (The Infinity Data Architecture)

Hierarchical Navigable Small World (HNSW)

In Infinity Data (a sovereign vector database in Rust replacing Pinecone and Snowflake), searching millions of high-dimensional embedding vectors (e.g. 1536-dimensional Ada-002 or 3072-dimensional text-embedding-3) requires approximate nearest neighbor search with logarithmic complexity.

AVX2 SIMD Cosine Distance Kernel

#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;

pub unsafe fn cosine_distance_simd_avx2(a: &[f32], b: &[f32]) -> f32 {
    let mut dot_acc = _mm256_setzero_ps();
    let mut norm_a_acc = _mm256_setzero_ps();
    let mut norm_b_acc = _mm256_setzero_ps();

    let chunks = a.len() / 8;
    for i in 0..chunks {
        let va = _mm256_loadu_ps(a.as_ptr().add(i * 8));
        let vb = _mm256_loadu_ps(b.as_ptr().add(i * 8));

        dot_acc = _mm256_fmadd_ps(va, vb, dot_acc);
        norm_a_acc = _mm256_fmadd_ps(va, va, norm_a_acc);
        norm_b_acc = _mm256_fmadd_ps(vb, vb, norm_b_acc);
    }

    // Horizontal reduction of 8-wide AVX2 registers...
    let dot = hsum_avx2(dot_acc);
    let norm_a = hsum_avx2(norm_a_acc).sqrt();
    let norm_b = hsum_avx2(norm_b_acc).sqrt();

    1.0 - (dot / (norm_a * norm_b))
}