Triangular Width Nesting for Exact Unlearning Across Heterogeneous Devices

Federated learning trains one model across many devices without collecting their data. Real fleets mix phones, microcontrollers and edge servers, so recent systems give each device a narrower or wider slice of a single shared network. Those systems cannot honour a deletion request, such as a user invoking the right to be forgotten, without retraining everything, because every device updates the same "core" channels that all slices share. Exact unlearning methods avoid full retraining by isolating data into separate sub-models. Their guarantee is that the model after deletion is distributed exactly as if the data had never been seen. But they assume every sub-model has the same architecture. As a result, a fleet today can adapt to device diversity or delete data cheaply, but not both.

We propose a single change to how channels connect. Split each layer's channels into ordered groups, and let group $k$ read only from groups $1$ through $k$ of the previous layer, never from wider groups. Three things follow from this one constraint. Any prefix of groups is a complete, dense, narrower network, so a weak device simply runs the first few groups. That is structured filter pruning, meaning the removal of whole channels rather than scattered weights, and it needs no sparse kernels. Data used to train group $k$ cannot influence groups below $k$. Deleting it therefore means retraining only groups $k$ and above, from a frozen prefix that serves as its own checkpoint. Width becomes the axis along which we roll back, the axis along which we compress for weak devices, and the axis along which we assign device tiers.

Core Claim

Lower-triangular channel-group connectivity turns a nested heterogeneous federated model into an exact unlearning system. A deletion request touching group $k$ costs a retrain of the suffix of groups $k$ through $K$, not a retrain of the whole model, and the post-deletion model is bit-identical to one trained from scratch without the deleted data under a fixed seed. We claim this design occupies a better point on the three-way trade-off between accuracy, deletion cost and on-device compute than either extreme. At one extreme is fully mixed nesting, as in HeteroFL and FjORD, which is accurate but offers no cheap exact deletion. At the other extreme is fully isolated sharding, as in SISA-style ensembles, which offers cheap deletion but pays in accuracy and in redundant inference.

Concretely, let $W^{(l)}_{k,j}$ be the weights mapping channel group $j$ of layer $l-1$ to group $k$ of layer $l$. The constraint is

$$W^{(l)}_{k,j} = 0 \quad \text{whenever } j > k,$$

for every layer $l$. Suppose groups are trained in order, each group only after all lower groups are frozen, and each group sees only the data of the clients assigned to it. A deletion from a client assigned to group $k$ then triggers retraining whose cost is

$$C_{\text{del}}(k) = \sum_{m=k}^{K} c_m,$$

where $c_m$ is the training cost of group $m$ alone. The prefix $1,\dots,k-1$ is untouched by construction. This is the width analogue of the depth-wise slicing in Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning. That work assigns data slices to successive LoRA layers of a centralized model and switches off layers at and above the affected slice. We move the slicing into channel width, drop the adapters, and use the resulting prefixes as the device tiers themselves.

Research Program

The proposal relies on three existing lines of work, each in a different role.

The nested-width federated methods motivate the architecture and set the accuracy bar. HeteroFL gives clients width-shrunk subnetworks at ratios from 1.0 down to 0.0625 and averages overlapping parameters. FjORD uses ordered dropout so that the first $p\cdot K$ neurons form a valid submodel with a fixed importance ordering. In both, the narrow core is updated by every tier and wider channels feed back into nothing below them only by accident of ordering, not by constraint. The dense connectivity from wide to narrow channels during training is exactly what destroys isolation. We keep their nesting and their static batch normalization, and we remove the backward dependency.

The exact-unlearning literature supplies the isolation and rollback logic, and it also constrains the design. SISA sharding and slicing (Machine Unlearning: Solutions and Challenges) and its federated variant Scalable Federated Unlearning via Isolated and Coded Sharding isolate clients into shards and retrain only the affected shard. Both assume identical architectures across shards, and both must store checkpoints. Efficient Verified Unlearning For Distillation acts as a constraint: it shows that ordinary distillation spreads influence everywhere. We therefore rule out the cross-tier self-distillation that FlexFL uses to fight the "large model paradox" (wide models, seen by few clients, underperform narrow ones).

Structured pruning supplies the hardware argument. Dropping whole channel groups leaves dense matrices that run on standard linear-algebra kernels (Compacting Deep Neural Networks for Internet of Things; Compressing Large-Scale Transformer-Based Models: A Case Study on BERT). A prefix of our network is literally a narrower dense network, with no index bookkeeping.

Building on these, the program has four parts.

The first part is the architecture. We will implement triangular grouping for PreResNet18 and a small CNN, and for an LSTM on text. Residual additions are handled per group, so group $k$'s residual stream is added only to group $k$, which keeps the prefix property through skip connections. Normalization is per group with statistics computed only from that group's assigned data, following HeteroFL's static batch normalization. Otherwise normalization statistics would silently leak deleted data into lower groups. Each wider group enters the classifier head through an additive term initialized at zero. A wider tier therefore starts as exactly the narrower model and can only move away from it where its data supports doing so. This is our proxy-free, distillation-free answer to the large model paradox, and we will test whether it is sufficient.

The second part is data-to-group assignment. A client of capacity tier $j$ can compute only groups $1..j$, so its data can train only a group at or below $j$. This creates a real tension. Weak devices are the most numerous, their data must train the earliest groups, and deleting from them triggers the most expensive retrains. We will study two remedies. The first splits each group into several parallel sub-groups that are block-diagonal to one another, each owned by a disjoint set of clients, so that only one sub-group plus the suffix is retrained. The second applies SISA slicing inside each group, so that retraining resumes from a mid-group checkpoint.

The third part is the deletion protocol. On a request, the server identifies the group, sub-group and slice of the affected client, discards every parameter at or above that point, and replays federated training for that suffix with the remaining clients under the original seeds and schedule.

The fourth part is the analysis. We will measure how the triangular constraint's lost capacity trades against deletion cost, as a function of the number of groups $K$ and the number of parallel sub-groups.

Baselines

The naive reference point is full retraining of HeteroFL from scratch after every deletion. It gives the accuracy ceiling for nested heterogeneous training and the worst deletion cost. On CIFAR-10 with a non-IID split and PreResNet18, HeteroFL reports 61.64% global accuracy against 58.99% for homogeneous federated averaging (HeteroFL). We will reproduce its setup, including width ratios, client counts and partitions, rather than rely on the number. Our method beats this baseline if it stays within a pre-registered margin of that accuracy while cutting mean deletion cost by at least the factor predicted by our cost formula.

The strongest existing competitor on the unlearning side is Sharding Eraser (Scalable Federated Unlearning via Isolated and Coded Sharding). It isolates clients into shards and reports a 65% to 88% reduction in retraining time on MNIST, FMNIST and CIFAR-10, and a 98% storage reduction relative to FedEraser. It is the strongest competitor because it is the only method in the file that performs exact-style federated unlearning with shard isolation. It requires homogeneous architectures, so we will run it in two forms. In the first, every client runs the smallest width, which is the only architecture that fits the weakest device. In the second, each tier forms its own shards with a tier-appropriate width. Both forms get the same data partition, total client compute, round budget and hyperparameter search budget as our method. We count it as beaten if we match its deletion time at higher per-tier accuracy, or match its accuracy with lower deletion time, at equal on-device compute.

The strongest approximate federated unlearning method in the file is Federated Unlearning via Class-Discriminative Pruning. It prunes channels with high class specificity and then fine-tunes, reporting an 8.9× to 11× speedup over retraining for ResNets and target-class accuracy dropping to 0%. It is class-level only and carries no exactness guarantee. We include it on class-deletion requests to show what exactness costs in speed. It is not a contender for sample- or client-level deletion.

The key ablation isolates the triangular connectivity itself by replacing it with block-diagonal connectivity. In that variant, groups never read from each other, which is equivalent to a SISA ensemble of narrow networks where a tier-$j$ device runs $j$ members. Everything else is held fixed: the same groups, data assignment, per-group normalization, zero-initialized head terms and FLOPs. If triangular connectivity does not beat block-diagonal accuracy at matched FLOPs by a clear margin, the core idea has failed. A second ablation removes the zero-initialized additive head, to test whether that mechanism is what prevents wide tiers from underperforming narrow ones.

Why not just…?

Why not just run SISA with one tiny model that fits every device? HeteroFL shows that this "least common denominator" choice is costly: a model constrained to the smallest client's capability reaches about 77% on its benchmark, versus over 90% when it participates in multi-width training. The block-diagonal ablation and the smallest-width Sharding Eraser baseline test this directly on our benchmarks, so the claim stands or falls on measured per-tier accuracy.

Why not just give strong devices an ensemble of independently trained small models? This is the real threat. Isolation is total, deletion is cheap, and wide devices still get more capacity. It is exactly our block-diagonal ablation. The argument against it is that ensemble members cannot reuse each other's features, so capacity is spent on redundant low-level filters. Triangular connectivity lets wider groups build on narrower features at roughly the same deletion cost for suffix groups. The penalty is that deletions from early groups are costlier than retraining a single ensemble member. We will report both sides, and if the accuracy gain is smaller than the variance across seeds, we will conclude that the ensemble is the better design.

Why not just train HeteroFL or FjORD normally and apply approximate unlearning, such as gradient ascent or Fisher-based removal? The surveys (Machine Unlearning: A Survey; Exploring the Landscape of Machine Unlearning) note that such methods give no zero-certified removal. The class-discriminative pruning paper reports that the Fisher baseline degrades badly under non-IID federated data. We will include gradient-ascent unlearning on HeteroFL as a speed reference and run membership inference attacks on all methods. The contrast is that our method's output can be checked for bit-identity against a model retrained from scratch, while theirs cannot.

Why not just prune for weak devices with an importance score, as FlexFL does? FlexFL's activation-sparsity score needs a server proxy dataset. Its self-distillation mixes information across tiers, which PURGE shows breaks isolation. Its 20–30% local compute overhead also falls on the weakest devices. Our prefixes need no importance score because the ordering is fixed by construction.

Proposed Experiments

We will use CIFAR-10 and CIFAR-100 with non-IID client partitions and PreResNet18 in HeteroFL's tier configuration, FEMNIST partitioned by writer via LEAF with a CNN, and LEAF Shakespeare with an LSTM. Clients are assigned to five capacity tiers, with more clients in the weak tiers, following HeteroFL's proportions. Deletion workloads are streams of client-level and sample-level requests drawn under three regimes: uniform over clients, concentrated on weak-tier clients (our worst case), and adversarially targeting the earliest group.

Our metrics are per-tier test accuracy and the gap between adjacent tiers, which detects the large model paradox. We also report deletion cost in federated rounds and in wall-clock time, server storage, measured inference latency of each prefix on a CPU and an edge GPU, and membership-inference success on deleted clients relative to retraining from scratch.

The first decisive check is exactness. After each deletion we retrain from scratch without the deleted clients under identical seeds and deterministic kernels, and require bitwise-identical parameters. We also require membership inference success on the deleted data to be indistinguishable from the scratch model. Any mismatch points to a leak, most likely through normalization statistics or shared optimizer state, and is a failure of the method, not a tuning issue.

The second check is the matched-FLOPs comparison of triangular versus block-diagonal connectivity across $K \in \{2, 4, 8\}$ with and without parallel sub-groups. It asks whether cross-group feature reuse buys accuracy that isolation cannot.

The third check is the weak-tier deletion regime. We plot mean deletion cost against the fraction of requests from weak devices, and identify the point at which our method's cost exceeds Sharding Eraser's. That crossover tells a practitioner when the design is worth adopting.

The fourth check is whether the widest tier is at least as accurate as every narrower tier on every data slice when self-distillation is excluded. It tests whether the zero-initialized additive head alone resolves the large model paradox that FlexFL addressed with distillation.