Semantic search in Dart without the hand-written cosine loop

A packed matrix and SIMD dot products for top-k similarity, with the memory numbers spelled out.

I had a Flutter app with about 20,000 short documents and a 384-dimension embedding for each one. Take the user's query embedding, find the five closest documents by cosine similarity, show them. On device, no server round trip.

The first version is the obvious one. Embeddings in a List<List<double>>, a loop that scores every row, sort, take the top five.

double cosine(List<double> a, List<double> b) {
  var dot = 0.0, na = 0.0, nb = 0.0;
  for (var i = 0; i < a.length; i++) {
    dot += a[i] * b[i];
    na += a[i] * a[i];
    nb += b[i] * b[i];
  }
  return dot / (sqrt(na) * sqrt(nb));
}

List<int> topK(List<double> query, List<List<double>> rows, int k) {
  final scored = <MapEntry<int, double>>[];
  for (var i = 0; i < rows.length; i++) {
    scored.add(MapEntry(i, cosine(query, rows[i])));
  }
  scored.sort((x, y) => y.value.compareTo(x.value));
  return scored.take(k).map((e) => e.key).toList();
}

This is correct. It is also 15.9 ms per query over the 20,000-row index on my machine (Apple Silicon, Dart 3.11). At 15.9 ms you feel it when the user is typing and you want to re-rank on each keystroke, and it grows linearly with the corpus.

The cost is not the algorithm. A linear scan is the right algorithm at this size. The cost is the layout. List<List<double>> is a list of pointers to separate heap objects, each double is a boxed 64-bit float, and the inner loop chases pointers and reads memory that was never meant to be walked in order.

The packed layout

vector_kit stores the whole index as one contiguous Float32List and scores it with SIMD. Same linear scan, same exact results, different memory.

import 'package:vector_kit/vector_kit.dart';

// rows: List<List<double>> of 20000 x 384, from your embedding model.
final index = VectorMatrix.fromRows(rows);

final query = model.embed(userText); // List<double>, length 384
final hits = index.topKCosine(query, 5);

for (final hit in hits) {
  print('${hit.index}  score=${hit.score}');
}

topKCosine over the 20,000-row index, top-5, runs in 1.4 ms. That is the same 15.9 ms work from above, about 11x faster, and the ranking is identical because nothing is approximated.

One detail that saved me a wrapper: query is a plain List<double>. The embedding that comes out of a model is already a List<double>, and it goes straight into topKCosine with no conversion to Float32List at the call site. The matrix is packed once when you build it, not on every query.

The primitive underneath is a dot that maps to hardware SIMD. At 768 dimensions it is 142 ns per call, against 665 ns for the equivalent loop over two List<double>. The raw product is exposed if that is all you need:

final a = Float32List.fromList(embA);
final b = Float32List.fromList(embB);
final d = dot(a, b); // 142 ns at 768 dims

The gap holds at larger scale. topKCosine with k=10 over 100,000 rows is 13.3 ms. The full-scan-and-sort baseline over the same data is 82 ms. The packed version never materializes 100,000 score entries into a list and sorts them. It keeps a running top-k, so it does less allocation as well as less arithmetic.

What the index costs in memory

The 20,000 x 384 index in float32 is 29.3 MB. That is the number you have to budget for, because it sits in memory for the life of the feature, and on a phone 29.3 MB is not free.

vector_kit has an int8 QuantizedMatrix that holds the same index in 7.6 MB, a quarter of the float32 size.

final quant = QuantizedMatrix.from(index);
final hits = quant.topKCosine(query, 10);

Quantization is lossy, so the question is what it costs in ranking quality. I measured recall against the float ranking instead of assuming it. On the demo's data the int8 index returned 100% recall@10, meaning the top-10 set matched the float top-10 exactly. That number is data-dependent. If your embeddings are less separated you will lose some recall, so run the same measurement on your own corpus before you ship. The tool to do that is in the box. The guarantee is not.

When not to use it

This is a linear scan. Every row is scored on every query. That is why the results are exact and why there is no index to build or tune beyond packing the matrix. It also sets a ceiling.

Up to somewhere around 100k to 1M vectors, scanning is fine and the numbers above are what you get. Past that, into tens of millions of vectors, a linear scan is the wrong structure no matter how tight the inner loop is, and you want an approximate nearest neighbor index (HNSW, IVF) that trades exactness for sublinear query time. vector_kit does not do that and does not pretend to. At that scale, reach for a real ANN library or a vector database and pay for the recall tuning that comes with it.

It is also not a full linear algebra package. It does dot products, cosine similarity, and top-k over a packed matrix. For general matrix multiply, decompositions, or autograd, this is not that.

For the case it targets, an exact top-k over a corpus that fits in memory on the device, the two numbers that matter are 1.4 ms per query and the choice between 29.3 MB and 7.6 MB for the index. Those are the ones I would check against your own data first.