Tier-Oblivious Shuffling for Federated Learning with Heterogeneous Model Sizes

The shuffle model of differential privacy gives near-central privacy accuracy without a trusted server. Differential privacy (DP) is a guarantee that any one person's data barely changes what an observer sees. In the shuffle model, each client adds a small amount of noise, and a shuffler strips sender identities before the server sees anything. The guarantee rests on a quiet assumption: every message looks the same, so each report hides among everyone else's. Federated learning on real devices breaks that assumption. Phones and sensors train models of different widths or adapter ranks, so their updates have different lengths, and a 2 MB message cannot hide among 200 KB messages. Today a practitioner must pick one of three bad options. They can force every device to the same small model, run a separate shuffle per device class and lose most of the privacy gain, or pad every update to full size and pay full bandwidth on the weakest devices.

This note proposes a fourth option. Each client sends the same fixed number of fixed-size messages. Each message is a pair (block index, noisy block of parameters), and the block indices are drawn from one distribution shared by all clients. When a small-model client draws a block its model does not contain, it sends a pure-noise "blanket" message instead. Every client's message stream is then statistically indistinguishable from every other's whatever its hardware tier. The weak devices' unused slots are not waste: they become free cover noise that hides the strong devices' contributions to the outer parameters. The server corrects for the known mixture to get unbiased block averages. The research question is how to choose the shared block-sampling distribution and the blanket probability so that accuracy on both the shared core and the large-model-only parameters is maximized, under a fixed per-client upload budget.

Core Claim

Nested heterogeneous architectures such as width-sliced HeteroFL (HeteroFL), ordered-dropout FjORD (FjORD) and rank-heterogeneous LoRA (FlexLoRA) have one structural property that makes them compatible with shuffling. A small client's parameters are an ordered prefix of a large client's parameters. Cutting the parameter vector into equal blocks along this ordering therefore turns a heterogeneous population into a homogeneous message domain, the set of block indices times $\mathbb{R}^b$, and that homogeneity is exactly what the amplification theorems need. Our claims are three. First, the full population of $n$ clients remains the hiding set for every block, rather than only the clients who own that block. Second, upload cost per client becomes a free parameter $m \cdot b$ that is independent of tier and can be far below the full model size $d$. Third, the tier of a client becomes formally private, closing the "parameter fingerprinting" leak that the file identifies in nested architectures.

The mechanism is a block-wise generalization of the Blanket-Mixed Gaussian of Shuffling-Aware Optimization for Private Vector Mean Estimation. That method has each client output pure Gaussian noise with probability $\gamma$ and its noised vector otherwise, and it shows that randomizers designed for local DP are suboptimal once shuffled. We reuse its randomizer. What is new is that the blanket probability is no longer a free design choice applied uniformly. Part of it is forced by heterogeneity: a client that does not own a block must blanket it. Concretely, let block $j$ be sampled with probability $q_j$, owned by a fraction $\pi_j$ of clients, and voluntarily blanketed with probability $\gamma$. The server receives on average $N_j = n m q_j$ messages tagged $j$. It estimates the mean update of block $j$ among its owners as

$$\hat{x}_j = \frac{1}{N_j\,\pi_j\,(1-\gamma)} \sum_{y \in \text{block } j} y,$$

where the blanket noise has mean zero. The mean squared error of $\hat{x}_j$ grows like $1/(q_j \pi_j^2)$ because only a $\pi_j(1-\gamma)$ fraction of block-$j$ messages carry signal. The privacy loss of block $j$, meanwhile, shrinks with $N_j$. Choosing $q$ is therefore a small convex allocation problem with a sharp trade-off. Spending samples on outer blocks costs core accuracy, but outer blocks are where the forced blankets supply free privacy.

Research Program

The first part is accounting. We will bound each client's privacy loss under $m$ shuffled messages with tier-independent block indices. We will use the numerical privacy-loss-distribution accountant of Koskela et al. rather than closed-form bounds such as the $\varepsilon_0\sqrt{\ln(1/\delta)/n}$ amplification of Feldman et al.. The file reports that closed-form bounds are often far looser. A client's $m$ messages touch distinct blocks of the same data, so we compose across them. The subsampled-shuffle Rényi analysis in Renyi Differential Privacy of The Subsampled Shuffle Model In Distributed Learning supplies the template for adding per-message block sampling. We will also prove the tier-privacy statement directly: the joint law of a client's message stream does not depend on its tier beyond the DP noise. This holds by construction because $q$ is shared and blanket messages have the same format and distribution as noised real blocks under the "hiding among clones" argument of Feldman et al..

The second part is optimization. We will solve for $q$ and $\gamma$ given the tier fractions, the per-client byte budget and a target $(\varepsilon,\delta)$. The ordered-dropout result that nested widths behave like an SVD-ordered basis (FjORD) suggests weighting by block importance, not only block error. We will compare an error-only allocation with one weighted by each block's empirical contribution to validation loss. The tier fractions $\pi_j$ are themselves sensitive. We will release them once through a shuffled DP histogram and fold that cost into the budget.

The third part is integration with real heterogeneous training. We will plug the estimator into HeteroFL-style width slicing with its static batch normalization, and into FlexLoRA. FlexLoRA aggregates full products $B_iA_i$, so we block the factors $B_i$, $A_i$ themselves along the rank dimension instead. Rank-$r_i$ clients then own a prefix of rank-one components, and we avoid shipping full products.

The fourth part is attack evaluation. A DP guarantee holds whatever weights the server sends, provided updates are clipped. This matters because MineGrad shows that a malicious server can configure a frozen backbone so that LoRA gradients reveal individual image patches, overturning the belief that small adapters are safe. We will run that attack and passive gradient inversion with a generative image prior (Jeon et al.) against shuffled block messages. We will also run user-level attribute inference from update trajectories (Wang et al.) and a tier-inference attack that tries to recover a client's hardware class from its message stream. Splitting updates into blocks may help an attacker separate contributions, which is the low-entanglement condition identified by Wu et al.. We will test this explicitly rather than assume shuffling neutralizes it.

Baselines

The naive reference is HeteroFL or FlexLoRA with per-client local Gaussian noise, no shuffling, and messages sent at their natural size. This baseline shows the accuracy that local DP alone yields. Run without any noise, the same setup also gives the non-private accuracy ceiling. Both will use identical data splits, tier mixes, rounds and clipping norms.

The strongest competitor is padding plus Blanket-Mixed Gaussian. Every client pads its update to the full dimension $d$, fills absent coordinates with noise, and runs the Shuffling-Aware Optimization randomizer. This approach restores a uniform message domain with an existing optimal single-message mechanism. Our method reduces to it when $m \cdot b = d$ and $q$ is uniform. The honest test is therefore at matched bytes. We will give padding-BMG the same upload budget through uniform random coordinate subsampling and tune $\gamma$ and the clipping norm with the same search budget. Beating it means higher test accuracy at equal $(\varepsilon,\delta)$ and equal bytes, or equal accuracy at fewer bytes. The gain must show up specifically on the large-model tier's accuracy, which depends on the outer blocks.

The communication-efficient shuffle-DP systems, FLAME and Camel, are the strongest existing methods for the bandwidth axis. FLAME uses top-k sparsification with privacy for the chosen indices. Camel sends a pseudo-random seed plus a sign bit in place of the gradient. Both assume a homogeneous model, so we run them on the padded model at matched bytes and accuracy targets. We found no reported accuracy for any of these methods under heterogeneous tiers on Lacuna.

Per-tier shuffling, with a separate shuffler per hardware class, is the natural systems answer and is discussed below. Two ablations isolate the key ingredient. In the first, absent blocks are filled with zeros instead of blankets, which should collapse tier privacy. In the second, the optimized $q$ is replaced by a uniform $q$, which isolates the value of the allocation.

Why not just…?

Why not just pad every update to full size and shuffle? Padding with noise is a real threat, because at full bandwidth it is essentially our scheme with a uniform block distribution. Our claimed advantage is confined to two things: the bandwidth-limited regime, and the allocation of samples between core and outer blocks. If the matched-bytes comparison above shows no accuracy gain from an optimized $q$, we will report the contribution as a tier-privacy proof and accounting result for padded shuffling, not a new mechanism. Zero-padding, the cheap version, is ruled out by construction, because all-zero tails identify the tier.

Why not just run one shuffle per hardware tier? Amplification scales roughly with the square root of the size of the hiding set (Feldman et al.). A tier holding 10% of clients therefore loses about a factor of three in privacy for the same noise, and the tier label itself is revealed. The per-tier baseline will measure this loss directly as the accuracy gap at equal $\varepsilon$, broken down by tier size.

Why not use secure aggregation with central DP, or distillation over public data? Secure aggregation needs equal-length vectors, which brings back padding cost plus heavy cryptographic overhead. It also gives no guarantee against a server that distorts the backbone weights, which is the MineGrad threat. Distillation needs a public dataset matched to private data, which the file notes fails in domains like clinical imaging. We include no distillation baseline. We do note it as an alternative where such data exist.

Proposed Experiments

The file lists no benchmark tables, so the datasets below are the standard ones these method families use. We will run width-heterogeneous image classification on CIFAR-10-scale data with HeteroFL and FjORD slicing at five width tiers and skewed tier mixes. We will run rank-heterogeneous LoRA fine-tuning of a Vision Transformer with ranks from 4 to 64, which is also the MineGrad attack setting. Metrics are per-tier and overall test accuracy, uplink bytes per client per round, and accounted $(\varepsilon,\delta)$. Attack metrics are reconstruction quality (PSNR and LPIPS, a learned perceptual-similarity score) and tier-inference accuracy against chance. We found no reported result on Lacuna for heterogeneous-tier accuracy under shuffle DP for any of the baselines.

The decisive checks are three. The first is the matched-bytes comparison against padding-BMG at fixed $\varepsilon$, varying the tier fractions; the predicted gain should grow as the large-model tier shrinks. The second is a tier-inference attack whose accuracy should fall to chance under our scheme and stay high under zero-padding and per-tier shuffling.

The third is an empirical privacy audit in the style of To Shuffle or not to Shuffle. That paper found shuffled training leaking up to 4.25x more than Poisson-based theory predicted, so we will check that our accounted $\varepsilon$ upper-bounds the audited leakage. We will plant canary clients in rare outer blocks, where forced blankets dominate and a loose bound would show up first.