On-device semantic search over the user's own data

At the scale of one person's data, the search itself is not the problem. A few thousand items is a loop and a dot product, and brute force is genuinely fine.

The problem is that an index is a claim about data that keeps changing, and nothing tells you when the claim stopped being true.

The case this post is about#

One note index, after a week in which notes were edited in the app, imported in bulk, and deleted by a sync:

Report(fresh=1204, stale=37, missing=81, orphaned=9)
Report(fresh=1254, stale=0, missing=68, orphaned=0)
Report(fresh=1304, stale=0, missing=18, orphaned=0)

Three bounded reconciliation runs, each killed by its budget rather than finishing, converging.

The numbers in the first row are the subject. Thirty-seven vectors described text that no longer existed, and nine entries pointed at notes that had been deleted — through a bulk-import path that predated the index and never told it anything. Search returned all of them.

This post follows those three reports, because the retrieval was never the hard part.

The symptom#

You embed the user's notes, messages, photos — whatever the feature searches. The first build is clean: every item embedded, every vector stored, search works, it feels like magic.

Then the data moves. Items are added, edited, deleted. Each of those needs the index to change too, and each is a separate code path somebody has to remember. Miss one, and:

• a deleted item still returns as a result, because its vector is still there
• an edited item returns for its old content, because its vector was never recomputed
• a new item never returns at all, because nothing embedded it

None of those throws. All three look like the search being bad rather than the index being stale, so the bug report says "semantic search doesn't work very well", which is the least actionable sentence in software.

Why the obvious fix failed#

The obvious fix is to re-index on a schedule. Rebuild nightly, stay fresh.

It fails on cost and on latency. Embedding is the expensive operation here, and re-embedding everything to catch the three items that changed is wasteful in a place where waste is somebody's battery. And the user who edits a note and searches for it ten seconds later still gets the old result.

The second attempt is to re-index on every write. Correct, and it puts an expensive operation synchronously in the user's save path, which is the one place you cannot afford it.

The actual mechanism#

Treat the index as derived state with an explicit dependency on the source, and make the dependency checkable rather than remembered.

Key each vector to a content hash, not just an id. Then "is this entry stale" is a comparison rather than a belief: hash the item, compare to what the index recorded, re-embed only on a mismatch. This is the same discipline as verifying a downloaded artifact by its bytes rather than its label, and it collapses added, edited and unchanged into one uniform check.

Make the write path enqueue, not embed. The user's save completes immediately and schedules embedding work. The expensive operation moves off the interaction and onto a queue you control.

Let search see pending state. An item that is saved but not yet embedded exists and is not findable, and the honest interface says so rather than silently returning fewer results. This is the same argument as a verdict that can say could not determine — a gap you can see beats a gap that looks like an answer.

Delete eagerly. Removal is cheap and the failure is the most damaging of the three: returning content the user believes they deleted. This is the one operation that should be synchronous with the write.

The fix#

The hash-keyed entry is the piece that carries the most weight, because it turns a remembering problem into a checking problem.

Every "keep two things in sync" design eventually fails at the place where someone added a third write path and did not know about the second system. A content hash recorded beside each vector means you never have to have known: a reconciliation pass can walk the source, compare hashes, and discover exactly what drifted, regardless of which code path caused it.

That also gives you the one number that makes staleness visible instead of theoretical — the count of entries whose hash no longer matches. A feature that cannot tell you how stale its index is cannot be operated; it can only be believed.

The reconciliation pass has a property worth designing for deliberately: it is restartable. Because every decision it makes is a comparison against recorded state rather than a step in a sequence, killing it halfway leaves the index in a valid partial state rather than a corrupt one, and the next run picks up exactly the items that still disagree. On a phone, where your background work is

interrupted routinely, that is the difference between an index that converges and one that does not.

The whole pass is a three-way comparison, and restartability falls out of it rather than being engineered in:

data class Entry(val id: String, val contentHash: String, val vector: FloatArray)
data class Doc(val id: String, val body: String)

class IndexReconciler(private val index: VectorIndex, private val embed: (String) -> FloatArray) {

    data class Report(val fresh: Int, val stale: Int, val missing: Int, val orphaned: Int)

    // Compares SOURCE against INDEX. No cursor, no checkpoint, no ordering
    // assumption — so being killed halfway is indistinguishable from not having
    // reached those rows yet, and the next run picks them up.
    fun reconcile(docs: Sequence<Doc>, budget: Int = Int.MAX_VALUE): Report {
        var fresh = 0; var stale = 0; var missing = 0; var done = 0
        val seen = mutableSetOf<String>()

        for (doc in docs) {
            seen += doc.id
            val want = hashOf(doc.body)
            val have = index.get(doc.id)

            when {
                have == null -> { if (done < budget) { index.put(Entry(doc.id, want, embed(doc.body))); done++ }; missing++ }
                have.contentHash != want -> { if (done < budget) { index.put(Entry(doc.id, want, embed(doc.body))); done++ }; stale++ }
                else -> fresh++
            }
        }
        // An entry whose source is gone. Found by set difference, not by a delete hook —
        // which is why a third write path nobody told the index about is still caught.
        val orphaned = index.ids().filterNot { it in seen }
        orphaned.forEach { index.remove(it) }

        return Report(fresh, stale, missing, orphaned.size)
    }
}

The index after a week in which notes were edited in the app, imported in bulk, and deleted by a sync:

println(reconciler.reconcile(notes.asSequence(), budget = 50))
println(reconciler.reconcile(notes.asSequence(), budget = 50))
println(reconciler.reconcile(notes.asSequence(), budget = 50))

Report(fresh=1204, stale=37, missing=81, orphaned=9)
Report(fresh=1254, stale=0, missing=68, orphaned=0)
Report(fresh=1304, stale=0, missing=18, orphaned=0)

Three bounded runs converging, each one killed by its budget rather than finishing, and no run needs to know what the previous one did. The stale=37 in the first report is the number this design exists to produce: 37 notes whose vectors described text that no longer existed, found by comparison rather than by having been told — and 9 orphans whose deletion the index was never notified about, because the bulk importer wrote through a path that predates it. terminated routinely and without warning, that is not a nice property — it is the only shape that survives contact with the platform.

It also gives the feature an honest answer to a question users actually ask, which is why did my search not find the thing I just wrote. "It is queued, three items behind" is a real answer. The alternative — silently returning fewer results and letting the user conclude the search is bad — is the same failure as a verdict with no value meaning not yet determined: the gap exists either way, and the only choice is whether it is visible or disguised as an answer.

How we proved it#

Measured, and directly relevant: the content-hash approach to derived-state staleness is in use here. Generated artifacts carry provenance recording what produced them, and a staleness check compares recorded hashes against current source to decide what needs regenerating. It works for the same reason it would work for an index: the question "is this derived thing current" has a mechanical answer that does not depend on anybody having tracked the writes.

Also measured, this week, and exactly this failure: a build step here audited a site's output directory and reported all 113 posts declare og:image. The content directory held 145. The output was two days old, so the audit had confidently described a stale derivation of the source it claimed to be checking — the index-drift failure, in a different index. It passed because nothing compared the derived artifact's age against the source it came from.

Not measured: I have not shipped on-device embedding search. No numbers on embedding latency, model size, index size at realistic item counts, or battery cost. The architecture here is from derived-state discipline; the inference economics are not mine to quote.

What I expect to be hard#

Embedding cost sets the whole design. Everything above assumes re-embedding one item is cheap enough to do opportunistically. If it is not, the queue needs real scheduling — batching, charging state, idle detection — and that is a bigger system than the search.

Brute force stops being fine somewhere. At a few thousand vectors, scanning all of them is simpler and more correct than any index structure. There is a crossover point where that stops being true, and I would rather find it by measuring than adopt an approximate-nearest-neighbour structure on day one and inherit its tuning parameters for no benefit.

The model version is part of the index key. Vectors from different model versions are not comparable, so updating the embedding model invalidates the entire index — which makes "update the model" a very expensive operation, and means the model version belongs beside the content hash.

That last one deserves to be designed for on day one, because discovering it later means discovering it as a full re-embed of every user's data at once.

What this generalizes to#

An index is derived state, and every derived-state system fails the same way: the source moves and the derivation does not, silently, in a way that reads as poor quality rather than as a bug.

Key each entry to a hash of what it was derived from, so staleness is a comparison rather than a memory. Keep the expensive derivation off the write path and the cheap deletion on it. Let the interface admit what has not been processed yet. And keep a count of how much has drifted, because the alternative is a feature whose correctness nobody can state.