Skip to content

armgit / ente

Public Imported from GitHub
0

πŸ’š End-to-end encrypted cloud for everything.

102 KB
Raw Blame
use std::cmp::{Ordering, Reverse};
use std::collections::{BinaryHeap, HashSet};

use super::arena::{PackedQuery, Query, VectorArena};
use super::kernel::splitmix64;
use super::{Match, SearchParams, VecDbError};

const M: usize = 16;
const LEVEL_ZERO_NEIGHBOR_CAP: usize = 2 * M;
const UPPER_LEVEL_NEIGHBOR_CAP: usize = M;
const EF_CONSTRUCTION: usize = 96;
const SELECTION_WINDOW_FACTOR: usize = 2;
const REVERSE_PRUNE_SLACK: usize = 4;
const EF_SEARCH_UPPER: usize = 1;
const EF_SEARCH_FLOOR_MIN: usize = 72;
const EF_SEARCH_FLOOR_MAX: usize = 128;
const EF_SEARCH_FLOOR_STEP: usize = 16;
const EF_SEARCH_FLOOR_CROSSOVER: usize = 65_536;
const EF_SEARCH_FLOOR_AT_CROSSOVER: usize = 80;
const _: () = assert!(EF_SEARCH_FLOOR_CROSSOVER.is_power_of_two());
const EF_SEARCH_LIMIT_FACTOR: usize = 4;
const SMALL_FILTER_FLOOR: usize = 1024;
const SMALL_FILTER_LIMIT_FACTOR: usize = 4;
const RANGE_SEARCH_FLOOR: usize = 200;
const RANGE_EXPANSION_SLACK: f32 = 0.10;
const LEVEL_SEED: u64 = 0x9E37_79B9_7F4A_7C15;
const NEIGHBOR_BATCH: usize = LEVEL_ZERO_NEIGHBOR_CAP;
const ABSENT_LEVEL: u16 = u16::MAX;
const ABSENT_DENSE: u32 = u32::MAX;
const MIN_GROWTH_SPARE: usize = 1024;

fn grow_amortized<T: Clone>(values: &mut Vec<T>, len: usize, fill: T) {
    debug_assert!(len >= values.len());
    if values.capacity() < len {
        let spare = (values.len() / 8).max(MIN_GROWTH_SPARE);
        let target = len.max(values.len() + spare);
        values.reserve_exact(target - values.len());
    }
    values.resize(len, fill);
}

fn neighbor_cap(level: usize) -> usize {
    if level == 0 {
        LEVEL_ZERO_NEIGHBOR_CAP
    } else {
        UPPER_LEVEL_NEIGHBOR_CAP
    }
}

fn reverse_prune_target(cap: usize, sorted_by_distance: &[Scored]) -> usize {
    let holds_equal_distances = sorted_by_distance
        .windows(2)
        .any(|pair| pair[0].distance == pair[1].distance);
    if holds_equal_distances {
        cap
    } else {
        cap.saturating_sub(REVERSE_PRUNE_SLACK).max(1)
    }
}

fn select_neighbors(
    arena: &VectorArena,
    candidates: &[Scored],
    cap: usize,
    selected: &mut [u32; LEVEL_ZERO_NEIGHBOR_CAP],
) -> usize {
    let window = candidates
        .len()
        .min(cap.saturating_mul(SELECTION_WINDOW_FACTOR));
    let mut count = 0;
    for candidate in &candidates[..window] {
        if count == cap {
            break;
        }
        let diverse = selected[..count]
            .iter()
            .all(|&kept| arena.distance_between_slots(candidate.slot, kept) > candidate.distance);
        if diverse {
            selected[count] = candidate.slot;
            count += 1;
        }
    }
    for alive in [true, false] {
        for candidate in candidates {
            if count == cap {
                return count;
            }
            if arena.is_alive(candidate.slot) == alive
                && !selected[..count].contains(&candidate.slot)
            {
                selected[count] = candidate.slot;
                count += 1;
            }
        }
    }
    count
}

#[derive(Clone, Copy)]
struct Scored {
    distance: f32,
    slot: u32,
}

impl PartialEq for Scored {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl Eq for Scored {}

impl PartialOrd for Scored {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Scored {
    fn cmp(&self, other: &Self) -> Ordering {
        self.distance
            .total_cmp(&other.distance)
            .then_with(|| self.slot.cmp(&other.slot))
    }
}

struct VisitedSet {
    words: Vec<u64>,
}

impl VisitedSet {
    fn with_capacity(slots: usize) -> Self {
        Self {
            words: vec![0; slots.div_ceil(64)],
        }
    }

    fn insert(&mut self, slot: u32) -> bool {
        let word = slot as usize / 64;
        let mask = 1u64 << (slot % 64);
        if self.words[word] & mask != 0 {
            return false;
        }
        self.words[word] |= mask;
        true
    }
}

struct UpperLevel {
    dense_of_slot: Vec<u32>,
    neighbors: Vec<u32>,
    lengths: Vec<u16>,
}

impl UpperLevel {
    fn new() -> Self {
        Self {
            dense_of_slot: Vec::new(),
            neighbors: Vec::new(),
            lengths: Vec::new(),
        }
    }

    fn memory_bytes(&self) -> usize {
        self.dense_of_slot.capacity() * size_of::<u32>()
            + self.neighbors.capacity() * size_of::<u32>()
            + self.lengths.capacity() * size_of::<u16>()
    }
}

pub(crate) struct GraphNodeParts {
    pub(crate) slot: u32,
    pub(crate) level: u8,
    pub(crate) neighbors: Vec<Vec<u32>>,
}

pub(crate) struct Graph {
    node_levels: Vec<u16>,
    zero_neighbors: Vec<u32>,
    zero_lengths: Vec<u16>,
    upper: Vec<UpperLevel>,
    entry_point: Option<u32>,
    insert_ordinal: u64,
}

impl Graph {
    pub(crate) fn new() -> Self {
        Self {
            node_levels: Vec::new(),
            zero_neighbors: Vec::new(),
            zero_lengths: Vec::new(),
            upper: Vec::new(),
            entry_point: None,
            insert_ordinal: 0,
        }
    }

    pub(crate) fn rebuild(arena: &VectorArena) -> Self {
        let mut graph = Self::new();
        for slot in arena.live_slots() {
            graph.insert(slot, arena);
        }
        graph
    }

    pub(crate) fn from_parts(
        entry_point: Option<u32>,
        parts: Vec<GraphNodeParts>,
        slot_count: usize,
        insert_ordinal: u64,
    ) -> Result<Self, VecDbError> {
        let mut slots: HashSet<u32> = HashSet::with_capacity(parts.len());
        for part in &parts {
            if part.slot as usize >= slot_count {
                return Err(VecDbError::Corrupt(format!(
                    "graph node {} is beyond the {slot_count} arena slots",
                    part.slot
                )));
            }
            if part.neighbors.len() != part.level as usize + 1 {
                return Err(VecDbError::Corrupt(format!(
                    "graph node {} level {} has {} adjacency lists",
                    part.slot,
                    part.level,
                    part.neighbors.len()
                )));
            }
            if !slots.insert(part.slot) {
                return Err(VecDbError::Corrupt(format!(
                    "duplicate graph node for slot {}",
                    part.slot
                )));
            }
            for (layer, list) in part.neighbors.iter().enumerate() {
                let cap = neighbor_cap(layer);
                if list.len() > cap {
                    return Err(VecDbError::Corrupt(format!(
                        "graph node {} level {layer} has {} neighbors above the {cap} cap",
                        part.slot,
                        list.len()
                    )));
                }
            }
        }
        for part in &parts {
            for list in &part.neighbors {
                for neighbor in list {
                    if !slots.contains(neighbor) {
                        return Err(VecDbError::Corrupt(format!(
                            "graph node {} links to unknown slot {neighbor}",
                            part.slot
                        )));
                    }
                }
            }
        }
        match entry_point {
            Some(slot) if !slots.contains(&slot) => {
                return Err(VecDbError::Corrupt(format!(
                    "graph entry point {slot} has no node"
                )));
            }
            None if !parts.is_empty() => {
                return Err(VecDbError::Corrupt(
                    "non-empty graph has no entry point".to_string(),
                ));
            }
            _ => {}
        }
        let capacity = parts
            .iter()
            .map(|part| part.slot as usize + 1)
            .max()
            .unwrap_or(0);
        let mut graph = Self::new();
        graph.entry_point = entry_point;
        graph.insert_ordinal = insert_ordinal;
        graph.reserve_slots(capacity);
        for part in parts {
            graph.attach_empty_node(part.slot, part.level as usize);
            for (layer, list) in part.neighbors.iter().enumerate() {
                graph.write_level_list(part.slot, layer, list);
            }
        }
        Ok(graph)
    }

    pub(crate) fn insert(&mut self, slot: u32, arena: &VectorArena) {
        let level = self.next_level();
        self.reserve_slots(arena.slot_count().max(slot as usize + 1));
        self.attach_empty_node(slot, level);
        let Some(entry) = self.entry_point else {
            self.entry_point = Some(slot);
            return;
        };
        let query = arena.stored_query(slot);
        let entry_level = self.level_of(entry).map_or(0, usize::from);
        let mut entries = {
            let context = QueryContext {
                graph: self,
                arena,
                query,
            };
            let mut nearest = context.scored(entry);
            for descend_level in (level + 1..=entry_level).rev() {
                nearest = context.greedy_descend(nearest, descend_level, Some(slot));
            }
            vec![nearest]
        };
        for link_level in (0..=level.min(entry_level)).rev() {
            let candidates = {
                let context = QueryContext {
                    graph: self,
                    arena,
                    query,
                };
                context.search_layer(&entries, link_level, EF_CONSTRUCTION, Some(slot), &|_| true)
            };
            let cap = neighbor_cap(link_level);
            let mut selected = [0u32; LEVEL_ZERO_NEIGHBOR_CAP];
            let count = select_neighbors(arena, &candidates, cap, &mut selected);
            if self.holds_level(slot, link_level) {
                self.write_level_list(slot, link_level, &selected[..count]);
            }
            for &neighbor in &selected[..count] {
                self.link_back(neighbor, link_level, slot, cap, arena);
            }
            entries = candidates;
        }
        if level > entry_level {
            self.entry_point = Some(slot);
        }
    }

    pub(crate) fn entry_point(&self) -> Option<u32> {
        self.entry_point
    }

    pub(crate) fn insert_ordinal(&self) -> u64 {
        self.insert_ordinal
    }

    pub(crate) fn node_count(&self) -> usize {
        self.slots().count()
    }

    pub(crate) fn slots(&self) -> impl Iterator<Item = u32> {
        self.node_levels
            .iter()
            .enumerate()
            .filter_map(|(index, &level)| (level != ABSENT_LEVEL).then_some(index as u32))
    }

    pub(crate) fn level_of(&self, slot: u32) -> Option<u8> {
        match self.node_levels.get(slot as usize) {
            Some(&level) if level != ABSENT_LEVEL => Some(level as u8),
            _ => None,
        }
    }

    pub(crate) fn neighbors_of(&self, slot: u32, level: u8) -> &[u32] {
        self.level_neighbors(slot, level as usize)
    }

    pub(crate) fn memory_bytes(&self) -> usize {
        self.node_levels.capacity() * size_of::<u16>()
            + self.zero_neighbors.capacity() * size_of::<u32>()
            + self.zero_lengths.capacity() * size_of::<u16>()
            + self.upper.capacity() * size_of::<UpperLevel>()
            + self
                .upper
                .iter()
                .map(UpperLevel::memory_bytes)
                .sum::<usize>()
    }

    fn slot_span(&self) -> usize {
        self.node_levels.len()
    }

    fn level_neighbors(&self, slot: u32, level: usize) -> &[u32] {
        if level == 0 {
            let Some(&length) = self.zero_lengths.get(slot as usize) else {
                return &[];
            };
            let base = slot as usize * LEVEL_ZERO_NEIGHBOR_CAP;
            return &self.zero_neighbors[base..base + length as usize];
        }
        let Some(upper) = self.upper.get(level - 1) else {
            return &[];
        };
        let Some(&dense) = upper.dense_of_slot.get(slot as usize) else {
            return &[];
        };
        if dense == ABSENT_DENSE {
            return &[];
        }
        let base = dense as usize * UPPER_LEVEL_NEIGHBOR_CAP;
        &upper.neighbors[base..base + upper.lengths[dense as usize] as usize]
    }

    fn holds_level(&self, slot: u32, level: usize) -> bool {
        self.level_of(slot)
            .is_some_and(|node_level| usize::from(node_level) >= level)
    }

    fn write_level_list(&mut self, slot: u32, level: usize, values: &[u32]) {
        debug_assert!(values.len() <= neighbor_cap(level));
        if level == 0 {
            let base = slot as usize * LEVEL_ZERO_NEIGHBOR_CAP;
            self.zero_neighbors[base..base + values.len()].copy_from_slice(values);
            self.zero_lengths[slot as usize] = values.len() as u16;
            return;
        }
        let upper = &mut self.upper[level - 1];
        let dense = upper.dense_of_slot[slot as usize] as usize;
        let base = dense * UPPER_LEVEL_NEIGHBOR_CAP;
        upper.neighbors[base..base + values.len()].copy_from_slice(values);
        upper.lengths[dense] = values.len() as u16;
    }

    fn reserve_slots(&mut self, capacity: usize) {
        if self.node_levels.len() >= capacity {
            return;
        }
        grow_amortized(&mut self.node_levels, capacity, ABSENT_LEVEL);
        grow_amortized(&mut self.zero_lengths, capacity, 0);
        grow_amortized(
            &mut self.zero_neighbors,
            capacity * LEVEL_ZERO_NEIGHBOR_CAP,
            0,
        );
    }

    fn attach_empty_node(&mut self, slot: u32, level: usize) {
        self.reserve_slots(slot as usize + 1);
        debug_assert!(self.node_levels[slot as usize] == ABSENT_LEVEL);
        self.node_levels[slot as usize] = level as u16;
        self.zero_lengths[slot as usize] = 0;
        for layer in 1..=level {
            self.claim_upper_block(slot, layer);
        }
    }

    fn claim_upper_block(&mut self, slot: u32, layer: usize) {
        while self.upper.len() < layer {
            self.upper.push(UpperLevel::new());
        }
        let span = self.node_levels.len();
        let upper = &mut self.upper[layer - 1];
        if upper.dense_of_slot.len() < span {
            grow_amortized(&mut upper.dense_of_slot, span, ABSENT_DENSE);
        }
        let dense = upper.lengths.len() as u32;
        upper.lengths.push(0);
        upper
            .neighbors
            .resize(upper.lengths.len() * UPPER_LEVEL_NEIGHBOR_CAP, 0);
        upper.dense_of_slot[slot as usize] = dense;
    }

    fn link_back(&mut self, slot: u32, level: usize, other: u32, cap: usize, arena: &VectorArena) {
        if !self.holds_level(slot, level) {
            return;
        }
        let mut buffer = [0u32; LEVEL_ZERO_NEIGHBOR_CAP + 1];
        let count = {
            let list = self.level_neighbors(slot, level);
            if list.contains(&other) {
                return;
            }
            buffer[..list.len()].copy_from_slice(list);
            list.len() + 1
        };
        buffer[count - 1] = other;
        if count <= cap {
            self.write_level_list(slot, level, &buffer[..count]);
            return;
        }
        let mut scored = [Scored {
            distance: 0.0,
            slot: 0,
        }; LEVEL_ZERO_NEIGHBOR_CAP + 1];
        for (entry, &neighbor) in scored.iter_mut().zip(&buffer[..count]) {
            *entry = Scored {
                distance: arena.distance_between_slots(slot, neighbor),
                slot: neighbor,
            };
        }
        scored[..count].sort_unstable();
        let mut kept = [0u32; LEVEL_ZERO_NEIGHBOR_CAP];
        let target = reverse_prune_target(cap, &scored[..count]);
        let kept_count = select_neighbors(arena, &scored[..count], target, &mut kept);
        self.write_level_list(slot, level, &kept[..kept_count]);
    }

    fn next_level(&mut self) -> usize {
        let mut state = LEVEL_SEED ^ self.insert_ordinal;
        self.insert_ordinal = self.insert_ordinal.wrapping_add(1);
        let raw = splitmix64(&mut state);
        let unit = ((raw >> 11) + 1) as f64 / (1u64 << 53) as f64;
        (-unit.ln() * (M as f64).ln().recip()) as usize
    }
}

struct QueryContext<'a> {
    graph: &'a Graph,
    arena: &'a VectorArena,
    query: Query<'a>,
}

impl QueryContext<'_> {
    fn scored(&self, slot: u32) -> Scored {
        Scored {
            distance: self.arena.distance_to_query(self.query, slot),
            slot,
        }
    }

    fn evaluate_batch(
        &self,
        chunk: &[u32],
        visited: &mut VisitedSet,
        slots: &mut [u32; NEIGHBOR_BATCH],
        distances: &mut [f32; NEIGHBOR_BATCH],
    ) -> usize {
        let mut count = 0;
        for &neighbor in chunk {
            if visited.insert(neighbor) {
                slots[count] = neighbor;
                count += 1;
            }
        }
        for (distance, &slot) in distances.iter_mut().zip(slots.iter()).take(count) {
            *distance = self.arena.distance_to_query(self.query, slot);
        }
        count
    }

    fn greedy_descend(&self, mut best: Scored, level: usize, banned: Option<u32>) -> Scored {
        loop {
            let mut improved = false;
            for &neighbor in self.graph.level_neighbors(best.slot, level) {
                if banned == Some(neighbor) {
                    continue;
                }
                let candidate = self.scored(neighbor);
                if candidate < best {
                    best = candidate;
                    improved = true;
                }
            }
            if !improved {
                return best;
            }
        }
    }

    fn search_layer(
        &self,
        entries: &[Scored],
        level: usize,
        ef: usize,
        banned: Option<u32>,
        admit: &impl Fn(u32) -> bool,
    ) -> Vec<Scored> {
        debug_assert!(ef > 0);
        let mut visited = VisitedSet::with_capacity(self.graph.slot_span());
        if let Some(banned) = banned {
            visited.insert(banned);
        }
        let mut candidates: BinaryHeap<Reverse<Scored>> = BinaryHeap::new();
        let mut results: BinaryHeap<Scored> = BinaryHeap::new();
        for &entry in entries {
            if !visited.insert(entry.slot) {
                continue;
            }
            candidates.push(Reverse(entry));
            if admit(entry.slot) {
                results.push(entry);
                if results.len() > ef {
                    results.pop();
                }
            }
        }
        let mut slots = [0u32; NEIGHBOR_BATCH];
        let mut distances = [0.0f32; NEIGHBOR_BATCH];
        while let Some(Reverse(current)) = candidates.pop() {
            if results.len() >= ef && results.peek().is_some_and(|worst| current > *worst) {
                break;
            }
            for chunk in self
                .graph
                .level_neighbors(current.slot, level)
                .chunks(NEIGHBOR_BATCH)
            {
                let count = self.evaluate_batch(chunk, &mut visited, &mut slots, &mut distances);
                for (&distance, &slot) in distances.iter().zip(slots.iter()).take(count) {
                    let scored = Scored { distance, slot };
                    if results.len() >= ef && results.peek().is_some_and(|worst| scored > *worst) {
                        continue;
                    }
                    candidates.push(Reverse(scored));
                    if admit(slot) {
                        results.push(scored);
                        if results.len() > ef {
                            results.pop();
                        }
                    }
                }
            }
        }
        results.into_sorted_vec()
    }

    fn level_zero_entries(&self) -> Vec<Scored> {
        let Some(entry) = self.graph.entry_point else {
            return Vec::new();
        };
        let top = self.graph.level_of(entry).map_or(0, usize::from);
        let mut entries = vec![self.scored(entry)];
        for level in (1..=top).rev() {
            entries = self.search_layer(&entries, level, EF_SEARCH_UPPER, None, &|_| true);
        }
        entries
    }

    fn top_scored(&self, ef: usize, admit: &impl Fn(u32) -> bool) -> Vec<Scored> {
        let entries = self.level_zero_entries();
        if entries.is_empty() {
            return Vec::new();
        }
        self.search_layer(&entries, 0, ef, None, admit)
    }

    fn top_scored_near(
        &self,
        slot: u32,
        ef: usize,
        fill: usize,
        admit: &impl Fn(u32) -> bool,
    ) -> Vec<Scored> {
        if self.graph.level_neighbors(slot, 0).is_empty() {
            return self.top_scored(ef, admit);
        }
        let near = self.search_layer(&[self.scored(slot)], 0, ef, None, admit);
        if near.len() >= fill {
            return near;
        }
        let mut entries = vec![self.scored(slot)];
        entries.extend(self.level_zero_entries());
        self.search_layer(&entries, 0, ef, None, admit)
    }

    fn range_scored(&self, max_distance: f32, admit: &impl Fn(u32) -> bool) -> Vec<Scored> {
        let expansion_bound = max_distance * (1.0 + RANGE_EXPANSION_SLACK);
        let mut visited = VisitedSet::with_capacity(self.graph.slot_span());
        let mut candidates: BinaryHeap<Reverse<Scored>> = BinaryHeap::new();
        let mut frontier: BinaryHeap<Scored> = BinaryHeap::new();
        let mut results: Vec<Scored> = Vec::new();
        for entry in self.level_zero_entries() {
            if !visited.insert(entry.slot) {
                continue;
            }
            if entry.distance <= max_distance && admit(entry.slot) {
                results.push(entry);
            }
            candidates.push(Reverse(entry));
            if self.arena.is_alive(entry.slot) {
                keep_frontier(&mut frontier, entry);
            }
        }
        let mut slots = [0u32; NEIGHBOR_BATCH];
        let mut distances = [0.0f32; NEIGHBOR_BATCH];
        while let Some(Reverse(current)) = candidates.pop() {
            if current.distance > expansion_bound && trails_frontier(&frontier, current) {
                break;
            }
            for chunk in self
                .graph
                .level_neighbors(current.slot, 0)
                .chunks(NEIGHBOR_BATCH)
            {
                let count = self.evaluate_batch(chunk, &mut visited, &mut slots, &mut distances);
                for (&distance, &slot) in distances.iter().zip(slots.iter()).take(count) {
                    let scored = Scored { distance, slot };
                    if scored.distance <= max_distance && admit(slot) {
                        results.push(scored);
                    }
                    let trails = trails_frontier(&frontier, scored);
                    if !trails || scored.distance <= expansion_bound {
                        candidates.push(Reverse(scored));
                    }
                    if !trails && self.arena.is_alive(slot) {
                        keep_frontier(&mut frontier, scored);
                    }
                }
            }
        }
        results.sort_unstable();
        results
    }
}

fn trails_frontier(frontier: &BinaryHeap<Scored>, scored: Scored) -> bool {
    frontier.len() >= RANGE_SEARCH_FLOOR && frontier.peek().is_some_and(|worst| scored > *worst)
}

fn keep_frontier(frontier: &mut BinaryHeap<Scored>, scored: Scored) {
    frontier.push(scored);
    if frontier.len() > RANGE_SEARCH_FLOOR {
        frontier.pop();
    }
}

pub(crate) fn search(
    graph: &Graph,
    arena: &VectorArena,
    query: &PackedQuery,
    params: &SearchParams,
    allowed_slots: Option<&HashSet<u32>>,
) -> Vec<Match> {
    search_from(graph, arena, query.as_query(), params, allowed_slots, None)
}

pub(crate) fn search_stored(
    graph: &Graph,
    arena: &VectorArena,
    slot: u32,
    params: &SearchParams,
    allowed_slots: Option<&HashSet<u32>>,
) -> Vec<Match> {
    search_from(
        graph,
        arena,
        arena.stored_query(slot),
        params,
        allowed_slots,
        Some(slot),
    )
}

fn search_from(
    graph: &Graph,
    arena: &VectorArena,
    query: Query<'_>,
    params: &SearchParams,
    allowed_slots: Option<&HashSet<u32>>,
    stored_slot: Option<u32>,
) -> Vec<Match> {
    debug_assert!(params.limit.is_some() || params.max_distance.is_some());
    if let Some(max_distance) = params.max_distance {
        debug_assert!(max_distance.is_finite() && max_distance >= 0.0);
    }
    if arena.live_count() == 0
        || params.limit == Some(0)
        || allowed_slots.is_some_and(HashSet::is_empty)
        || !query.is_finite()
    {
        return Vec::new();
    }
    if params.exact {
        return brute_force(arena, query, params, allowed_slots, stored_slot);
    }
    if let Some(allowed) = allowed_slots
        && allowed.len() <= small_filter_cap(params.limit)
    {
        return brute_force(arena, query, params, allowed_slots, stored_slot);
    }
    if graph.entry_point.is_none() {
        return brute_force(arena, query, params, allowed_slots, stored_slot);
    }
    let context = QueryContext {
        graph,
        arena,
        query,
    };
    match params.limit {
        Some(limit) => approx_limited(&context, limit, params, allowed_slots, stored_slot),
        None => approx_threshold(
            &context,
            params.max_distance.unwrap_or(f32::MAX),
            allowed_slots,
            stored_slot,
        ),
    }
}

fn small_filter_cap(limit: Option<usize>) -> usize {
    limit.map_or(SMALL_FILTER_FLOOR, |limit| {
        limit
            .saturating_mul(SMALL_FILTER_LIMIT_FACTOR)
            .max(SMALL_FILTER_FLOOR)
    })
}

fn result_bound(arena: &VectorArena, allowed: Option<&HashSet<u32>>) -> usize {
    let live = arena.live_count();
    allowed.map_or(live, |set| set.len().min(live))
}

fn ef_search_floor(live: usize) -> usize {
    if live < EF_SEARCH_FLOOR_CROSSOVER {
        return EF_SEARCH_FLOOR_MIN;
    }
    let doublings = (live.ilog2() - EF_SEARCH_FLOOR_CROSSOVER.ilog2()) as usize;
    (EF_SEARCH_FLOOR_AT_CROSSOVER + doublings * EF_SEARCH_FLOOR_STEP).min(EF_SEARCH_FLOOR_MAX)
}

fn admissible(arena: &VectorArena, allowed: Option<&HashSet<u32>>, slot: u32) -> bool {
    arena.is_alive(slot) && allowed.is_none_or(|set| set.contains(&slot))
}

fn admission<'a>(
    arena: &'a VectorArena,
    allowed: Option<&'a HashSet<u32>>,
    banned: Option<u32>,
) -> impl Fn(u32) -> bool + 'a {
    move |slot| banned != Some(slot) && admissible(arena, allowed, slot)
}

fn approx_limited(
    context: &QueryContext<'_>,
    limit: usize,
    params: &SearchParams,
    allowed: Option<&HashSet<u32>>,
    stored_slot: Option<u32>,
) -> Vec<Match> {
    let bound = result_bound(context.arena, allowed);
    let ef = match stored_slot {
        Some(_) => limit,
        None => limit.saturating_mul(EF_SEARCH_LIMIT_FACTOR),
    }
    .max(ef_search_floor(context.arena.live_count()))
    .min(bound);
    let admit = admission(context.arena, allowed, stored_slot);
    let excluded = stored_slot.is_some_and(|slot| admissible(context.arena, allowed, slot));
    let available = bound - usize::from(excluded);
    let scored = match stored_slot {
        Some(slot) => context.top_scored_near(slot, ef, ef.min(available), &admit),
        None => context.top_scored(ef, &admit),
    };
    if scored.len() < limit.min(available) {
        return brute_force(context.arena, context.query, params, allowed, stored_slot);
    }
    to_matches(context.arena, scored, Some(limit), params.max_distance)
}

fn approx_threshold(
    context: &QueryContext<'_>,
    max_distance: f32,
    allowed: Option<&HashSet<u32>>,
    banned: Option<u32>,
) -> Vec<Match> {
    let admit = admission(context.arena, allowed, banned);
    let scored = context.range_scored(max_distance, &admit);
    to_matches(context.arena, scored, None, Some(max_distance))
}

fn brute_force(
    arena: &VectorArena,
    query: Query<'_>,
    params: &SearchParams,
    allowed: Option<&HashSet<u32>>,
    banned: Option<u32>,
) -> Vec<Match> {
    let mut top: BinaryHeap<Scored> = BinaryHeap::new();
    let mut all: Vec<Scored> = Vec::new();
    let mut consider = |slot: u32| {
        if banned == Some(slot) || !arena.is_alive(slot) {
            return;
        }
        let distance = arena.distance_to_query(query, slot);
        if params.max_distance.is_some_and(|cap| distance > cap) {
            return;
        }
        let scored = Scored { distance, slot };
        match params.limit {
            Some(limit) => {
                top.push(scored);
                if top.len() > limit {
                    top.pop();
                }
            }
            None => all.push(scored),
        }
    };
    match allowed {
        Some(set) => {
            for &slot in set {
                consider(slot);
            }
        }
        None => {
            for slot in arena.live_slots() {
                consider(slot);
            }
        }
    }
    let scored = if params.limit.is_some() {
        top.into_sorted_vec()
    } else {
        all.sort_unstable();
        all
    };
    to_matches(arena, scored, None, None)
}

fn to_matches(
    arena: &VectorArena,
    mut scored: Vec<Scored>,
    limit: Option<usize>,
    max_distance: Option<f32>,
) -> Vec<Match> {
    if let Some(max_distance) = max_distance {
        let keep = scored.partition_point(|entry| entry.distance <= max_distance);
        scored.truncate(keep);
    }
    if let Some(limit) = limit {
        scored.truncate(limit);
    }
    scored
        .into_iter()
        .filter_map(|entry| {
            arena.key_of_slot(entry.slot).map(|key| Match {
                key: key.to_string(),
                distance: entry.distance,
            })
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use std::f32::consts::FRAC_1_SQRT_2;
    use std::sync::LazyLock;

    use super::super::StorageKind;
    use super::super::arena::UpsertOutcome;
    use super::super::test_support::{assert_identical_graphs, stale_downward_edge_exists};
    use super::*;

    const FIXTURE_DIMS: usize = 16;
    const FIXTURE_COUNT: usize = 1500;

    static FIXTURE: LazyLock<(VectorArena, Graph)> =
        LazyLock::new(|| build_fixture(FIXTURE_COUNT, FIXTURE_DIMS, 0x00F1_0000));

    fn normalized(mut values: Vec<f32>) -> Vec<f32> {
        let norm = values.iter().map(|value| value * value).sum::<f32>().sqrt();
        for value in &mut values {
            *value /= norm;
        }
        values
    }

    fn seeded_unit_vector(seed: u64, dims: usize) -> Vec<f32> {
        let mut state = seed;
        normalized(
            (0..dims)
                .map(|_| {
                    let unit = (splitmix64(&mut state) >> 40) as f32 / (1u64 << 24) as f32;
                    unit * 2.0 - 1.0
                })
                .collect(),
        )
    }

    fn clustered_unit_vector(center_seed: u64, noise_seed: u64, dims: usize) -> Vec<f32> {
        let center = seeded_unit_vector(center_seed, dims);
        let noise = seeded_unit_vector(noise_seed, dims);
        let mut spread_state = noise_seed ^ 0xD1B5_4A32_D192_ED03;
        let spread = 0.6 + (splitmix64(&mut spread_state) >> 40) as f32 / (1u64 << 24) as f32;
        normalized(
            center
                .iter()
                .zip(&noise)
                .map(|(center, noise)| center + spread * noise)
                .collect(),
        )
    }

    fn build_clustered_fixture(
        count: usize,
        dims: usize,
        clusters: u64,
        seed: u64,
    ) -> (VectorArena, Graph) {
        build_clustered_fixture_with(count, dims, clusters, seed, StorageKind::F32)
    }

    fn build_clustered_fixture_with(
        count: usize,
        dims: usize,
        clusters: u64,
        seed: u64,
        storage: StorageKind,
    ) -> (VectorArena, Graph) {
        let mut arena = VectorArena::with_storage(dims, storage).unwrap();
        for index in 0..count as u64 {
            arena
                .upsert(
                    &format!("key-{index}"),
                    &clustered_unit_vector(
                        seed + index % clusters,
                        seed + 0x0100_0000 + index,
                        dims,
                    ),
                )
                .unwrap();
        }
        let graph = Graph::rebuild(&arena);
        (arena, graph)
    }

    const LATENT_DIMS: usize = 24;

    fn latent_projection(seed: u64, dims: usize) -> Vec<Vec<f32>> {
        (0..LATENT_DIMS as u64)
            .map(|axis| seeded_unit_vector(seed + 0x0300_0000 + axis, dims))
            .collect()
    }

    fn projected_unit_vector(projection: &[Vec<f32>], latent: &[f32]) -> Vec<f32> {
        let dims = projection[0].len();
        let mut values = vec![0.0f32; dims];
        for (weight, basis) in latent.iter().zip(projection) {
            for (value, basis_value) in values.iter_mut().zip(basis) {
                *value += weight * basis_value;
            }
        }
        normalized(values)
    }

    fn build_latent_fixture(
        count: usize,
        dims: usize,
        clusters: u64,
        seed: u64,
    ) -> (VectorArena, Graph) {
        let projection = latent_projection(seed, dims);
        let mut arena = VectorArena::new(dims).unwrap();
        for index in 0..count as u64 {
            let latent = clustered_unit_vector(
                seed + index % clusters,
                seed + 0x0100_0000 + index,
                LATENT_DIMS,
            );
            arena
                .upsert(
                    &format!("key-{index}"),
                    &projected_unit_vector(&projection, &latent),
                )
                .unwrap();
        }
        let graph = Graph::rebuild(&arena);
        (arena, graph)
    }

    fn build_arena(count: usize, dims: usize, seed: u64) -> VectorArena {
        let mut arena = VectorArena::new(dims).unwrap();
        for index in 0..count {
            arena
                .upsert(
                    &format!("key-{index}"),
                    &seeded_unit_vector(seed + index as u64, dims),
                )
                .unwrap();
        }
        arena
    }

    fn build_fixture(count: usize, dims: usize, seed: u64) -> (VectorArena, Graph) {
        let arena = build_arena(count, dims, seed);
        let graph = Graph::rebuild(&arena);
        (arena, graph)
    }

    const DUPLICATE_GROUP_SEED: u64 = 0x1DEA_0000;
    const PEAKY_GROUP_SEED: u64 = 0x9EA4_0000;
    const PEAKY_TAIL: f32 = 0.04;
    const BACKGROUND_SEED: u64 = 0x8AC0_0000;
    const JITTER_SEED: u64 = 0x71E7_0000;

    fn build_duplicate_groups(groups: usize, per_group: usize) -> (VectorArena, Graph) {
        build_duplicate_groups_with(16, StorageKind::F32, groups, per_group)
    }

    fn build_duplicate_groups_with(
        dims: usize,
        storage: StorageKind,
        groups: usize,
        per_group: usize,
    ) -> (VectorArena, Graph) {
        build_groups(dims, storage, groups, per_group, |group, _| {
            group_center(group, dims)
        })
    }

    fn build_groups(
        dims: usize,
        storage: StorageKind,
        groups: usize,
        per_group: usize,
        member: impl Fn(usize, usize) -> Vec<f32>,
    ) -> (VectorArena, Graph) {
        let mut arena = VectorArena::with_storage(dims, storage).unwrap();
        for index in 0..groups * per_group {
            let vector = member(index / per_group, index % per_group);
            arena.upsert(&format!("key-{index}"), &vector).unwrap();
        }
        let graph = Graph::rebuild(&arena);
        (arena, graph)
    }

    fn group_center(group: usize, dims: usize) -> Vec<f32> {
        seeded_unit_vector(DUPLICATE_GROUP_SEED + group as u64, dims)
    }

    fn peaky_unit_vector(group: usize, dims: usize) -> Vec<f32> {
        let mut state = PEAKY_GROUP_SEED + group as u64;
        let mut values: Vec<f32> = (0..dims)
            .map(|_| {
                if splitmix64(&mut state).is_multiple_of(2) {
                    PEAKY_TAIL
                } else {
                    -PEAKY_TAIL
                }
            })
            .collect();
        values[group % dims] = 1.0;
        normalized(values)
    }

    fn jittered(center: &[f32], seed: u64, spread: f32) -> Vec<f32> {
        let noise = seeded_unit_vector(seed, center.len());
        normalized(
            center
                .iter()
                .zip(&noise)
                .map(|(center, noise)| center + spread * noise)
                .collect(),
        )
    }

    fn group_of(arena: &VectorArena, key: &str, per_group: usize) -> usize {
        arena.slot_of_key(key).unwrap() as usize / per_group
    }

    fn assert_leading_group(
        arena: &VectorArena,
        found: &[Match],
        count: usize,
        group: usize,
        per_group: usize,
    ) {
        let (head, tail) = found.split_at(count);
        for hit in head {
            assert_eq!(group_of(arena, &hit.key, per_group), group);
            assert_eq!(hit.distance, head[0].distance);
        }
        for hit in tail {
            assert!(hit.distance > head[0].distance);
        }
    }

    fn assert_leading_group_members(
        arena: &VectorArena,
        found: &[Match],
        count: usize,
        group: usize,
        per_group: usize,
    ) {
        for hit in &found[..count] {
            assert_eq!(group_of(arena, &hit.key, per_group), group, "{}", hit.key);
        }
    }

    fn params(limit: Option<usize>, max_distance: Option<f32>, exact: bool) -> SearchParams {
        SearchParams {
            limit,
            max_distance,
            exact,
            allowed_keys: None,
        }
    }

    fn reference_ranking(
        arena: &VectorArena,
        query: &PackedQuery,
        allowed: Option<&HashSet<u32>>,
    ) -> Vec<(f32, u32)> {
        let mut scored: Vec<(f32, u32)> = arena
            .live_slots()
            .filter(|slot| allowed.is_none_or(|set| set.contains(slot)))
            .map(|slot| (arena.distance_to_query(query.as_query(), slot), slot))
            .collect();
        scored.sort_unstable_by(|a, b| a.0.total_cmp(&b.0).then_with(|| a.1.cmp(&b.1)));
        scored
    }

    fn keys(matches: &[Match]) -> Vec<&str> {
        matches.iter().map(|found| found.key.as_str()).collect()
    }

    fn assert_sorted(matches: &[Match]) {
        for pair in matches.windows(2) {
            assert!(pair[0].distance <= pair[1].distance);
        }
    }

    fn apply_upsert(arena: &mut VectorArena, graph: &mut Graph, key: &str, vector: &[f32]) {
        if let UpsertOutcome::NewSlot(slot) = arena.upsert(key, vector).unwrap() {
            graph.insert(slot, arena);
        }
    }

    fn graph_parts(graph: &Graph) -> Vec<GraphNodeParts> {
        graph
            .slots()
            .map(|slot| {
                let level = graph.level_of(slot).unwrap();
                GraphNodeParts {
                    slot,
                    level,
                    neighbors: (0..=level)
                        .map(|layer| graph.neighbors_of(slot, layer).to_vec())
                        .collect(),
                }
            })
            .collect()
    }

    fn assert_graph_invariants(graph: &Graph) {
        for slot in graph.slots() {
            let level = graph.level_of(slot).unwrap();
            for layer in 0..=level {
                let neighbors = graph.neighbors_of(slot, layer);
                assert!(neighbors.len() <= neighbor_cap(layer as usize));
                for &neighbor in neighbors {
                    assert_ne!(neighbor, slot);
                    assert!(graph.level_of(neighbor).is_some());
                }
            }
        }
    }

    fn axis_vector(dims: usize, axis: usize) -> Vec<f32> {
        let mut values = vec![0.0; dims];
        values[axis] = 1.0;
        values
    }

    fn two_axis_vector(first: (usize, f32), second: (usize, f32)) -> Vec<f32> {
        let mut values = vec![0.0f32; 8];
        values[first.0] = first.1;
        values[second.0] = second.1;
        values
    }

    fn handcrafted() -> (VectorArena, Graph) {
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("a", &axis_vector(8, 0)).unwrap();
        arena
            .upsert(
                "b",
                &two_axis_vector((0, FRAC_1_SQRT_2), (1, FRAC_1_SQRT_2)),
            )
            .unwrap();
        arena.upsert("c", &axis_vector(8, 1)).unwrap();
        arena
            .upsert("d", &two_axis_vector((0, -1.0), (1, 0.0)))
            .unwrap();
        arena
            .upsert("t1", &two_axis_vector((0, 0.5), (2, 0.866_025_4)))
            .unwrap();
        arena
            .upsert("t2", &two_axis_vector((0, 0.5), (3, 0.866_025_4)))
            .unwrap();
        let graph = Graph::rebuild(&arena);
        (arena, graph)
    }

    fn measured_recall(
        arena: &VectorArena,
        graph: &Graph,
        queries: u64,
        make_query: impl Fn(u64) -> Vec<f32>,
    ) -> f64 {
        let mut hits = 0usize;
        for index in 0..queries {
            let query = arena.pack_query(&make_query(index)).unwrap();
            let reference = reference_ranking(arena, &query, None);
            let expected: HashSet<&str> = reference[..10]
                .iter()
                .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
                .collect();
            let found = search(graph, arena, &query, &params(Some(10), None, false), None);
            assert_eq!(found.len(), 10);
            hits += found
                .iter()
                .filter(|found| expected.contains(found.key.as_str()))
                .count();
        }
        hits as f64 / (queries as usize * 10) as f64
    }

    #[test]
    fn exact_search_matches_handcrafted_ground_truth() {
        let (arena, graph) = handcrafted();
        let query = arena.pack_query(&axis_vector(8, 0)).unwrap();
        let all = search(&graph, &arena, &query, &params(Some(10), None, true), None);
        assert_eq!(keys(&all), ["a", "b", "t1", "t2", "c", "d"]);
        let expected = [0.0, 1.0 - FRAC_1_SQRT_2, 0.5, 0.5, 1.0, 2.0];
        for (found, expected) in all.iter().zip(expected) {
            assert_eq!(found.distance, expected);
        }
        let inclusive = search(&graph, &arena, &query, &params(None, Some(0.5), true), None);
        assert_eq!(keys(&inclusive), ["a", "b", "t1", "t2"]);
        let below_ties = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(0.499), true),
            None,
        );
        assert_eq!(keys(&below_ties), ["a", "b"]);
        let tie_cut = search(
            &graph,
            &arena,
            &query,
            &params(Some(3), Some(0.5), true),
            None,
        );
        assert_eq!(keys(&tie_cut), ["a", "b", "t1"]);
        let closest = search(
            &graph,
            &arena,
            &query,
            &params(Some(1), Some(2.0), true),
            None,
        );
        assert_eq!(keys(&closest), ["a"]);
    }

    #[test]
    fn tiny_index_approx_equals_exact() {
        let (arena, graph) = handcrafted();
        let query = arena.pack_query(&axis_vector(8, 0)).unwrap();
        let all = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        assert_eq!(keys(&all), ["a", "b", "t1", "t2", "c", "d"]);
        let inclusive = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(0.5), false),
            None,
        );
        assert_eq!(keys(&inclusive), ["a", "b", "t1", "t2"]);
        let tie_cut = search(
            &graph,
            &arena,
            &query,
            &params(Some(3), Some(0.5), false),
            None,
        );
        assert_eq!(keys(&tie_cut), ["a", "b", "t1"]);
        let closest = search(
            &graph,
            &arena,
            &query,
            &params(Some(1), Some(2.0), false),
            None,
        );
        assert_eq!(keys(&closest), ["a"]);
    }

    #[test]
    fn empty_index_returns_empty_for_all_modes() {
        let arena = VectorArena::new(8).unwrap();
        let graph = Graph::new();
        let query = arena.pack_query(&axis_vector(8, 0)).unwrap();
        for exact in [false, true] {
            for (limit, max_distance) in [(Some(5), None), (None, Some(1.0)), (Some(1), Some(0.5))]
            {
                let found = search(
                    &graph,
                    &arena,
                    &query,
                    &params(limit, max_distance, exact),
                    None,
                );
                assert!(found.is_empty());
            }
        }
        assert_eq!(graph.entry_point(), None);
        assert_eq!(graph.node_count(), 0);
    }

    #[test]
    fn single_element_serves_every_mode() {
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("only", &axis_vector(8, 0)).unwrap();
        let graph = Graph::rebuild(&arena);
        let query = arena.pack_query(&axis_vector(8, 0)).unwrap();
        for exact in [false, true] {
            let by_limit = search(&graph, &arena, &query, &params(Some(10), None, exact), None);
            assert_eq!(keys(&by_limit), ["only"]);
            assert_eq!(by_limit[0].distance, 0.0);
            let by_threshold = search(
                &graph,
                &arena,
                &query,
                &params(None, Some(0.0), exact),
                None,
            );
            assert_eq!(keys(&by_threshold), ["only"]);
        }
        let without_graph = search(
            &Graph::new(),
            &arena,
            &query,
            &params(Some(3), None, false),
            None,
        );
        assert_eq!(keys(&without_graph), ["only"]);
    }

    #[test]
    fn banned_entry_point_is_excluded_yet_still_routes_traversal() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let entry = graph.entry_point().unwrap();
        let entry_key = arena.key_of_slot(entry).unwrap();
        let query = arena.pack_query(&arena.vector_values(entry)).unwrap();
        let reference = reference_ranking(arena, &query, None);
        assert_eq!(reference[0].1, entry);
        for exact in [true, false] {
            let found = search_stored(graph, arena, entry, &params(Some(10), None, exact), None);
            assert_eq!(found.len(), 10);
            assert_sorted(&found);
            assert!(found.iter().all(|hit| hit.key != entry_key));
            if exact {
                let expected: Vec<&str> = reference[1..11]
                    .iter()
                    .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
                    .collect();
                assert_eq!(keys(&found), expected);
            }
        }
        let everything = search_stored(graph, arena, entry, &params(None, Some(2.5), false), None);
        assert_eq!(everything.len(), FIXTURE_COUNT - 1);
        assert!(everything.iter().all(|hit| hit.key != entry_key));
        let large_filter: HashSet<u32> = (0..1200).chain([entry]).collect();
        assert!(large_filter.len() > small_filter_cap(Some(10)));
        let filtered = search_stored(
            graph,
            arena,
            entry,
            &params(Some(10), None, false),
            Some(&large_filter),
        );
        assert_eq!(filtered.len(), 10);
        assert!(filtered.iter().all(|hit| hit.key != entry_key));
        let small_filter: HashSet<u32> = reference[..12].iter().map(|&(_, slot)| slot).collect();
        let brute = search_stored(
            graph,
            arena,
            entry,
            &params(Some(12), None, false),
            Some(&small_filter),
        );
        let expected: Vec<&str> = reference[1..12]
            .iter()
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
            .collect();
        assert_eq!(keys(&brute), expected);
    }

    #[test]
    fn banned_only_node_yields_empty_in_every_mode() {
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("only", &axis_vector(8, 0)).unwrap();
        let graph = Graph::rebuild(&arena);
        let allowed: HashSet<u32> = [0].into_iter().collect();
        for exact in [true, false] {
            for filter in [None, Some(&allowed)] {
                let by_limit =
                    search_stored(&graph, &arena, 0, &params(Some(5), None, exact), filter);
                assert!(by_limit.is_empty());
                let by_threshold =
                    search_stored(&graph, &arena, 0, &params(None, Some(2.5), exact), filter);
                assert!(by_threshold.is_empty());
            }
        }
    }

    #[test]
    fn range_search_crosses_distant_bridges_after_retired_nodes() {
        for storage in [StorageKind::F32, StorageKind::I8] {
            for retired in [1, RANGE_SEARCH_FLOOR] {
                let mut arena = VectorArena::with_storage(32, storage).unwrap();
                let near = axis_vector(32, 0);
                let mut bridge = near.clone();
                bridge[0] = 0.8;
                bridge[1] = 0.6;
                let mut hit = near.clone();
                hit[0] = 0.98;
                hit[1] = (1.0f32 - 0.98 * 0.98).sqrt();
                let count = RANGE_SEARCH_FLOOR + 2;
                for index in 0..count {
                    let vector = if index < RANGE_SEARCH_FLOOR {
                        &near
                    } else if index == RANGE_SEARCH_FLOOR {
                        &bridge
                    } else {
                        &hit
                    };
                    arena.upsert(&format!("key-{index}"), vector).unwrap();
                }
                let parts = (0..count as u32)
                    .map(|slot| GraphNodeParts {
                        slot,
                        level: 0,
                        neighbors: vec![if slot + 1 < count as u32 {
                            vec![slot + 1]
                        } else {
                            Vec::new()
                        }],
                    })
                    .collect();
                let graph = Graph::from_parts(Some(0), parts, count, count as u64).unwrap();
                for index in 0..retired {
                    arena.remove(&format!("key-{index}"));
                }
                let query = arena.pack_query(&near).unwrap();
                let exact = search(
                    &graph,
                    &arena,
                    &query,
                    &params(None, Some(0.05), true),
                    None,
                );
                assert_eq!(exact.len(), RANGE_SEARCH_FLOOR - retired + 1);
                assert_eq!(
                    search(
                        &graph,
                        &arena,
                        &query,
                        &params(None, Some(0.05), false),
                        None,
                    ),
                    exact,
                    "storage={storage:?}, retired={retired}",
                );
            }
        }
    }

    #[test]
    fn stored_key_search_fills_across_duplicate_groups() {
        let (arena, graph) = build_duplicate_groups(4, 80);
        let stored = 120;
        let found = search_stored(
            &graph,
            &arena,
            stored,
            &params(Some(100), None, false),
            None,
        );
        assert_eq!(found.len(), 100.min(arena.live_count() - 1));
        assert_sorted(&found);
        assert!(found.iter().all(|hit| hit.key != "key-120"));
        assert_leading_group(&arena, &found, 79, 1, 80);
    }

    #[test]
    fn stored_key_search_reaches_its_own_group_from_a_node_linked_elsewhere() {
        let (arena, graph) = build_duplicate_groups(4, 80);
        let stray = 80;
        assert!(
            graph
                .neighbors_of(stray, 0)
                .iter()
                .all(|&neighbor| neighbor / 80 == 0)
        );
        let found = search_stored(&graph, &arena, stray, &params(Some(10), None, false), None);
        assert_eq!(found.len(), 10);
        assert_leading_group(&arena, &found, 10, 1, 80);
    }

    #[test]
    fn filtered_stored_key_search_fills_from_other_duplicate_groups() {
        let (arena, graph) = build_duplicate_groups(4, 400);
        let stored = 600;
        let allowed: HashSet<u32> = arena.live_slots().filter(|slot| slot / 400 != 1).collect();
        assert!(allowed.len() > small_filter_cap(Some(100)));
        let found = search_stored(
            &graph,
            &arena,
            stored,
            &params(Some(100), None, false),
            Some(&allowed),
        );
        assert_eq!(found.len(), 100);
        assert_sorted(&found);
        for hit in &found {
            assert!(allowed.contains(&arena.slot_of_key(&hit.key).unwrap()));
        }
        let nearest = group_of(&arena, &found[0].key, 400);
        assert_ne!(nearest, 1);
        assert_leading_group(&arena, &found, 100, nearest, 400);
    }

    #[test]
    fn duplicate_groups_near_the_neighbor_cap_stay_whole_at_production_dims() {
        for storage in [StorageKind::F32, StorageKind::I8] {
            for (groups, per_group, limit) in [(4, 40, 60), (8, 40, 60), (4, 80, 100)] {
                let (arena, graph) = build_duplicate_groups_with(512, storage, groups, per_group);
                let query = arena.pack_query(&group_center(0, 512)).unwrap();
                let found = search(
                    &graph,
                    &arena,
                    &query,
                    &params(Some(limit), None, false),
                    None,
                );
                assert_eq!(found.len(), limit);
                assert_sorted(&found);
                assert_leading_group(&arena, &found, per_group, 0, per_group);
            }
        }
    }

    #[test]
    fn duplicate_groups_of_peaky_vectors_stay_whole_in_int8() {
        for (groups, per_group, limit) in [(4, 40, 60), (8, 40, 60), (4, 80, 10), (4, 80, 80)] {
            let (arena, graph) =
                build_groups(512, StorageKind::I8, groups, per_group, |group, _| {
                    peaky_unit_vector(group, 512)
                });
            let query = arena.pack_query(&peaky_unit_vector(0, 512)).unwrap();
            let found = search(
                &graph,
                &arena,
                &query,
                &params(Some(limit), None, false),
                None,
            );
            assert_eq!(found.len(), limit);
            assert_sorted(&found);
            assert_leading_group(&arena, &found, per_group.min(limit), 0, per_group);
        }
    }

    #[test]
    fn a_duplicate_burst_at_the_neighbor_cap_survives_background_and_churn() {
        const BURST: usize = LEVEL_ZERO_NEIGHBOR_CAP;
        const BACKGROUND: usize = 2000;
        let duplicate = group_center(0, 512);
        let mut arena = VectorArena::with_storage(512, StorageKind::I8).unwrap();
        let mut graph = Graph::new();
        for index in 0..BACKGROUND {
            apply_upsert(
                &mut arena,
                &mut graph,
                &format!("background-{index}"),
                &seeded_unit_vector(BACKGROUND_SEED + index as u64, 512),
            );
        }
        for index in 0..BURST {
            apply_upsert(
                &mut arena,
                &mut graph,
                &format!("duplicate-{index}"),
                &duplicate,
            );
        }
        let query = arena.pack_query(&duplicate).unwrap();
        assert_whole_burst(&graph, &arena, &query, BURST);
        for index in (0..BURST).step_by(2) {
            let key = format!("duplicate-{index}");
            assert!(arena.remove(&key).is_some());
            apply_upsert(&mut arena, &mut graph, &key, &duplicate);
        }
        assert_whole_burst(&graph, &arena, &query, BURST);
    }

    fn assert_whole_burst(graph: &Graph, arena: &VectorArena, query: &PackedQuery, burst: usize) {
        let found = search(graph, arena, query, &params(Some(burst), None, false), None);
        let members = found
            .iter()
            .filter(|hit| hit.key.starts_with("duplicate-"))
            .count();
        assert_eq!(members, burst, "{members} of {burst} burst members");
    }

    #[test]
    fn link_back_fills_to_the_cap_only_beside_equal_distances() {
        let cap = LEVEL_ZERO_NEIGHBOR_CAP;
        for (twins, expected) in [(false, cap - REVERSE_PRUNE_SLACK), (true, cap)] {
            let mut arena = VectorArena::new(16).unwrap();
            for index in 0..=cap + 1 {
                let source = if twins && index == 2 { 1 } else { index };
                let vector = seeded_unit_vector(0x11B0_0000 + source as u64, 16);
                arena.upsert(&format!("key-{index}"), &vector).unwrap();
            }
            let mut graph = Graph::rebuild(&arena);
            let full: Vec<u32> = (1..=cap as u32).collect();
            graph.write_level_list(0, 0, &full);
            graph.link_back(0, 0, cap as u32 + 1, cap, &arena);
            assert_eq!(graph.level_neighbors(0, 0).len(), expected);
        }
    }

    #[test]
    fn overflowing_backlinks_preserve_a_diverse_retired_bridge() {
        for storage in [StorageKind::F32, StorageKind::I8] {
            let mut arena = VectorArena::with_storage(32, storage).unwrap();
            let owner = axis_vector(32, 0);
            arena.upsert("owner", &owner).unwrap();
            let mut nearby = owner;
            nearby[1] = 0.1;
            let nearby = normalized(nearby);
            for index in 1..32 {
                arena.upsert(&format!("near-{index}"), &nearby).unwrap();
            }
            let mut bridge = vec![0.0; 32];
            bridge[1] = -1.0;
            arena.upsert("bridge", &bridge).unwrap();
            let mut survivor = bridge;
            survivor[2] = 0.1;
            let survivor = normalized(survivor);
            arena.upsert("survivor", &survivor).unwrap();
            let parts = (0..34)
                .map(|slot| GraphNodeParts {
                    slot,
                    level: 0,
                    neighbors: vec![match slot {
                        0 => (1..=32).collect(),
                        32 => vec![33],
                        _ => vec![0],
                    }],
                })
                .collect();
            let mut graph = Graph::from_parts(Some(0), parts, 34, 34).unwrap();
            arena.remove("bridge").unwrap();
            let query = arena.pack_query(&survivor).unwrap();
            for round in 0..80 {
                let UpsertOutcome::NewSlot(slot) = arena.upsert("incoming", &nearby).unwrap()
                else {
                    panic!("incoming was not retired");
                };
                graph.reserve_slots(arena.slot_count());
                graph.attach_empty_node(slot, 0);
                graph.write_level_list(slot, 0, &[0]);
                graph.link_back(0, 0, slot, LEVEL_ZERO_NEIGHBOR_CAP, &arena);
                assert!(graph.neighbors_of(0, 0).contains(&32), "round {round}");
                for (limit, distance) in [(Some(1), None), (None, Some(0.05))] {
                    let found = search(
                        &graph,
                        &arena,
                        &query,
                        &params(limit, distance, false),
                        None,
                    );
                    assert_eq!(keys(&found), ["survivor"]);
                }
                arena.remove("incoming").unwrap();
            }
        }
    }

    #[test]
    fn jittered_groups_near_the_neighbor_cap_stay_whole() {
        for storage in [StorageKind::F32, StorageKind::I8] {
            for spread in [1e-3, 1e-5, 1e-6] {
                let (arena, graph) = build_groups(512, storage, 4, 80, |group, member| {
                    jittered(
                        &group_center(group, 512),
                        JITTER_SEED + (group * 80 + member) as u64,
                        spread,
                    )
                });
                let query = arena.pack_query(&group_center(0, 512)).unwrap();
                let found = search(
                    &graph,
                    &arena,
                    &query,
                    &params(Some(100), None, false),
                    None,
                );
                assert_eq!(found.len(), 100);
                assert_sorted(&found);
                assert_leading_group_members(&arena, &found, 80, 0, 80);
            }
        }
    }

    fn scored_at(distances: &[f32]) -> Vec<Scored> {
        distances
            .iter()
            .enumerate()
            .map(|(slot, &distance)| Scored {
                distance,
                slot: slot as u32,
            })
            .collect()
    }

    #[test]
    fn reverse_prune_target_keeps_the_full_cap_only_on_equal_distances() {
        let tied = scored_at(&[0.2, 0.4, 0.4, 0.9]);
        let tied_far = scored_at(&[0.2, 0.4, 0.9, 0.9]);
        let apart = scored_at(&[0.2, 0.4, 0.400_001, 0.9]);
        assert_eq!(
            reverse_prune_target(LEVEL_ZERO_NEIGHBOR_CAP, &tied),
            LEVEL_ZERO_NEIGHBOR_CAP
        );
        assert_eq!(
            reverse_prune_target(LEVEL_ZERO_NEIGHBOR_CAP, &tied_far),
            LEVEL_ZERO_NEIGHBOR_CAP
        );
        assert_eq!(
            reverse_prune_target(LEVEL_ZERO_NEIGHBOR_CAP, &apart),
            LEVEL_ZERO_NEIGHBOR_CAP - REVERSE_PRUNE_SLACK
        );
        assert_eq!(
            reverse_prune_target(UPPER_LEVEL_NEIGHBOR_CAP, &[]),
            UPPER_LEVEL_NEIGHBOR_CAP - REVERSE_PRUNE_SLACK
        );
        for cap in 1..=REVERSE_PRUNE_SLACK {
            assert_eq!(reverse_prune_target(cap, &apart), 1);
        }
    }

    #[test]
    fn reverse_pruning_leaves_slack_below_the_level_zero_cap() {
        let (arena, graph) = build_fixture(4000, 16, 0x51AC_0000);
        let lengths: Vec<usize> = arena
            .live_slots()
            .map(|slot| graph.level_neighbors(slot, 0).len())
            .collect();
        let full = lengths
            .iter()
            .filter(|&&len| len == LEVEL_ZERO_NEIGHBOR_CAP)
            .count();
        let mean = lengths.iter().sum::<usize>() as f64 / lengths.len() as f64;
        assert!(lengths.iter().all(|&len| len <= LEVEL_ZERO_NEIGHBOR_CAP));
        assert!(mean < 31.0, "mean level-zero degree {mean}");
        assert!(
            full * 2 < lengths.len(),
            "{full} full lists of {}",
            lengths.len()
        );
    }

    #[test]
    fn cold_search_fills_across_duplicate_groups() {
        let (arena, graph) = build_duplicate_groups(4, 80);
        let query = arena
            .pack_query(&seeded_unit_vector(DUPLICATE_GROUP_SEED, 16))
            .unwrap();
        let ten = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        assert_eq!(ten.len(), 10);
        assert_leading_group(&arena, &ten, 10, 0, 80);
        let hundred = search(
            &graph,
            &arena,
            &query,
            &params(Some(100), None, false),
            None,
        );
        assert_eq!(hundred.len(), 100);
        assert_sorted(&hundred);
        assert_leading_group(&arena, &hundred, 80, 0, 80);
    }

    #[test]
    fn all_dead_index_returns_empty() {
        let mut arena = build_arena(5, 8, 0x0B00_0000);
        let graph = Graph::rebuild(&arena);
        for index in 0..5 {
            arena.remove(&format!("key-{index}")).unwrap();
        }
        let query = arena.pack_query(&axis_vector(8, 0)).unwrap();
        for exact in [false, true] {
            let by_limit = search(&graph, &arena, &query, &params(Some(3), None, exact), None);
            assert!(by_limit.is_empty());
            let by_threshold = search(
                &graph,
                &arena,
                &query,
                &params(None, Some(2.5), exact),
                None,
            );
            assert!(by_threshold.is_empty());
        }
    }

    #[test]
    fn tombstoned_nearest_neighbors_never_surface() {
        let (mut arena, graph) = build_fixture(300, 16, 0x3000_0000);
        let query = arena
            .pack_query(&seeded_unit_vector(0x3111_0000, 16))
            .unwrap();
        let reference = reference_ranking(&arena, &query, None);
        let removed: Vec<String> = reference[..10]
            .iter()
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap().to_string())
            .collect();
        let survivors: Vec<String> = reference[10..20]
            .iter()
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap().to_string())
            .collect();
        for key in &removed {
            arena.remove(key).unwrap();
        }
        for exact in [false, true] {
            let found = search(&graph, &arena, &query, &params(Some(10), None, exact), None);
            assert_eq!(found.len(), 10);
            for hit in &found {
                assert!(!removed.contains(&hit.key));
            }
            if exact {
                assert_eq!(keys(&found), survivors);
            }
        }
        let nearest_distance = reference[0].0;
        let within = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(nearest_distance), false),
            None,
        );
        for hit in &within {
            assert!(!removed.contains(&hit.key));
        }
        let allowed: HashSet<u32> = reference[..12].iter().map(|&(_, slot)| slot).collect();
        let filtered = search(
            &graph,
            &arena,
            &query,
            &params(Some(12), None, false),
            Some(&allowed),
        );
        assert_eq!(keys(&filtered), survivors[..2]);
    }

    #[test]
    fn replacement_moves_key_to_its_new_position() {
        let (mut arena, mut graph) = build_fixture(300, 16, 0x4000_0000);
        let old_vector = arena.vector_values(7);
        let new_vector = seeded_unit_vector(0x4222_0000, 16);
        let outcome = arena.upsert("key-7", &new_vector).unwrap();
        assert_eq!(outcome, UpsertOutcome::NewSlot(300));
        graph.insert(300, &arena);
        assert_eq!(arena.vector_values(7), old_vector);
        let new_query = arena.pack_query(&new_vector).unwrap();
        for exact in [false, true] {
            let top = search(
                &graph,
                &arena,
                &new_query,
                &params(Some(1), None, exact),
                None,
            );
            assert_eq!(keys(&top), ["key-7"]);
            assert!(top[0].distance < 1e-3);
        }
        let old_query = arena.pack_query(&old_vector).unwrap();
        let moved_distance = arena.distance_to_query(old_query.as_query(), 300);
        assert!(moved_distance > 0.3);
        let near_old = search(
            &graph,
            &arena,
            &old_query,
            &params(None, Some(0.3), false),
            None,
        );
        for hit in &near_old {
            assert_ne!(hit.key, "key-7");
        }
        let everything = search(
            &graph,
            &arena,
            &new_query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_eq!(everything.len(), 300);
    }

    #[test]
    fn replacement_of_entry_point_keeps_graph_searchable() {
        let (mut arena, mut graph) = build_fixture(300, 16, 0x5000_0000);
        let entry_slot = graph.entry_point().unwrap();
        let entry_key = arena.key_of_slot(entry_slot).unwrap().to_string();
        let new_vector = seeded_unit_vector(0x5222_0000, 16);
        let outcome = arena.upsert(&entry_key, &new_vector).unwrap();
        assert_eq!(outcome, UpsertOutcome::NewSlot(300));
        graph.insert(300, &arena);
        assert!(graph.entry_point().is_some());
        let query = arena.pack_query(&new_vector).unwrap();
        let top = search(&graph, &arena, &query, &params(Some(1), None, false), None);
        assert_eq!(keys(&top), [entry_key.as_str()]);
        let everything = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_eq!(everything.len(), 300);
    }

    #[test]
    fn insert_after_deletion_serves_the_new_key() {
        let (mut arena, mut graph) = build_fixture(300, 16, 0x6000_0000);
        assert_eq!(arena.remove("key-3"), Some(3));
        let new_vector = seeded_unit_vector(0x6222_0000, 16);
        let outcome = arena.upsert("fresh", &new_vector).unwrap();
        assert_eq!(outcome, UpsertOutcome::NewSlot(300));
        graph.insert(300, &arena);
        let query = arena.pack_query(&new_vector).unwrap();
        for exact in [false, true] {
            let top = search(&graph, &arena, &query, &params(Some(1), None, exact), None);
            assert_eq!(keys(&top), ["fresh"]);
        }
        let everything = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_eq!(everything.len(), 300);
        assert!(everything.iter().all(|hit| hit.key != "key-3"));
        assert!(everything.iter().any(|hit| hit.key == "fresh"));
    }

    #[test]
    fn replacement_of_the_only_node_preserves_the_routing_node() {
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("solo", &axis_vector(8, 0)).unwrap();
        let mut graph = Graph::rebuild(&arena);
        assert_eq!(graph.entry_point(), Some(0));
        arena.upsert("solo", &axis_vector(8, 3)).unwrap();
        graph.insert(1, &arena);
        assert_eq!(graph.entry_point(), Some(0));
        let query = arena.pack_query(&axis_vector(8, 3)).unwrap();
        let found = search(&graph, &arena, &query, &params(Some(5), None, false), None);
        assert_eq!(keys(&found), ["solo"]);
        assert_eq!(found[0].distance, 0.0);
    }

    #[test]
    fn small_filter_takes_the_exact_path_within_the_filter() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0001, FIXTURE_DIMS))
            .unwrap();
        let allowed: HashSet<u32> = (0..FIXTURE_COUNT as u32)
            .filter(|slot| slot % 150 == 3)
            .collect();
        assert_eq!(allowed.len(), 10);
        let reference = reference_ranking(arena, &query, Some(&allowed));
        let found = search(
            graph,
            arena,
            &query,
            &params(Some(3), None, false),
            Some(&allowed),
        );
        assert_eq!(found.len(), 3);
        for (hit, &(distance, slot)) in found.iter().zip(&reference) {
            assert_eq!(hit.key, arena.key_of_slot(slot).unwrap());
            assert_eq!(hit.distance, distance);
            assert!(allowed.contains(&slot));
        }
    }

    #[test]
    fn usize_max_limit_does_not_overflow_with_or_without_filter() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0006, FIXTURE_DIMS))
            .unwrap();
        let allowed: HashSet<u32> = (0..3).collect();
        let filtered = search(
            graph,
            arena,
            &query,
            &params(Some(usize::MAX), None, false),
            Some(&allowed),
        );
        assert_eq!(filtered.len(), 3);
        let unfiltered = search(
            graph,
            arena,
            &query,
            &params(Some(usize::MAX), None, false),
            None,
        );
        assert_eq!(unfiltered.len(), FIXTURE_COUNT);
    }

    #[test]
    fn large_filter_traverses_the_graph_and_respects_the_filter() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0002, FIXTURE_DIMS))
            .unwrap();
        let allowed: HashSet<u32> = (0..1200).collect();
        assert!(allowed.len() > small_filter_cap(Some(10)));
        let reference = reference_ranking(arena, &query, Some(&allowed));
        let found = search(
            graph,
            arena,
            &query,
            &params(Some(10), None, false),
            Some(&allowed),
        );
        assert_eq!(found.len(), 10);
        assert_sorted(&found);
        for hit in &found {
            assert!(allowed.contains(&arena.slot_of_key(&hit.key).unwrap()));
        }
        let expected: HashSet<&str> = reference[..10]
            .iter()
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
            .collect();
        let hits = found
            .iter()
            .filter(|hit| expected.contains(hit.key.as_str()))
            .count();
        assert!(hits >= 9, "filtered recall@10 was {hits}/10");
        let within = search(
            graph,
            arena,
            &query,
            &params(None, Some(0.9), false),
            Some(&allowed),
        );
        assert!(!within.is_empty());
        assert_sorted(&within);
        for hit in &within {
            assert!(hit.distance <= 0.9);
            assert!(allowed.contains(&arena.slot_of_key(&hit.key).unwrap()));
        }
    }

    #[test]
    fn every_params_combination_upholds_result_contracts() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0003, FIXTURE_DIMS))
            .unwrap();
        let small_filter: HashSet<u32> = (0..600).collect();
        let large_filter: HashSet<u32> = (0..1200).collect();
        let filters: [Option<&HashSet<u32>>; 3] = [None, Some(&small_filter), Some(&large_filter)];
        for allowed in filters {
            let reference = reference_ranking(arena, &query, allowed);
            for exact in [true, false] {
                for limit in [None, Some(1), Some(7), Some(5000)] {
                    for max_distance in [None, Some(0.9)] {
                        if limit.is_none() && max_distance.is_none() {
                            continue;
                        }
                        let found = search(
                            graph,
                            arena,
                            &query,
                            &params(limit, max_distance, exact),
                            allowed,
                        );
                        assert_sorted(&found);
                        if let Some(cap) = limit {
                            assert!(found.len() <= cap);
                        }
                        for hit in &found {
                            let slot = arena.slot_of_key(&hit.key).unwrap();
                            assert!(arena.is_alive(slot));
                            if let Some(set) = allowed {
                                assert!(set.contains(&slot));
                            }
                            if let Some(threshold) = max_distance {
                                assert!(hit.distance <= threshold);
                            }
                            assert_eq!(
                                hit.distance,
                                arena.distance_to_query(query.as_query(), slot)
                            );
                        }
                        let expected: Vec<(f32, u32)> = reference
                            .iter()
                            .copied()
                            .filter(|(distance, _)| {
                                max_distance.is_none_or(|threshold| *distance <= threshold)
                            })
                            .take(limit.unwrap_or(usize::MAX))
                            .collect();
                        if exact {
                            assert_eq!(found.len(), expected.len());
                            for (hit, (distance, slot)) in found.iter().zip(&expected) {
                                assert_eq!(hit.key, arena.key_of_slot(*slot).unwrap());
                                assert_eq!(hit.distance, *distance);
                            }
                        } else if max_distance.is_none() {
                            assert_eq!(found.len(), expected.len());
                        } else if !expected.is_empty() {
                            assert!(!found.is_empty());
                        }
                    }
                }
            }
        }
    }

    #[test]
    fn stepped_threshold_search_expands_to_cover_the_live_set() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0004, FIXTURE_DIMS))
            .unwrap();
        let everything = search(graph, arena, &query, &params(None, Some(2.5), false), None);
        assert_eq!(everything.len(), FIXTURE_COUNT);
        assert_sorted(&everything);
    }

    #[test]
    fn tight_threshold_search_stops_early_and_finds_the_head() {
        let (arena, graph) = (&FIXTURE.0, &FIXTURE.1);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00DD_0005, FIXTURE_DIMS))
            .unwrap();
        let reference = reference_ranking(arena, &query, None);
        let threshold = reference[4].0;
        let found = search(
            graph,
            arena,
            &query,
            &params(None, Some(threshold), false),
            None,
        );
        let expected: Vec<&str> = reference
            .iter()
            .take_while(|(distance, _)| *distance <= threshold)
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
            .collect();
        assert_eq!(keys(&found), expected);
    }

    #[test]
    fn reserve_slots_grows_the_slot_arrays_a_bounded_number_of_times() {
        let mut graph = Graph::new();
        let mut reallocations = 0;
        let mut capacity = graph.zero_neighbors.capacity();
        for slots in 1..=20_000 {
            graph.reserve_slots(slots);
            if graph.zero_neighbors.capacity() != capacity {
                capacity = graph.zero_neighbors.capacity();
                reallocations += 1;
            }
        }
        assert!(reallocations < 64, "{reallocations} reallocations");
        assert_eq!(graph.node_levels.len(), 20_000);
        for (len, capacity) in [
            (graph.node_levels.len(), graph.node_levels.capacity()),
            (graph.zero_lengths.len(), graph.zero_lengths.capacity()),
            (graph.zero_neighbors.len(), graph.zero_neighbors.capacity()),
        ] {
            assert!(
                capacity <= len + len / 8 + MIN_GROWTH_SPARE,
                "{capacity} reserved for {len}"
            );
        }
    }

    #[test]
    fn from_parts_reserves_the_slot_arrays_exactly() {
        let (arena, graph) = build_fixture(1500, 16, 0x8100_0000);
        let slots = arena.slot_count();
        assert!(slots >= 1024);
        let rebuilt = Graph::from_parts(
            graph.entry_point(),
            graph_parts(&graph),
            slots,
            graph.insert_ordinal(),
        )
        .unwrap();
        assert_eq!(rebuilt.node_levels.capacity(), slots);
        assert_eq!(rebuilt.zero_lengths.capacity(), slots);
        assert_eq!(
            rebuilt.zero_neighbors.capacity(),
            slots * LEVEL_ZERO_NEIGHBOR_CAP
        );
        for upper in &rebuilt.upper {
            assert_eq!(upper.dense_of_slot.capacity(), slots);
        }
    }

    #[test]
    fn identical_insert_sequences_build_identical_graphs() {
        let arena = build_arena(500, 16, 0x7000_0000);
        let first = Graph::rebuild(&arena);
        let second = Graph::rebuild(&arena);
        assert_identical_graphs(&first, &second);
        assert_graph_invariants(&first);
    }

    #[test]
    fn from_parts_round_trips_the_snapshot_accessors() {
        let (arena, graph) = build_fixture(300, 16, 0x8000_0000);
        let parts = graph_parts(&graph);
        assert_eq!(parts.len(), graph.node_count());
        let rebuilt = Graph::from_parts(
            graph.entry_point(),
            parts,
            arena.slot_count(),
            graph.insert_ordinal(),
        )
        .unwrap();
        assert_identical_graphs(&rebuilt, &graph);
        let query = arena
            .pack_query(&seeded_unit_vector(0x8111_0000, 16))
            .unwrap();
        let from_original = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        let from_rebuilt = search(
            &rebuilt,
            &arena,
            &query,
            &params(Some(10), None, false),
            None,
        );
        assert_eq!(from_original, from_rebuilt);
    }

    #[test]
    fn inserts_after_a_maximal_persisted_ordinal_wrap_instead_of_panicking() {
        let arena = build_arena(2, 8, 0x00D0_0000);
        let mut graph = Graph::from_parts(None, Vec::new(), arena.slot_count(), u64::MAX).unwrap();
        graph.insert(0, &arena);
        assert_eq!(graph.insert_ordinal(), 0);
        graph.insert(1, &arena);
        assert_eq!(graph.insert_ordinal(), 1);
        assert!(graph.level_of(0).is_some());
        assert!(graph.level_of(1).is_some());
    }

    #[test]
    fn from_parts_rejects_malformed_parts() {
        let node = |slot: u32, level: u8, neighbors: Vec<Vec<u32>>| GraphNodeParts {
            slot,
            level,
            neighbors,
        };
        assert!(Graph::from_parts(None, Vec::new(), 0, 0).is_ok());
        assert!(Graph::from_parts(Some(0), vec![node(0, 0, vec![Vec::new()])], 1, 0).is_ok());
        assert!(Graph::from_parts(Some(0), vec![node(0, 1, vec![Vec::new()])], 1, 0).is_err());
        assert!(Graph::from_parts(Some(0), vec![node(0, 0, vec![vec![9]])], 10, 0).is_err());
        assert!(Graph::from_parts(None, vec![node(0, 0, vec![Vec::new()])], 1, 0).is_err());
        assert!(Graph::from_parts(Some(5), vec![node(0, 0, vec![Vec::new()])], 6, 0).is_err());
        assert!(
            Graph::from_parts(
                Some(0),
                vec![node(0, 0, vec![Vec::new()]), node(0, 0, vec![Vec::new()])],
                1,
                0
            )
            .is_err()
        );
        assert!(
            Graph::from_parts(
                Some(1),
                vec![
                    node(0, 0, vec![vec![1]]),
                    node(1, 1, vec![vec![0], Vec::new()])
                ],
                2,
                0
            )
            .is_ok()
        );
    }

    #[test]
    fn from_parts_rejects_slots_beyond_the_arena() {
        let node = |slot: u32, level: u8, neighbors: Vec<Vec<u32>>| GraphNodeParts {
            slot,
            level,
            neighbors,
        };
        assert!(Graph::from_parts(Some(0), vec![node(0, 0, vec![Vec::new()])], 0, 0).is_err());
        assert!(Graph::from_parts(Some(2), vec![node(2, 0, vec![Vec::new()])], 2, 0).is_err());
        assert!(
            Graph::from_parts(
                Some(u32::MAX - 1),
                vec![node(u32::MAX - 1, 0, vec![Vec::new()])],
                3,
                0
            )
            .is_err()
        );
    }

    #[test]
    fn from_parts_tolerates_stale_edges_to_shrunken_levels() {
        let node = |slot: u32, level: u8, neighbors: Vec<Vec<u32>>| GraphNodeParts {
            slot,
            level,
            neighbors,
        };
        let graph = Graph::from_parts(
            Some(1),
            vec![
                node(0, 0, vec![vec![1]]),
                node(1, 1, vec![vec![0, 2], vec![0]]),
                node(2, 0, vec![vec![1]]),
            ],
            3,
            0,
        )
        .unwrap();
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("a", &axis_vector(8, 0)).unwrap();
        arena
            .upsert(
                "b",
                &two_axis_vector((0, FRAC_1_SQRT_2), (1, FRAC_1_SQRT_2)),
            )
            .unwrap();
        arena.upsert("c", &axis_vector(8, 1)).unwrap();
        let query = arena.pack_query(&axis_vector(8, 1)).unwrap();
        let found = search(&graph, &arena, &query, &params(Some(3), None, false), None);
        assert_eq!(keys(&found), ["c", "b", "a"]);
    }

    #[test]
    fn overfull_neighbor_lists_are_rejected() {
        let parts: Vec<GraphNodeParts> = (0..40u32)
            .map(|slot| GraphNodeParts {
                slot,
                level: 0,
                neighbors: vec![if slot == 0 {
                    (0..40).collect()
                } else {
                    vec![0]
                }],
            })
            .collect();
        assert!(Graph::from_parts(Some(0), parts, 40, 0).is_err());
    }

    #[test]
    fn tolerated_self_edges_and_duplicates_stay_safe() {
        let dims = 16;
        let mut arena = build_arena(40, dims, 0x00E0_0000);
        let parts: Vec<GraphNodeParts> = (0..40u32)
            .map(|slot| GraphNodeParts {
                slot,
                level: 0,
                neighbors: vec![vec![0, 0, slot, (slot + 1) % 40]],
            })
            .collect();
        let graph = Graph::from_parts(Some(0), parts, arena.slot_count(), 0).unwrap();
        assert_eq!(graph.neighbors_of(0, 0), [0, 0, 0, 1]);
        let query = arena
            .pack_query(&seeded_unit_vector(0x00E1_0000, dims))
            .unwrap();
        let reference = reference_ranking(&arena, &query, None);
        let top = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        for (hit, &(distance, slot)) in top.iter().zip(&reference) {
            assert_eq!(hit.key, arena.key_of_slot(slot).unwrap());
            assert_eq!(hit.distance, distance);
        }
        let everything = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_eq!(everything.len(), 40);
        let mut graph = graph;
        apply_upsert(
            &mut arena,
            &mut graph,
            "fresh",
            &seeded_unit_vector(0x00E2_0000, dims),
        );
        let fresh_query = arena
            .pack_query(&seeded_unit_vector(0x00E2_0000, dims))
            .unwrap();
        let found = search(
            &graph,
            &arena,
            &fresh_query,
            &params(Some(1), None, false),
            None,
        );
        assert_eq!(keys(&found), ["fresh"]);
        let all = search(
            &graph,
            &arena,
            &fresh_query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_sorted(&all);
        assert!(all.len() <= 41);
        assert!(all.iter().any(|hit| hit.key == "fresh"));
    }

    #[test]
    fn entry_point_below_the_top_level_still_reaches_every_node() {
        let node = |slot: u32, level: u8, neighbors: Vec<Vec<u32>>| GraphNodeParts {
            slot,
            level,
            neighbors,
        };
        let graph = Graph::from_parts(
            Some(1),
            vec![
                node(0, 2, vec![vec![1, 2], vec![2], vec![2]]),
                node(1, 0, vec![vec![0]]),
                node(2, 2, vec![vec![0], vec![0], vec![0]]),
            ],
            3,
            0,
        )
        .unwrap();
        let mut arena = VectorArena::new(8).unwrap();
        arena.upsert("a", &axis_vector(8, 0)).unwrap();
        arena.upsert("b", &axis_vector(8, 1)).unwrap();
        arena.upsert("c", &axis_vector(8, 2)).unwrap();
        let query = arena.pack_query(&axis_vector(8, 2)).unwrap();
        let found = search(&graph, &arena, &query, &params(Some(3), None, false), None);
        assert_eq!(found.len(), 3);
        assert_eq!(found[0].key, "c");
    }

    #[test]
    fn repeated_replacements_preserve_levels_and_keep_live_nodes_reachable() {
        let (mut arena, mut graph) = build_fixture(600, 16, 0xB000_0000);
        let original_levels: Vec<_> = graph
            .slots()
            .map(|slot| (slot, graph.level_of(slot)))
            .collect();
        let key = arena
            .key_of_slot(graph.entry_point().unwrap())
            .unwrap()
            .to_string();
        for round in 0..40u64 {
            let vector = seeded_unit_vector(0xB100_0000 + round, 16);
            let slot = arena.slot_count() as u32;
            assert_eq!(
                arena.upsert(&key, &vector).unwrap(),
                UpsertOutcome::NewSlot(slot)
            );
            graph.insert(slot, &arena);
            assert!(!stale_downward_edge_exists(&graph));
            for &(slot, level) in &original_levels {
                assert_eq!(graph.level_of(slot), level);
            }
            assert_graph_invariants(&graph);
            let reloaded = Graph::from_parts(
                graph.entry_point(),
                graph_parts(&graph),
                arena.slot_count(),
                graph.insert_ordinal(),
            )
            .unwrap();
            assert_identical_graphs(&reloaded, &graph);
            let query = arena.pack_query(&vector).unwrap();
            let top = search(&graph, &arena, &query, &params(Some(1), None, false), None);
            assert_eq!(keys(&top), [key.as_str()]);
            let everything = search(
                &graph,
                &arena,
                &query,
                &params(None, Some(2.5), false),
                None,
            );
            assert_eq!(everything.len(), 600);
        }
        let rebuilt = Graph::from_parts(
            graph.entry_point(),
            graph_parts(&graph),
            arena.slot_count(),
            graph.insert_ordinal(),
        )
        .unwrap();
        assert_identical_graphs(&rebuilt, &graph);
        let query = arena
            .pack_query(&seeded_unit_vector(0xB200_0000, 16))
            .unwrap();
        let from_churned = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        let from_rebuilt = search(
            &rebuilt,
            &arena,
            &query,
            &params(Some(10), None, false),
            None,
        );
        assert_eq!(from_churned, from_rebuilt);
    }

    #[test]
    fn randomized_churn_upholds_contracts_determinism_and_connectivity() {
        let dims = 16;
        let mut primary = (VectorArena::new(dims).unwrap(), Graph::new());
        let mut shadow = (VectorArena::new(dims).unwrap(), Graph::new());
        let mut state = 0xC000_0000u64;
        let mut live: Vec<String> = Vec::new();
        let mut dead: Vec<String> = Vec::new();
        let mut next_id = 0u64;
        for _ in 0..12 {
            for _ in 0..50 {
                let roll = splitmix64(&mut state);
                let action = roll % 10;
                if action < 4 || live.is_empty() {
                    let key = format!("key-{next_id}");
                    next_id += 1;
                    let vector = seeded_unit_vector(splitmix64(&mut state), dims);
                    for pair in [&mut primary, &mut shadow] {
                        apply_upsert(&mut pair.0, &mut pair.1, &key, &vector);
                    }
                    live.push(key);
                } else if action < 7 {
                    let key = live[roll as usize % live.len()].clone();
                    let vector = seeded_unit_vector(splitmix64(&mut state), dims);
                    for pair in [&mut primary, &mut shadow] {
                        apply_upsert(&mut pair.0, &mut pair.1, &key, &vector);
                    }
                } else if action < 9 {
                    let key = live.swap_remove(roll as usize % live.len());
                    for pair in [&mut primary, &mut shadow] {
                        assert!(pair.0.remove(&key).is_some());
                    }
                    dead.push(key);
                } else if let Some(key) = dead.pop() {
                    let vector = seeded_unit_vector(splitmix64(&mut state), dims);
                    for pair in [&mut primary, &mut shadow] {
                        apply_upsert(&mut pair.0, &mut pair.1, &key, &vector);
                    }
                    live.push(key);
                }
            }
            let (arena, graph) = (&primary.0, &primary.1);
            assert_graph_invariants(graph);
            assert_eq!(arena.live_count(), live.len());
            let reloaded = Graph::from_parts(
                graph.entry_point(),
                graph_parts(graph),
                arena.slot_count(),
                graph.insert_ordinal(),
            )
            .unwrap();
            assert_identical_graphs(&reloaded, graph);
            for _ in 0..3 {
                let query_vector = seeded_unit_vector(splitmix64(&mut state), dims);
                let query = arena.pack_query(&query_vector).unwrap();
                let reference = reference_ranking(arena, &query, None);
                let top = search(graph, arena, &query, &params(Some(10), None, false), None);
                assert_sorted(&top);
                assert_eq!(top.len(), reference.len().min(10));
                for hit in &top {
                    let slot = arena.slot_of_key(&hit.key).unwrap();
                    assert!(arena.is_alive(slot));
                    assert_eq!(
                        hit.distance,
                        arena.distance_to_query(query.as_query(), slot)
                    );
                }
                let expected: HashSet<&str> = reference
                    .iter()
                    .take(10)
                    .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
                    .collect();
                let hits = top
                    .iter()
                    .filter(|hit| expected.contains(hit.key.as_str()))
                    .count();
                assert!(
                    hits + 1 >= top.len(),
                    "churn recall was {hits}/{}",
                    top.len()
                );
                let everything =
                    search(graph, arena, &query, &params(None, Some(2.5), false), None);
                assert_sorted(&everything);
                assert_eq!(everything.len(), live.len());
                if reference.len() >= 5 {
                    let threshold = reference[4].0;
                    let within = search(
                        graph,
                        arena,
                        &query,
                        &params(None, Some(threshold), false),
                        None,
                    );
                    assert_sorted(&within);
                    let expected_within: HashSet<&str> = reference
                        .iter()
                        .take_while(|(distance, _)| *distance <= threshold)
                        .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
                        .collect();
                    for hit in &within {
                        assert!(hit.distance <= threshold);
                        assert!(expected_within.contains(hit.key.as_str()));
                    }
                }
                let allowed: HashSet<u32> =
                    arena.live_slots().filter(|slot| slot % 2 == 0).collect();
                if !allowed.is_empty() {
                    let filtered = search(
                        graph,
                        arena,
                        &query,
                        &params(Some(5), None, false),
                        Some(&allowed),
                    );
                    assert_sorted(&filtered);
                    assert_eq!(filtered.len(), allowed.len().min(5));
                    for hit in &filtered {
                        assert!(allowed.contains(&arena.slot_of_key(&hit.key).unwrap()));
                    }
                }
            }
        }
        assert_identical_graphs(&primary.1, &shadow.1);
        let (arena, graph) = (&primary.0, &primary.1);
        let rebuilt = Graph::from_parts(
            graph.entry_point(),
            graph_parts(graph),
            arena.slot_count(),
            graph.insert_ordinal(),
        )
        .unwrap();
        assert_identical_graphs(&rebuilt, graph);
        let query = arena
            .pack_query(&seeded_unit_vector(0xC900_0000, dims))
            .unwrap();
        let from_churned = search(graph, arena, &query, &params(Some(10), None, false), None);
        let from_rebuilt = search(
            &rebuilt,
            arena,
            &query,
            &params(Some(10), None, false),
            None,
        );
        assert_eq!(from_churned, from_rebuilt);
    }

    #[test]
    fn nearly_all_dead_graph_terminates_with_only_the_living() {
        let (mut arena, graph) = build_fixture(400, 16, 0xD000_0000);
        for index in 0..400 {
            if index % 80 != 0 {
                arena.remove(&format!("key-{index}")).unwrap();
            }
        }
        assert_eq!(arena.live_count(), 5);
        let query = arena
            .pack_query(&seeded_unit_vector(0xD100_0000, 16))
            .unwrap();
        let reference = reference_ranking(&arena, &query, None);
        let expected: Vec<&str> = reference
            .iter()
            .map(|&(_, slot)| arena.key_of_slot(slot).unwrap())
            .collect();
        let top = search(&graph, &arena, &query, &params(Some(10), None, false), None);
        assert_eq!(keys(&top), expected);
        let everything = search(
            &graph,
            &arena,
            &query,
            &params(None, Some(2.5), false),
            None,
        );
        assert_eq!(keys(&everything), expected);
    }

    #[test]
    fn non_finite_queries_return_empty_without_panicking() {
        let (arena, graph) = handcrafted();
        for value in [f32::NAN, f32::INFINITY, f32::NEG_INFINITY] {
            let mut bad = axis_vector(8, 0);
            bad[3] = value;
            let query = arena.pack_query(&bad).unwrap();
            for exact in [false, true] {
                for (limit, max_distance) in [(Some(3), None), (None, Some(1.0))] {
                    let found = search(
                        &graph,
                        &arena,
                        &query,
                        &params(limit, max_distance, exact),
                        None,
                    );
                    assert!(found.is_empty());
                }
            }
        }
    }

    #[test]
    fn ef_search_floor_steps_once_per_doubling_above_the_crossover() {
        assert_eq!(ef_search_floor(0), 72);
        assert_eq!(ef_search_floor(1), 72);
        assert_eq!(ef_search_floor(65_535), 72);
        assert_eq!(ef_search_floor(65_536), 80);
        assert_eq!(ef_search_floor(131_071), 80);
        assert_eq!(ef_search_floor(131_072), 96);
        assert_eq!(ef_search_floor(262_143), 96);
        assert_eq!(ef_search_floor(262_144), 112);
        assert_eq!(ef_search_floor(524_287), 112);
        assert_eq!(ef_search_floor(524_288), 128);
        assert_eq!(ef_search_floor(1_000_000), 128);
        assert_eq!(ef_search_floor(2_000_000), 128);
        assert_eq!(ef_search_floor(usize::MAX), 128);
    }

    #[test]
    fn ef_search_floor_never_drops_and_stays_within_the_cap() {
        let mut previous = ef_search_floor(0);
        for live in [
            0,
            1,
            EF_SEARCH_FLOOR_CROSSOVER - 1,
            EF_SEARCH_FLOOR_CROSSOVER,
            100_000,
            2 * EF_SEARCH_FLOOR_CROSSOVER - 1,
            2 * EF_SEARCH_FLOOR_CROSSOVER,
            4 * EF_SEARCH_FLOOR_CROSSOVER - 1,
            4 * EF_SEARCH_FLOOR_CROSSOVER,
            8 * EF_SEARCH_FLOOR_CROSSOVER - 1,
            8 * EF_SEARCH_FLOOR_CROSSOVER,
            1_000_000,
            4_000_000,
            usize::MAX,
        ] {
            let floor = ef_search_floor(live);
            assert!(
                floor >= previous,
                "floor at {live} was {floor}, below {previous}"
            );
            assert!(
                floor <= EF_SEARCH_FLOOR_MAX,
                "floor at {live} was {floor}, above the cap"
            );
            previous = floor;
        }
    }

    #[test]
    fn approx_recall_at_10_meets_the_bar_on_8k_vectors() {
        let seed = 0x9000_0000u64;
        let (arena, graph) = build_clustered_fixture(8000, 64, 64, seed);
        let recall = measured_recall(&arena, &graph, 50, |index| {
            clustered_unit_vector(seed + index % 64, seed + 0x0200_0000 + index, 64)
        });
        assert!(recall >= 0.98, "recall@10 was {recall}");
    }

    #[test]
    fn uniform_random_recall_stays_above_the_documented_floor() {
        let (arena, graph) = build_fixture(8000, 64, 0x9500_0000);
        let recall = measured_recall(&arena, &graph, 50, |index| {
            seeded_unit_vector(0x9511_0000 + index, 64)
        });
        assert!(recall >= 0.90, "recall@10 was {recall}");
    }

    #[test]
    #[ignore]
    fn approx_recall_at_10_meets_the_bar_on_100k_vectors() {
        let seed = 0xA000_0000u64;
        let (arena, graph) = build_latent_fixture(100_000, 512, 512, seed);
        let projection = latent_projection(seed, 512);
        let recall = measured_recall(&arena, &graph, 50, |index| {
            let latent =
                clustered_unit_vector(seed + index % 512, seed + 0x0200_0000 + index, LATENT_DIMS);
            projected_unit_vector(&projection, &latent)
        });
        assert!(recall >= 0.97, "recall@10 was {recall}");
    }

    #[test]
    fn i8_approx_recall_at_10_meets_the_bar_on_8k_vectors() {
        let seed = 0x9000_0000u64;
        let (arena, graph) = build_clustered_fixture_with(8000, 64, 64, seed, StorageKind::I8);
        assert_eq!(arena.storage_kind(), StorageKind::I8);
        let recall = measured_recall(&arena, &graph, 50, |index| {
            clustered_unit_vector(seed + index % 64, seed + 0x0200_0000 + index, 64)
        });
        assert!(recall >= 0.975, "i8 recall@10 was {recall}");
    }

    #[test]
    fn i8_uniform_random_recall_stays_above_the_documented_floor() {
        let mut arena = VectorArena::with_storage(64, StorageKind::I8).unwrap();
        for index in 0..8000u64 {
            arena
                .upsert(
                    &format!("key-{index}"),
                    &seeded_unit_vector(0x9500_0000 + index, 64),
                )
                .unwrap();
        }
        let graph = Graph::rebuild(&arena);
        let recall = measured_recall(&arena, &graph, 50, |index| {
            seeded_unit_vector(0x9511_0000 + index, 64)
        });
        assert!(recall >= 0.895, "i8 recall@10 was {recall}");
    }

    #[test]
    fn i8_exact_search_recovers_the_f32_ground_truth_at_10() {
        let seed = 0x9000_0000u64;
        let (f32_arena, _) = build_clustered_fixture(8000, 64, 64, seed);
        let (i8_arena, i8_graph) =
            build_clustered_fixture_with(8000, 64, 64, seed, StorageKind::I8);
        let mut hits = 0usize;
        for index in 0..50u64 {
            let values = clustered_unit_vector(seed + index % 64, seed + 0x0200_0000 + index, 64);
            let f32_query = f32_arena.pack_query(&values).unwrap();
            let truth: HashSet<&str> = reference_ranking(&f32_arena, &f32_query, None)[..10]
                .iter()
                .map(|&(_, slot)| f32_arena.key_of_slot(slot).unwrap())
                .collect();
            let i8_query = i8_arena.pack_query(&values).unwrap();
            let exact = search(
                &i8_graph,
                &i8_arena,
                &i8_query,
                &params(Some(10), None, true),
                None,
            );
            assert_eq!(exact.len(), 10);
            let reference = reference_ranking(&i8_arena, &i8_query, None);
            for (hit, &(distance, slot)) in exact.iter().zip(&reference) {
                assert_eq!(hit.key, i8_arena.key_of_slot(slot).unwrap());
                assert_eq!(hit.distance, distance);
            }
            hits += exact
                .iter()
                .filter(|hit| truth.contains(hit.key.as_str()))
                .count();
        }
        let recall = hits as f64 / 500.0;
        assert!(
            recall >= 0.99,
            "i8-exact vs f32 truth recall@10 was {recall}"
        );
    }
}