Retrieval quality against index size for on-device browsing history

The Dart Agent's core claim is that it answers from what you have actually read. That requires an index over your browsing history, and it has to live on your machine. Which turns a research problem into an engineering one: how good can retrieval be inside a storage and latency budget a laptop will tolerate?

We built a 14-month synthetic browsing corpus — 41,000 documents, with a realistic mix of long articles, documentation, short pages, and PDFs — and a set of 1,200 queries written to resemble what people actually ask an agent about their own history. Then we evaluated seven index configurations against it.

The curve bends early

The unquantised 1024-dimension baseline is the ceiling, and it costs 8.2 GB for our corpus — which for a 14-month history is more than most people will accept for a browser feature. The interesting result is how quickly the curve approaches it. A 384-dimension embedding with product quantisation reaches 91% of baseline recall at 0.9 GB. Doubling that storage to 1.8 GB recovers only a further three points.

The row we recommend is not the highest-recall row. It is the one where a hybrid approach — dense vectors for semantic similarity plus a chunk-level inverted index for exact terms — recovers five recall points over dense-only at almost no storage cost. Browsing queries turn out to contain a lot of exact strings: error messages, function names, product SKUs, people's names. Dense retrieval handles those poorly and an inverted index handles them almost for free.

Why more storage stops helping

Past roughly 900 MB, the errors that remain are not representation errors. We hand-inspected 200 failures from the best configuration and found that 71% of them were chunking failures: the relevant passage spanned a boundary, or a table was split from its caption, or a document's structure meant the answer lived in a section whose surrounding text did not resemble the query at all.

This reframes where effort should go. Once you are past the knee of the curve, buying a larger embedding model improves the smallest category of failure. Improving how documents are split — respecting headings, keeping tables with captions, overlapping windows across boundaries — addresses the largest. We spent the following quarter on chunking rather than embeddings, and it was the right call by a wide margin.

We were about to buy a bigger embedding model. The failure analysis said the bottleneck was three lines of splitting logic. Measuring the failures rather than the successes saved us a quarter.

Latency and the update path

Query latency matters less than people assume, because 38 ms is imperceptible next to the inference that follows it. The number that actually constrains the design is incremental update cost. Every page you visit has to be chunked, embedded, and inserted while you are using the browser, on the same hardware that is rendering it.

At the recommended configuration, indexing a typical article costs about 240 ms of background compute, which we schedule during idle periods and cap so it never competes with the compositor. The 1024-dimension configurations cost roughly 1.4 s per page — and a person browsing quickly can outrun that, which produces an index that is permanently behind and a browser that feels warm. That failure mode does not show up in a recall benchmark at all.

Method

Limitations

A synthetic corpus is the weakest part of this study. We built it to resemble real browsing, but we generated it, and a real 14-month history has structure — revisits, bursts around projects, long dormant stretches — that we approximated rather than reproduced. Our queries were written by people who knew the corpus, which almost certainly makes them easier than genuine questions about a history you half remember. Recall@10 is also a proxy: what matters is whether the agent's final answer was right, and a retrieval miss is sometimes recoverable while a retrieval hit is sometimes wasted. We are working on an end-to-end measure and expect it to be less flattering.

The corpus generator, query set, and evaluation harness are open. If you have a real browsing history you would be willing to evaluate against locally — nothing leaves your machine, the harness reports aggregate scores only — we would value the result: research@dartbrowser.com.

Related work

Dense retrieval [1] and the approximate-nearest-neighbour structures that make it practical [2, 3, 4] are mature. BEIR [6] established that retrieval quality generalises poorly across domains, which is the finding most relevant to us: personal browsing history is a domain with no public benchmark and unusual properties, including heavy revisitation and a long tail of near-duplicates. Our failure analysis also echoes a point made repeatedly in the hybrid-retrieval literature [5] — that lexical matching remains necessary for exact strings — and quantifies how much it is worth in this specific setting.

Artefacts

Everything below is published or available on request. A number nobody can reproduce is an advertisement, not a result.

References

1. Karpukhin, V., Oğuz, B., Min, S., et al. (2020). Dense Passage Retrieval for Open-Domain Question Answering. EMNLP.
2. Jégou, H., Douze, M., & Schmid, C. (2011). Product Quantization for Nearest Neighbor Search. IEEE TPAMI, 33(1).
3. Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI.
4. Johnson, J., Douze, M., & Jégou, H. (2019). Billion-scale Similarity Search with GPUs. IEEE Big Data.
5. Robertson, S., & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in IR.
6. Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., & Gurevych, I. (2021). BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets & Benchmarks.