MP-Rec: Hardware-Software Co-design to Enable Multi-path Recommendation

Samuel Hsia, Udit Gupta, Bilge Acun, Newsha Ardalani, Pan Zhong, Gu-Yeon Wei and 2 others

Everyone treats a recommendation model's embedding table as a fixed thing and optimises around it — MP-Rec keeps several different ways of producing the same embedding, on several different accelerators, and picks per query based on how big it is and how fast the answer is due.

The argument in one glance

Problem

Recommendation models are mostly lookup table

A model that personalises content has to turn a user identifier or a clicked item into a vector, and it does that by indexing a table with one row per possible value. Those tables have grown super-linearly into the terabytes, so memory capacity and bandwidth dominate the system design.
What people did

Attack the memory problem from every direction

A large body of work compresses tables, shards them, caches them, or builds custom memory and storage hardware to fetch from them faster. All of it takes the table for granted as the way embeddings are represented.
Why it fell short

You can generate embeddings instead, but the bill moves rather than shrinking

A compute stack can produce an embedding from an identifier by hashing and then running a small network, which shrinks memory by orders of magnitude and raises arithmetic by orders of magnitude. Deployed statically it misses latency targets on every query.
This paper's idea

Keep several representations alive and choose per query

Build a hybrid that uses both a table and a compute stack and is more accurate than either. Map each representation to whichever accelerator suits it. Then at runtime pick the most accurate path that will still finish in time, given how large this particular query is.

Why this problem is worth solving

Deep learning recommendation is one of the largest consumers of machine learning capacity in production, and structurally it is a memory problem wearing a neural network costume. The model’s job is to turn categorical facts — which items a person clicked, what they searched for — into vectors it can compute with, and it does that through an

An embedding table is a lookup table with one row per possible value of a categorical feature, mapping that value to a vector of numbers; because there is a row for every possible item or user, these tables reach terabytes.

. Those tables have grown super-linearly, so a decade of systems work has gone into compressing them, sharding them, caching them and building memory and storage hardware to reach them faster.

Serving them has its own constraint: every request carries a

A latency target, or service level agreement, is the maximum time a system is allowed to take to answer a request — and it applies to the slow tail of requests, not the average, so a system is judged by how often it misses rather than by how fast it usually is.

measured in milliseconds, so a slower but better answer is only better if it still arrives on time. Every one of those efforts holds the representation constant. The paper’s argument is that this is an unexamined assumption rather than a necessity — embeddings can also be generated on demand by hashing an identifier and running the result through a small network, which trades memory capacity for arithmetic at a rate of several orders of magnitude in both directions. That sounds like a straight swap of one bottleneck for another, and deployed naively it is worse than that: the generated representation misses its latency targets so comprehensively that every query violates them. But the trade has structure worth exploiting, because the two representations stress different hardware resources and are best served by different accelerators, and because whether a query can afford the expensive path depends on how big that query happens to be.

What people did before, and where it broke

Compress the table. Matrix factorisation, weight sharing and related techniques shrink the footprint. Effective, and still a table.
Shard and cache the table. A substantial literature places table partitions across machines or exploits access frequency to keep hot rows close. Also effective, also assuming a table.
Build hardware to reach the table faster. Custom memory-level and storage-level accelerators aimed at embedding access time. Same assumption again.
Generate embeddings from a compute stack instead. Hash the identifier several ways, normalise, and run a small network to produce the vector. Memory shrinks enormously; arithmetic rises by a factor of ten to a hundred, and static deployment at a realistic query rate violates the latency target on every single query.
Split operators across heterogeneous hardware. Prior work shows that partitioning a fixed model’s operators across CPU and accelerator beats CPU-only execution. Real gains, but the model stays fixed, so there is no accuracy to be had from the exercise.
Choose the right server architecture for the workload. Other work matches heterogeneous server configurations to recommendation workloads including their daily traffic cycles. Complementary, and again at the level of placing a given model.
The gap. Everything optimises around the representation. Nobody had treated which representation to use as a runtime decision, or noticed that the choice interacts with which accelerator is available and with how large the incoming query is.

How MP-Rec builds and chooses among paths

From one fixed representation to several selectable ones

↓ →
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The third and fourth stages create options; the last two make them usable.

The idea

Make the representation a variable, not a constant. The framing move is to notice that an entire research literature has been optimising around a data structure that was never mandatory. Once storing and generating embeddings are both on the table, a third option appears that nobody had built: feed the identifier to a table and a compute stack, concatenate the two results, and train them jointly. The paper reports that this hybrid is the most accurate of all the representations examined, and gives two reasons — the two mechanisms have different learning capacities, so they capture different things, and they stress independent hardware resources, so a system can use both its memory and its compute rather than saturating one and idling the other. The gain is small in absolute terms, 0.19% and 0.22% on the two public datasets, which is the currency recommendation trades in. Turning something the field had treated as a fixed architectural given into a parameter that can be selected, and then discovering the interesting configurations live between the extremes, is the same reframing performed when a fixed dataflow choice is turned into a tunable dial, covered elsewhere on this site.

No accelerator wins at everything, so stop asking which one to buy. The characterisation is done on real hardware — processors, graphics processors, Google tensor processors and Graphcore graph processors, at core, chip, board and pod scale — and the answer is that each is best at something different. Tensor processors excel at tables, helped by dedicated embedding layers that shard large tables and replicate small ones. Graph processors excel at the compact compute stacks, since those fit in their on-chip memory. Graphics processors are the energy-efficient option for large-capacity models, partly because the tensor processor’s scratchpad cannot hold the tables and ends up going off-chip repeatedly. Matching a representation to a compatible accelerator is worth up to 16.65 times, and no single platform is optimal across all objectives — which is precisely why a static choice is the wrong shape of answer. Heterogeneous hardware without a dominance ordering, where the right placement depends on the individual item rather than on a ranking of the machines, is the same structure that makes processor selection a genuine per-function decision in serverless scheduling, covered elsewhere on this site.

Caching works differently when the data is computed rather than stored. The generated representation is far too slow to use most of the time, and the design’s most interesting piece is what makes it usable sometimes. The cache has two tiers exploiting two different redundancies. The first exploits access frequency: identifier popularity follows a power law, so caching the intermediate values of hot identifiers lets the entire encoder stage be skipped. The second exploits value similarity, which only exists because the representation is computed — profile the intermediate values a workload produces, build a set of centroids describing their distribution, and replace the decoder network with a nearest-neighbour search against those centroids. Since the vectors are normalised, that search reduces to parallel dot products, and the number of centroids is a dial trading approximation quality against compute. Exploiting the strong skew in embedding access to serve most requests from a much smaller structure is the same observation behind caching designs for embedding storage, covered elsewhere on this site, but the second tier has no analogue there because a stored table has no intermediate values to be similar.

Following a query through the system

One inference request arrives at a serving node

A recommendation query with a service level target of ten milliseconds, on a machine with both a processor and a graphics processor, each holding several representations.

Step 1 of 5

The paths were built before any query arrived

Offline, each representation is mapped onto the platforms whose memory budget can hold it, producing a set of accuracy-ranked execution paths.

This is why the memory footprint roughly doubles: several representations are resident on each platform at once. The offline stage maximises memory capacity utilisation rather than minimising footprint.

Why it works

The two representations are complementary rather than competing. A table and a compute stack have different learning capacities and stress different hardware → concatenating them raises accuracy above either alone → and lets one machine use both its memory bandwidth and its arithmetic units.
Query size decides what is affordable, and query size varies. A lognormal distribution of sizes means many queries have latency headroom → the expensive accurate path can run on those → so the average accuracy rises without the tail latency target being missed.
Static deployment of the accurate path is catastrophic; dynamic deployment is not. Statically serving the generated representation at the tested rate violates the deadline on every query → activating it selectively converts a total failure into a net gain → which is why the same representation appears as both the problem and the solution.
Access frequency follows a power law. A small set of identifiers accounts for a large share of lookups → caching their intermediate values skips the encoder entirely for those → closing much of the gap between generation and table lookup.
Computed values cluster, and stored values do not. Intermediate results from the encoder concentrate in a describable distribution → a centroid search replaces the decoder network → a redundancy that exists only because the representation is generated rather than looked up.

What it costs (trade-offs and scope)

Memory footprint roughly doubles. Keeping several representations resident on each platform is the price of being able to choose between them, and the paper reports the increase directly rather than downplaying it. On a system where memory capacity is the original problem, that is a real objection.
The production result is an order of magnitude smaller than the public one. On the public datasets the hybrid representation improves accuracy by 0.19% and 0.22%. In the internal production setting the improvement is 0.014%. The authors report both.
The largest speedup number is potential, not measured. Integrating graph processors is said to offer 34.24 times throughput improvement that could be unlocked with future software support. It is a projection, and clearly labelled as one.
The 16.65-fold figure is about matching, not about the system. It measures what compatible representation-hardware pairing is worth on real accelerators, not what MP-Rec delivers end to end, which is 2.49 and 3.76 times.
Accelerator deployment has friction the numbers do not show. Changing input shapes on the graph processor requires recompilation taking around thirty minutes, which sits awkwardly with a design premised on query sizes varying continuously.
The headline metric is defined by the authors. Throughput of correct predictions bundles speed and accuracy into one number. It is a reasonable thing to optimise for a recommender, and it is not directly comparable to work reporting either quantity alone.
The decoder cache is an approximation. Replacing the decoder network with a nearest-centroid match trades accuracy for speed on top of everything else, tuned by how many centroids are kept.

The evaluation

Property	Metric	Table on processors (baseline)	MP-Rec
Throughput of correct predictions	baseline
Model accuracy	baseline
Latency target violations at 10 milliseconds
Value of matching representation to accelerator	a single fixed pairing
Memory footprint	one representation per platform

Evaluated on the open MLPerf recommendation model with the Kaggle and Terabyte datasets, on real hardware including tensor and graph processors.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The accuracy improvements are small numbers that mean more than they look — a fifth of a percent is commercially meaningful in recommendation — but the gap between the public and production results deserves attention. On Kaggle and Terabyte the hybrid representation gains 0.19% and 0.22%; in the authors’ internal production setting it gains 0.014%, more than an order of magnitude less. They report this rather than omitting it, which is to their credit, and it suggests the headroom depends heavily on how well-tuned the baseline model already is. Two of the more striking numbers also need reading carefully. The 16.65-fold figure measures what pairing a representation with a compatible accelerator is worth, not what the system delivers; end to end the result is 2.49 and 3.76 times. And the 34.24-fold graph processor figure is explicitly a potential contingent on software support that does not yet exist. Finally, the price of having options is holding them: memory footprint roughly doubles because several representations sit resident on every platform, which is an awkward cost on a workload whose defining problem is memory capacity.

Background

Where this sits

Recommendation systems have been the quiet giant of production machine learning for years, consuming a large share of inference capacity while attracting less attention than language models. The systems literature around them has concentrated almost entirely on the embedding table as an object to be stored, moved and fetched efficiently, which is reasonable given that the tables are where the terabytes are. What this paper contributes is less a mechanism than a widening of the design space: once you accept that an embedding can be computed rather than retrieved, the question stops being how to serve a table quickly and becomes which of several ways to produce an embedding suits this query, this deadline and this hardware. That framing brings the workload into contact with a broader theme in heterogeneous systems, where the right answer is rarely a single configuration and usually a policy for selecting among several. The wider body of work on embedding storage, sharding and accelerator design for recommendation is covered elsewhere on this site.

If you remember only three things

1. A recommendation model can either store embeddings in terabyte-scale tables or generate them from a compute stack at ten to a hundred times the arithmetic — and a hybrid that does both is more accurate than either, because the two have different learning capacities and stress independent hardware.
2. No accelerator is best at everything: tensor processors suit tables, graph processors suit compact compute stacks, graphics processors suit large-capacity models efficiently, and matching them well is worth up to 16.65 times.
3. Because query sizes vary, the expensive accurate path is affordable on some queries and not others, so choosing per query converts a representation that violates the deadline 100% of the time into a 2.49 to 3.76 times gain in throughput of correct predictions.

Check yourself

Check your understanding

1. What does generating embeddings from a compute stack change about the resource bill?
2. Why is the hybrid representation more accurate than either component alone?
3. What makes the two tiers of the cache different from each other?
4. Why does choosing the representation per query work when choosing it once does not?

Sources

The paper is “MP-Rec: Hardware-Software Co-design to Enable Multi-path Recommendation” by Samuel Hsia, Udit Gupta, Bilge Acun, Newsha Ardalani, Pan Zhong, Gu-Yeon Wei, David Brooks and Carole-Jean Wu, published at ASPLOS 2023 Volume 3, pages 449-465, DOI 10.1145/3582016.3582068. The authors are at Meta AI and Harvard University.

This explainer is written from the full text, read via the arXiv version at arxiv.org/abs/2302.10872. All figures above come from the paper’s own sections 2 through 6: the description of table-based, generated and hybrid representations and the ten to hundredfold increase in arithmetic for the compute-based ones, the accuracy improvements of 0.19% and 0.22% on Kaggle and Terabyte against 0.014% in the internal production setting, the 16.65 times speedup from matching representations to compatible accelerators and the finding that tensor processors suit tables while graph processors suit compact compute stacks and graphics processors are most energy-efficient for large-capacity models, the throughput of correct predictions improvements of 2.49 and 3.76 times, the reduction in latency target violations from 30.73% to 3.14% at a ten millisecond target with static deployment of the compute-based representations violating on all queries, the two-tier cache exploiting access frequency and value similarity, and the roughly doubled memory footprint from holding multiple representations resident. The 34.24 times figure for graph processor integration is described in the paper as potential contingent on future software support, and the approximately thirty minute recompilation on input shape change is noted in section 6.