How the Allowlist Filter Prevents Wasted Computation in Turbovec

Turbovec’s allowlist filter eliminates wasted computation by converting external IDs into a slot-level bitmap that enables block-granularity early exit, skipping scoring entirely for blocks that contain no allowed vectors.

Turbovec is a high-performance approximate nearest neighbor search library that employs SIMD kernels to score vectors against queries. When searching large indexes, the allowlist filter prevents unnecessary arithmetic operations by restricting computation to a caller-defined subset of vectors before any distance calculations occur, as implemented in the RyanCodrai/turbovec repository.

Converting Allowlists to Slot Masks

The filtering process begins in turbovec/src/id_map.rs within the search_with_allowlist method. This function receives an optional slice of external IDs and transforms it into a per-slot bitmap that maps directly to the internal storage positions.

The implementation validates the input and constructs a boolean mask where each index corresponds to a slot in the inner index:

// turbovec/src/id_map.rs
// https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs#L191-L206
let mask_buf: Option<Vec<bool>> = allowlist.map(|ids| {
    assert!(!ids.is_empty(), "allowlist is empty");
    let mut mask = vec![false; self.inner.len()];
    for &id in ids {
        let slot = match self.id_to_slot.get(&id) {
            Some(&s) => s,
            None => panic!("id {id} in allowlist is not present in index"),
        };
        mask[slot] = true;
    }
    mask
});

This conversion step ensures that only valid IDs are accepted (panicking on empty allowlists or unknown IDs) and collapses duplicate entries into a single bit flag.

Block-Level Early Exit

The inner index stores vectors in fixed-size blocks of 32 slots. Before the SIMD kernel scores any vector within a block, it queries block_has_allowed in turbovec/src/search.rs to determine if the block contains at least one allowed slot.

The function treats the bitmap as packed 64-bit words, checking a 32-slot window with minimal overhead:

// turbovec/src/search.rs
// https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/search.rs#L1305-L1316
pub(crate) fn block_has_allowed(mask: Option<&[u64]>, base_vec: usize) -> bool {
    match mask {
        None => true,
        Some(m) => {
            let word = m[base_vec >> 6];                 // 64‑slot word
            let bit_offset = base_vec & 63;
            let allowed = ((word >> bit_offset) & 0xFFFF_FFFF) != 0;
            if !allowed {
                BLOCKS_SKIPPED_BY_MASK.fetch_add(1, Ordering::Relaxed);
            }
            allowed
        }
    }
}

If the 32-bit window contains no set bits, the entire block is bypassed, and the BLOCKS_SKIPPED_BY_MASK atomic counter increments for telemetry. On x86-64 platforms with AVX-512 support, the kernel can evaluate two blocks simultaneously using block_pair_has_allowed, doubling the skip throughput.

Per-Slot Validation and Result Translation

When a block passes the early-exit test, the kernel still respects the bitmap on a per-slot basis through mask_allows checks. This ensures that only allowed slots contribute to the top-k heap, even if a block contains a mix of allowed and disallowed vectors.

After scoring completes, search_with_allowlist translates internal slot indices back to external IDs using the slot_to_id mapping. Because the filter eliminated disallowed slots before they reached the scoring stage, the result set is guaranteed to be a subset of the allowlist, and the effective k becomes min(k, allowlist.len()).

Performance Characteristics and Telemetry

The allowlist filter delivers zero-cost skipping for blocks that contain no target vectors. When a block is filtered out, the engine performs no vector decoding, no distance calculations, and no heap updates for that block. This can reduce runtime proportionally to the fraction of filtered vectors.

The bitmap check requires only a single memory load and a few bit operations per block, making it significantly cheaper than the SIMD scoring kernels it replaces. The BLOCKS_SKIPPED_BY_MASK counter provides accurate telemetry for quantifying computation savings.

Implementation Examples

The following Rust example demonstrates basic allowlist usage with IdMapIndex:

use turbovec::IdMapIndex;

let mut idx = IdMapIndex::new(1536, 4).unwrap();
let vectors = vec![0.0f32; 1536 * 3];
idx.add_with_ids(&vectors, &[101, 102, 103]).unwrap();

// Query vector (same dimension)
let query = vec![0.0f32; 1536];

// Allowlist – only keep ID 102
let allowed = [102u64];
let (scores, ids) = idx.search_with_allowlist(&query, 5, Some(&allowed));

assert_eq!(ids, vec![102]); // only the allowed ID appears

Python bindings expose the same functionality using NumPy arrays:

import turbovec
import numpy as np

# Build the index (dim=1536, 4‑bit quantisation)

idx = turbovec.IdMapIndex(dim=1536, bit_width=4)

# Add three vectors with external IDs

idx.add(vectors, ids=[101, 102, 103])

# Query vector

q = np.zeros(1536, dtype=np.float32)

# Allowlist as a NumPy array of uint64

allowlist = np.array([102], dtype=np.uint64)

scores, ids = idx.search(q, k=5, allowlist=allowlist)
print(ids)  # → [102]

To inspect how many blocks were skipped during a search, use the telemetry functions:

use turbovec::search::{reset_blocks_skipped_by_mask, blocks_skipped_by_mask};

reset_blocks_skipped_by_mask();
let _ = idx.search(&query, k=10, allowlist=Some(&allowed));
println!("Blocks skipped: {}", blocks_skipped_by_mask());

Summary

• Slot-mask conversion in turbovec/src/id_map.rs translates external IDs into an internal bitmap that maps to storage slots.
• Block-granularity early exit in turbovec/src/search.rs uses block_has_allowed to skip entire blocks of 32 vectors when no allowed slots are present.
• Zero-cost filtering eliminates SIMD scoring, heap updates, and memory traffic for filtered blocks.
• Telemetry support via BLOCKS_SKIPPED_BY_MASK quantifies the computational savings per query.
• Result guarantees ensure that only allowlist IDs appear in results, with an effective k bounded by the allowlist size.

Frequently Asked Questions

What happens if the allowlist contains IDs that do not exist in the index?

The search_with_allowlist method in turbovec/src/id_map.rs validates every ID against the id_to_slot mapping. If any ID is not found, the function panics with a descriptive message indicating which external ID is missing, preventing silent errors in filtered results.

How does the allowlist filter affect the number of results returned?

The filter bounds the effective k to min(k, allowlist.len()). Because the kernel only scores allowed vectors, it cannot return more results than were present in the allowlist, even if the requested k exceeds the allowlist size.

What is the performance overhead of using an allowlist filter?

The overhead consists of a single bitmap check per block (comprising a 64-bit load and bit operations) and per-slot validation for blocks that pass. This is negligible compared to the cost of SIMD scoring, and the filter provides net positive performance by eliminating entire blocks of computation.

Can the allowlist filter skip multiple blocks at once on modern hardware?

Yes. On x86-64 platforms with AVX-512, the kernel utilizes block_pair_has_allowed to evaluate two consecutive blocks simultaneously, allowing the engine to skip up to 64 slots in a single predicate check.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}