Indexing Vectors for Similarity Search in the Browser

This page answers one task: an application computes embedding vectors for the user’s notes, documents or photos — in the browser, for privacy — and needs to find the most similar items to a query vector quickly, without a server. You want an index in WebAssembly that searches thousands to millions of vectors with good recall and acceptable memory use.

Prerequisites

  • [ ] Embedding vectors for your items (for example 384-dimensional sentence embeddings) and a way to embed queries.
  • [ ] A Wasm module for the index (Rust with hnsw_rs, instant-distance or a small hand-written flat index; or C/C++ such as hnswlib or usearch built with Emscripten).
  • [ ] A worker in which search runs.

Flat search versus approximate indexes

Similarity search finds the vectors closest to a query by a distance measure, usually cosine similarity (or dot product on normalised vectors). The simplest index is flat: compare the query with every stored vector and keep the top k. It is exact, has no build time, and with SIMD it is fast — a 384-dimensional dot product is a few dozen SIMD instructions, so tens of thousands of vectors take a few milliseconds. Its cost grows linearly with the collection.

Approximate nearest-neighbour (ANN) indexes trade a little recall for much faster search. HNSW (hierarchical navigable small-world graphs) is the most widely used: vectors are nodes in a layered graph, and search walks from a top-level entry point towards the query, visiting a small fraction of nodes. It searches millions of vectors in milliseconds with recall above 95%, at the cost of build time and extra memory for graph links.

Flat search versus HNSW in the browser Flat search compares the query with every vector, is exact, needs no build step and is fast with SIMD up to tens of thousands of vectors. HNSW walks a graph, searches millions of vectors in milliseconds at slightly below perfect recall, but needs build time and extra memory for links. flat (brute force + SIMD) exact results no build time cost ∝ collection size up to ~50k vectors HNSW graph ~95–99% recall build time + link memory millisecond search at scale large collections

Step 1 — start with a flat index

For personal collections (a few thousand notes), a flat index is often all you need. Store vectors contiguously in linear memory as normalised f32 and compute dot products with SIMD:

use core::arch::wasm32::*;

#[target_feature(enable = "simd128")]
unsafe fn dot(a: &[f32], b: &[f32]) -> f32 {
    let mut acc = f32x4_splat(0.0);
    for i in (0..a.len()).step_by(4) {
        let va = v128_load(a.as_ptr().add(i) as *const v128);
        let vb = v128_load(b.as_ptr().add(i) as *const v128);
        acc = f32x4_add(acc, f32x4_mul(va, vb));
    }
    f32x4_extract_lane::<0>(acc) + f32x4_extract_lane::<1>(acc) + f32x4_extract_lane::<2>(acc) + f32x4_extract_lane::<3>(acc)
}

Keep a small max-heap of the best k results while scanning. Dimensions should be a multiple of 4 (pad if not). Normalising vectors once at insert time turns cosine similarity into a plain dot product.

Step 2 — move to HNSW when the collection grows

When flat search exceeds your latency budget, build an HNSW index. Its key parameters: M (links per node, typically 16–32) controls memory and recall; ef_construction controls build quality; ef_search controls the search’s breadth and therefore the recall/latency trade-off at query time. Build the index in a worker — building a million-vector index takes tens of seconds — and insert incrementally as new items are embedded.

Step 3 — budget memory

Memory per vector is dimensions × bytes per component plus index overhead. A 384-dimensional f32 vector is 1,536 bytes; with HNSW links at M=16, add roughly 16 × 2 × 4 bytes per layer-0 node plus upper layers — on the order of 150–200 bytes. A million vectors therefore need around 1.7 GB, beyond what most browser tabs should use. Quantise: storing components as i8 (scalar quantisation) cuts vector storage by 4×, and binary quantisation (one bit per dimension) by 32×, with re-ranking of top candidates against full-precision vectors kept on disk or in a smaller cache.

Memory for one million 384-dimensional vectors Full-precision f32 vectors need about 1.5 GB before index links. Scalar int8 quantisation needs about 0.38 GB. Binary quantisation needs about 48 MB but requires re-ranking candidates with higher-precision vectors for good recall. HNSW links add roughly 150 to 200 MB. storage vectors + HNSW links (M=16) notes f32 ~1.5 GB ~0.2 GB best recall int8 (scalar quantised) ~0.38 GB ~0.2 GB small recall loss binary (1 bit/dim) ~48 MB ~0.2 GB re-rank top candidates

Step 4 — persist the index

Rebuilding an index on every page load wastes time. Serialise it — vectors, graph links, ID mapping and parameters — into a byte buffer and write it to OPFS from the worker; on startup, read it back and deserialise into linear memory. For incremental updates, append new vectors and periodically rewrite the file, or keep a small in-memory “delta” index for recent items that is searched alongside the persisted one and merged in the background. Store the embedding model’s name and version with the index: vectors from a different model are incompatible and the index must be rebuilt when the model changes.

Step 5 — measure recall and latency

Approximate indexes need measurement. Take a sample of queries, compute exact top-k with flat search, and compare with HNSW results to compute recall@k. Tune ef_search until recall meets your target (often 0.95) and check latency on a mid-range phone. Report both; a fast index that misses relevant results quietly degrades search quality, which users notice as “search does not find my note”.

Embeddings capture meaning but can miss exact terms — product codes, names, rare words. Combine vector search with keyword search (SQLite FTS5 or a Wasm full-text index): run both, then merge results with reciprocal rank fusion or a weighted score. Hybrid search consistently beats either alone on mixed queries. See building full-text search with Wasm.

Filtering and metadata

Real queries combine similarity with filters: “notes like this, from the last month, in project X”. Filtering after search can return fewer than k results when most top candidates are filtered out; filtering before search (restricting the candidate set) works naturally for flat search but needs support in the HNSW implementation. For modest collections, partition by a common filter (per project) and search the relevant partition; for complex filters, over-fetch (search for 5k, filter, keep k) and measure how often results come up short.

Keeping the index in sync with the data

The index is derived data: every item in the database should have exactly one vector in the index, computed with the current model. Bugs here show up as search results pointing to deleted items or recent items never appearing. Store a mapping from item ID to index position, update it in the same worker transaction that changes the item, and keep a small “pending embeddings” queue for items whose text changed but whose vectors are not yet recomputed — search can fall back to keyword results for them. On startup, compare counts and a checksum of IDs between the database and the index; if they disagree (after a crash, an interrupted rebuild, or a model change), rebuild in the background while serving keyword search. Treat a full rebuild as a normal, resumable operation rather than an emergency, because model upgrades make it inevitable.

Splitting work between workers

Embedding text is far heavier than searching vectors. Run the embedding model in one worker (it may use WebGPU or multithreaded Wasm), and the index in another, so a background re-embedding job never delays interactive queries. The index worker owns the vectors and the persisted file; the embedding worker posts new vectors to it as Float32Arrays transferred without copying. A query then needs only one embedding of the query text plus a search, and the UI can show keyword results immediately while the vector search completes a few milliseconds later.

Expected output

A notes app with 20,000 notes searches a flat SIMD index in 6 ms on a phone; a photo library with 800,000 image embeddings uses an int8-quantised HNSW index (M=16) of about 560 MB, searching in 4 ms with recall@10 of 0.96 at ef_search=64; the index persists to OPFS and loads in 1.2 s; and hybrid search with FTS5 finds exact product codes that vector search alone missed.

Gotchas

  • Unnormalised vectors with dot product. Results are wrong for cosine similarity. Normalise at insert.
  • HNSW for small collections. Flat search is exact and fast enough. Measure first.
  • Ignoring memory. A million f32 vectors exceed tab budgets. Quantise.
  • Mixing embeddings from different models. Results are meaningless. Store the model version.
  • No recall measurement. Quality degrades silently. Compare against exact search.

Performance note

Flat search over 20,000 384-dimensional vectors took 6 ms with SIMD and 19 ms without on a mid-range phone; HNSW over 800,000 vectors took 4 ms per query.

Query latency on a mid-range phone Milliseconds per query for flat search over 20,000 vectors without SIMD and with SIMD, and for HNSW search over 800,000 int8-quantised vectors. ms per query flat, 20k, scalar 19 ms flat, 20k, SIMD 6 ms HNSW, 800k, int8 4 ms

Frequently Asked Questions

Can DuckDB or SQLite do vector search? Extensions exist for both (for example vector similarity functions); availability in Wasm builds varies, so check before relying on them.

Which distance metric should I use? The one the embedding model was trained for — usually cosine similarity on normalised vectors.

How do I delete items from HNSW? Most implementations mark deletions and rebuild periodically; plan for compaction.

Should embedding run in the same worker? Separate workers let embedding (heavy) and search (light) run without blocking each other.

How do I detect that the index and database have drifted apart? Compare item counts and an ID checksum at startup; rebuild in the background if they differ.

← Back to Databases & Persistent Storage in Wasm