EVStore: Storage and Caching Capabilities for Scaling Embedding Tables in Deep Recommendation Systems

Daniar Heri Kurniawan, Ruipu Wang, Kahfi S. Zulkifli, Fandi A. Wiranata, John Bent, Ymir Vigfusson and 1 other

The systems that decide what you see next on a shopping site or a video service turn categories like a user or a product into lists of numbers by looking them up in enormous tables, and those tables have grown to tens of terabytes, tripling every two years, so they are kept entirely in expensive fast memory — at one company recommendation systems consumed nearly 80 percent of all hardware devoted to artificial intelligence; the obvious relief is to keep only the popular entries in memory and the rest on disk, and the obvious way to judge that is the fraction of lookups found in memory, which reaches a healthy 60 to 90 percent; this paper (Chicago and Emory) shows that number is close to meaningless, because answering one request requires around 26 separate lookups and a single miss makes the whole request slow, so what actually matters is how often ALL of them hit — which is between 1 and 50 percent; redesigning the cache around that, plus storing some entries at reduced precision and letting a missing entry borrow the answer of a semantically similar one, cuts memory needs by 94 percent for a 0.2 percent accuracy cost.

The argument in one glance

Problem

The lookup tables have become the dominant cost of recommendation

Recommendation systems decide a great deal of what people see — by one set of measurements, 30 percent of traffic on a large retailer, 60 percent of videos watched on a video platform, 75 percent of films viewed on a streaming service. They work by turning categorical inputs, meaning which user or which product, into lists of numbers a neural network can consume, and that conversion happens by looking each category up in an EMBEDDING TABLE. Those tables have become the dominant cost. Real deployments hold billions of entries needing tens of terabytes, the standard platforms keep them entirely in fast memory because they have no mechanism to fetch an entry from disk, and their sizes TRIPLE every two years as better recommendations demand richer representations. At one large company, recommendation systems accounted for nearly 80 percent of all hardware devoted to artificial intelligence.
What people did

Put the tables on disk and cache the popular entries

The natural remedy is the one used everywhere else in computing. Move the enormous table to cheap storage, keep the frequently used entries in memory, and let a well-studied replacement algorithm decide what stays. Decades of research have produced excellent algorithms for exactly this, from simple recency and frequency policies to adaptive and machine-learned ones, and their quality is judged by a standard measure — the fraction of lookups answered from memory.
Why it fell short

That measure is close to meaningless for this workload

Answering one recommendation request requires not one lookup but around 26, one per categorical feature, and the neural network cannot run until every one of them has returned. A single miss sends a request to disk, which is orders of magnitude slower, so the whole request is slow regardless of how well the other 25 went — an ALL-OR-NOTHING structure. Measured on real data, the established algorithms achieve a healthy-looking 60 to 90 percent of individual lookups from memory, while the fraction of requests where ALL the lookups hit ranges from just 1 to 50 percent. The standard metric is not merely imprecise here, it is measuring a quantity only loosely related to what the user experiences, and every algorithm judged by it has been tuned for the wrong objective.
This paper's idea

Cache for whole groups, shrink the entries, and let similar entries stand in

This paper (Chicago, Emory and Seagate — Kurniawan, Wang, Zulkifli, Wiranata, Bent, Vigfusson, Gunawi) builds EVStore, three cooperating layers on commodity hardware. The first repairs the objective — every cached entry carries a GROUP SCORE recording how many of its companions were present when it was last used, so entries belonging to well-cached groups are retained and entries that only appear in requests that miss anyway are evicted, raising the all-hit rate by up to 18 percent. The second exploits that these numbers need not be exact, storing some entries at 16, 8 or even 4 bits instead of 32, which fits eight times more of them in the same memory. The third exploits what embeddings MEAN — since similar things have similar vectors by construction, a missing entry can borrow the answer of a semantically similar one, and the stand-in is chosen to be both similar and popular so it is likely already cached. Together they cut memory needs by 94 percent for a 0.2 percent accuracy cost.

Why this problem is worth solving

The cost being attacked here is one of the largest in modern computing infrastructure, so it is worth understanding what the memory is actually holding.

A neural network consumes numbers, but much of what a recommendation system knows about is CATEGORICAL — which user, which product, which page, which word. There may be hundreds of such features, each with millions or even billions of possible values, and feeding that directly to a network is hopeless. The standard solution is an EMBEDDING TABLE, which maps each category to a short list of numbers, its EMBEDDING VECTOR, learned during training. This does two things. It makes the network tractable by replacing an astronomically large space with a compact one. And, importantly, it places similar things near each other — the words “kitty” and “cat” end up with almost identical vectors, so the network gets comparable results for both without ever being told they are synonyms. The cost is memory, and it has become enormous. Deployments hold billions of entries needing tens of terabytes, kept entirely in fast memory because the standard platforms have no mechanism to fetch from disk, and sizes triple every two years because richer recommendations require richer representations. At one large company these systems consumed nearly 80 percent of all hardware devoted to artificial intelligence

. Any reduction here is worth a great deal.

The obstacle is a structural property of the lookups that ordinary caching does not anticipate.

Serving one recommendation request requires looking up one entry in EACH categorical feature’s table — around 26 separate lookups in the configuration studied here — and the neural network cannot begin until all of them have returned. If even one must be fetched from disk, that request waits for disk, which is orders of magnitude slower than memory, and the other 25 successful lookups have saved nothing. This is an ALL-OR-NOTHING structure, and it breaks the assumption behind how caches are evaluated. The conventional measure is the INDIVIDUAL HIT RATE, the fraction of lookups answered from memory, which treats each lookup as independently valuable. What actually determines whether a request is fast is the PERFECT HIT RATE, the fraction of requests where every lookup hits. These diverge dramatically, because to get a perfect hit you must win 26 times in a row — measured here, individual hit rates of 60 to 90 percent correspond to perfect hit rates of only 1 to 50 percent

. Every algorithm evaluated on the conventional measure has been optimizing something only loosely connected to what a user waits for.

What people did before, and where it broke

Keep the whole table in memory. What the standard open-source platforms do, with no mechanism to fetch an entry from disk at all. Simple and fast, but it means one model can occupy an entire server, preventing other models from running and wasting the rest of the machine.
Classical cache replacement algorithms. Decades of excellent work exists, from recency and frequency policies through adaptive variants to machine-learned ones. All are designed and evaluated for workloads where each lookup is independently useful, which this one is not.
Judging caches by hit rate. The universal measure, and the reason the mismatch went unnoticed — 60 to 90 percent looks like success, while the quantity that governs request latency sits between 1 and 50 percent.
Custom storage hardware for embedding lookups. Recent work does move the tables to storage and optimize the lookups, and does so effectively. But it generally requires bespoke devices, custom drives or programmable hardware, which is why adoption has been limited.
The gap. Nobody had attacked the problem from inside the recommendation platform itself, on ordinary hardware, using the structure of how these lookups actually happen. Doing so requires first noticing that the standard measure of cache quality is the wrong objective for this workload. That is the gap EVStore fills.

How three layers cooperate to shrink the memory requirement

Fix the objective, shrink the entries, then let similar entries substitute

Caching by hit rate optimizes the wrong thing

One request needs about 26 lookups and cannot proceed until all return, so a single miss makes the whole request slow. Conventional algorithms maximize the fraction of individual lookups that hit, reaching 60 to 90 percent, while the fraction of requests where everything hits is only 1 to 50 percent.
↓ →
Score entries by the company they keep new

Every cached entry carries a group score. When a request completes, the number of its lookups that hit becomes that score for every entry involved, kept as the best seen so far. Entries belonging to well-cached groups are retained and those appearing only in requests that miss anyway are evicted first.
↓ →
Evict by group score, cheaply new

Entries are ordered by score and the lowest go first, with newly fetched entries admitted even over higher-scoring residents because recency still matters. Since eviction happens constantly, entries are held in a structure giving constant-time operations so the bookkeeping does not become the bottleneck.
↓ →
Store some entries at reduced precision new

The numbers in an embedding need not be exact, so a second tier holds entries at 16, 8 or 4 bits rather than 32. That fits up to eight times more entries in the same space, raising hit rates, and smaller values are also faster to read — worth 15 percent on lookup latency, which is 40 percent of the total.
↓ →
Let a similar entry answer for a missing one new

Because embeddings place similar things close together by construction, a missing entry can borrow the vector of a semantically similar one. A third layer maps each entry to a stand-in, chosen offline using standard vector-distance measures, and caches only those key-to-key mappings rather than any values.
↓ →
Choose stand-ins that are already in memory new

A similar entry is only useful if it is present, so among the ten most similar candidates the system picks the most frequently accessed one. The substitute is therefore likely to be resident, which is what turns a miss into an answer rather than merely into a different miss.

Implemented inside a widely used open-source recommendation platform in about nine thousand lines of code and released publicly, evaluated on production traces and a standard advertising dataset with 26 categorical features.

The idea

The standard measure of cache quality is the wrong objective here, and noticing that is the paper. Hit rate is so universal a measure that it is rarely questioned, and for most workloads it is right — each lookup that avoids disk saves real time. This workload is different in a structural way. A request needs about 26 lookups and cannot start until all of them return, so the value of a hit depends entirely on whether its 25 companions also hit. Winning 26 independent coin flips at 90 percent each succeeds only about one time in fifteen, which is why individual hit rates of 60 to 90 percent coexist with all-hit rates of 1 to 50 percent. Every algorithm tuned on the conventional measure has therefore been optimizing something only loosely connected to latency. Discovering that a long-trusted metric is measuring the wrong unit is the site’s most persistent lesson, and it appears here in an unusually sharp form — elsewhere a cache showed an excellent hit rate that did not matter because it was off the critical path, whereas here the hit rate is on the critical path but aggregates over the wrong thing.

Once the objective is right, the fix is to cache groups rather than items. The repair is elegant precisely because it is small. Each cached entry carries a score recording how many of its companions were present the last time it was used, kept as the best seen so far. An entry that keeps turning up in requests where almost everything hits is worth keeping, because retaining it likely completes a whole request. An entry that only ever appears in requests that miss several things anyway is worth little, because keeping it saves nothing on its own. So eviction is reordered around whether an entry contributes to a COMPLETE answer rather than whether it is individually popular. One measured consequence is telling: one variant deliberately sacrifices individual hit rate to gain all-hit rate, which looks like a regression on the traditional metric and is an improvement on the one that matters. Optimizing the unit the user actually experiences rather than a component-level proxy is a discipline covered elsewhere on this site wherever a system stops improving parts and starts improving outcomes.

The data’s own meaning licenses two different approximations. The remaining two layers both trade exactness for capacity, and both are justified by what embeddings are. First, the numbers need not be precise — storing them at 4 bits instead of 32 fits eight times more entries in the same memory, and more entries means more complete requests. Second, and more interestingly, embeddings place similar things near each other BY CONSTRUCTION, which is the entire reason they work. So if an entry is missing, the vector of a semantically similar entry is very nearly the right answer, and the system can substitute it. The refinement that makes this practical is choosing a stand-in that is both similar and popular, since a substitute that is also absent helps nobody. Exploiting a property the data was built to have, rather than treating the store as an opaque key-value service, is the same use-what-the-domain-guarantees move covered elsewhere on this site where knowing what the values mean is what makes an otherwise unavailable optimization safe.

Serving one recommendation request

From 26 lookups to an answer without touching disk

How a request passes through the three layers. Numbers from the paper's evaluation.

Step 1 of 5

What the request needs

A recommendation request arrives with categorical inputs — a user, a context, a set of items. Each must be converted to a vector by looking it up in its own table, about 26 lookups in total, and the neural network cannot begin until every one has returned. One miss means waiting for disk and the whole request is slow.

the tables together may hold billions of entries and tens of terabytes, so only a fraction fits in memory
conventional caching reaches 60 to 90 percent of individual lookups from memory, but only 1 to 50 percent of requests get everything

Why it works

A request needs about 26 lookups and cannot start until all return → the value of any single hit depends on whether its companions also hit → so individual hit rate, the conventional measure, is only loosely connected to latency.
Scoring each entry by how many companions were present when it was last used → identifies entries that contribute to complete answers rather than merely popular ones → raising the all-hit rate by up to 18 percent over the best established algorithms.
Embedding values need not be exact → storing them at 4 bits rather than 32 fits eight times more entries in the same memory and reads faster → improving both hit rate and the lookup latency that is 40 percent of the total.
Embeddings place similar things close together by construction → the vector of a similar entry is very nearly the right answer for a missing one → converting a disk access into an approximation whose cost is 0.2 percent accuracy.
A substitute is only useful if it is present → choosing the most popular among each entry’s ten nearest neighbours makes the stand-in likely resident → which is what turns a miss into an answer rather than into a different miss.

What it costs (trade-offs and scope)

Accuracy is genuinely traded away. The headline memory reduction comes with a 0.2 percent accuracy drop, small but real, and in a business where recommendation quality is the product, whether that is acceptable is a judgement rather than a technicality.
The approximation layer assumes the tables do not change. The stand-in mapping is computed offline from vector distances and access frequencies, and the design assumes the embedding table stays static during serving, so continuously updated models would need that mapping refreshed.
It requires offline preprocessing. Producing the similarity mapping means computing nearest neighbours across tables that may hold millions of entries, plus tracking historical access frequencies — real work, done once, but a prerequisite rather than a drop-in change.
Gains depend on the workload having exploitable structure. The group scoring helps because requests repeatedly touch overlapping sets of entries, and the substitution helps because popular entries have similar neighbours. Workloads without that structure would benefit less.
The evaluation is one platform and one main dataset. Results come from integrating with a single widely used open-source recommendation platform, measured largely on one standard advertising dataset with 26 categorical features and production traces, so the specific numbers are tied to that setting.

The evaluation

EVStore was implemented inside a widely used open-source recommendation platform, in about nine thousand lines including offline tooling, and released publicly. The caching layer was compared against ten established replacement algorithms spanning recency, frequency, adaptive and machine-learned policies, measured on both the conventional individual hit rate and the all-hit rate, at cache sizes from 0.5 to 20 percent of the table data. End-to-end latency, throughput, accuracy and memory footprint were then measured against the unmodified platform, including how much memory each configuration needs to meet a 2 millisecond average latency target.

Serving embedding lookups for recommendation

Property	Whole table in memory	Conventional caching	EVStore
Memory required
What it optimizes
All-lookups-hit rate
Accuracy cost
Models per machine

Meeting a 2 millisecond average latency target requires 100 percent of the data in memory on the unmodified platform and 6 percent with all optimizations enabled, a 94 percent reduction for a 0.2 percent accuracy cost. Average latency falls up to 23 percent and the ninetieth percentile up to 27 percent, and the freed memory allows four models to share one machine.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the trade honestly, because accuracy is genuinely being sold. The headline 94 percent memory reduction comes with a 0.2 percent accuracy drop, which is small but real, and in a business where recommendation quality is the product, whether that exchange is acceptable is a commercial judgement rather than a technical one. Two of the three layers depend on approximation being tolerable at all, so a setting where exact values are required would benefit only from the first. The substitution layer additionally assumes the embedding tables remain static while serving, since its mapping from each entry to a similar stand-in is computed offline from vector distances and access frequencies — a continuously updated model would need that mapping refreshed. That preprocessing is real work, computing nearest neighbours across tables holding millions of entries, done once but a prerequisite rather than a drop-in change. The gains also depend on the workload having the structure being exploited, namely requests that repeatedly touch overlapping sets of entries and popular entries that have similar neighbours. And the evaluation is tied to one open-source platform and largely one standard dataset with 26 categorical features. Within that scope the lessons travel well beyond recommendation: check whether your metric aggregates over the unit your users actually experience; when a request needs everything to succeed, optimize for complete success rather than average success; and consider whether what your data MEANS licenses an approximation that treating it as opaque bytes would forbid.

Background

Measure the unit the user experiences, then let the data's meaning buy you room

This paper sits in the site’s machine-learning-systems and storage cluster and rhymes with several ideas covered elsewhere on this site. Its central finding is a particularly sharp instance of the site’s most persistent lesson — that a trusted metric can measure the wrong thing — and it is worth contrasting with the open-hardware graphics page, where a cache showed an excellent hit rate that did not matter because the component was off the critical path. Here the cache is squarely on the critical path and the hit rate is still misleading, because it aggregates over individual lookups when a request needs all twenty-six to succeed, so 60 to 90 percent individual hits coexist with 1 to 50 percent complete requests. Its response, scoring cached entries by whether they contribute to a complete answer rather than by their own popularity, is the optimize-the-outcome-not-the-component discipline the site rewards, and it produces the telling result that one variant is deliberately worse on the traditional metric and better on the real one. Its two approximation layers exploit what embeddings inherently are, storing values imprecisely and letting semantically similar entries substitute for missing ones, which is the same use-what-the-domain-guarantees move the non-uniform-bandwidth page makes when it replicates only data the compiler has proven read-only, and the same representation-determines-what-errors-cost insight the superconducting-logic page reaches when uniform weighting turns out to make failure graceful. And its insistence on working within an existing platform on commodity hardware, where prior storage work needed custom drives or programmable devices, is the lower-the-adoption-barrier concern that decides whether good ideas are ever used.

If you remember only three things

1. Recommendation systems convert categorical inputs into vectors by looking them up in EMBEDDING TABLES, which have become the dominant infrastructure cost — billions of entries needing tens of terabytes, held entirely in fast memory because the standard platforms cannot fetch from disk, tripling in size every two years, and accounting at one large company for nearly 80 percent of all hardware devoted to artificial intelligence. Moving them to storage and caching the popular entries is the obvious remedy, but it collides with a structural property: one request needs about 26 separate lookups and cannot proceed until every one returns, so a single miss makes the whole request slow.
2. That ALL-OR-NOTHING structure means the universal measure of cache quality is measuring the wrong unit. Individual hit rate treats each lookup as independently valuable, and the established algorithms achieve a healthy-looking 60 to 90 percent — while the fraction of requests where everything hits, which is what actually determines latency, ranges from just 1 to 50 percent, because a perfect hit requires winning 26 times in a row. Every algorithm tuned on the conventional metric has therefore been optimizing something only loosely connected to what a user waits for.
3. EVStore fixes the objective and then buys room with two approximations the data itself licenses. Each cached entry carries a GROUP SCORE recording how many companions were present when it was last used, so entries that contribute to complete answers are retained — raising the all-hit rate by up to 18 percent, with one variant deliberately sacrificing individual hit rate to do so. A second tier stores entries at 4 bits instead of 32, fitting eight times more. A third exploits that embeddings place similar things together by construction, letting a missing entry borrow a similar entry's vector, with the stand-in chosen to be both similar and popular so it is likely resident. Together they cut the memory needed to meet a latency target by 94 percent for a 0.2 percent accuracy cost.

Check yourself

Check your understanding

1. Established caching algorithms achieve 60 to 90 percent hit rates here, yet the paper calls that close to meaningless. Predict why.
2. Each cached entry carries a score recording how many companions were present when it was last used. Predict what that accomplishes.
3. A missing entry can be answered with a different entry's vector. Predict why that is defensible rather than simply wrong.
4. Storing embedding values at 4 bits instead of 32 helps in two distinct ways. Predict both.

Sources

EVStore: Storage and Caching Capabilities for Scaling Embedding Tables in Deep Recommendation Systems (ACM DL, DOI 10.1145/3575693.3575718) — ASPLOS 2023.
Author PDF (UCARE, University of Chicago) — the full 14-page paper, read in full for this explainer.
dblp record — bibliographic entry and author list.