Practical Federated Recommendation Model Learning Using ORAM with Controlled Privacy

Recommendation models learn from sensitive user data, and federated learning is meant to train them without collecting that data — but these models carry enormous lookup tables no phone can download whole, so users must fetch only the few table entries their data touches, which itself reveals what that data is; this paper (Penn State, Virginia Tech, Cornell, NVIDIA) builds FEDORA, which hides which entries a user touches using oblivious memory, makes that normally-crippling technique affordable with a tunable privacy knob grounded in differential privacy and by hosting the huge oblivious store on a cheap SSD without wearing it out, cutting latency about fivefold and extending the SSD's life over a hundredfold.

The argument in one glance

Problem

Private recommendation training needs data no phone can hold, and touching part of it leaks the rest

Recommendation models — for music, video, news, products — are trained on sensitive user features like demographics and behavior, which raises privacy concerns and increasingly runs into regulation, even though that sensitive data is exactly what makes the models good. Federated learning is the popular way to train a model without collecting raw data: each user trains locally on their own data and uploads only model updates. But it does not work for recommendation models, because these models carry huge embedding tables — the lookup tables that convert a sparse feature, like "recently bought item X", into a dense vector — and the tables are far too big for a phone to download and train in full. The obvious fix is to have each user download only the handful of table entries their own data touches. But that leaks the very features it was meant to protect: which entries you fetch reveals what your data is. So the private-training method is blocked by the model's size, and the natural workaround around the size reintroduces the leak.
What people did

Hide which entries a user touches with oblivious memory

The standard cryptographic defense is oblivious RAM (ORAM): a primitive that randomizes and encrypts memory accesses so that, to an observer, every access looks the same regardless of which entry was really wanted. Wrap the embedding table in ORAM and the pattern of entries a user downloads no longer reveals their features.
Why it fell short

ORAM at embedding-table scale is unaffordably slow and heavy

ORAM buys that privacy at a brutal price. To hide one real access, a scheme like Path ORAM reads and rewrites an entire path through a large tree, so every logical lookup becomes many physical ones, and it inflates the stored data by several times because it needs spare room to shuffle blocks around. At the scale of recommendation embedding tables — which are already enormous — this latency and memory overhead is prohibitive, and it must be paid on every access. Vanilla ORAM gives perfect access-pattern privacy but is unusable; the naive speedups people apply to ORAM throw the privacy away entirely. There was no way to get the protection at a cost a real federated system could bear.
This paper's idea

A tunable privacy dial, and a cheap oblivious store that survives

FEDORA makes ORAM-based federated recommendation training practical with three moves. It defines feature-level differential privacy, a formal privacy notion tailored to hiding a user's feature values, with a knob (epsilon) that trades a small, precisely-quantified amount of privacy for large ORAM speedups — with vanilla ORAM and the reckless optimization as its two extremes. It hosts the huge ORAM on a cheap, power-efficient SSD rather than costly memory, with optimizations that keep the SSD from being worn out by ORAM's constant rewrites. And it is designed to fit modern federated-learning workflows. Together these keep the model accurate while cutting latency about fivefold and extending SSD lifetime over a hundredfold.

Why this problem is worth solving

The mechanism at the center is one that turns even a “private” training method into a leak.

Even when the contents of memory are encrypted, the pattern of which addresses a program accesses can reveal secrets — here, which embedding-table entry a user downloads betrays which feature (say, which item they bought) they have. Oblivious RAM, or ORAM, is the cryptographic primitive that closes this channel: it makes the sequence of physical memory accesses statistically independent of the logical accesses actually requested, so an observer learns nothing about what was really wanted. The dominant family, Path ORAM, stores data as blocks in a binary tree; a small on-chip position map records which path each block currently lives on, and a small on-chip buffer called the stash holds blocks in transit. To read one block, the controller looks up its path, reads and decrypts that entire path into the stash, serves the block, reassigns the block to a fresh random path, and writes the path back — so every access looks like reading and rewriting a random path, no matter which block was wanted. The privacy is airtight, but the cost is that a single logical access becomes a whole path of physical reads and writes, plus several times the storage to leave room for shuffling, which is what makes ORAM so expensive to deploy at scale.

The right way to make that cost negotiable is to borrow the language of a well-studied privacy framework.

Differential privacy is the standard framework for quantifying how much an algorithm’s output leaks about any single secret in its input. An algorithm is epsilon-differentially-private if, for two inputs that differ in one protected element, the probability of any given output changes by at most a factor governed by epsilon: a small epsilon means the two inputs produce nearly identical output distributions, so an adversary can barely tell them apart (strong privacy), while a larger epsilon permits more leakage in exchange for less noise or overhead. What counts as the protected element — the definition of neighboring inputs — is chosen per application: hiding one training sample, or one whole user, gives different guarantees. FEDORA defines its own notion, feature-level differential privacy, where the protected element is a single feature value of a user, a middle ground between hiding a sample (too weak, since a user’s samples share features) and hiding a whole user (too strong). Framing the privacy this way turns an all-or-nothing choice into a dial: epsilon at most 10 is generally considered reasonably safe and at most 1 strongly safe, and tuning epsilon lets the system trade a bounded, interpretable amount of privacy for performance.

What people did before, and where it broke

Collect the sensitive data centrally and train. Have the service provider gather user features and train the recommendation model directly. Where it broke. This is what raises the privacy concern and increasingly violates regulation; users are unwilling to share, and losing the data degrades model quality, which is the tension the whole line of work exists to resolve.
Federated learning as usual. Train without collecting raw data by having users train locally and upload updates. Where it broke. Recommendation models’ embedding tables are far too large for a user’s device to download and train in full, so plain federated learning simply cannot be applied to them.
Download only the relevant table entries. Let each user fetch and train just the embedding rows their data touches, shrinking what the device handles. Where it broke. The set of entries a user downloads reveals their private features, so this reintroduces exactly the leak federated learning was meant to prevent.
Wrap the table in vanilla ORAM. Hide the access pattern with a standard oblivious-memory scheme, or speed ORAM up with the usual heuristics. Where it broke. Vanilla ORAM gives perfect access-pattern privacy but is prohibitively slow and memory-hungry at embedding-table scale, while the common heuristic optimizations that make ORAM fast quietly destroy the privacy guarantee entirely.
The gap. No system offered access-pattern privacy for federated recommendation training at a cost a real deployment could afford, with the privacy loss formally bounded rather than heuristically hoped for, and no one had made a large oblivious store cheap to host without either paying for vast memory or wearing out the hardware. That combination is what FEDORA assembles.

How FEDORA works

Private subset training over a tunable, SSD-hosted oblivious store

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

The idea

Hide the access pattern, because in federated recommendation the pattern is the secret. The subtle leak here is not in the data a user uploads but in which embedding rows they ask for: fetch the row for a particular purchased item and you have announced that purchase. FEDORA’s foundation is to route embedding-table access through oblivious memory so the sequence of physical accesses is independent of which rows a user truly needs, closing that channel. This is the same access-pattern threat that arises whenever encrypted data is touched in a data-dependent way, and defending it by making the observable accesses reveal nothing about the underlying request is the same obliviousness discipline the memory-timing side-channel work covered elsewhere on this site is built on, severing the link between what a computation secretly wants and what an observer can see it do.

Turn perfect-but-unusable privacy into a formally-bounded dial. The reason ORAM had not been usable here is that it is offered as all or nothing: full obliviousness at a crippling cost, or fast heuristics with no guarantee at all. FEDORA’s conceptual contribution is to make the privacy continuous and principled by casting the relaxation as feature-level differential privacy. Vanilla ORAM sits at one end (epsilon zero, perfect), the reckless optimization at the other (unbounded leakage), and every point in between is a design that leaks a precisely quantified, interpretable amount in exchange for real speed — with the well-studied differential-privacy machinery giving meaning to that amount and even bounding an adversary’s success. Existing ad-hoc ORAM speedups turn out to be special cases of this general framework. Expressing a system’s privacy loss in the rigorous, tunable vocabulary of differential privacy so that performance can be traded for a measured, defensible reduction in protection is the same quantified-privacy approach the private-inference-systems work covered elsewhere on this site relies on, replacing a binary secure-or-not stance with a knob whose settings carry a formal guarantee.

Put the oblivious store on cheap flash, and stop it from destroying the drive. An oblivious store big enough for recommendation embedding tables would be ruinously expensive in memory, so FEDORA hosts it on a commodity SSD, which is far cheaper per byte and power-efficient. The catch is that ORAM writes on every single access — it rewrites a whole path each time — and SSDs wear out after a limited number of writes, so a naive ORAM would burn through a drive’s endurance almost immediately. FEDORA adds SSD-friendly optimizations that sharply reduce the write traffic, keeping latency reasonable and extending the drive’s usable lifetime by orders of magnitude. Designing an access scheme around the write-endurance and performance realities of flash, rather than treating the SSD as an idealized fast disk, is the same flash-aware discipline the learned flash-translation-layer work covered elsewhere on this site is built on, shaping how data is written so the SSD survives the workload instead of being ground down by it.

Following a user’s update through FEDORA

One user's private contribution to the federated model

A trace, from the paper, of how a user trains on the embedding rows their data needs without revealing which rows, and at a cost the system can afford.

Step 1 of 5

The user needs a few specific embedding rows

A user's local data references a handful of sparse features, so training their part of the recommendation model requires only the corresponding embedding-table rows — a tiny subset of the enormous table. Downloading those rows directly, though, would reveal exactly which features the user has.

The whole table is far too large for the device; the subset is what makes on-device training feasible at all.

Why it works

Obliviousness removes the leak subset-downloading creates. Fetching only the relevant embedding rows exposes a user’s features through the access pattern → but routing those accesses through ORAM makes the physical pattern independent of the requested rows → so users get the practicality of subset training without revealing what their data is.
A differential-privacy framing makes the cost negotiable. ORAM was offered as perfect-but-unusable or fast-but-unprotected → but casting the relaxation as feature-level differential privacy turns it into a tunable epsilon with a formal, interpretable guarantee → so a small, bounded privacy loss buys large ORAM speedups instead of an all-or-nothing choice.
The framework unifies and bounds prior hacks. Ad-hoc ORAM optimizations promised speed with unclear privacy → but they emerge as special cases of feature-level differential privacy → so their leakage becomes quantifiable and the whole design space is spanned by one knob.
Cheap flash makes a huge oblivious store affordable. Holding an embedding-scale ORAM in memory would be prohibitively costly → but a commodity SSD is far cheaper and power-efficient per byte → so the large store becomes economically deployable, provided the flash survives.
Write-aware design keeps the SSD alive. ORAM rewrites a whole path on every access, which would exhaust an SSD’s write endurance almost at once → but SSD-friendly optimizations cut that write traffic → so the drive keeps reasonable latency and lasts far longer, reported as up to a thousandfold-plus lifetime improvement over other SSD-based ORAM.

What it costs (trade-offs and scope)

Privacy is deliberately relaxed, by a chosen amount. FEDORA’s speed comes from setting epsilon above zero, so it is not perfectly oblivious; it leaks a bounded, quantified amount of information about a user’s features. The paper argues this is interpretable and small at safe epsilon regimes, but it is a real, tunable reduction in protection, and choosing epsilon is a policy decision with a genuine privacy cost.
The guarantee is feature-level, and its meaning depends on the definition. Feature-level differential privacy hides individual feature values, a deliberate middle ground; it is weaker than hiding an entire user and stronger than hiding a single sample. Extending it to hide multiple correlated values or the number of features costs proportionally more noise, so protecting richer secrets tightens the budget.
It assumes a trusted execution environment. The prototype relies on a trusted execution environment holding a small on-chip scratchpad for the ORAM’s stash and position map; the security rests on that trusted component behaving correctly, and the approach inherits whatever assumptions and attack surface the trusted-hardware base carries.
SSD hosting trades latency and endurance for cost. Putting the ORAM on flash is what makes a huge store affordable, but even with the optimizations an SSD is slower than memory and has finite endurance; the gains are relative to other SSD-based ORAM and a baseline, and the absolute latency and lifetime still reflect that the store lives on flash.
It targets federated recommendation training specifically. The design and its guarantees are built around the access-pattern leakage of embedding-table subset training under federated learning, and it composes with, rather than replaces, gradient-level protections like secure aggregation and differential privacy; the techniques are tuned to this setting rather than being a general oblivious-computation system.

The evaluation

Making private federated recommendation training feasible

Property	Plain federated learning	Vanilla ORAM
Handles large embedding tables
Access-pattern privacy
Privacy is formally quantified	No
Where the store lives	n/a
Reported improvement over baseline	n/a	Baseline (too costly)

From the paper's evaluation. FEDORA makes ORAM-based federated recommendation training practical, keeping model accuracy high by safely using private features while, on average, improving latency about 5 times and SSD lifetime about 158 times over the baseline, and up to 24 times latency and over 1000 times lifetime over other SSD-based ORAM designs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is making a known-strong but known-unusable defense practical for a real workload. Federated recommendation training needs private features but cannot download whole embedding tables; downloading subsets leaks features; and oblivious memory, the standard fix, is far too costly at this scale. FEDORA’s answer is threefold: formalize the privacy as feature-level differential privacy so the obliviousness becomes a tunable epsilon that trades a bounded, interpretable amount of leakage for speed (with vanilla ORAM and the reckless optimization as its extremes, and prior hacks as special cases); host the huge oblivious store on a cheap SSD with optimizations that keep its writes from destroying the drive; and fit modern federated workflows, composing with secure aggregation and gradient differential privacy. The reported gains are strong — accurate models, about fivefold lower latency and over a hundredfold longer SSD life than the baseline, and far more against other SSD-based ORAM. Read that with its trade-offs: the privacy is deliberately relaxed by a chosen epsilon rather than perfect, the guarantee is specifically feature-level, the system assumes a trusted execution environment, and hosting on flash trades absolute latency and endurance for affordability. Within that scope, FEDORA turns private federated recommendation training from a theoretical impossibility into an engineered, tunable system.

Background

Why recommendation models are the hard case for privacy

It helps to see why recommendation models, of all machine-learning systems, are where private training gets so difficult. Most models are dense: their parameters are used for every input, so federated learning can ship the whole model to a device and train it locally. Recommendation models are different because they are dominated by embedding tables — vast lookup structures with a row for every possible item, user, or category, most of which any single user never touches. These tables can run to enormous sizes, dwarfing the rest of the model, which is why serving and storing them is its own systems challenge and why they cannot simply be handed to a phone. That sparsity is a blessing and a curse: it means a user only needs a few rows, making subset training conceivable, but it also means the identity of those rows is a fingerprint of the user’s private features. The very structure that makes these models scalable is what makes them leaky. That world, where the sheer size and sparsity of embedding tables is the central obstacle to building and running recommendation systems, is the same one the embedding-table storage-and-caching work covered elsewhere on this site inhabits, wrestling with how to hold and serve tables too large for conventional memory. FEDORA adds the privacy dimension: not just how to store these tables, but how to let users train on them without the access itself giving them away.

If you remember only three things

1. Recommendation models need sensitive user features for quality, and federated learning is meant to train them without collecting raw data, but it fails for these models because their embedding tables are too large for a device to download whole; downloading only the relevant rows leaks the user's features (which rows they touch reveals their data), and the standard defense of hiding access patterns with oblivious memory (ORAM) is prohibitively slow and memory-heavy at embedding-table scale — perfect obliviousness is unusable, and the usual ORAM speedups discard the privacy.
2. FEDORA makes it practical with three ideas: feature-level differential privacy (epsilon-FDP), a formal notion of hiding a user's individual feature values that turns obliviousness into a tunable knob — vanilla ORAM is the perfect epsilon-zero extreme, the reckless optimization the no-privacy extreme, and prior heuristic ORAM optimizations are special cases — so a small, quantified privacy loss buys large speedups; hosting the huge ORAM on a cheap, power-efficient SSD with SSD-friendly optimizations that curb the per-access writes that would otherwise exhaust the drive's endurance; and a design that supports modern federated-learning modes and composes with secure aggregation and gradient differential privacy, all assuming a trusted execution environment with a small on-chip scratchpad.
3. By safely using private features, FEDORA keeps model accuracy high while, on average, improving latency about 5 times and SSD lifetime about 158 times over the baseline, and up to 24 times latency and over 1000 times SSD lifetime over other SSD-based ORAM designs; the trade-offs are that privacy is deliberately relaxed by a chosen epsilon rather than perfect, the guarantee is specifically feature-level, it relies on a trusted execution environment, and flash hosting trades absolute latency and endurance for cost.

Check yourself

Check your understanding

1. Why can plain federated learning not train recommendation models, and why does the obvious fix leak privacy?
2. What is oblivious RAM (ORAM), and why is it so expensive at embedding-table scale?
3. What is feature-level differential privacy (epsilon-FDP) and how does it help?
4. What did FEDORA achieve, and what are its trade-offs?

Sources

The paper is “FEDORA: Practical Federated Recommendation Model Learning Using ORAM with Controlled Privacy” by Jinyu Liu (Pennsylvania State University), Wenjie Xiong (Virginia Tech), G. Edward Suh (NVIDIA and Cornell University), and Kiwan Maeng (Pennsylvania State University), published at ASPLOS 2025 (Volume 2), DOI 10.1145/3676641.3716014.

This explainer is written from the full text of the authors’ copy of the paper. Everything above comes from the paper’s own sections: the introduction motivating private recommendation training (sensitive user features are crucial for model quality but raise privacy and regulatory concerns), why federated learning is impractical for these models (their embedding tables are too large for user devices to download and train in full), and why downloading only relevant entries leaks features; the adoption of oblivious RAM to hide the access pattern and the challenge of its latency and memory overheads; the background on Path ORAM (blocks in a binary tree, the position map and stash held on-chip, and the read-decrypt-serve-reassign-writeback path operation that makes every access look like reading and rewriting a random path, with several-times storage inflation) and on federated learning with secure aggregation and differential privacy, which FEDORA composes with; the definition of feature-level differential privacy (epsilon-FDP) as a variant of epsilon-differential privacy where neighboring inputs differ in one user feature value, its interpretation and the safe epsilon regimes (at most 10 reasonably safe, at most 1 strongly safe), and its extension via group privacy to hide multiple values or the number of features; the demonstration that vanilla ORAM achieves epsilon-FDP with epsilon zero but is prohibitively slow while naive optimizations give unbounded leakage, and that heuristic ORAM optimizations are special cases of the epsilon-FDP design; the system design hosting the large ORAM on a power- and cost-efficient SSD with SSD-friendly optimizations to reduce writes and extend endurance, implemented in software assuming a trusted execution environment with a small (4 KB) on-chip scratchpad; and the evaluation reporting high model accuracy from using private features together with, on average, about 5 times latency and 158 times SSD lifetime improvement over the baseline and up to 1.8-to-24 times latency and 21-to-1000-plus times SSD lifetime improvement over other SSD-based ORAM designs.