Recommendation models turn categorical inputs such as user and item IDs into vectors by looking them up in embedding tables. These tables are so large that they cannot live on a phone. Recent work shows they can be queried privately: the client sends its feature IDs under homomorphic encryption (a way of computing on encrypted numbers without decrypting them), and the server looks them up in compressed tables without ever seeing which IDs were requested. What no one can yet do is let the model learn from a data owner's private interactions under the same encryption. The usual tool for learning, gradient descent with a tuned learning rate, is blind in the encrypted setting. Nobody can watch a validation loss, so a bad step size diverges silently. Highly compressed embedding tables are also known to be the slowest and most tuning-sensitive models to train.
We propose to sidestep both problems by changing what is learned. We would freeze a public, compressed base model and learn small additive correction tables, one scalar per row of each compressed sub-table. These are fitted by a closed-form block Newton update that needs no learning rate. Compression is what makes this possible. When an ID is split into a few base-$p$ digits, each training example touches exactly one row of each digit table. The statistics needed for the update are then plain encrypted sums, and the only nonlinear operation left is a reciprocal over a numeric range known in advance. Compression is usually discussed as a memory saving. Here it also shrinks the encrypted learning problem from millions of independent parameters to a few hundred well-populated ones, small enough to solve exactly and blindly.
Core Claim
Take a model whose categorical features are stored as base-$p$ digit tables, as in client-side digit decomposition. Let a data owner hold labeled interactions that are shifted relative to the public training data. We claim that the owner's per-entity behavior can be absorbed into encrypted per-digit-row logit corrections. These corrections would be computed by a fixed, tuning-free sequence of homomorphic additions, one ciphertext multiplication per sample, and one bounded-range reciprocal. The resulting accuracy should be close to what plaintext fine-tuning of the same corrections with an oracle-tuned learning rate achieves. It should also be clearly better than both no adaptation and a single global recalibration.
For digit table $j$ and digit value $v$, the correction is one Newton step on the logistic loss restricted to that row:
$$ b_{j,v} \;=\; \frac{\sum_{i:\,d_j(i)=v} \big(y_i - \pi_i\big)}{\sum_{i:\,d_j(i)=v} \pi_i(1-\pi_i) \;+\; \lambda}. $$
Here $d_j(i)$ is the $j$-th digit of example $i$'s ID, $y_i \in \{0,1\}$ is its label, and $\pi_i$ is the predicted click probability. That probability comes from the base model's logit plus the corrections from the other digit tables. The term $\lambda$ is a ridge prior strength. The numerator and denominator are both sums over the examples that hit the row. Under encryption, each is the encrypted one-hot digit vector multiplied by an encrypted per-sample scalar and accumulated across the batch using packed ciphertext slots.
The division is the only non-polynomial step. Its input lies in $[\lambda,\; n/4 + \lambda]$, where $n$ is the private dataset size, because $\pi(1-\pi) \le 1/4$. A fixed-iteration inverse approximation (Goldschmidt or Newton) therefore reaches a target precision in a number of steps determined by that interval alone. The step count is set by the interval, not tuned. Cross-digit coupling is handled by $K$ rounds of backfitting: recompute $\pi_i$ with the other tables' corrections, then update each table again. We expect $K = 2$ or $3$ to suffice, because the base model already explains most of the signal.
How This Differs From Prior Work
Two systems supply the encrypted lookup we build on, and both stop at inference. HE-LRM moves digit decomposition to the client so that a server-side lookup costs a single multiplicative level, with block-diagonal packing across features. It treats the tables as fixed and leaves training out of scope. CodedHELUT evaluates coded word-embedding lookups with a polynomial indicator under the CKKS approximate scheme. It also never updates the tables. We reuse HE-LRM's encoding and add the missing learning step.
FastQuery attacks the communication cost of private LLM token lookups through low-bit packing. It is orthogonal to our question and could later be combined with the correction tables.
The method-level ancestor is Parameter-free HE-friendly Logistic Regression. That work documents the "hyperparameter trap" of encrypted gradient descent and escapes it with a closed-form ridge solve on teacher logits, using the Sherman–Woodbury identity to keep the encrypted inversion small. Its solve is for a shallow linear model on dense tabular features and has no notion of high-cardinality IDs. Our contribution is to notice that digit decomposition gives an analogous closed form for sparse categorical features. The relevant curvature matrix is block-diagonal within each digit table, so the "inversion" collapses to per-row scalar reciprocals. No Sherman–Woodbury step or public-data Gram matrix is needed.
Two plaintext compression papers motivate the approach. Compositional embeddings with quotient–remainder partitions show that collision-free multi-table composition preserves accuracy at large compression. The 100GB-to-10MB DLRM study shows the cost: the compressed model needs 4.5 epochs instead of one and careful tuning. That observation tells us not to attempt full encrypted retraining of compressed tables. It is part of why we freeze the base model and learn only bounded corrections.
Research Program
We would build the system in three layers.
The first layer is a plaintext reference implementation of digit-row Newton corrections on top of a compressed base DLRM, a deep learning recommendation model. This layer answers the statistical questions. How much of a distribution shift do per-digit-row corrections recover, compared with per-ID corrections that have the same memory cost? How does the choice of radix $p$ trade expressivity against the number of examples per row? Each row sees roughly $n/p$ examples when digits are spread evenly, so the variance of $b_{j,v}$ grows roughly linearly in $p$. That gives an analyzable rule for choosing $p$ from public data alone, which we will test against an empirical sweep. We will also test whether assigning IDs to digits by public frequency, so that popular items concentrate in their own rows, beats arbitrary assignment.
The second layer is the encrypted implementation in CKKS. The client encrypts one-hot digit vectors and labels, as in HE-LRM. The server computes encrypted base logits by HE-LRM-style inference, then evaluates a polynomial sigmoid. The logit range for the sigmoid is fixed from public data, which avoids the out-of-interval divergence that SecureNets and the parameter-free LR work describe. The server then accumulates numerators and denominators and applies the fixed-depth reciprocal. The corrections stay encrypted under the data owner's key. At later inference they add one ciphertext lookup at a single extra multiplicative level.
We will measure multiplicative depth, whether bootstrapping is triggered (the costly noise-reset operation analyzed in Circuit Bootstrapping), wall-clock time, and ciphertext traffic. We will also measure agreement between encrypted and plaintext corrections.
The third layer is an interactive variant. The data owner decrypts only the per-row numerator and denominator sums and performs the division. This removes the reciprocal circuit, but the owner learns aggregated base-model residuals. We will quantify how much latency this saves, so that the cost of full non-interactivity is explicit rather than assumed.
Baselines
The naive reference point is no adaptation. The frozen compressed base model, trained on public data, is evaluated by encrypted inference on the shifted private test period. Any adaptation has to beat it. Its encrypted cost is the floor that our method adds to. For scale, HE-LRM reports 489 seconds of single-threaded CPU end-to-end inference on Criteo Terabyte (HE-LRM). No reported AUC result was found on Lacuna for adapting HE-LRM under shift.
The strongest existing tuning-free encrypted method is global recalibration in the style of Parameter-free HE-friendly Logistic Regression. It fits a closed-form logistic correction to the base model's logits, using mean matching on the private data, so that a single intercept and scale are learned with no per-entity terms. On UCI Cancer it raised accuracy from 86.9% to 90.5% over encrypted gradient-descent logistic regression and cut training latency by about 68%. No reported result was found on Lacuna for it on Criteo or Avazu, so we will run it ourselves on the same splits and base model.
This is the most important comparison. If global recalibration recovers nearly all the gain, the per-row machinery is not justified. We count our method as beating it only if the AUC improvement on the private test period exceeds the gap between the two methods' run-to-run spread. As a yardstick for scale, SCMA reports that +0.0032 AUC on Criteo is a meaningful gain in this domain.
The strongest learning-based competitor is gradient descent on exactly the same correction parameterization. It is run three ways: with a learning rate and epoch count tuned by an oracle on the private validation set in plaintext (an upper bound no encrypted system can realize); with a learning rate transferred from tuning on public data (the realistic encrypted protocol); and with a fixed default. All three use the same base model, the same private data, and the same number of encrypted forward passes for residuals. The SGD runs get as many update rounds as the encrypted budget we give our method allows, plus a generous multiple for the oracle. Matching the oracle within run-to-run noise, while the transferred-rate SGD varies or degrades across shifts, would count as success.
Two ablations isolate the key ingredient. The first replaces digit-row corrections with per-ID corrections hashed into the same number of slots. This tests whether collision-free digit structure, rather than mere parameter count, matters, echoing the hashing comparison in the quotient–remainder paper. The second replaces the closed-form Newton step with the same step using a fixed $\lambda$ chosen badly by one to two orders of magnitude. This tests the claim that the one remaining knob is benign. A plaintext full fine-tune of the compressed tables is reported as a non-private ceiling.
Why not just…?
Why not just run encrypted gradient descent with a learning rate tuned on public data? This is the real threat. If public and private distributions are close, a transferred rate may simply work. Two pieces of evidence point the other way. The parameter-free LR paper reports divergence and erratic losses under encrypted gradient descent. The 100GB-to-10MB DLRM study shows compressed embeddings converge slowly and are tuning-sensitive. Each extra encrypted epoch also costs forward and update passes. Our baseline runs this exact protocol on the same parameterization across several shift magnitudes. If transferred-rate SGD matches the oracle everywhere at comparable encrypted cost, our advantage reduces to determinism, and we will say so.
Why not just recalibrate the model globally? It is cheaper and already closed-form. Shifts in recommendation data are largely per-entity, however: which items and contexts are popular in a given owner's population. One intercept cannot express that. The comparison above decides it directly. We additionally report the AUC recovered by global recalibration as a fraction of the plaintext ceiling, so the per-row increment is visible.
Why not keep the tables on the device and fine-tune in plaintext there? The tables are too large for phones (On-Device Recommender Systems tutorial). HE-LRM's argument also applies: shipping tables exposes the proprietary model. The corrections we learn are tiny, a few hundred scalars per feature, which is why they can be stored encrypted alongside the server's compressed tables.
Why not let the data owner decrypt the sums and divide? This is a legitimate design point, and we include it as the interactive variant. It trades a small model-output leakage for a shallower circuit. Measuring both makes the price of non-interactivity concrete.
Proposed Experiments
We would use the benchmarks in the file with temporal shift. On Criteo Kaggle (about 46M samples, 26 categorical fields), the base model is trained on the first six days and the last day is split into private adaptation and test halves. Avazu (41M samples) is treated the same way by day. Criteo Terabyte is used for scale and cost measurements with an HE-LRM-style compressed base model. Metrics are test AUC and log loss, encrypted multiplicative depth, bootstrapping count, wall-clock time, and communication. All results are averaged over seeds and over several sizes of the private set, so that the predicted variance-versus-$p$ behavior can be checked.
Three outcomes would be decisive. The first is whether digit-row corrections beat global recalibration on day-shift AUC by more than seed noise. If they do not, the proposal fails. The second is whether the closed-form update tracks oracle-tuned SGD while showing a flat response to $\lambda$ over two decades, whereas transferred-rate SGD does not. This is the tuning-sensitivity claim. The third is whether encrypted corrections agree with plaintext ones closely enough that AUC is unchanged, at a total encrypted cost dominated by the single base-model forward pass rather than by the adaptation itself. This is the overhead claim. The radix sweep against the public-data rule for $p$ is a secondary result that would turn a fixed heuristic in HE-LRM and CodedHELUT into a principled choice.
References
- HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption
- Privacy-Preserving Embedding via Look-up Table Evaluation with Fully Homomorphic Encryption
- FastQuery: Communication-efficient Embedding Table Query for Private LLM Inference
- Parameter-free HE-friendly Logistic Regression
- Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems
- The trade-offs of model size in large recommendation models : 100GB to 10MB Criteo-tb DLRM model
- SecureNets: Secure Inference of Deep Neural Networks on an Untrusted Cloud
- Circuit Bootstrapping: Faster and Smaller
- Semantically Constrained Memory Allocation (SCMA) for Embedding in Efficient Recommendation Systems
- On-Device Recommender Systems: A Tutorial on The New-Generation Recommendation Paradigm