On-Device Embeddings

Chapter 1: The Budget

“It has to run in 30 milliseconds” is the kind of sentence that gets said in planning meetings and then never derived. Let us derive it, because the number is not one number — it is three different numbers for three different regimes, and knowing which regime you are in tells you which of the four dials to turn.

Where 30 milliseconds comes from

Regime 1 — interactive query. The classic human-factors result is that responses under about 100 ms feel instantaneous; past that, the user perceives the system reacting rather than simply being. So the whole query path gets 100 ms. Spend it:

Note what the table teaches immediately: the neural network is 2 of 60 milliseconds. If you spent a month making the text encoder twice as fast you would win one millisecond of a sixty-millisecond path. The thumbnails are the bill. This will keep happening.

Regime 2 — live camera. If you are embedding what the camera sees, every frame, the budget is the frame interval. At 30 frames per second that is

and the model does not get all of it — the camera pipeline, the preview render, and any drawing you do share the frame. Twenty milliseconds for the model is a realistic slice. This is where the famous 30 ms figure lives.

Regime 3 — background indexing. There is no latency budget at all. Nobody is waiting. What exists instead is a thermal budget and an energy budget, and they are the subject of the last third of this chapter.

The four currencies

Every on-device model spends four things, and they are only loosely related to each other. Confusing them is the single most common source of bad on-device decisions.

A multiply–accumulate, precisely

A MAC is one multiply plus one add: acc += a * b. It is the atom of neural network arithmetic because every convolution and every matrix multiply is a pile of them. Hardware vendors usually quote TOPS — tera-operations per second — and count a MAC as two operations. So:

There is a second, nastier ambiguity. Papers report “FLOPs” for models, and in the efficient-vision literature that number is almost always MACs, not floating-point operations. When MobileCLIP’s paper lists its MCi0 image encoder at 2.4 G FLOPs at 256×256 input, read it as 2.4 billion MACs — 4.8 billion arithmetic operations. We will carry it as MACs and say so every time.

Worked example: can MCi0 hit 30 ms on a phone NPU?

Real numbers, from the MobileCLIP paper (Vasu et al., 2023). The MCi0 image encoder has 11.8 M parameters in its ImageNet-classification form (11.4 M as the image tower of MobileCLIP-S0), takes 2.4 G MACs at 256×256, and the authors measure 1.5 ms on an iPhone 12 Pro Max. Our job is to reproduce that order of magnitude from first principles so we can predict it for hardware we do not have.

Step 1 — the compute time. Assume a modest neural accelerator rated at 2 TOPS for 8-bit integers. Peak MAC rate:

Nobody achieves peak. Real convolution stacks with varying shapes, depthwise layers, and layout changes get somewhere between 20% and 60% of it. Take 40%:

Step 2 — the memory time. Every weight must be read at least once. At int8, 11.4 M parameters is 11.4 MB. A phone’s accelerator might see 25 GB/s of usable bandwidth:

Step 3 — which one wins? The two times are not added; the hardware overlaps them. The larger one dominates, and there is a clean way to know which without doing both calculations. Define arithmetic intensity: MACs performed per byte read.

And define the machine balance: how many MACs the chip can do in the time it takes to read one byte.

Since I = 210 > 16 = B, this workload is compute-bound by a factor of 13. The prediction is 6.0 ms, dominated by arithmetic. The paper measures 1.5 ms — four times better, which tells you the A14’s neural engine is both faster than our 2 TOPS assumption and better utilized than 40%. That is exactly what a first-principles estimate is for: it gets you the right order of magnitude and tells you which resource to argue about.

The layer that is bandwidth-bound anyway

The 210 figure is an average over the whole network, and averages lie. Consider a single 1×1 convolution at the deep end of the network: input 8×8×512, output 8×8×512.

Comfortably compute-bound. Now the same layer applied to a 1×1 spatial grid — a classifier head, or the final projection:

Sixty-four times less intense, and now sixteen times below the machine balance of 16. That layer runs at 1/16 of the chip’s peak no matter how you optimize the arithmetic, because it is waiting on memory. This is why the last few layers of a small network often take a disproportionate share of the runtime, and why “we cut 30% of the MACs and got 4% faster” is such a common and confusing result.

Parameters are not latency: the text tower proves it

MobileCLIP-S0 pairs the 11.4 M-parameter MCi0 image tower with a text tower called MCt that has 42.4 M parameters — nearly four times as many — and runs in 1.6 ms, essentially the same time as the image tower’s 1.5 ms. How?

Two reasons, and both are worth internalizing.

Reason one: most of those parameters are a lookup table. CLIP-family text encoders use a byte-pair vocabulary of 49,408 tokens. At the usual base text width of 512, the token embedding table alone is

which is over half of MCt’s 42.4 M. And a lookup table costs exactly zero MACs. You read 77 rows out of 49,408 and move on. Those 25 million parameters cost you disk and RAM and nothing else.

Reason two: the sequence is 77 positions, not 65,536. A 256×256 image is 65,536 pixels; the convolution stack processes a spatial grid that starts enormous. The text encoder processes 77 token positions. For a transformer-shaped block, MACs are roughly (sequence length) × (non-embedding parameters):

Same ballpark as the measured 1.6 ms, again with our conservative chip. So the text tower is bigger on disk and comparable in time. If you were optimizing for app download size you would attack the text tower; if you were optimizing for indexing throughput you would attack the image tower. They are different problems and the parameter count told you nothing about which.

Worked example: the energy bill for indexing 40,000 photos

This is regime 3, and it is where on-device projects actually die. Compute it properly.

Step 1 — energy per model call. Mobile accelerators land in the neighbourhood of 1–3 TOPS per watt for int8 work. Take 2 TOPS/W, meaning 2 × 10¹² operations per joule. Our encoder does 2.4 G MACs = 4.8 G ops:

Step 2 — energy for everything else. Before the model sees anything, a 12-megapixel JPEG must be decoded and resized to 256×256. A hardware JPEG decoder is efficient but not free; call it 30 mJ for a 12 MP frame, a plausible measured ballpark and one you must confirm on your own hardware. Add ~0.6 mJ for the resize and normalize.

Step 3 — the sweep.

Step 4 — as a fraction of a battery. A 4,400 mAh cell at a nominal 3.85 V holds

That is an acceptable number: about the same as fifteen minutes of screen-on time, spent once, overnight, while charging. The project survives.

Now look at where the 2.16% went.

The neural network is one-fourteenth of the bill. If you halved the model — a genuinely hard research achievement — you would move total energy from 2.16% to 2.08% of a charge. If instead you used the photo library’s existing thumbnails rather than decoding full-resolution originals, you might cut the decode cost by 20× and take the whole sweep to 0.24% of a charge.

Thermal: why 10 minutes of work takes 40 minutes

Wall-clock time for the sweep, if it ran flat out:

(taking 8 ms decode + 1 ms resize + 6 ms encode + 0.3 ms write per photo). But the phone will not let you. Sustained heavy accelerator use raises the skin temperature, the governor throttles clocks, and the OS suspends background tasks that misbehave. A realistic sustained duty cycle for a background indexer is 25–40%. At 25%:

which is fine if you run it while charging and screen-off, and is a disaster if you run it during a user’s first launch while they wait. That scheduling decision is worth more than any model choice on this page.

Concept → realization: what “fits” means in bytes

Put the whole memory picture in one table so you know what you are shipping. Byte counts use 10⁶ per MB, the convention app stores use.

Read the last two rows against each other. The index is the thing that has to be resident all the time, and it is the thing Chapter 3 shrinks by a factor of fifteen for almost nothing. The towers are big but episodic: you load the image tower during the sweep and unload it, you load the text tower when the user opens search and unload it when they leave. Episodic memory is cheap; resident memory is what gets your process killed.

Chapter 2: Shrinking the Encoder

Chapter 1 gave us a budget. Now we need a model that fits inside it and is still worth running. There are three genuinely different ways to make an encoder smaller, they compose, and people constantly confuse them.

Pruning is a fourth — removing weights or channels outright — covered in the site’s TinyML series. This chapter builds the first three on a real system, MobileCLIP, and then does the size arithmetic.

Architecture: what a mobile-shaped encoder looks like

MobileCLIP’s image tower, MCi, is built from the FastViT family: reparameterizable convolution blocks plus convolutional token mixing, rather than a pure vision transformer. Two design decisions in it are worth staring at because they are counterintuitive.

Decision one: lower the feed-forward expansion, raise the depth. A standard transformer feed-forward block expands the channel width by 4× and contracts it back. The MobileCLIP authors set that expansion to 3.0 and added layers, keeping the image encoder’s parameter count the same. Their reported finding is that this has minimal impact on latency but a good improvement in capacity.

Why would that be? Because a wide feed-forward layer is a big matrix multiply with low arithmetic intensity per parameter at the small spatial resolutions where it lives — exactly the bandwidth-bound regime from Chapter 1. Trading width for depth moves parameters into places where they are reused across more spatial positions. Same parameter budget, more useful work per byte read.

Decision two: the three MCi variants differ only in width and depth. Here is the published stage configuration, where C is channels per stage and L is blocks per stage:

MCi1 is MCi0 with every stage doubled in depth. MCi2 is MCi1 made 25% wider. Do the marginal arithmetic, because this is how you decide which one to ship:

The first millisecond buys 1.6 points; the next 1.1 milliseconds buy 0.7. Diminishing returns, as always — but now quantified, so “which variant” is an arithmetic question rather than a taste question. Multiply by your call count: for the 40,000-photo sweep, choosing MCi2 over MCi0 costs 40,000 × 2.1 ms = 84 s of extra compute and roughly 2.3 extra points of accuracy.

The text encoder ablation, which is the best table in the paper

MobileCLIP’s text tower MCt is a hybrid: convolutional “Text-RepMixer” blocks plus a few self-attention blocks. The authors swept how many self-attention layers to include, and the result is the cleanest illustration of marginal return you will find.

Compute accuracy per millisecond for the first step and the last step, by hand:

One attention layer in an otherwise convolutional text encoder is worth 2.1 accuracy points for a tenth of a millisecond. Layers five and six are worth 0.1 points for three-tenths of a millisecond. The paper picks 4, which is where the curve has clearly flattened but has not yet started costing you for nothing.

Distillation: MobileCLIP’s multi-modal reinforced training

Architecture gets you a fast network. It does not get you an accurate one: small contrastive models trained the ordinary way are markedly worse, because contrastive learning on noisy web captions is data-hungry and a small model cannot absorb enough signal per example.

MobileCLIP’s answer is a training method, not an architecture, and the trick is worth understanding in full because it is reusable.

The ordinary recipe. Take image–caption pairs off the web. Encode both. Push matching pairs together and non-matching pairs apart with a contrastive loss. Problem: web captions are noisy and often not descriptive (“IMG_2231”, “so cute!!”), so the supervision per example is weak.

The reinforced recipe, in three moves.

Move 1 — synthetic captions. Run a captioning model (the paper uses CoCa ViT-L-14) over every image and generate several descriptive captions. Now each image has its real caption and a handful of manufactured ones that actually describe the pixels.

Move 2 — an ensemble teacher. Run a set of strong CLIP encoders — the paper uses OpenAI’s ViT-L-14 and a DataComp-XL ViT-L-14 — over the images and captions and record their embeddings. The student is then trained not only to match the right caption, but to reproduce the similarity structure that the big teachers see. That is knowledge distillation, applied to a contrastive space.

Move 3 — store all of it. This is the part that makes it practical. Captions, image augmentation parameters, and teacher embeddings are computed once, offline, and stored alongside the dataset. The result is called a reinforced dataset. The paper ships two: DataCompDR-12M with 30 stored image augmentations per sample, and DataCompDR-1B with 10 — five synthetic captions each, in both cases. During training you read the teacher’s answer off disk instead of running a ViT-L-14 forward pass. The paper reports that training on DataCompDR therefore carries no time overhead versus non-reinforced training.

Why the small dataset stores more augmentations than the big one

Thirty augmentations for the 12-million-sample set and ten for the billion-sample set reads backwards the first time. Surely the bigger dataset gets the bigger treatment? It does not, and working out why turns a memorized number into a rule you can apply to your own training run.

One stored augmentation is consumed per pass over a sample. Store fewer than the number of passes and the model sees the same crop twice; store more and the extra ones are dead bytes on disk. So the right count is the epoch count. Count epochs for each dataset from the published schedule:

There it is. The 12M set is small, so a fixed compute budget sweeps it thirty times; the 1B set is large, so the same style of budget sweeps it ten. The augmentation count is not a quality dial that someone tuned. It is the epoch count, precomputed and written into the dataset.

That cross-check is worth the space for a second reason. One sentence in the paper’s own ablation section states the assignment the other way round, contradicting both its dataset section and its storage tables. Papers contain typos. The defence is not to read more carefully; it is to hold every quoted number against a second number that would have to move with it.

The loss, and the coefficient that is quoted wrong more often than any other

The student’s total loss is a single mixing coefficient λ between the ordinary CLIP contrastive term and the distillation term:

L_CLIP is “get this specific pair right” — the standard contrastive loss over a batch of b image–text pairs. L_Distill is “see the batch the way the teachers see it”: build the b × b matrix of image-to-text similarities, row-softmax it for both student and teacher, and take the KL divergence between the two, symmetrized over image-to-text and text-to-image. Note the shape carefully — the distillation target is a b × b matrix of relative preferences, not a d-dimensional vector. The student is never asked to reproduce the teacher’s coordinates, only its rankings — which is what lets an 11.4 M-parameter student learn from a far larger ViT-L-14 teacher whose embeddings are a different width entirely. The stored teacher vectors are 1536-dimensional, being the concatenation of two 768-D ensemble members; MobileCLIP-S0’s own embedding is 512-D. Those two numbers never have to match, because only the b × b similarity matrices are compared, and a similarity matrix has the same shape no matter what width produced it.

Now the part that is easy to get wrong, and that circulates in secondhand summaries. The paper’s hyperparameter table lists a CLIP loss weight of 0.25 and a knowledge-distillation weight of 0.75 — that is λ = 0.75 — and that table is the recipe for MobileCLIP-B, the ViT-B/16-based model. The small variants, the ones that matter for a phone, are different: S0, S1 and S2 use λ = 1.0. Same hyperparameters otherwise, but the contrastive term is multiplied by (1 − 1.0) = 0, so it contributes nothing. MobileCLIP-S0 is trained by pure distillation.

Why would the small models want the more extreme setting? Because λ trades classification against retrieval, and the paper measures the whole curve:

Read the two rows against each other by hand. Classification climbs monotonically all the way to pure distillation; retrieval peaks in the middle and falls off:

So λ = 1.0 buys one point of classification for two points of retrieval, and λ ≈ 0.75 splits the difference. MobileCLIP-B, the flagship trained for the 38-benchmark average, takes the balanced setting. The small variants take the classification-favouring end. Neither is “the” recipe, and quoting 0.25/0.75 as if it were MobileCLIP-S0’s recipe is precisely the error this section exists to prevent.

How much does the training method buy? A controlled row

The paper runs the same architectures on DataComp-12M and on the reinforced DataCompDR-12M, for the same number of iterations, and the difference is entirely the training data’s extra content:

Ten to fourteen points of zero-shot ImageNet accuracy, on identical architectures, from changing nothing but what the dataset contains. Put that next to the architecture table: going from MCi0 to MCi2 was worth 2.3 points and cost 2.1 ms per call. The training method was worth 10–14 points and costs nothing at inference.

The headline results, and what they mean for our photo app

MobileCLIP-S0 is MCi0 plus MCt: 11.4 M + 42.4 M parameters, 1.5 + 1.6 ms on an iPhone 12 Pro Max, 67.8% zero-shot ImageNet-val, and 58.1 average over the 38-benchmark DataComp suite. The paper’s framing is that S0 is roughly 5× faster and 3× smaller than OpenAI’s ViT-B/16 CLIP at the same average accuracy, and that MobileCLIP-S2 is 2.3× faster than the previous best ViT-B/16-based CLIP while being more accurate.

Also reported: the training approach delivers 10× to 1000× improved learning efficiency compared with non-reinforced CLIP training — 10× on iterations and 100× on data for ImageNet-val, and up to 1000× on Flickr30k retrieval.

Plug S0 into Chapter 1’s sweep: 40,000 photos at 1.5 ms of model time is 60 seconds of accelerator work. The decode is still the bill. The model has stopped being the problem, which is precisely the point of the whole exercise.

Quantization: the mechanics, derived

Now the third knob. Quantization replaces a 32-bit float with a small integer plus a shared scale. For symmetric 8-bit quantization of a group of weights w:

Here s is the scale — the real-world value of one integer step — and q is an integer in [−127, 127]. Store q as one byte and s once per group. The reconstruction ŵ is not equal to w; the difference is quantization error, and the entire art is controlling it.

The crucial and non-obvious fact: s is set by the largest value in the group, but the error it inflicts is suffered by every value in the group. One outlier ruins the neighbourhood. Let us prove it with arithmetic you can check by hand.

Worked example: one outlier costs three bits

Take six weights from a row, five of them ordinary and one large:

Case A — per-tensor scale, outlier included. max|w| = 2.40, so

Mean absolute error over the five small weights:

Case B — the outlier lives in a different group. Now the five small weights get their own scale: max = 0.31, so

The comparison.

And the reason is mechanical — it is exactly the ratio of the scales:

One large weight in the group costs every other weight in that group roughly three bits of effective precision. Your int8 quantization delivers, in practice, about five bits of usable resolution on the weights that matter. That is why per-channel quantization (a separate scale per output channel) and group-wise quantization (a separate scale per 64 or 128 weights) are not micro-optimizations — they are the difference between a model that survives quantization and one that does not.

The overhead of finer scales, priced

Every extra scale is a stored number. Group size g with an fp16 scale and an fp16 zero-point costs 4 bytes per group, spread over g weights:

Per-channel scales cost you 0.8% more storage and buy you the 9× error reduction we just computed. It is the easiest trade in this entire lesson and it is still, somehow, skipped.

Weights versus activations: two very different problems

Quantizing weights is comparatively easy: they are fixed, you can look at them all, you can choose scales offline. Quantizing activations is hard: their range depends on the input, so the scale must either be recomputed per call (dynamic quantization, costing a pass over the tensor to find the max) or fixed in advance from a calibration set (static quantization, which fails whenever a real input exceeds what the calibration set contained).

A concrete failure mode: you calibrate on 500 daytime photos, the activation range comes out as [−6, 6], you set the scale, you ship. A user photographs a bright specular highlight, an activation hits 14, and it clips to 6. Not a small error — a hard truncation, in one channel, early in the network, that propagates through every subsequent layer. The symptom is that the model works beautifully on your test set and produces nonsense on 0.3% of real photos, which is exactly the hardest kind of bug to find.

Worked example: size math for the whole shipped system

Now assemble the app. Bytes at 10⁶ per MB.

Check one cell by hand: 42.4 × 10⁶ parameters × 1 byte = 42.4 × 10⁶ bytes = 42.4 MB. And at fp32, × 4 = 169.6 MB.

An extra move that matters more than it should: 25.3 M of MCt’s 42.4 M is the token embedding table, and lookup tables tolerate aggressive quantization far better than compute weights do, because their errors do not compound through layers. Quantize the table to int4 and the rest to int8:

Total shipped model size drops from 53.8 MB to 41.2 MB. For an app that also has to contain, you know, an app, that is a real decision.

Chapter 3: Dimension × Precision

The model is small. Now shrink the index, which is the thing that must stay resident forever and therefore the thing most likely to get your process killed.

There are two independent axes, and the good news is that they multiply.

where d is the number of dimensions kept and b is bits per dimension. Halve d, quarter b, and you have divided by eight. The question is what it costs in retrieval quality, and the honest answer depends entirely on whether the embedding was trained to be truncatable.

Why you cannot just chop a normal embedding

Take a 768-dimensional embedding from an ordinary encoder and keep the first 128 numbers. What did you lose?

For a typical trained encoder, the information is spread roughly evenly across coordinates — there is no reason for coordinate 3 to matter more than coordinate 500, because nothing in the loss ever asked for that. So a unit-norm vector distributes its squared length across all 768 slots, and keeping the first 128 keeps about

The truncated vector is essentially a random 128-dimensional projection of the original. Random projections do preserve inner products — that is the Johnson–Lindenstrauss result — but only up to a noise floor that scales as one over the square root of the kept dimension:

So any two photos whose true cosine similarity to your query differs by less than about 0.09 will swap places essentially at random. In a photo library, the top-20 results for “dog on a beach” are all within 0.09 of each other — that is what it means for them all to be good matches. You have destroyed the ranking you cared about and kept the ranking you did not.

Matryoshka: train the vector to be truncatable

Matryoshka Representation Learning (Kusupati et al., 2022) fixes this by changing the training objective, not the model. The idea is one sentence long: compute the loss at several nested prefix lengths at once.

Pick a nesting set, say M = {8, 16, 32, 64, 128, 256, 512, 1024, 2048}. For each m in M, take the first m coordinates of the embedding, push them through a head, and compute the task loss. Sum:

Now think about what gradient coordinate 3 receives. It appears in every term of the sum — the 8-dimensional one, the 16-dimensional one, all of them. Coordinate 1000 appears only in the terms with m ≥ 1024. The early coordinates are under nine times the pressure, so the optimizer puts the most broadly useful information there. The result is a vector ordered by importance, coarse to fine — nested dolls.

The paper reports: up to 14× smaller embedding size for ImageNet-1K classification at the same accuracy, up to 14× real-world speedups for large-scale retrieval, and up to 2% improvement on long-tail few-shot classification — all while being as robust as the original representation, and with no additional cost at inference or deployment. That last clause is the one that matters for us: MRL is free at the edge. You pay for it once, in the teacher’s training run.

Worked example: truncate, and then renormalize (do not skip this)

Take an 8-dimensional embedding built from raw scores u = [6, 4, 3, 2, 1.5, 1.2, 1, 0.8]. First normalize it:

Now truncate to the first four coordinates and measure how much length survived:

So 92.4% of the squared norm lives in the first half — that is what MRL training buys, versus the 50% you would expect from an unordered vector. Renormalize:

Why the division is not cosmetic. Suppose photo A retains 92.4% of its energy in the first four coordinates and photo B, a fuzzier image, retains only 80%. If you skip renormalization and rank by raw dot product, A gets a systematic multiplicative advantage of

a 7.5% ranking bonus that has nothing to do with whether A matches the query. It is a bias toward “photos whose meaning is concentrated in the early coordinates,” which is not a category anybody asked to search for. Skipping one division introduces a systematic retrieval bug that no unit test will catch, because every individual similarity looks plausible.

Composing truncation with quantization

Now stack the second axis. After truncating to 128 dimensions and renormalizing, quantize the vector to int8 with a per-vector scale:

The full index, for 40,000 photos:

against the fp32 768-dimensional baseline:

How much does int8 hurt an embedding? Much less than you fear

Here is a genuinely surprising result and it is worth deriving, because it explains why quantizing vectors is safe while quantizing weights is dangerous.

A unit-norm 128-dimensional vector has coordinates averaging 1/√128 = 0.0884 in magnitude; the largest might be around 0.25. So the per-vector scale is

Rounding error per coordinate is roughly uniform on [−s/2, +s/2], with variance s²/12. Over 128 coordinates the error vector has expected squared length

The cosine between the true vector and its reconstruction, for an error orthogonal in expectation, is

Two-hundred-thousandths of a percent. Int8 quantization of a normalized embedding is, for retrieval purposes, free.

Going further: binary embeddings

If int8 is nearly free, what about one bit per dimension? Keep only the sign:

And the comparison becomes a Hamming distance — XOR two 128-bit words and count the set bits, which every modern CPU does in a couple of instructions. There is a clean relationship between Hamming distance and angle for random-ish vectors: the probability that two coordinates disagree in sign is approximately θ/π, where θ is the angle between the vectors. So

Worked: two 128-bit codes differ in 20 positions.

The cost is resolution: with 128 bits there are only 129 possible distance values, so huge numbers of photos tie. That is not a defect if you use binary codes for what they are good at — a fast, coarse filter.

The pattern that makes all of this work: coarse pass, then rescore

Do not choose one precision. Use two.

Cost arithmetic for stage 1: 40,000 popcounts of a 64-bit word. A phone core does on the order of 10⁹ of those per second, so

Stage 2: 200 × 768 = 153,600 MACs, plus 307 kB of sequential reads. Both are far under a millisecond. Total: well under 1 ms for a search over 40,000 photos, using 320 kB of resident memory for the coarse codes and reading the full vectors from disk only for 200 of them.

Concept → realization: the index record, byte by byte

Here is what actually sits on disk, per photo, in the design we have arrived at. Total 148 bytes.

c
struct IndexRecord {          // 148 bytes, packed, one per photo
    uint64_t asset_id;        // 8  B  - photo library identifier
    uint64_t coarse;          // 8  B  - 64-bit sign code, stage 1
    int8_t   vec[128];        // 128 B - matryoshka prefix, renormalized, int8
    uint16_t scale_f16;       // 2  B  - per-vector scale s = max|z| / 127
    uint16_t norm_f16;        // 2  B  - original ||z[0:128]|| before renormalizing
};

// 40,000 photos -> 5,920,000 bytes = 5.92 MB resident.
// The coarse codes alone, gathered into one contiguous array for
// stage 1, are 40,000 * 8 = 320 kB - and that array is the ONLY
// thing that has to be hot in cache during a scan.

Note the layout decision hiding in that comment. If you store the records as an array of structs, stage 1 touches 8 useful bytes out of every 148, so a 320 kB working set becomes 5.92 MB of memory traffic — eighteen times more than necessary, and enough to blow out the cache. Store the coarse codes in their own contiguous array (a struct of arrays) and stage 1 streams 320 kB, which fits comfortably in a phone’s last-level cache. Same data, same algorithm, an order of magnitude in real latency.

Chapter 4: The Index on the Phone

You have 40,000 vectors of 128 int8 numbers. A query arrives. What data structure do you use?

The reflex answer, imported from server-side vector databases, is an approximate nearest neighbour index — HNSW, usually. This chapter argues that on a phone the reflex is usually wrong, and does the arithmetic to say exactly when it stops being wrong. The conclusion is uncomfortable for people who like building indexes: up to a few hundred thousand vectors, a plain loop wins.

The plain loop, priced honestly

Flat search, also called brute force or exhaustive search, computes the similarity to every stored vector and keeps the best k. For N vectors of d dimensions:

For N = 100,000 and d = 128 at int8:

Compute time. ARM cores have an instruction (SDOT) that performs sixteen 8-bit multiply-accumulates in one go on a 128-bit register. At 2 GHz with two such pipes the theoretical peak is 2 × 10⁹ × 16 × 2 = 64 × 10⁹ int8 MACs per second. Real code with loads and reductions gets maybe an eighth of that; call it 8 × 10⁹:

Memory time. The scan is perfectly sequential, so it gets close to peak bandwidth. At 15 GB/s:

Arithmetic intensity is 12.8 M / 13.2 MB = 0.97 MACs per byte, versus a machine balance here of 8 × 10⁹ / 15 × 10⁹ = 0.53. So it is mildly compute-bound: about 1.6 ms on one core, and under half a millisecond across four.

Now the comparison that should end most arguments:

You are buying 1.3 milliseconds — inside a 60-millisecond query path where thumbnails cost 40 — and paying with double the resident memory, a rebuild problem, and a silent recall loss.

Deriving HNSW’s memory, because nobody publishes it

Hierarchical Navigable Small World graphs (Malkov & Yashunin, 2016) build a multi-layer proximity graph. Each element is assigned a maximum layer drawn from an exponentially decaying distribution, upper layers act as an express highway, and search descends greedily. It is an excellent structure. It is also, on a phone, expensive in exactly the currency you have least of.

The level of a node is drawn as level = ⌊−ln(U) · m_L⌋ for a uniform U, with the standard choice m_L = 1/ln(M). Then

A pleasing result: with the standard parameter choice, exactly one node in M is promoted to each next layer. With M = 16, the expected number of upper-layer memberships per node is a geometric sum:

Layer 0 stores up to M_max0 = 2M = 32 links per node; each upper-layer membership stores up to M = 16. Expected links per node:

At 4 bytes per neighbour identifier:

Which is — and this is a genuinely useful coincidence to remember — exactly the size of the vector itself in our design. HNSW with M = 16 over 128-dimensional int8 vectors doubles your index memory.

Raise M to 32 for better recall and it gets worse: M_max0 = 64, m_L = 1/ln 32, expected upper memberships = 1/31 = 0.0323, so 64 + 0.0323 × 32 = 65.03 links = 260 bytes per node — twice the vector, for 26 MB of graph.

Build cost: why it is 40 seconds and not 3

Inserting a node runs a greedy search down the layers with a candidate list of size efConstruction, then applies the neighbour-selection heuristic. A typical insert at efConstruction = 200 evaluates on the order of 2,000 distances. For 100,000 insertions:

Three seconds of math. But every one of those distance evaluations requires fetching a vector at a random address in a 13 MB array — far larger than the last-level cache. Each miss costs about 100 ns to DRAM, and a graph traversal typically incurs a couple per candidate:

Twelve times the arithmetic time, spent waiting for memory. On a phone this is worse still, because 40 seconds of sustained random-access work heats the SoC, the governor throttles, and the OS may suspend your background task partway through — leaving you with a half-built graph and no clean way to resume.

Where flat search actually breaks

Push N up and watch which wall you hit first. All at 128-d int8, 132 bytes per vector.

Look carefully at the million-vector row. Sixteen milliseconds is annoying but survivable — four cores brings it to four. What is not survivable is 132 MB resident. Background execution contexts on mobile platforms get a small fraction of a foreground app’s memory allowance, often only tens of megabytes, and exceeding it does not make you slow, it makes you terminated.

The index everybody forgets: partition by something the user already understands

Photo libraries have structure that has nothing to do with vectors. Roughly 80% of searches are about the last year or two. Photos belong to albums, to places, to people.

So: keep one flat array per year. Scan the most recent three years first — say 12,000 of the 40,000 vectors — and only fall through to the rest if the user scrolls past the first page or the best similarity is below a threshold. Expected work:

It is not clever and it will not appear in a paper. It also costs nothing, never loses recall, needs no rebuild, and handles deletion by deleting. When a partition key correlates with query intent, partitioning beats approximation.

Memory-mapping: the index that is not in memory at all

There is a third option between resident and absent. Memory-map the index file and let the operating system page it in. A sequential scan over a 5.28 MB mapped file reads at storage speed — modern phone flash does over 1 GB/s sequentially:

and effectively zero on subsequent queries, because the page cache holds it — memory you did not have to claim, and that the OS can reclaim under pressure without killing you. Your resident set stays tiny and your warm-query latency stays low.

Now do the same for HNSW. Its access pattern is random, so each hop is a potential page fault: a 4 kB page read at roughly 100 microseconds of storage latency, times a few hundred hops.

The “fast” index is now ten times slower than the “slow” one, purely because of locality. Sequential access is not a minor implementation detail on constrained hardware; it is the whole game.

Concept → realization: the forty-line scanner

Here is the entire “vector database” for the photo app. Note that it never allocates, never rebuilds, and returns exact results.

c
// coarse: N contiguous uint64 sign-codes.  q64: query's sign-code.
// Stage 1 - 320 kB streamed, ~40 microseconds for N = 40,000.
void stage1(const uint64_t* coarse, int N, uint64_t q64,
            int* out_idx, int K) {
    // keep the K smallest popcounts with a tiny fixed-size max-heap
    for (int i = 0; i < N; ++i) {
        int h = __builtin_popcountll(coarse[i] ^ q64);   // 1 instruction
        heap_offer(out_idx, K, i, h);
    }
}

// Stage 2 - exact int8 dot product over the K survivors only.
// vdot8 is one SDOT-based loop: 16 MACs per instruction.
void stage2(const int8_t* vecs, const int8_t* q, int d,
            const int* cand, int K, float* score) {
    for (int j = 0; j < K; ++j)
        score[j] = vdot8(vecs + (size_t)cand[j] * d, q, d);
}

The design decisions embedded in twenty lines: coarse codes in their own array so stage 1 is a pure sequential stream; a fixed-size heap so there is no allocation in the hot path; size_t on the index multiply so a million-vector library does not overflow a 32-bit product; and stage 2 touching only K vectors so the random-access part is bounded by a number you chose rather than by N.

Chapter 5: Always On

Everything so far assumed the model runs when asked. Now consider the harder regime: a model that runs forever. A wake word listener. A fall detector. A gesture watcher. These are embedding models too — and their design is dominated by a currency the photo app barely noticed.

Power is not latency

Latency is joules per call. Power is joules per second. They are related by the call rate:

A model that takes 2.4 mJ per call — the one from Chapter 1, which we happily ran 40,000 times — becomes, at 50 calls per second:

Seventeen percent of the battery for a background listener is a product that gets deleted. The same model, the same joules per call, and a completely different verdict — because the rate changed.

The shape of a keyword spotter

Keyword spotting (KWS) is the canonical always-on model: detect a small set of words in a continuous audio stream, on a device that may be a microcontroller. The classic reference is Zhang et al., Hello Edge (2017), which evaluated the architecture family under microcontroller memory and compute constraints and found depthwise-separable convolutions to be the sweet spot — DS-CNN reaching 95.4% accuracy, about 10 points above a plain fully-connected network with a similar parameter count.

The front end and the timing:

Check the 49: a 1-second context at a 20 ms hop with a 40 ms window gives (1000 − 40)/20 + 1 = 49 frames. The window slides by one frame every 20 ms, so a naive implementation runs the whole network 50 times a second.

Worked example: the streaming trick, worth 49×

Here is the single most important optimization in always-on inference, and it is a pure engineering win with no accuracy cost.

Naive. Every 20 ms, assemble the last 49 frames and run the whole network. Say the network is 20 M MACs per call:

At a DSP efficiency of 100 GOPS per watt — a reasonable figure for a low-power audio DSP doing int8 convolutions:

Streaming. Notice that 48 of those 49 frames were already processed on the previous call, and a convolution is translation-equivariant: the activation it computed for frame 17 last time is bit-for-bit the activation it needs for frame 17 this time. So cache the intermediate activations in a ring buffer and compute only the new frame’s column. Incremental work:

Twenty milliwatts becomes four-tenths of a milliwatt. Forty-nine times, exactly the ratio of receptive field to hop, and the model is numerically identical.

What the cache costs. For each convolution layer with kernel width k and C channels, you must retain the last k−1 columns of its input. For four layers of k = 3 and C = 64, at int8:

Half a kilobyte of state buys a 49× power reduction. This is why streaming or causal convolutions are mandatory, not optional, in always-on designs — and why an architecture with a global operation (a pooling over the whole window, a full self-attention) is disqualified: nothing can be cached across a shift if every output depends on every input.

The cascade: why the big model is allowed to exist at all

Even 20 mW is too much for some devices, and no useful embedding model runs at 100 µW. The universal answer is a cascade: a chain of increasingly expensive, increasingly accurate stages, where each stage only wakes the next.

Average power:

Compare with running stage 3 continuously at 900 mW:

And look at how evenly the 2.4 mW is split: 0.5 from the always-on stage, 1.0 from the sometimes stage, 0.9 from the rare stage. A balanced cascade has roughly equal contributions from each tier — if one term dominates, that is where your next engineering hour goes. If the VAD term dominated, you would move it into analog hardware; if the AP term dominated, you would tighten stage 2’s specificity.

Worked example: the false-alarm arithmetic that shocks everyone

The always-on regime imposes a specificity requirement so extreme that most engineers get it wrong on the first try. Count the opportunities.

Suppose your detector has a per-window false-accept rate of 0.5% — which sounds excellent, and would be a fine number for an offline classifier.

That is a wake every four seconds. Now invert the question: to tolerate one false wake per day, what per-window rate do you need?

Seven-figure specificity. No single-window classifier gives you that at any useful sensitivity. The solution is not a better model but a better decision rule: require the detector to fire on several consecutive windows.

If false alarms in adjacent windows were independent with rate p, requiring k in a row gives approximately p^k. With p = 0.005 and k = 3:

From 21,600 to one every two days, and the cost is

Sixty milliseconds is imperceptible on a wake word. That is the trade: latency you cannot feel, bought with four orders of magnitude of specificity.

Why an embedding rather than a classifier

The obvious KWS design is a classifier with one output per keyword. It works, and it has a fatal product limitation: the keyword set is frozen at training time, so a user cannot invent their own wake word without a round trip to your training infrastructure.

The embedding design fixes this. Train a model that maps a one-second audio window to a vector such that utterances of the same word land near each other, regardless of which word it is. Then a keyword is just a stored vector.

Mazumder et al., Few-Shot Keyword Spotting in Any Language (2021), built exactly this: an automated multilingual keyword bank mined from open speech corpora in nine languages, used to train an embedding model. Their reported results:

Five examples. In a language the embedding model never saw. That is the payoff of embeddings over classification heads: the taxonomy becomes data instead of architecture, exactly as in the photo app where the query became data instead of a tag list.

Concept → realization: adding a wake word on the device

The whole personalization flow, and how little it costs.

python
# user records their chosen wake word five times
clips = record_five()                        # 5 x float32[16000]
E     = [embed(c) for c in clips]           # 5 x float32[1024]

# the "training" is one line: the prototype is the mean direction
proto = normalize(mean(E, axis=0))            # float32[1024]
store(proto)                                 # 1024 * 4 = 4,096 bytes

# at inference, once every 20 ms, on the streaming embedding
score = dot(proto, z_t)                      # 1024 MACs. That is the whole detector.
if score > tau and run_length >= 3:
    wake()

Four kilobytes per custom wake word, 1,024 MACs per evaluation on top of the embedding, no retraining, no server, no new model download. A better version fits a small logistic regression on the five positives plus a bank of stored negatives — still a handful of kilobytes — but the prototype version already works and is the right thing to ship first.

And note the calibration problem hiding in tau. Five recordings tell you where the positives are but nothing about where the negatives are, so τ cannot be chosen from them. The fix is to ship a fixed bank of, say, 5,000 stored negative embeddings (ordinary speech, television, kitchen noise), score them against the new prototype on the device, and pick τ at the percentile that meets your false-alarm budget. 5,000 × 1,024 × 1 byte at int8 = 5.1 MB shipped once, and it converts an uncalibratable threshold into an arithmetic one.

Chapter 6: Distance to Normal

A pump in a factory. It has run for four years. You have a vibration sensor on its housing and a microcontroller with 256 kB of SRAM, and management would like to know before the bearing fails.

Try to phrase this as classification and you hit a wall immediately: you have no failures. The pump has never failed. You cannot label what has not happened, you cannot collect a balanced dataset, and if you wait until you have a hundred bearing failures to train on, you have already had a hundred bearing failures.

What you do have is four years of the pump being fine. That is an enormous amount of data about one class. So change the question from “which class is this?” to “how far is this from everything I have ever seen?” — and distance is exactly what an embedding space is for.

The pipeline

Everything interesting is in the last arrow. There are three standard ways to represent “normal” and they differ enormously in memory, which is the currency that matters on a microcontroller.

The memory-bank approach is the one that scaled best in the image domain: PatchCore (Roth et al., 2021) stores a coreset-subsampled bank of nominal patch features and scores by nearest-neighbour distance, reaching image-level anomaly-detection AUROC up to 99.6% on MVTec AD — more than halving the error of the next best method at the time — with competitive inference times and strong results in the few-sample regime. The technique transfers directly: your “patches” are one-second windows.

Worked example: Mahalanobis, all the way through, by hand

Let us do this with d = 2 so every number is checkable.

Step 1 — the normal set. Five embeddings recorded while the pump was healthy:

Step 2 — the mean.

Step 3 — the deviations.

Step 4 — the covariance. Sum of squared deviations, divided by n − 1 = 4:

So the covariance matrix and its inverse are both diagonal and trivially computed:

Step 5 — score a new window. The pump now produces the embedding t = (3.5, 6).

Is 12.5 an anomaly? That question has no answer until you supply a budget, which is the point of the next step.

The threshold comes from the alarm budget, not from statistics

If the normal embeddings really were Gaussian, then D² for a normal window follows a chi-square distribution with d degrees of freedom. For d = 2 this has an unusually clean tail:

Threshold A — the textbook 1%.

Our test point scored 12.5 > 9.21. Alarm. But now count what that threshold costs. At one window per second:

Nobody will look at the 864th. The detector is worthless.

Threshold B — one false alarm per day. Invert the requirement:

Our test point scored 12.5 < 22.73. No alarm. The same measurement, the same model, opposite verdicts — and the second one is the correct engineering answer, because a detector that cries wolf 864 times a day is not a detector.

What the budget costs you in sensitivity

Raising the threshold from 9.21 to 22.73 did not come free. Measure the price. A developing fault shifts the embedding away from μ; how far must it shift to be caught?

A fault must be 57% further from normal to trigger the day-budget threshold. Faults between those two distances — genuinely abnormal, but subtly — are invisible by construction. That is the sensitivity you sold to buy quiet.

Buying the sensitivity back with time

The same trick as the wake word: require persistence. A real bearing fault does not appear for one second and vanish; a sensor glitch does. So require k consecutive exceedances of the lower threshold.

With per-window false rate α = 0.01 and k = 3, treating windows as independent:

So you get a quieter detector than threshold B, at threshold A’s sensitivity of D = 3.035, and the entire cost is three seconds of detection latency on a fault that has been developing for weeks.

Drift: the normal manifold moves, and that is a trap

Machines change. A bearing wears in over its first month. The factory is 8°C colder in January. The lubricant is replaced. If “normal” is frozen at commissioning, your detector will be screaming by March for reasons that have nothing to do with faults.

The standard fix is to update the model continuously with an exponentially weighted moving average:

which is beautiful on a microcontroller — d multiply-adds per window and no history to store. But choose α carefully, because it defines a time constant:

Now the trap, stated precisely. Anything that changes more slowly than τ is absorbed into “normal” instead of being reported. A bearing that degrades over three weeks moves the mean by an amount per window that is far below what the EWMA will resist, so the detector tracks the fault all the way to failure and never alarms. Meanwhile a fault that appears in ten seconds is caught easily.

Quantify it. If a fault adds a constant drift δ per window to the true embedding, the EWMA mean lags behind by a steady-state offset of about δ/α. The detector effectively sees only that lag:

So α is not a smoothing convenience. It is a declaration of which fault timescales you are choosing to be blind to. Two mitigations are standard: run two detectors with very different α and alarm on their disagreement, or freeze adaptation whenever the current score is elevated so a developing fault cannot teach the model to accept itself.

Concept → realization: the whole detector in 256 kB

c
// Fixed footprint. No malloc. Runs on a Cortex-M4 at 1 Hz.
//   encoder weights (int8) ......... 50,000 B
//   FFT scratch + window buffer .... 19,200 B
//   mean mu[32] (float) ............    128 B
//   inverse covariance L[32][32] ...  4,096 B
//   memory bank 200 x int8[32] .....  6,400 B
//   ------------------------------------------
//   total .......................... 79,824 B  (31% of 256 kB SRAM)

float score_window(const float* z) {
    float dev[32], acc = 0.f;
    for (int i = 0; i < 32; ++i) dev[i] = z[i] - mu[i];
    // D^2 = dev' * Sinv * dev, with Sinv stored as its Cholesky factor L
    for (int i = 0; i < 32; ++i) {
        float u = 0.f;
        for (int j = 0; j <= i; ++j) u += L[i][j] * dev[j];
        acc += u * u;                     // 32*33/2 = 528 MACs total
    }
    return acc;                           // D^2, compare against t
}

// Adaptation, gated so a developing fault cannot teach the model
// to accept itself - the single most important line in the file.
if (acc < t_freeze)
    for (int i = 0; i < 32; ++i) mu[i] += alpha * (z[i] - mu[i]);

Two details worth naming. Storing the Cholesky factor L of the inverse covariance instead of the full matrix halves the memory and turns the quadratic form into a triangular product — 528 multiply-adds instead of 1,024, and it guarantees the score is non-negative even after numerical drift. And the t_freeze gate on the last line is the difference between a detector that adapts to seasons and a detector that adapts to its own failure.

Finally, note what leaves the machine: one float, once a second. When an alarm fires you might upload the 32-dimensional embedding — 32 bytes — for a human to look at. Not the vibration signal, not the audio. This is the same architecture as the photo app, and it leads directly to the next chapter’s question, which is whether those 32 bytes are as harmless as they look.

Chapter 7: What Leaves the Device

Six chapters of engineering have produced a system that computes embeddings locally. Now somebody in a planning meeting says the sentence that undoes it: “we should sync the embeddings so search works on the user’s laptop too.”

It is a completely reasonable product request, and the vectors are small — that is why it gets waved through:

This chapter is about why that number is a trap, and what the honest options are.

Three postures, stated precisely

Posture B is where almost every product lands, and it is where the interesting problem is, because the intuition that an embedding is “just numbers” is wrong in a way that has been measured.

Embeddings are lossy, not anonymous

The intuition goes: the encoder throws away enormous amounts of information — 3 MB of JPEG becomes 132 bytes — so surely you cannot get the content back.

That reasoning confuses compression ratio with irreversibility. The encoder discards information that is irrelevant to meaning; it preserves meaning as precisely as it can, because that is the training objective. And meaning is what the private content is.

Morris et al., Text Embeddings Reveal (Almost) As Much As Text (2023), framed inversion as controlled generation: generate text whose re-embedding lands near a target vector, then iteratively correct and re-embed. Their reported results:

Ninety-two percent, exactly, on two different state-of-the-art embedding models. The mental model to adopt is: an embedding is a compressed encoding of the content, not a hash of it. Hashes are designed to be irreversible. Embeddings are designed to be maximally informative about meaning, which is the opposite design goal.

The image case is less studied but structurally identical: with a generative decoder trained against the encoder, an image embedding yields a reconstruction that preserves the scene, the setting, and often the people. For a photo library, “we only have the embeddings” means “we have a lossy but semantically faithful description of every photo you have ever taken.”

Do the usual mitigations help? Arithmetic, one at a time

Truncation and quantization. Surely 132 bytes leaks less than 3,072? Somewhat — but we computed in Chapter 3 that int8 costs 0.002% of the cosine, meaning the quantized vector is functionally the same vector. And truncation to a matryoshka prefix keeps the most semantically loaded coordinates by construction. You have removed the fine detail and kept the meaning, which is precisely backwards for privacy. Not a defense.

A device-held random rotation. Multiply every vector by a secret orthogonal matrix R. The server can still compute inner products, because

Which is exactly the problem: it preserves every distance, so it preserves every bit of structure that inversion exploits. It defeats an attacker who has your encoder and no key, and is defeated by anyone who can obtain a few hundred (plaintext, rotated) pairs and solve for R — a linear system, not a cryptographic one. Useful as a speed bump. Not a defense.

Additive noise. This one genuinely trades utility for privacy, so it deserves real arithmetic. Add independent Gaussian noise of per-coordinate standard deviation σ to a unit-norm vector. The expected squared length of the noise is

and the cosine between the vector and its noised version is approximately

Evaluate at d = 128:

Read the last row against a fact from Chapter 3: in a real photo library, the genuinely good matches for a query sit at cosine similarities around 0.80–0.90 to each other. At σ = 0.05 the vector is only 0.87 similar to itself. The noise is now larger than the signal you were ranking by. There is a narrow band where noise helps meaningfully and does not destroy retrieval, and you must locate it by measurement rather than by hoping.

Federated aggregation, and what it does and does not hide

The other reason to send something up is to improve the model without collecting data. Federated averaging (McMahan et al., 2016) is the base recipe: each device trains locally on its own data and sends the resulting parameter update; the server averages the updates weighted by how much data each device had.

Worked, on a single parameter, three devices:

Check it the other way: (100(0.20) + 300(−0.10) + 600(0.05)) / 1000 = (20 − 30 + 30)/1000 = 20/1000 = 0.020. Consistent.

Now look at the table again as an attacker. The server received Δ_B = −0.10 from device B. Federated averaging by itself does not hide anything — it hides data only in the sense that the raw examples were not transmitted, and gradients computed on a small local dataset are famously informative about that dataset. Two additions are needed to make the claim real:

On device, federated participation also has to obey Chapter 1’s budget: a local training round is a forward and backward pass, roughly three times the cost of inference per example, and it only runs when charging, idle, and on unmetered network — which means your effective cohort is systematically biased toward users who charge overnight on home Wi-Fi. That bias is a modelling problem, not just a logistics one.

Concept → realization: the data-flow table you should be able to fill in

For any on-device embedding system, write this table before writing the code. If a row is uncomfortable, the architecture is wrong, and it is much cheaper to learn that now.

The row people miss is the fourth one interacting with the second. Your model weights are public — you shipped them in an app anyone can download. So every attacker who obtains the embeddings also has the encoder, which is exactly the setting in which the 92% inversion result was measured. There is no security through the obscurity of your embedding space.

Who actually gets the file: a threat model in one table

“Is this secure?” is unanswerable. “Secure against whom, holding what?” is answerable, and it is the only version of the question that produces engineering decisions. Here are the five parties who realistically end up holding an embedding file, ranked by how often it happens rather than by how dramatic they sound.

Read the last row twice. Every number in this chapter is a lower bound on what a stored embedding reveals, because the file persists and the attack improves. A design that is exactly at the acceptable threshold today is over it in three years without anyone touching the code.

Worked example: what a leaked index file actually costs

Concrete beats abstract. Suppose the 40,000-photo index — 132 bytes a record, 5.28 MB total — ends up in a breach dump. Price the damage rather than gesturing at it.

The attacker downloads your app and extracts the image encoder; that is an afternoon. They now hold 40,000 vectors and the function that produced them. Two attacks are available, and they differ enormously in cost.

Attack one: matching. Take any photo they already have — from a social account, a previous breach, a public profile — embed it, and check the cosine against all 40,000. This is one forward pass plus a 5.28 MB scan, so milliseconds, and it answers “was this picture in that person’s library?” with high confidence. Nothing is reconstructed; nothing needs to be. Membership alone is often the sensitive fact — whether a specific person, place, document or medical image was present.

Attack two: reconstruction. Train or fine-tune a decoder that maps embeddings back toward inputs. This is the expensive attack, and it is the one the inversion literature measures: 92% of 32-token texts recovered exactly from their embeddings. For images the analogous result is a semantically faithful reconstruction rather than a pixel-exact one — the scene, the setting, the objects, the number of people. Whether that is worse than exact depends entirely on what the photo was of.

Saying it out loud: the consent sentence

Every design in this chapter eventually becomes a sentence in a privacy screen, and writing that sentence early is a surprisingly effective engineering tool. Write it honestly, then read it back.

The dishonest version is the one that gets shipped by default: “We sync a compact numerical representation of your photos, not the photos themselves.” Every word is true and the sentence is misleading, because “numerical representation” implies irreversibility that the arithmetic does not support.

The honest version: “We upload a compact vector for each photo. It is not the photo, but anyone holding it and our app can determine whether a given picture is in your library, and can reconstruct a recognisable description of what each photo shows.”

Both sentences describe the same system. If the second one would not survive the design review, the design should not survive it either — and finding that out during the review is roughly a thousand times cheaper than finding it out afterwards.

Chapter 8: Where to Cut

Eight chapters of parts. Now assemble them into a method, because the actual skill being taught here is not “know about MobileCLIP” — it is being able to sit down with a budget and produce a design that meets it, and to know which knob to turn when it does not.

The four dials and what each one actually costs

Read the first column. Three dials shrink memory; one grows it. On a device where memory is the wall that terminates your process, that asymmetry should determine the order in which you reach for them — and it is the reverse of the order most engineers reach in.

One cost model, written once

Before turning any dial, write the whole system as three formulas. Then the dials stop being a list of tricks and become variables you can differentiate by eye. Every term below was derived somewhere in Chapters 1 through 4; this is just the collection.

Memory. Each stored record is d components at b bits, plus a fixed per-record overhead c covering the photo identifier, the dequantization scale, and the stored norm:

If you build a graph index, add g bytes per node on top. Chapter 4 derived g ≈ 8M + 4 for HNSW with degree parameter M, which is 132 bytes at the customary M = 16 — almost exactly the same as the 128-dimensional int8 vector it is meant to help you find.

Search time. A flat scan reads every byte exactly once and does one cheap integer operation per byte, so it is bandwidth-bound and its time is simply bytes divided by streaming bandwidth β:

Chapter 4 pinned the constant with one measurement: 100,000 vectors of 128 int8 components is 12.8 MB and took 1.6 ms, so

Eight gigabytes per second of useful single-core streaming throughput. That one number generates every scan estimate in this lesson, and it is the first thing you should re-measure on your own hardware, because it is the only empirical constant in the model.

Query time, end to end, is the search plus everything around it — and the things around it are usually larger:

Energy for the initial sweep, from Chapter 1, where e_pre is the per-photo preprocessing cost and η is the accelerator’s efficiency in operations per joule:

The factor of 2 is the MAC-to-op conversion from Chapter 1 — one multiply-accumulate is two operations, which is why a vendor’s TOPS figure must be halved before it enters this formula.

Now differentiate by eye, which is the entire reason for writing them down. d and b appear as a product in both the memory formula and the scan formula. Halving d and moving from fp32 to int8 does not add; it multiplies:

N appears linearly everywhere and is the one variable you do not control — the user decides how many photos they have. And the index term is the only one with the opposite sign: it subtracts from T_search while adding to M. Two dials move both budgets in the good direction at once; one trades them against each other. That is the whole priority order, visible in the algebra.

Worked example: design the photo app end to end

Requirements, stated as numbers so we can check them:

Choose the architecture. MobileCLIP-S0: 11.4 M image tower at 1.5 ms, 42.4 M text tower at 1.6 ms, 67.8% zero-shot ImageNet-val. Quantize both to int8 with per-channel scales, and the text token table to int4:

Choose dimension and precision. Take the 512-dimensional output, truncate the matryoshka prefix to 128, renormalize, quantize to int8, and also store a 64-bit sign code for the coarse pass:

Choose the index. N = 40,000. From Chapter 4’s table, a flat scan at this size is a fraction of a millisecond, and the coarse pass is 40 microseconds. HNSW would add ~5.3 MB of graph and save under a millisecond. No index. Two-stage flat.

Check the latency budget.

Check the energy budget. From Chapter 1, using existing thumbnails rather than decoding originals:

Check recall. This one cannot be computed. It must be measured — on device, with the actual quantized vectors, against an exact fp32 baseline, on real user-style queries. Chapter 3 gives the knob: if recall@10 comes in under 0.95, raise the coarse shortlist from 200 until it plateaus, and only if that fails raise the kept dimension from 128 to 256.

Three experiments worth running on it before reading on. First, drag the encoder to S1. The download bar goes red and nothing else moves, because S1 keeps the same 63.4 M-parameter Base text tower that S0 replaced with the 42.4 M MCt — the accuracy is affordable, the text encoder is not. Second, set the library to a million and the structure to HNSW: the memory bar overshoots while the latency bar barely improves, which is the graph paying 132 bytes a node to save time you were not short of. Third, take dimension to 512 at 32 bits and then fix it in the order the callout prescribed — precision first, then dimension — and watch two bars retreat together on each move.

Worked example two: the design that fails

The first worked example passed on every line, which makes it a poor teacher. Here is the same app under a harder brief, because the method is only visible when something breaks.

A power user with 500,000 photos, on a four-year-old phone. Two things change: the background memory allowance is tighter, call it 25 MB, and the memory system is slower — re-measure β and it comes back at 4 GB/s, half of what the new device gave us. Latency ceiling is still 100 ms, and the fixed pipeline cost around the search is still 0.2 + 1.6 + 40 + 15 = 56.8 ms, leaving 43.2 ms for the search itself.

Start naive: the encoder’s native 512-dimensional fp32 output, stored as is.

Both budgets fail, and they fail by different factors, which already tells you something: memory is 41× over and time is 5.9× over, so any fix that helps only time is irrelevant. Apply the order of operations.

Check each row by hand rather than trusting the table. Move 1 is 512 × 1 + 12 = 524 B, and 500,000 × 524 = 262 MB; the scan reads 500,000 × 512 = 256 MB at 4 GB/s = 64 ms. Move 2 is 128 × 1 + 12 = 140 B, so 70 MB and 500,000 × 128 ÷ 4 × 10⁹ = 16 ms. Latency now fits: 56.8 + 16 = 72.8 ms against 100. Memory does not: 70 MB against 25.

And here the chapter’s own advice runs out, which is the interesting part. Precision is spent — you are at int8 and the next stop is 1 bit. Dimension is spent — 128 is already the matryoshka prefix you validated. Neither remaining dial goes anywhere good, so the fifth move is the one that was never a dial at all: change what is resident.

The 128-bit sign codes stay in memory permanently — that is Chapter 3’s binary trick, 16 bytes a photo. The int8 vectors live in a file the operating system pages in on demand, so they cost zero resident bytes and the page cache is reclaimable rather than fatal. The coarse pass streams 500,000 × 16 = 8 MB at 4 GB/s = 2 ms, and stage two touches only the survivors.

Notice what the second example demonstrates that the first could not. The first four dials are finite. When they run out, the remaining moves are all about arrangement — what is resident versus mapped, what is contiguous versus scattered, what is searched by default versus on request. Those moves do not appear in any model card, and on constrained hardware they are frequently the ones that decide whether the product ships.

Concept → realization: the budget as twenty lines of build script

Everything above should live in your repository, not in a notebook someone lost. This runs in continuous integration and fails the build when a design change quietly breaks a budget:

python
# budget.py — run in CI. Numbers, not opinions.
BETA   = 8e9    # B/s streaming, MEASURED on the oldest supported phone
ETA    = 2e12   # ops/joule, vendor TOPS already halved
CHARGE = 60984  # J in a 4400 mAh @ 3.85 V cell

def budget(N, d, bits, img_mb, txt_mb, tok_mb, txt_ms, macs_g,
           coarse_b=8, graph_b=0, pre_mj=1.5, shortlist=200):
    per_vec = d * bits / 8 + 12                 # + id, scale, norm
    resident = N * (per_vec + coarse_b + graph_b)
    app_mb  = img_mb + (txt_mb - tok_mb) + tok_mb * 0.5   # int8, int4 tokens
    scan_ms = (N * coarse_b if coarse_b else N * d * bits / 8) / BETA * 1e3
    rescore = shortlist * per_vec / BETA * 1e3 if coarse_b else 0.0
    query   = 0.2 + txt_ms + scan_ms + rescore + 40 + 15  # + thumbs + render
    joules  = N * (pre_mj + 2 * macs_g * 1e9 / ETA * 1e3) / 1e3
    return {"app_mb": app_mb, "index_mb": resident / 1e6,
            "query_ms": query, "charge_pct": joules / CHARGE * 100}

CAPS = {"app_mb": 60, "index_mb": 30, "query_ms": 100, "charge_pct": 3.0}

def test_photo_app_fits():
    # MobileCLIP-S0, 40k photos, 128-d int8, two-stage
    b = budget(N=40_000, d=128, bits=8, img_mb=11.4, txt_mb=42.4,
               tok_mb=25.3, txt_ms=1.6, macs_g=2.4)
    for k, cap in CAPS.items():
        assert b[k] <= cap, f"{k} = {b[k]:.2f} exceeds {cap}"

Three decisions are worth naming. BETA is a constant you measured, not one you looked up, and it carries a comment saying which device it came from — because the moment someone benchmarks it on a new phone and updates it, every budget in the file silently loosens. The energy term keeps 2 * macs_g explicit rather than folding the factor of two away, so nobody re-derives it wrongly next year. And the whole thing is a test, so an innocent-looking bump from 128 to 192 dimensions fails continuous integration instead of failing a user’s phone.

Failure signatures: which cut went too far?

This is the diagnostic table. When quality is bad, the symptom tells you which dial to blame — and the symptoms are genuinely distinguishable, which is the useful part.

The distinction in the first row is the most valuable one on the page. Recall@50 good, recall@1 bad means the information is present and the ordering is coarse — a cheap fix. Recall@50 bad means the information is gone — an expensive fix. Measure both, always, and never report only one.

The measurement protocol

Everything in this lesson is arithmetic until you validate it on the device. Five measurements, in order, and none of them is optional.

Measurement 3 deserves one more sentence, because it is the one that separates a working product from a demo. The baseline is not the benchmark score in the paper. It is your own model, at fp32, at full dimension, doing an exhaustive scan, on the same device, over the same library. That number is your ceiling. Every cut you made in Chapters 2, 3 and 4 is measured as a loss against it, and if you never computed it you do not know what any of your engineering cost.

Chapter 9: Connections

Ten chapters, one repeated move: compute a vector on the device, compare it to something already on the device, and let the comparison be the product. Photo search, wake words, and a failing bearing are the same architecture with the budgets shifted by three orders of magnitude.

This chapter introduces nothing. It collects — the formulas in one place with every symbol named, the numbers with their provenance, the misconceptions the lesson was built to dislodge, and an honest list of what we did not cover. Read it once now and once again the week you actually have to build something.

The three questions, in the order they have to be asked

Strip away the specifics and every chapter was answering one of three questions, always in this order, because each one constrains the next.

Asking them out of order is the standard failure. Picking a model before you know the regime means you optimized latency for a path where memory was the wall. Picking an index before you know what may leave the device means you built a beautiful ANN structure for data that could have gone to a server anyway.

The formula sheet, with every symbol named

Nine chapters produced eleven expressions. Here they are together, so that the next time you need one you do not have to re-derive it — and so that when a number surprises you, you have somewhere to check it against.

Two of these deserve a second look because they are the ones people misuse. The arithmetic-intensity test (I versus B) decides which of the first two formulas applies, and applying the wrong one is how a team spends a month cutting MACs on a model that was waiting for memory the whole time. And the outlier formula is a base-two logarithm, which means the damage is mild for a 2× outlier and severe for a 100× one — a shape you cannot guess and must compute.

The numbers worth carrying out of here

Every one of those has a chapter reference attached on purpose. A number without a provenance is a rumour, and the failure in Chapter 2 — where a widely repeated loss coefficient turned out to belong to a different model in the same family — is what rumours cost.

The same shape at three scales

The three systems in this lesson look unrelated and are structurally identical. Lay them side by side and the template becomes obvious enough to apply to a fourth thing you meet next month.

Read the last row across. In all three, the thing that used to require retraining became a stored vector. That is the single most valuable structural consequence of using embeddings rather than classifiers, and it is why the same architecture survives a three-order-of-magnitude change in budget: the taxonomy moved out of the weights and into the data, so the weights stopped needing to change.

Misconceptions this lesson was built to dislodge

Each of these is a belief that is common, plausible, and wrong — and each cost a chapter to dismantle.

What this lesson deliberately did not cover

Honesty about the edges is part of the method. Four things sit just outside this lesson and you will meet all of them.

Pruning and sparsity. Chapter 2 named it as a fourth compression knob and then set it aside. Removing weights or whole channels composes with everything here, but it interacts with hardware in ways that need their own treatment — unstructured sparsity often buys nothing at all on a mobile accelerator that has no sparse kernel. The site’s TinyML series covers it properly.

Quantization-aware training. Everything in Chapter 2 was post-training quantization: calibrate, round, ship. When the accuracy loss is unacceptable, the alternative is to simulate the rounding during training so the weights learn to be quantization-friendly. It is strictly more powerful and strictly more expensive.

Runtime and export. The lesson costed models in parameters and milliseconds and never discussed how a trained network actually becomes a mobile binary — Core ML, LiteRT, ExecuTorch, ONNX Runtime Mobile, each with its own operator coverage and its own way of silently falling back to the CPU when an operator is unsupported. That fallback is a common source of a model that benchmarks at 1.5 ms in a paper and 40 ms in your app, and diagnosing it is a per-runtime skill.

Federated and on-device learning. Chapter 7 mentioned federated averaging in passing as one of the things that can leave a device. Actually training on user data locally — secure aggregation, client drift, differential privacy budgets — is a whole discipline sitting behind that one reference.

How to read a paper before you believe its numbers

Chapter 2 contained a small crisis: a coefficient that circulates widely as “MobileCLIP-S0’s loss weights” belongs to a different model in the same paper, and an augmentation count is stated one way in the dataset section and the opposite way in one ablation sentence. That is normal. Papers are written by tired people under deadlines. Four habits make you resistant.

Where to go next on this site

Three directions lead out of here. Downward, into the compression machinery this lesson used as a black box — pruning, quantization-aware training, neural architecture search. Sideways, into the server-side counterpart, where every constraint inverts and it is instructive to watch the same problem produce opposite answers. And upward, into what happens when the thing you are trying to fit on the device is not a 11.4 M-parameter encoder but a language model.

The cheat sheet

Ten questions you should now be able to answer from a blank page

Not a quiz — a self-test. Cover the right column. If a row takes more than a minute, the chapter number tells you where to go back to.

The sixth row is the one worth checking yourself on, because it is pure application of a formula you now own: bytes divided by measured bandwidth, nothing else. If that arrived quickly, the lesson worked.

One last thing

The reason on-device work rewards arithmetic so heavily is that the constraints are real and they are knowable in advance. A server can be given more machines. A phone cannot. Every megabyte, every millisecond and every millijoule in this lesson could have been computed before a single line was written, and almost every failed on-device project failed because nobody did that computation until after the code existed.

So the skill is not knowing MobileCLIP. It is being able to sit down with a blank page, write M = N · (d · b ÷ 8 + c), and know within an hour whether the thing you have been asked to build can exist on the device you have been asked to build it for.

On a phone, the arithmetic is how you stop fooling yourself. It is unglamorous, it takes twenty minutes, and it is the entire difference between a demo and a product.

References

1. Vasu, Pouransari, Faghri, Vemulapalli, Tuzel. “MobileCLIP: Fast Image-Text Models through Multi-Modal Reinforced Training.” CVPR, 2024. arXiv:2311.17049
2. Kusupati et al. “Matryoshka Representation Learning.” NeurIPS, 2022. arXiv:2205.13147
3. Malkov, Yashunin. “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.” IEEE TPAMI, 2018. arXiv:1603.09320
4. Zhang, Suda, Lai, Chandra. “Hello Edge: Keyword Spotting on Microcontrollers.” 2017. arXiv:1711.07128
5. Mazumder, Banbury, Meyer, Warden, Reddi. “Few-Shot Keyword Spotting in Any Language.” Interspeech, 2021. arXiv:2104.01454
6. Roth, Pemula, Zepeda, Schölkopf, Brox, Gehler. “Towards Total Recall in Industrial Anomaly Detection” (PatchCore). CVPR, 2022. arXiv:2106.08265
7. Morris, Kuleshov, Shmatikov, Rush. “Text Embeddings Reveal (Almost) As Much As Text.” EMNLP, 2023. arXiv:2310.06816
8. McMahan, Moore, Ramage, Hampson, Agüera y Arcas. “Communication-Efficient Learning of Deep Networks from Decentralized Data” (FedAvg). AISTATS, 2017. arXiv:1602.05629
9. Lin, Chen, Lin, Gan, Han. “MCUNet: Tiny Deep Learning on IoT Devices.” NeurIPS, 2020. arXiv:2007.10319
10. Radford et al. “Learning Transferable Visual Models From Natural Language Supervision” (CLIP). ICML, 2021. arXiv:2103.00020