Engram row cache: four-way sets evict or refuse re-read rows while a third of slots are free (87 % vs 99.8 % re-read hit rate at 1 vs 4 GiB) #269

What happens

RowCache (helios/src/engram/cache.rs) stores each row in one four-way set, chosen by a hash of the row ID. When that set is full, the victim is the way with the lowest (usage estimate, last access); the usage estimate is an approximate access count, the minimum of four 8-bit counters (1 MiB of counters per table) that every lookup increments, misses included. The incoming row replaces it only if its own usage estimate is at least as high as the victim's; otherwise the insert is dropped. A row cannot use free slots in other sets, so a full set evicts or refuses rows while most other sets still have free slots. No metric counts refused inserts.

Measured on DeepSeek V4.1 Flash with tensor parallelism 3 on three GB10 hosts (DGX Spark class, unified memory), one rank per host, with disk Engram tables. One server ran with the default 1 GiB cache and one with --embedding-table-cache-size 4G. Each server received five non-streaming /v1/completions requests (token-ID prompts, max_tokens 1, logprobs 20), in this order:

1. A: a 20,000-token excerpt of the repository's docs/*.md.
2. A with its first 16 tokens replaced.
3. B: a 60,000-token excerpt from another part of the same text.
4. B with its first 16 tokens replaced.
5. A again, with a different 16-token start.

The changed start prevents prefix-cache reuse (cached_tokens is 0 in every response), while almost every Engram n-gram repeats. Counters are flare_engram_* deltas from /metrics on rank 0's host, read before and after each request; the other two hosts were not sampled, and each host holds its own cache. Hit rate is hits / (hits + misses) from flare_engram_row_cache_*, which count each distinct row ID once per gather. Time is the client-side duration of the request. Rank 0's host reports row_cache_capacity_rows 3,613,836 at 1 GiB and 15,118,212 at 4 GiB, over two tables.

The five requests read about 2.72 million distinct rows on that host (the 4 GiB cache ended with 2,715,850 resident rows after 6,650 evictions), 75 % of the 1 GiB cache's 3,613,836 slots. The 1 GiB cache ended with 2,427,737 rows (67.2 % of its slots) and 453,178 evictions. Every miss is followed by exactly one insert, so refused inserts are misses minus rows added minus evictions: 265,994 at 1 GiB and 3,192 at 4 GiB. During B the cache filled from 20.4 % to 67.2 % of its slots, with 223,854 evictions and 77,741 refusals. The two later re-reads, at 67.2 %, added 223,635 evictions and 188,191 refusals. 2.72 million rows over 903,459 four-way sets is 3.0 rows per set; with rows spread uniformly (X rows per set, Poisson with mean 3.0), E[min(X, 4)]/4 = 67 % of the slots fill, which matches the 67.2 % measured, and about 35 % of the sets are full.

#78 covers first-touch misses with disk Engram, and #230 covers splitting the readiness wait into cache and disk. #267 proposes a branch that changes prefetch and pins read-ahead rows until they are used; it also edits cache.rs: read-ahead rows bypass the admission rule and cannot be evicted while pinned, but the four-way sets and the admission rule for ordinary misses are unchanged. This issue is about rows that were already read once and are not kept while the cache as a whole has free slots. #78 also reports, for a random prompt of about 500k tokens on TP4, median same-body re-read hit rates of 92.07 %, 98.97 % and 99.90 % with --embedding-table-cache-size 8, 16 and 32 GiB.

Why it matters

The re-reads with 1 GiB took 2.03 s longer for B (+11.4 %, 311,763 more misses) and 0.61 s longer for the third read of A (+10.5 %, 93,973 more misses). The readiness wait (flare_replay_readiness_wait_nanoseconds_total) accounts for both differences: it rose by 2.14 s at 1 GiB and 0.14 s at 4 GiB during the B re-read, and by 0.65 s and 0.05 s during the third read of A. That wait is the exposed delay measured across ranks, so it also reflects the two hosts whose counters were not sampled. Each request ran once. With similar miss counts the two servers differed by 0.01 s (A with a new start) and 0.15 s (B); the first request after start differed by 0.54 s with miss counts 14 apart, 0.48 s of it readiness wait, so the 0.61 s for the third read of A is not significant on its own. Both re-reads cost the same extra readiness wait per extra miss counted on rank 0's host, 6.4 µs.

1 GiB is the default on unified-memory GPUs. Where memory limits the KV cache, a larger row cache takes the same bytes from it.

With the unmodified host reserve, the core used here (see Environment) started with 12,528 KV pages of 128 tokens at 1 GiB (seven other starts of the same core with the same flags under that reserve gave 11,320 to 16,952) and did not start with a 4 GiB cache in the one attempt: a rank exited during startup, and its error was not recorded. Both servers in the table therefore ran a locally patched runtime that lowers the integrated-GPU system headroom (HOST_SYSTEM_SHARE in selene/src/offload.rs, a twentieth of total memory) to a fortieth, about 3 GiB more per host. docs/cli-design.md states that this headroom applies under every memory limit, so --memory-limit cannot reduce it. The cache code is unchanged in that runtime, and both servers used the same reserve.

With the lowered reserve, the 4 GiB configuration started with 14,215 and 11,548 KV pages on two starts, against 41,358 and 41,301 at 1 GiB. That core loads about 104.6 GiB per GPU including the 1 GiB row cache, so its KV budget is small and the relative loss is large; no other configuration was measured.

Not measured

• Repeated runs, and other prompts, request orders or concurrency.
• Counters on the hosts of ranks 1 and 2.
• Any change to cache.rs on hardware. Every alternative below is from emulation only.

Possible direction

A trace-driven emulation of RowCache was used to compare alternatives. It applies the victim choice, admission rule and recency order of cache.rs, with 1 MiB of usage counters and the mean per-table capacity of the measured servers. Sets are chosen by a 64-bit hash modulo the set count, with a different hash function from XXH3. It models one table and doubles the counts for two, assuming both tables see the same rows. Requests 2 to 5 are replayed in 4,096-token chunks and the first request in 12 equal chunks, matching its 12 prefill launches; the first read of B is replayed in 16 chunks where the server ran 17 launches. No counter halving occurs in this trace. Row IDs come from raw token n-grams (8 heads each for orders 2, 3 and 4) instead of the compressed vocabulary, which gives about 4 % more distinct rows than the servers read. At 1 GiB with four ways, the emulation gives 85.6 % for B with a new start and 86.4 % for the third read of A, against 87.06 % and 87.85 % measured. At 4 GiB it gives 99.79 % and 99.74 %, against 99.81 % and 99.74 % measured. For the first reads of A and B it gives 8.9 % and 16.4 %, against 9.50 % and 18.77 % measured. Across three hash seeds, the 4-way, 8-way and two-set results move by at most 0.11 percentage points; the other rows used one seed.

Emulated hit rates at the same 1 GiB budget:

• More ways use the same bytes, but each lookup scans 8 or 16 index entries instead of 4, and each eviction computes usage estimates for more residents.
• With two candidate sets, a row is inserted into whichever of its two sets has more free slots; when both are full, the victim is the lowest (usage estimate, last access) among the 8 residents, under the same admission rule. This also uses the same bytes. It needs a second set index and a second set probe on every lookup that does not find the row in the first set, which includes every miss.

A counter for refused inserts would make this behaviour visible in /metrics. Would a change of this kind to the set layout be considered, and is there a preferred way to qualify it on hardware?

Environment

• Three GB10 hosts (DGX Spark class, unified memory), tensor parallelism 3, one rank per host, --embedding-table-storage default (disk), no resident scales, 4,096-token prefill chunks.
• Checkpoint deepseek-ai/DeepSeek-V4.1-Flash-1017. Core exported with recipe defaults from bbad44fe plus an earlier revision of Make the compiler memory headroom a preparation setting #122 (bf5ca911, preparation only) with --compile-headroom 6G.
• Runtime: bbad44fe plus e774a468, with the reserve change described above. Serving flags: --scheduler-policy throughput --kv-cache-limit memory --prefix-cache-memory 0, a disk prefix cache limited to 50 GiB, no --memory-limit. Host page caches were dropped before each server start.
• git diff bbad44fe 0572fd12 is empty for helios/src/engram/, helios/src/engram.rs, helios/src/runtime_core/selection.rs and helios/src/runtime_core/model.rs, which divides the budget among table groups.
• Prompts: tokens 1,000 to 21,000 (A) and 60,000 to 120,000 (B) of the concatenated docs/*.md, tokenized with the checkpoint's tokenizer and keeping only token IDs from 3 to 127,999.