GRACE: A Scalable Graph-Based Approach to Accelerating Recommendation Model Inference

Haojie Ye, Sanketh Vedula, Yuhan Chen, Yichen Yang, Alex M. Bronstein, Ronald G. Dreslinski and 2 others

Recommendation models spend most of their time fetching item feature vectors from memory and adding them together, and since users repeatedly ask for the same combinations of items, the obvious saving is to pre-add the popular combinations and store the results — but nobody could find those combinations at scale, because counting how often every possible combination occurs explodes combinatorially; this paper (University of Michigan and Technion) records only how often each PAIR of items is requested together, as a graph whose size does not grow with the number of users at all, then grows clusters greedily from the highest-degree node, using bounds derived from the pair counts to estimate the value of a larger combination without ever counting it.

The argument in one glance

Problem

Recommendation runs on memory bandwidth, and the tables outgrew the fast memory

A recommendation model decides which items to show a user. Its expensive part is not arithmetic. For each user it fetches one feature vector per item that user has interacted with, then adds those vectors together. The tables holding those vectors reach terabytes, the accesses are irregular so ordinary caches miss, and bandwidth demand has grown thirty times in four years to two terabytes per second — far faster than memory hardware has improved. One large operator reports these models consume more than sixty percent of its artificial intelligence inference work, so the waste is measured in millions of dollars and in carbon.
What people did

Pre-add the popular combinations and store the results

Users request the same items together over and over, because item popularity follows a power law where a few items dominate. So instead of fetching several vectors and adding them at request time, pre-compute the sum of a popular GROUP of items once, store that single result, and fetch it as one vector. Prior systems did exactly this. SPACE stored the sums of all PAIRS drawn from a small popular subset. MERCI generalised to groups larger than two by clustering items that co-occur and storing every sum within each cluster.
Why it fell short

Pairs are too weak, and finding larger groups does not scale

SPACE reduced memory traffic by only nine percent, because two items both being popular does not make them popular TOGETHER — only about a quarter of its stored pair sums accounted for ninety-five percent of the accesses, so most of the precious fast memory held sums almost nobody wanted. MERCI found genuinely better groups but had to inspect the full user trace, giving a cost that grows quadratically with items and linearly with users. To survive, it split items into sub-groups and clustered only within them, which discards every co-occurrence that crosses a boundary. Worse, MERCI optimised traffic reduction alone, so it filled the small fast memory with rarely used sums and pushed ordinary item vectors out to the slow memory, throttling the machine it was meant to speed up.
This paper's idea

Record only pairs as a graph, then bound what larger groups are worth

This paper (University of Michigan and Technion — Ye, Vedula, Chen, Yang, Bronstein, Dreslinski, Mudge, Talati) records nothing about groups larger than two. It builds an ITEM CO-OCCURRENCE GRAPH where each node is an item and each edge weight counts how often those two items were requested together. This graph is order-agnostic, its node count grows only linearly with items, and its SIZE DOES NOT GROW WITH USERS AT ALL. Clusters are then grown greedily from the highest-degree node. The value of adding one more item to a cluster cannot be read off the graph, since the graph knows nothing about triples — so the algorithm derives a lower and an upper BOUND on that value from the pair counts alone and interpolates between them. Clustering becomes linear in items and independent of users, running 8.3 times faster than MERCI, and because the cluster-size limit is tunable, the system can stop growing clusters early to keep the fast memory balanced.

Why this problem is worth solving

The cost here is unusual in that almost none of it is computation.

A DEEP LEARNING RECOMMENDATION MODEL predicts how likely a user is to click on something. It has two halves. Dense inputs such as age or location go through an ordinary neural network. Sparse inputs — the items this user has previously interacted with — go through an EMBEDDING LAYER. An EMBEDDING TABLE holds one feature vector per item, and there may be millions of items. For each user the layer looks up the vector for every item that user touched, then adds those vectors together into one summary vector. The number of items a user touched is called the POOLING FACTOR, and in the datasets used here it averages between 30 and 145. The arithmetic is trivial, just addition. The expense is entirely in the lookups, because which vectors are needed depends on the user, so the accesses are scattered across a table that can reach terabytes. Ordinary processor caches therefore miss almost every time, and the work becomes limited by how fast memory can deliver data

. One large operator reports these models consume more than sixty percent of its artificial intelligence inference work, and the embedding layer alone accounts for over eighty percent of the time in some of its production models.

The gap between what these models want and what hardware provides keeps widening.

Table sizes have grown sixteen times in four years to reach terabytes, and bandwidth demand has grown thirty times to two terabytes per second — far faster than memory hardware has improved. So production systems use two memories at once. A graphics processor has memory that is fast but small, typically tens of gigabytes. The host processor has memory that is slow but large, hundreds of gigabytes. The embedding table cannot fit in the fast memory, so the fast memory is used as a SOFTWARE-MANAGED CACHE holding a chosen portion, and everything else is read from the slow memory. This creates a two-sided problem rather than a one-sided one. Putting the right things in fast memory reduces how long the fast side takes, but every byte moved to the slow side lengthens the slow side, and the request is not finished until BOTH sides finish. A design that only minimises total traffic can therefore make the machine slower, by unbalancing the two

What people did before, and where it broke

Put the popular items in fast memory. FAE profiles how often each item is accessed, picks a popularity threshold, and places the hottest vectors in the fast memory. RecNMP adds a small cache to each near-memory processing unit for the same purpose. Both are reasonable and both help a little.
But they never reduce the traffic. The same number of vectors is fetched; only the source changes. Measured against a baseline that pretends fast memory is unlimited, FAE reaches only 1.1 times the throughput — work taking 10 seconds now takes about 9.1.
Pre-add pairs of popular items. SPACE stores popular single vectors AND the sum of every pair drawn from a small popular subset, so a request touching both items of a stored pair fetches one vector instead of two.
But popular twice is not the same as popular together. SPACE cut memory traffic by only nine percent. The authors measured that just 25 percent of its stored pair sums accounted for 95 percent of the accesses — so most of the scarce fast memory held sums almost nobody asked for. SPACE also tracks pairs only among a number of items that grows with the square root of the table, so it does not scale.
Cluster co-accessed items and store every sum inside each cluster. MERCI generalised beyond pairs. It repeatedly tests merging two clusters and measures the real benefit by inspecting the full user trace, which finds genuinely good groups.
But the search does not scale, and it fights itself. The cost grows quadratically with items and linearly with users, so MERCI must split items into sub-groups and cluster only within them — discarding every co-occurrence that crosses a sub-group boundary and losing the global picture. And it optimises traffic reduction alone, so it builds large clusters that fill the small fast memory with rarely used sums and push ordinary vectors to the slow memory.
The gap. Nobody had a way to find popular groups of arbitrary size at production scale, and nobody was optimising the quantity that actually decides throughput. The proof is stark: an infinite-fast-memory baseline scores 1.0, SPACE reaches 1.14 and MERCI 1.20, while an oracle allowed any pair sum reaches 2.16. Most of the available benefit was going uncollected.

How pair counts become groups

Record pairs only, bound what groups are worth, and stop before the fast memory is unbalanced

Fetch one vector per item and add them up

For each user the embedding layer looks up a feature vector for every item that user touched, then sums them. The accesses are scattered, the table is far larger than fast memory, and demand has grown thirty times in four years, so the work is limited entirely by memory bandwidth.
↓ →
Record which pairs of items appear together new

While serving real traffic, sample some users and record every PAIR of items each one touched. This recording is fire-and-forget, so it never delays a live request. Nothing is recorded about triples or larger groups, which is what keeps the cost bounded.
↓ →
Turn those counts into a graph new

Build a graph offline where each node is an item and each edge weight counts how often those two items were requested together. Node count grows only linearly with items, the representation ignores the order items were touched in, and the graph size does not grow with the number of users at all.
↓ →
Grow clusters greedily from the busiest node new

Sort nodes by degree and take the busiest unclustered one as an anchor. Repeatedly consider its neighbours and admit whichever adds the most value per cache line consumed. A cluster of k items costs 2 to the power k, minus 1, minus k extra lines, because every subset of two or more must be stored.
↓ →
Bound the value of a group instead of measuring it new

The graph cannot say how often three items appear together. Counting that exactly would need a pass over the trace for every subset, which is exponential in cluster size. Instead, derive a lower and an upper bound on the saving from the pair counts using inclusion-exclusion, and interpolate between them.
↓ →
Stop early enough to keep both memories busy new

A cluster-size limit and a tolerance threshold control how aggressively clusters grow. Growing them less leaves room for ordinary item vectors in fast memory, which keeps the slow side from becoming the bottleneck. A small decision tree picks both settings from three properties of the dataset.

Evaluated on eight real datasets from web service vendors, from 10,978 to 2,345,346 items, plus four mixtures modelling multiple tables, on an 80-core Intel Xeon Platinum 8380 with 512GB of DDR4-3200 and an NVIDIA A40 with 48GB. Released as open source.

The idea

Record less, and the cost stops growing. The instinct when you need to know which groups of items are popular is to count groups of items. That instinct is what defeated everyone. Counting every subset is combinatorial, and even MERCI’s disciplined version costs a pass over the whole user trace per candidate merge, which is why it grows quadratically with items and linearly with users. This paper records strictly less information — only pairs — and gets a representation with three useful properties. It ignores the order in which a user touched items, so different orderings collapse into the same evidence. Its node count grows only linearly with items. And most importantly, adding more users only changes edge WEIGHTS, never the graph’s size, so a trace of ten million users costs no more storage than one of ten thousand. Choosing a summary whose size is governed by the small dimension rather than the large one is the same compress-the-history-into-a-fixed-shape move covered elsewhere on this site where a bounded structure replaces an unbounded log and turns an intractable analysis into a cheap one.

When the exact answer is exponential, bound it instead. Recording only pairs leaves a genuine hole. If items a and b appear together 5 times, and b and c 4 times, and a and c 3 times, how often do all three appear together? The graph cannot say. It could be anywhere from 0 to 3. But the SAVING from caching that group can still be bracketed, because each possible answer implies a specific total, and the extremes give a lower and an upper bound. The algorithm computes both from the pair counts using inclusion-exclusion, interpolates halfway between them, and divides by the cache lines the cluster would consume to get a value per line. This is deliberately an estimate, and the paper says so — measuring the truth would require an exponential number of counts. Replacing an exact quantity that cannot be afforded with a cheap bound that ranks candidates well enough is the same discipline covered elsewhere on this site where a conservative approximation is chosen precisely because it keeps an analysis tractable at production scale.

Optimise the quantity that decides throughput, not the one that is easy to measure. MERCI’s failure is the most instructive part of this paper. Its objective, minimising memory traffic, sounds unimpeachable, and it genuinely achieves 37 percent — close to GRACE’s 40 percent. Yet it loses badly on actual throughput, because a request is not finished until both the fast memory and the slow memory finish their share. Large clusters consume the scarce fast memory with rarely used sums, evicting ordinary vectors to the slow side and making that side the bottleneck. GRACE deliberately builds SMALLER clusters than the traffic-minimising choice, accepting slightly less traffic reduction to keep both memories busy, and ends up 1.4 times faster. Optimising a plausible proxy instead of the thing you actually care about is the same trap covered elsewhere on this site where a benchmark improves a proxy metric while the quantity users experience gets worse.

Growing a cluster from six items

The paper's own walk-through, with five users and six items

Cache budget is 10 lines, interpolation factor 0.5, tolerance 0.4. Numbers are the paper's.

Step 1 of 5

Five users, six items

The recorded trace is small enough to follow completely. User 0 touched items 0, 1, 2 and 3. User 1 touched 2, 4 and 5. User 2 touched 0, 2 and 3. User 3 touched 4 and 5. User 4 touched 2, 3 and 4. Only pairs are recorded, so each user contributes one count for each pair among the items they touched.

items 2 and 3 appear together in users 0, 2 and 4, so that edge has weight 3
items 0 and 2 appear together in users 0 and 2, giving weight 2, and items 4 and 5 in users 1 and 3, also weight 2

Why it works

Only pairs are recorded, and more users change edge weights rather than adding nodes → the graph’s size is set by the item count alone → so clustering becomes linear in items and independent of users, running 8.3 times faster than MERCI and 26.6 times faster on the largest mixtures.
Nothing is split into sub-groups → every recorded co-occurrence stays visible to the clustering decision → so groups that MERCI loses across its sub-group boundaries are still found, which is why GRACE reduces traffic 40 percent against MERCI’s 37.
Exact group frequencies would need an exponential number of counts, but pair counts bound them → candidates can be ranked by an interpolated bound instead of a measurement → so arbitrary-length groups become searchable at production scale.
A request finishes only when both memories finish, and clusters consume scarce fast memory → capping cluster growth leaves room for ordinary vectors → producing a near-even split of time between the two memories rather than a slow-memory bottleneck.
All subsets of a cluster are stored in subset-bit-pattern order → an address is computed by arithmetic on the item index rather than looked up in a table → so address generation costs 6 percent of reduction time and hides entirely behind the previous batch.

What it costs (trade-offs and scope)

A cluster of k items costs 2 to the power k, minus 1, minus k extra lines. Five items already need 26 extra lines for 5 vectors. This exponential is why a maximum cluster size exists at all, and in practice the best average cluster size is around 8 or below.
The ranking is an estimate, not a measurement. Bounds from pair counts cannot distinguish a group that always appears together from one whose pairs merely overlap, and the midpoint interpolation is an empirical choice. Nothing guarantees the greedy choice is optimal.
On a single uniform memory the advantage nearly disappears. Tested on homogeneous graphics-processor memory, GRACE beats MERCI by only 5 percent, because with no fast and slow split to balance, performance tracks traffic reduction alone and the two are close. Most of the headline win comes from balance, not from better groups.
It is profile-guided, so it assumes behaviour is stable. The system profiles a period, builds the cache offline, and serves subsequent periods. If tastes shift faster than the rebuild cycle the groups go stale — mitigated by clustering being cheap enough to repeat hourly, but not eliminated.
The benefit depends on the data having dense co-occurrence. Gains correlate with average graph degree, and the datasets that win most have degrees in the hundreds or thousands. The main results also assume extra capacity equal to one full copy of the embedding table.

The evaluation

GRACE was measured on eight real datasets from web service vendors, ranging from Steam with 10,978 items to Amazon Clothes with 2,345,346, plus four mixtures modelling a system with several tables at once. The machine was an 80-core Intel Xeon Platinum 8380 with 512GB of DDR4-3200 memory and an NVIDIA A40 with 48GB. Every scheme was given extra capacity equal to one full copy of the embedding table, and each competitor’s parameters were swept to report its best result. All numbers are normalised to a baseline that pretends fast memory is unlimited.

Making a recommendation embedding layer faster

Property	Place hot vectors in fast memory (FAE)	Pre-add popular pairs (SPACE)	Cluster on a pair-count graph (GRACE)
Memory traffic cut
Largest group stored
Cost of the analysis
Balances the two memories
Embedding layer throughput

GRACE closes 52.1 percent of the gap between prior work and an oracle allowed any pair sum. Tail latency at the 95th percentile improves 1.54 times over SPACE and 1.41 over MERCI. End-to-end model throughput rises 1.6 times on an embedding-heavy model and 1.2 times on a computation-heavy one. Clustering runs 8.3 times faster than MERCI on average. Notably, an off-the-shelf graph clustering tool applied to the same graph scores 0.34, nearly three times SLOWER than the baseline.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The most important limit is one the authors report themselves. On a single uniform memory, with no fast and slow split to balance, GRACE beats MERCI by only 5 percent, because performance then tracks traffic reduction alone and 40 percent against 37 is a narrow margin. So the headline 1.4 times comes mostly from keeping both memories busy rather than from finding better groups — which makes the result a statement about heterogeneous systems specifically, not about grouping in general. The cluster cost is also exponential, since k items need 2 to the power k, minus 1, minus k extra lines, which is why a maximum size exists and why the useful average sits around 8. The ranking is explicitly an estimate: bounds from pair counts cannot separate a group that always appears together from one whose pairs merely overlap, the midpoint interpolation is an empirical choice, and the greedy search offers no optimality guarantee. The approach is profile-guided, so it assumes user behaviour is stable between rebuilds, and the main results assume spare capacity equal to a full extra copy of the embedding table — though a constrained sweep at half and a quarter of that still beats SPACE by 1.63 and 1.54 times. Gains also correlate with how densely items co-occur, so sparse datasets benefit less. Within that scope the lessons are strong: record the summary whose size is governed by your small dimension, bound what you cannot afford to measure, and check that your objective is the quantity you actually care about.

Background

Summarise into a fixed shape, bound what you cannot count, and check your objective

This paper sits in the site’s machine learning systems cluster and rhymes with several ideas covered elsewhere on this site. Most directly, it shares its central trick with the quantum optimization page that also builds a graph and attacks its HIGHEST-DEGREE node first — there a hub is frozen to shrink a circuit, here a hub anchors a cluster, and both work because item popularity and real network connectivity follow the same power-law shape where a few nodes carry most of the weight. Its choice to record only pairs, so that adding users changes edge weights rather than graph size, is the same summarise-into-a-fixed-shape discipline the profiling and tracing pages show when a bounded structure replaces an unbounded log. Its cost model is a clean instance of bounding what you cannot afford to compute, since exact group frequencies need exponentially many counts while pair counts bracket them cheaply — the same tractability-first reasoning the static analysis pages use when they choose a conservative approximation on purpose. The failure it diagnoses in MERCI, where minimising traffic starves the fast memory and slows the machine down, is the measure-the-true-thing-not-a-proxy lesson the performance-measurement page makes its whole argument, and its finding that a general-purpose graph clustering tool scores 0.34 on this problem — three times slower than doing nothing — is the same re-derive-do-not-port conclusion the superconducting-logic and accelerator pages reach when a technique tuned for one objective is transplanted into another. It also pairs naturally with the embedding-table storage page, which attacks the same bottleneck from the caching side and hits a different hit-rate failure mode.

If you remember only three things

1. Recommendation models are limited by memory bandwidth, not arithmetic: for each user they fetch one feature vector per item that user touched and add them together, from tables reaching terabytes with scattered accesses that defeat caches. Demand grew thirty times in four years to two terabytes per second, and one operator reports these models consume over sixty percent of its artificial intelligence inference work. Pre-adding popular item groups would cut the traffic, but finding which groups are popular means counting every possible subset, which explodes combinatorially.
2. The move is to record strictly LESS: only how often each PAIR of items is requested together, as a graph where nodes are items and edge weights are co-occurrence counts. Adding users changes only edge weights, never the graph size, so clustering becomes linear in items and independent of users — 8.3 times faster than the prior best, which had to split items into sub-groups and lose every co-occurrence crossing a boundary. Since the graph cannot say how often three items co-occur, the value of a larger group is bracketed by a lower and an upper bound derived from pair counts and interpolated, replacing an exponential measurement with a cheap estimate.
3. The subtler contribution is choosing the right objective. The prior system minimised memory traffic, which sounds correct and reaches 37 percent against GRACE's 40, yet loses by 1.4 times on throughput — because a request finishes only when BOTH the fast and slow memory finish, and large clusters fill scarce fast memory with rarely used sums while evicting ordinary vectors to the slow side. GRACE deliberately builds smaller clusters to keep both busy. Honestly reported: on a single uniform memory that advantage shrinks to 5 percent, so most of the win is balance rather than better grouping.

Check yourself

Check your understanding

1. The graph records only how often each PAIR of items appears together. Predict why that limitation does not prevent the algorithm from evaluating larger groups.
2. MERCI reduces memory traffic by 37 percent and GRACE by 40 percent, yet GRACE is 1.4 times faster overall. Predict what explains a gap that large from a 3-point difference.
3. SPACE stores the sum of every pair drawn from a set of popular items, yet cuts memory traffic by only 9 percent. Predict why storing pairs of popular items works so poorly.
4. An off-the-shelf graph clustering tool was applied to the same co-occurrence graph and scored 0.34, meaning nearly three times SLOWER than doing nothing. Predict why a mature, well-regarded algorithm did so badly.

Sources

GRACE: A Scalable Graph-Based Approach to Accelerating Recommendation Model Inference (author PDF, University of Michigan) — ASPLOS 2023; the full paper, read in full for this explainer.
ACM Digital Library (DOI 10.1145/3582016.3582029) — published version.
GRACE source code — the authors’ open-source release.