Jason Chen

Scoring a candidate means reading its embedding and reducing it against the user's. As two kernels, the gathered embeddings are written to memory and immediately read back. Fused, they never leave registers. The arithmetic is trivial — the whole problem is memory traffic, so removing passes removes time.

Gains compose multiplicatively, so the stack matters more than any one trick. Fusion and precision are exact byte ratios you can derive from the shapes; the microarchitectural factors are typical magnitudes for a bandwidth-bound gather kernel, not measurements. All of it is chasing the same ceiling — a dot product does two FLOPs per element read, so arithmetic intensity sits far below the ~10–20 FLOP/byte where an accelerator turns compute-bound. Stacked, this class of optimization lands around an order of magnitude at the kernel level; end-to-end gains land nearer 2× once the stages it never touches start to dominate.

Memory is served in fixed 32-byte sectors, not bytes. A warp's 32 lanes are coalesced into the smallest set of sectors covering their addresses, and you pay for every sector fetched whether you use it or not. Contiguous access wastes nothing. A random gather touches a different sector per lane, so narrow loads throw most of the bus away.

A gather cannot be made contiguous — the rows are wherever the index says. Widening the load is the lever you actually have: same sectors touched, four times the useful bytes per one, and a quarter of the load instructions to issue.

Once the row is in registers it still has to be summed. A shared-memory tree needs a barrier at every level; register shuffles let lanes read each other directly, so the same log-depth tree runs with no barriers and no shared memory at all.

Both collapse 32 lanes in log₂32 = 5 steps. The difference is what each step costs: a barrier serialises the whole block and the staging array burns shared memory that would otherwise raise occupancy.

Millions of candidates in, a handful out. Both retrieval paths run in parallel, then merge. Drag a stage — everything the early stages drop is GPU time never spent.

Illustrative model. Per-stage cost is a fixed price per candidate examined.

Ranked candidates arrive faster than the latency budget allows sorting. Keep the best K — but pay neither a full sort nor a heap update per item. Admit into a buffer of m·K; when it fills, partition once and keep the best K. The discarded half is overwritten, never reallocated.

Raising m buys fewer partitions with linearly more memory. Worst case the partition work amortizes to m/(m-1) per admitted item — 2.00 at m=2, 1.50 at m=3. In practice the boundary suppresses admissions so hard that admits grow like K·ln(N/K), and partitions are rarer still. Average O(N) overall, against O(N log K) for a heap.

Learned retrieval optimises for relevance, but eligibility is a hard constraint — who an advertiser will pay to reach, what budget is left, what policy allows. A model can happily surface a candidate that fails all three. Checking exactly is expensive on high-cardinality attributes, and an ineligible candidate that survives doesn't just waste compute: it occupies a slot in a fixed-width funnel that an eligible one could have had. A Bloom filter answers "definitely not present" in constant time and constant space, paying for it with false positives. Cheap rejects up front, exact check only on what survives — the filter is never the authority.

False positive rate is (1 − e^(−kn/m))^k, minimised at k = (m/n)·ln2. Measured value samples 4,000 absent keys. More hashes help until they fill the array, then hurt — the reason a filter has to be sized against the load it will actually see. The closed form assumes perfectly independent hashing, so once the array saturates it drifts from what any concrete hash function really does; showing both numbers is the point.

To spend more capacity on one request you split it across workers — and the split has to be exactly disjoint. Slicing on index position is cheap, until replicas refresh on their own schedules and the same item sits at a different position on each. Slices then overlap and gaps open: candidates scored twice, others silently dropped. Slicing on a stable attribute of the item costs more and is worth it, because a retrieval path that quietly loses candidates is worse than a slower one.

Position-based slicing is correct only while every replica agrees on where an item lives. Staggered index updates break that agreement, and the failure is silent — no error, just a quieter funnel. Keying the split on an attribute that travels with the item makes the partition replica-independent, which is the property that actually matters.

Weighted sources, one ordered output. In round r, every queue with weight ≥ r emits once — so weight sets share, not position, and nothing arrives in a burst. This is the shape of running several retrieval models in parallel and deciding how much of the result each one owns.

Deterministic, and order-preserving within each queue.

Supplementary sources keep surfacing candidates the main queue already has. Naive dedup credits whoever emits first. This one remembers main membership and reattributes the duplicate, so a supplementary slot is only spent on genuinely new supply. The catch: main is a bounded top-K filled on the fly, so membership is only knowable inside the window.

Reattribution costs the supplementary source its slot but not its credit. Items evicted from the bounded window before a supplementary match arrives cannot be reattributed — those are counted separately.