TurboVec swap_remove: O(1) Vector Deletion with Swap-and-Pop Semantics

TurboVec's swap_remove method deletes a vector from a TurboQuantIndex in constant time by swapping the target element with the last vector in the compressed storage, returning the original index of the moved element while automatically invalidating the internal search cache.

The swap_remove implementation in the RyanCodrai/turbovec repository provides an efficient mechanism for removing vectors from quantized indexes without rebuilding the entire data structure. Unlike traditional deletion methods that require shifting elements and maintaining order, this operation performs O(1) deletion by overwriting the removed slot and truncating the underlying packed-code buffers.

How swap_remove Works in TurboVec

Swap-and-Pop Semantics

When you call swap_remove(idx), the method implements classic swap-and-pop semantics on the compressed vector storage. The vector stored at idx is overwritten by the last vector in the index (n_vectors - 1). This approach destroys the original ordering of elements but achieves constant-time deletion regardless of index size.

The operation affects three core components:

• The packed-code buffer containing compressed vector representations
• The scales array storing per-vector normalization factors
• The blocked search cache requiring immediate invalidation

Return Value and Index Management

The function returns the original slot index of the vector that was moved into the deleted position. Specifically:

• If idx points to the last element, the returned value equals idx
• Otherwise, the return value is n_vectors - 1 (before truncation)

This return value is critical for maintaining external mappings, as it indicates which physical slot now occupies the position where deletion occurred.

Cache Invalidation

Because the layout of packed codes changes, the internal blocked-search cache (self.blocked) is rebuilt using OnceLock::new(). This forces reconstruction on the next search query, ensuring correctness while deferring the cost of cache rebuilding until necessary.

Implementation Details in turbovec/src/lib.rs

The core implementation resides in turbovec/src/lib.rs at lines 663-706. The TurboQuantIndex::swap_remove method executes the following sequence:

1. Bounds checking – The method asserts that idx < self.n_vectors with a clear panic message for out-of-bounds access
2. Layout calculation – Computes bytes_per_vec from the dimension (dim) and bits per vector (bit_width)
3. Packed byte movement – Uses copy_within to move the last vector's packed bytes into the idx slot (when idx is not the last element)
4. Scale factor transfer – Copies the normalization scale: self.scales[idx] = self.scales[last]
5. Storage truncation – Shrinks both the packed-code vector and scales array to the new length
6. Length adjustment – Decrements self.n_vectors by one
7. Cache reset – Replaces the blocked cache with a new OnceLock to force rebuild on next search

Handling External IDs with TurboQuantIndexIdMap

When working with external identifiers, the TurboQuantIndexIdMap wrapper (implemented in turbovec/src/id_map.rs, lines 57-80) provides automatic ID table management. Because swap_remove changes physical slot assignments, this wrapper updates external ID mappings to remain consistent with the new internal layout.

Code Examples

Basic swap_remove Usage

use turbovec::TurboQuantIndex;

let dim = 256;
let mut idx = TurboQuantIndex::new(dim, 4).unwrap();

// Add 10 random vectors
let data = gaussian_normalized(10, dim, 0xDEAD_BEEF);
idx.add(&data);

// Delete the vector at slot 3
let moved_from = idx.swap_remove(3);
// `moved_from` is the old index of the vector that was moved (9 in this case)
assert_eq!(moved_from, 9);
assert_eq!(idx.len(), 9);

Using the ID-Map Layer

use turbovec::TurboQuantIndexIdMap;

let mut map = TurboQuantIndexIdMap::new(dim, 4).unwrap();
let ids: Vec<u64> = (0..10).collect();
map.add_batch(&data, &ids).unwrap();

// Remove by external id
let removed = map.remove(5);
assert!(removed);                // true if id existed
// Internally the corresponding slot was swapped, and the map tables were updated.

Cache Invalidation After Deletion

let q = &data[5 * dim..6 * dim];
let res = idx.search(q, 1);
assert_eq!(res.indices_for_query(0)[0], 5); // self-query works

let moved_from = idx.swap_remove(5);
assert_eq!(moved_from, idx.len());           // last vector moved into slot 5

let q_moved = &data[(idx.len()) * dim..(idx.len()+1) * dim];
let res = idx.search(q_moved, 1);
assert_eq!(res.indices_for_query(0)[0], 5); // cache rebuilt, new slot found

Summary

• O(1) deletion: swap_remove provides constant-time removal by swapping the target element with the last vector and truncating storage
• Index return value: The method returns the original slot of the moved vector (n_vectors - 1 before the call) to facilitate external mapping updates
• Order destruction: This operation destroys element ordering; the last vector moves into the deleted slot
• Automatic cache invalidation: The blocked-search cache is immediately invalidated via OnceLock::new() and rebuilt on the next search
• Safety: Bounds checking via assert! ensures idx < n_vectors with a clear panic message
• ID map support: TurboQuantIndexIdMap automatically handles external identifier consistency when using swap_remove operations

Frequently Asked Questions

What is the time complexity of TurboVec's swap_remove?

TurboVec's swap_remove operates in O(1) time complexity. The method performs a constant amount of work regardless of the number of vectors in the index: it copies the last vector's packed bytes into the removed slot, moves the corresponding scale factor, truncates the storage buffers, and decrements the length counter. This makes it significantly faster than linear-time deletion methods for large vector collections.

Does swap_remove maintain the order of vectors in the index?

No, swap_remove explicitly does not maintain element ordering. By design, it overwrites the vector at the specified index with the last vector in the collection, then truncates the storage. This swap-and-pop semantics means the element that previously occupied the highest slot moves into the deleted position, destroying the original sequence. If order preservation is required, you must rebuild the index or use a different data structure.

How does swap_remove affect the internal search cache?

The method immediately invalidates the internal blocked-search cache. After truncation, the implementation replaces self.blocked with a new OnceLock, forcing a complete cache rebuild on the next search operation. This is necessary because the physical layout of packed codes changes when vectors are swapped and removed, rendering the old blocked-search index invalid.

Can I use swap_remove with external ID mappings?

Yes, but you should use the TurboQuantIndexIdMap wrapper. While TurboQuantIndex::swap_remove changes physical slot assignments, the TurboQuantIndexIdMap implementation (in turbovec/src/id_map.rs) automatically updates external ID tables to reflect the new positions. This ensures that external identifiers remain consistent after deletion operations without requiring manual index management.

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