Updated July 2026: TraceMind retired its k-d-tree index in v1.3.0; this article now describes the current architecture.
Local AI tools have a speed problem that does not get discussed enough. Running an embedding model in the browser via WASM is genuinely fast. Querying 50 stored vectors against a new embedding is trivially fast. But the folklore says that once you reach thousands of pages, you need a specialized index or search falls apart.
I believed that folklore too. TraceMind originally shipped with a Voy k-d-tree index for exactly this reason. Then I took it out. This is the story of why, and why the thing that replaced it, a plain brute-force scan, is faster to reason about and fast enough in practice.
The baseline: what makes vector search slow
When you type a search query, TraceMind generates an embedding for that query using all-MiniLM-L6-v2. The result is a 384-dimensional vector, a list of 384 numbers that encode the semantic meaning of your query.
To find relevant pages, you need to find stored page embeddings that are close to the query embedding in that 384-dimensional space. "Close" means having a high cosine similarity.
The brute-force approach: compute the similarity between the query vector and every stored vector, sort, return the top results. This is exact, correct, and completely predictable. It is also O(n) in the number of stored vectors, which means the cost grows linearly with your history size.
The standard worry is that O(n) does not scale. And in the general case, that is true. If you have millions of vectors, scanning all of them per query is wasteful, and that is precisely the problem approximate nearest-neighbor indexes were invented to solve.
If you want to understand the embedding layer itself before diving into retrieval, the post on how vector embeddings work in your browser covers it thoroughly.
Why we reached for a k-d tree first
A k-d tree (k-dimensional tree) is a space-partitioning data structure. It recursively splits the dataset along different dimensions, building a binary tree so that a query can prune away large regions of the space instead of checking every point. In low-to-moderate dimensions it turns an O(n) scan into something much closer to O(log n).
Voy packaged this up nicely: a Rust vector-search library compiled to WASM, with a clean API to build an index, add vectors, query for nearest neighbors, and serialize the index to IndexedDB so it survived between sessions. On paper it was the textbook answer, and that is exactly why I chose it.
But two problems showed up once it was running inside a real Manifest V3 extension.
The first is the curse of dimensionality. K-d trees work well in low dimensions (roughly 2 to 20). At 384 dimensions the pruning that makes them fast stops working well, because there are too many dimensions along which a branch might still hide a closer neighbor. At that point a k-d tree is doing a lot of bookkeeping to avoid a scan it half ends up doing anyway.
The second problem was the browser itself, and it turned out to be decisive.
The CSP wall
Chrome extensions on Manifest V3 run under a strict Content Security Policy. The policy that makes extensions safer, no arbitrary code execution, is the same policy that WASM vector libraries fight with. The kind of dynamic code generation these libraries rely on needs the unsafe-eval class of permissions that Manifest V3 does not grant to extension pages.
So the index lived in an awkward place: technically present, but a dormant, fragile code path that had to be nursed around the security model rather than working with it. I was maintaining complexity to keep an optimization alive that, at TraceMind's actual scale, I did not need.
That is the moment worth being honest about. The engineering-textbook choice and the right choice were not the same choice.
What replaced it: brute force over a packed int8 cache
In v1.3.0 I removed the Voy index entirely and replaced it with the simplest thing that could possibly work: brute-force cosine similarity in plain JavaScript.
The trick that makes "brute force" a non-embarrassing answer is the data layout. Instead of storing embeddings as scattered float arrays, TraceMind quantizes each 384-float vector down to 384 bytes (int8) and packs them into one contiguous cache. Quantization shrinks the memory footprint enough that the whole set of vectors sits in compact memory, and the similarity loop runs over tight, contiguous bytes instead of chasing pointers across the heap.
The result:
- It is CSP-safe. Plain JavaScript over typed arrays needs no special permissions, so it works with the extension security model instead of against it.
- It is exact. Every vector is compared, so a strong semantic match is never pruned away by an index heuristic.
- There is no index to build. Adding a page appends one vector to the cache. Nothing to serialize, reload, or keep in sync.
- It is fast enough. At thousands to tens of thousands of vectors, a full scan finishes in the low milliseconds, comfortably inside the budget for search that feels instant.
A Bloom filter still sits in front of the pipeline, but its job is narrow and deliberate: a fast pre-check that can reject a query with no possible matches before any scanning happens. It is a filter, not the index.
How retrieval fits the search pipeline
TraceMind uses Reciprocal Rank Fusion (RRF) to combine two ranked lists:
-
Brute-force cosine results: the top stored page embeddings closest to the query embedding. This is the semantic signal: pages conceptually related to your query even if they share no exact keywords.
-
FlexSearch full-text results: a text index that matches exact terms, partial terms, and document-frequency patterns. This catches proper nouns, version numbers, and specific terminology that semantic similarity can blur over.
RRF merges the two lists with a formula that rewards documents appearing high in both and penalizes documents that only rank well in one. The merged list is the final ranking.
This hybrid approach matters in practice. Pure semantic search sometimes surfaces documents that are thematically related but not specifically relevant. Pure keyword search misses documents that discuss the same concept with different vocabulary. The combination handles both failure modes better than either alone.
The post on building local-first AI goes deeper on the storage architecture if you want the full picture.
Where the embedding model runs
Worth separating clearly: dropping the vector index did not change how embeddings are produced. The all-MiniLM-L6-v2 model runs via WebGPU when your hardware supports it, and falls back to single-threaded WASM otherwise. That is the compute-heavy part of the pipeline, and it stays on-device either way. The retrieval layer, the part this post is about, is just a cosine loop over the vectors the model produced.
What happens when the corpus gets very large
It is worth being honest about the scaling ceiling here, because "brute force" does have one.
At thousands of pages the scan is instant. At tens of thousands it is still comfortably within budget. At hundreds of thousands to millions of vectors, O(n) per query would eventually stop being free, and that is exactly the regime where an approximate index like HNSW earns its complexity.
But a personal browser history is not that regime. Most users accumulate thousands to tens of thousands of pages, and TraceMind has no page cap; new installations default to keeping captured history until the user chooses a shorter window. Browser storage capacity is the practical ceiling. That corpus size sits well inside the range where a scan wins on simplicity without losing on speed.
If TraceMind ever needed to serve much larger corpora, the right move would be a purpose-built approximate index, reintroduced deliberately, not the k-d tree we started with. Until then, adding that machinery back would be complexity in search of a problem that does not exist yet.
This is the kind of architectural decision that TraceMind's local-first approach was built around: fit the technology to the actual problem, and do not over-engineer for scale that has not arrived.
The practical result
The end effect of all this, quantized vectors, a packed cache, an exact cosine scan, RRF fusion, is that search in TraceMind feels fast regardless of how large your history has grown, and the code that delivers it is small enough to hold in your head.
You type a query. The query gets embedded. The cosine scan returns the nearest vectors. FlexSearch returns keyword matches. RRF merges them. Results appear, well inside the threshold where people perceive latency as lag.
That responsiveness is what makes semantic search useful as a daily tool rather than an occasional novelty. Slow search gets abandoned. Fast search becomes a reflex.
The lesson I took from retiring the k-d tree: on consumer hardware, in a browser tab, at personal scale, the fastest thing is often the simplest thing that fits the constraints, not the cleverest structure from the textbook.