# How the Allowlist Filter Prevents Wasted Computation in Turbovec

> Discover how Turbovec's allowlist filter prevents wasted computation. It efficiently skips vector blocks, saving valuable processing time and resources.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: internals
- Published: 2026-06-10

---

**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`](https://github.com/RyanCodrai/turbovec/blob/main/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:

```rust
// 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`](https://github.com/RyanCodrai/turbovec/blob/main/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:

```rust
// 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`:

```rust
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:

```python
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:

```rust
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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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.