How to Implement Filtered or Hybrid Search with an Allowlist in IdMapIndex

Use IdMapIndex::search_with_allowlist to restrict vector searches to a specific subset of IDs by passing a slice of allowed external IDs, which internally builds a boolean mask that the underlying TurboQuantIndex uses to skip disallowed vectors during SIMD-accelerated nearest-neighbor search.

The IdMapIndex struct in the turbovec repository provides a stable-identifier wrapper around the positional TurboQuantIndex, allowing you to maintain persistent external IDs across插入 and deletion operations. When implementing multi-tenant retrieval, permission-based filtering, or hybrid search strategies that combine restricted and unrestricted results, the allowlist API enables runtime filtering without index rebuilding or data duplication.

Understanding the Internal Architecture

Bidirectional ID Mapping

IdMapIndex maintains two lookup tables in turbovec/src/id_map.rs to translate between external stable IDs and internal positional slots:

• slot_to_id: Vec<u64> — Maps each internal slot index (the position used by the underlying quantised index) to its external ID.
• id_to_slot: HashMap<u64, usize> — Provides O(1) reverse lookups from an external ID to its internal slot.

This bidirectional mapping allows the index to accept external ID-based queries while the inner TurboQuantIndex operates on dense positional arrays.

Mask-Based Filtering Pipeline

When you call search_with_allowlist, the implementation converts your ID list into a dense boolean mask before executing the search:

1. Mask Construction — In IdMapIndex::search_with_allowlist (lines 199–226 of turbovec/src/id_map.rs), the method allocates a Vec<bool> where mask[slot] = true only if the corresponding external ID appears in the allowlist.
2. Masked Search — The mask is passed to TurboQuantIndex::search_with_mask in turbovec/src/search.rs, which executes the standard SIMD-accelerated distance computation but skips any vector where the mask entry is false.
3. Result Translation — After the inner index returns slot indices, the wrapper translates these back to external IDs using slot_to_id and returns (scores, ids) to the caller.

The mask is constructed on-the-fly for each query, meaning no persistent index structure is modified and no rebuilding is required when allowlists change.

Implementing Basic Filtered Search

Rust Implementation

The following example demonstrates creating an index, inserting vectors with stable IDs, and restricting a query to a specific allowlist:

use turbovec::IdMapIndex;

// Initialize a 1536-dimensional index with 4-bit quantization
let mut idx = IdMapIndex::new(1536, 4).unwrap();

// Insert three vectors with external IDs
let vectors = vec![0.0_f32; 1536 * 3];
idx.add_with_ids(&vectors, &[1001, 1002, 1003]).unwrap();

// Define an allowlist restricting search to IDs 1001 and 1003 only
let allowlist = &[1001_u64, 1003_u64];

// Retrieve top-2 neighbors restricted to the allowlist
let (scores, ids) = idx.search_with_allowlist(&vectors[..1536], 2, Some(allowlist));

println!("Returned IDs: {:?}", ids); // Output: [1001, 1003]

The search_with_allowlist method validates that the allowlist is non-empty and that every ID exists in the index before constructing the mask and delegating to the inner search routine.

Python Bindings

The same functionality is exposed through the Python bindings in turbovec-python. Pass the allowlist parameter as a list of integers:

from turbovec import IdMapIndex
import numpy as np

# Initialize index (dimensions must match training data)

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

# Add vectors with external IDs

vectors = np.zeros((3, 1536), dtype=np.float32)
idx.add_with_ids(vectors, [1001, 1002, 1003])

# Filtered search

scores, ids = idx.search(vectors[0:1], k=2, allowlist=[1001, 1003])
print(ids)  # Output: [1001, 1003]

The Python binding forwards directly to the Rust implementation, preserving the same safety guarantees and mask-based execution.

Building Hybrid Search Pipelines

Because search_with_allowlist operates as a transparent mask layer, you can combine filtered and unfiltered searches to implement hybrid retrieval strategies. This pattern is useful for boosting results from a specific tenant or category while still filling the result set from the broader corpus.

// Filtered search on high-priority IDs
let (scores_priority, ids_priority) = idx.search_with_allowlist(
    &query, 
    5, 
    Some(&[1001, 1002])
);

// Unfiltered search on the full index
let (scores_general, ids_general) = idx.search(&query, 5);

// Merge results with priority items first
let mut merged_scores = scores_priority.clone();
let mut merged_ids = ids_priority.clone();
merged_scores.extend(scores_general);
merged_ids.extend(ids_general);

// Truncate to desired total k
let k = 5;
merged_scores.truncate(k);
merged_ids.truncate(k);

You can also construct dynamic allowlists at runtime based on user permissions, temporal constraints, or query classification, passing the computed vector directly to search_with_allowlist without modifying the underlying index structure.

API Constraints and Validation

The allowlist API enforces strict validation to prevent silent failures:

• Non-empty allowlist — Passing an empty slice triggers an immediate panic.
• Existence validation — Every ID in the allowlist must exist in the index; otherwise the method panics with the message "id {id} in allowlist is not present in index".
• Duplicate tolerance — Duplicate IDs in the allowlist are silently deduplicated during mask construction, ensuring consistent behavior without error.

These constraints ensure that filtered searches behave deterministically and that missing data is surfaced immediately during development.

Summary

• IdMapIndex::search_with_allowlist enables runtime filtering by converting external ID lists into internal boolean masks.
• The mask is applied within TurboQuantIndex::search_with_mask in turbovec/src/search.rs, preserving SIMD acceleration while skipping disallowed vectors.
• Bidirectional mapping tables (slot_to_id and id_to_slot) in turbovec/src/id_map.rs handle translation between external IDs and internal slots.
• Hybrid search is achieved by executing separate filtered and unfiltered queries and merging results, or by dynamically computing allowlists per-query.
• The API requires non-empty allowlists containing only existing IDs, with duplicates automatically deduplicated.

Frequently Asked Questions

What happens if an ID in the allowlist does not exist in the index?

The method panics immediately with a descriptive error message indicating which specific ID is missing. This strict validation prevents silent omission of requested vectors and ensures query integrity.

Can I include duplicate IDs in the allowlist?

Yes. Duplicate IDs are silently deduplicated during mask construction. The search proceeds as if the ID appeared only once, with no performance penalty or error raised.

How does the allowlist affect search performance?

The allowlist adds an O(n) mask construction step (where n is the number of vectors in the index) and a boolean check during the SIMD search loop. For typical indices, the overhead is negligible compared to the distance computations, though extremely large allowlists (approaching the full index size) approach the performance characteristics of an unfiltered search.

Is it possible to implement hybrid search without executing two separate queries?

While the current API requires separate calls to search_with_allowlist and search for distinct filtered and unfiltered logic, you can simulate single-query hybrid behavior by constructing an allowlist that represents your "priority" set and then merging results programmatically. Future implementations could extend the mask API to support weighted or tiered masking within a single search pass.

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