Federated fine-tuning of large language models runs into a basic tradeoff. The cheapest way to make client updates both tiny and exactly averageable is to freeze two projection matrices and let clients train only a small core matrix between them. The update is then linear in the core, so the server can average cores with no error. The cost is that every client is confined to one fixed subspace for the whole run. Fed-SB picks that subspace from an SVD of a small public proxy dataset; CoSA, in centralized training, picks it at random. If the subspace misses the directions that heterogeneous clients need, nothing in the protocol can recover them.
This note proposes a cheap way out of that confinement. A random subspace can be described entirely by a random seed, so the server can move every client into a fresh subspace each round by broadcasting a few bytes. The averaged core from each round is folded into the frozen weights. Over many rounds the accumulated update spans far more directions than any single subspace, while each round's aggregation stays exact and each round's payload stays the size of the core. Making the projections structured makes refreshing practical on edge devices. We use the Subsampled Randomized Hadamard Transform (SRHT): flip coordinate signs at random, mix all coordinates with a fast Walsh-Hadamard transform, then keep a random subset. Clients can apply, regenerate, and replay these projections in $O(d \log d)$ time without storing dense matrices.
Core Claim
For each adapted weight matrix $W \in \mathbb{R}^{d_1 \times d_2}$, round $t$ uses projections $L_t = \sqrt{d_1/a}\, D_{1,t} H P_{1,t}^\top$ and $R_t = \sqrt{d_2/b}\, P_{2,t} H D_{2,t}$. Here $D_{\cdot,t}$ are random sign diagonals, $H$ is the normalized Walsh-Hadamard matrix, and $P_{\cdot,t}$ select $a$ rows and $b$ columns, all generated from a broadcast seed $s_t$. Clients train only a core $Y_{i,t} \in \mathbb{R}^{a \times b}$, starting from zero. The server averages the cores and merges:
$$W_{t+1} = W_t + L_t \Big(\tfrac{1}{m}\textstyle\sum_{i=1}^m Y_{i,t}\Big) R_t ,$$
where $m$ is the number of participating clients. Because $L_t$ and $R_t$ are shared, this equals the average of the clients' own updates $L_t Y_{i,t} R_t$ exactly. Each round therefore costs $ab$ floats up and $ab$ floats plus one seed down per layer. There is no proxy data, no server-side SVD, and no dense basis to ship.
The claim to test has two parts. First, under non-IID client data and at equal communication, refreshing the subspace each round reaches higher accuracy than any fixed-subspace method (Fed-SB, or a federated CoSA). Second, the SRHT structure keeps the client-side cost of refreshing small enough to be practical, where dense Gaussian projections would not be.
Refreshing gives the clients new directions without the downlink cost that refreshing a data-derived basis would carry. That is the new ingredient. SRHT is what makes it cheap on clients. It is not, by itself, the source of the communication savings.
Relation to Prior Work
Two papers motivate the gap and one constrains it.
FedEx-LoRA shows that averaging low-rank factors $B_i, A_i$ separately does not equal averaging the products $B_i A_i$. It corrects the mismatch by folding the residual into the frozen weights and sending SVD-compressed packets back to clients. We avoid the residual altogether, so neither the SVD nor its downlink is needed.
Fed-SB makes aggregation exact by freezing SVD-derived bases and training a square core $R$. It also shows that training a single linear core avoids the noise amplification that LoRA suffers under differential privacy. We inherit both properties. We replace its proxy-dependent, permanently fixed subspace with seed-refreshed random ones. Fed-SB itself names proxy mismatch as its limitation.
CoSA supplies the parameterization $LYR$ with fixed random projections and shows it rivals LoRA centrally, for example 83.23 versus 81.42 GLUE average on RoBERTa-base. CoSA uses dense Gaussian matrices, keeps them fixed, and never considers federation.
The structured-projection side supplies the method. Lacotte et al. prove that SRHT behaves asymptotically like a uniformly random orthogonal matrix, with tighter spectra than Gaussian sketches. They also note that the "fixed sketch" regime, where one projection is reused throughout, is theoretically open, while refreshed sketches are better understood. Our design deliberately sits in the refreshed regime. The theory of Krahmer et al. justifies sign-randomized structured operators as data-oblivious embeddings.
Real layer widths are often not powers of two; Mistral-7B's MLP width is 14336, for example. For these we borrow the block construction of Block SRHT, which applies independent local Hadamard transforms to power-of-two blocks and keeps subspace-embedding guarantees.
The gradient-sketching line differs in kind: FetchSGD, FedSKETCH, and Sketched-SGD. These methods compress full-model gradients with Count Sketch and recover heavy hitters at the server. Sketching for First Order Method constrains our design in two ways. It shows that the de-sketched estimate $R^\top R g$ carries variance proportional to $d/m$. It also shows that a known seed lets an adversary reconstruct training data, so sketching is not privacy. We train inside the subspace rather than de-sketching gradients, which removes the first problem. We do not claim any privacy from randomness.
Research Program
The first component is the protocol and its implementation. Each client keeps the base model and a replay log of $(s_t, \bar Y_t)$ pairs. A returning or new client reconstructs its current weights by replaying the log. For SRHT this replay is cheap. Computing $L_t \bar Y_t R_t$ amounts to scattering $\bar Y_t$ into the sampled positions of a $d_1 \times d_2$ zero matrix, applying a two-sided fast Walsh-Hadamard transform, and applying signs, at $O(d_1 d_2 \log d)$ cost. With dense Gaussian projections the same step costs roughly a factor $b/\log d$ more and requires regenerating the dense matrices. In the forward pass, $x \mapsto L_t Y R_t x$ is likewise computed through fast transforms.
We will measure catch-up cost for clients that join late, because stateless participation is a stated failure mode for error-feedback compressors. When the log grows large, the server can instead offer a full checkpoint, and we will report where that crossover falls.
The second component is analysis. Refreshing turns training into random-subspace descent on the full weight update. We will derive a convergence bound for smooth objectives under bounded client heterogeneity, with expected progress per round scaling like $ab/(d_1 d_2)$ of a full step, the fraction of directions a random subspace covers. We will compare it with the fixed-subspace case, where the error floor is the part of the optimal update lying outside the subspace. The Haar-like spectrum of SRHT should make the per-round contraction tighter than with Gaussian projections. We will test whether that predicted difference is visible in practice or negligible.
The third component is the knobs. We will vary the refresh period, from every round, to every $k$ rounds, to never. We will vary the core shape $a \times b$ at a fixed parameter count, and the client learning rate after a refresh. Restarting the core at zero each round may waste local steps, so we will try a short warmup.
Baselines
The naive reference points are two. Plain federated LoRA (FedIT) with averaged factors shows the cost of inexact aggregation; FedEx-LoRA reports 56.94% on GSM8K with Mistral-7B, against 62.77% for centralized LoRA. Centralized fine-tuning with the same adapter budget is the ceiling.
The strongest existing competitors are Fed-SB and FedEx-LoRA. On GSM8K with Mistral-7B, FedEx-LoRA reports 62.62%. No separate GSM8K accuracy for Fed-SB is reported in the file (no reported result found on Lacuna for Fed-SB GSM8K accuracy). Fed-SB reports up to 230x less communication than FedEx-LoRA on MATH, and 70.33% versus FedIT's 49.57% on SNLI under differential privacy at $\epsilon = 1$.
Fed-SB is the competitor that matters most, because it matches our communication profile. Both methods send a small core, both aggregate exactly, and both behave well under differential privacy. If refresh does not beat Fed-SB, the proposal fails. We will run Fed-SB with its 0.1% proxy drawn from the pooled data, which is its favorable case, and with a proxy drawn from a mismatched domain. We will match the core parameter count, the number of rounds, the number of local steps, and the learning-rate tuning budget (the same grid size for every method), and use the same client partitions and seeds.
Beating Fed-SB means higher final accuracy at equal total bytes on non-IID partitions, with no loss in the IID case. Matching FedEx-LoRA's 62.62% on GSM8K at Fed-SB-level communication would be a clear win.
Two ablations isolate the proposal's ingredients. A fixed SRHT subspace with no refresh, which is federated CoSA with structured projections, isolates the value of refreshing. Refreshed dense Gaussian subspaces generated from the same seeds isolate the value of structure. That second ablation should show equal accuracy and communication but higher client time and memory.
We also include an SRHT gradient sketch in the FetchSGD style, replacing Count Sketch with SRHT and keeping server-side momentum and heavy-hitter recovery. It represents the other natural way to connect these two directions.
Why not just…?
Why not just use seeded Gaussian projections, which cost the same to communicate? On bytes sent, they are a genuine tie, and we say so. The SRHT-specific claims are client compute, memory, and replay cost, plus a possible conditioning advantage suggested by Lacotte et al.. The refreshed-Gaussian ablation settles both. If accuracy matches and SRHT's wall-clock advantage on a phone-class CPU is small at real layer widths, the contribution reduces to seed refreshing. We would report it that way.
Why not just keep Fed-SB's fixed subspace, or re-run its SVD periodically? A fixed subspace cannot represent directions outside itself; Fed-SB concedes this under proxy mismatch. Re-running the SVD requires proxy data that matches the clients' shifting data. It also requires sending new $d \times r$ bases downlink, which is exactly the cost a seed avoids. The mismatched-proxy and non-IID experiments test whether this matters in practice. If fixed subspaces match refresh even there, the proposal's premise is wrong.
Why not just sketch gradients with SRHT instead of Count Sketch? That would fill the gap left by FetchSGD-style methods. But de-sketching carries variance proportional to $d/m$ (Sketching for First Order Method). Heavy-hitter recovery also needs server state and, in Sketched-SGD, a second round trip. Training directly in the subspace has neither cost. The SRHT-sketch baseline measures how large this difference is at equal bytes.
Why not just use FedEx-LoRA? It reaches near-centralized accuracy. Its downlink, however, is SVD-compressed residual packets, and it pays for a server SVD every round; its reported communication is about 1.02x that of FedIT. We compare at matched bytes rather than matched rounds.
Proposed Experiments
The main testbed is GSM8K and Commonsense170K, fine-tuning Mistral-7B and Llama-3.2 3B, the models used by both FedEx-LoRA and Fed-SB. GLUE on RoBERTa-base serves as a cheap sweep setting. Clients number 10 to 100, with partitions ranging from IID, to Dirichlet label or topic skew, to one task per client for commonsense subtasks. For privacy we use SNLI with DP-SGD at $\epsilon = 1$, against Fed-SB's 70.33%.
The metrics are accuracy against cumulative uplink and downlink bytes, client wall-clock time and peak memory per round, server time per round, and catch-up cost for clients joining late. The decisive comparison is refreshed SRHT against Fed-SB and the fixed-SRHT ablation on the most skewed partition at equal bytes.
A refreshed run that gains accuracy over the fixed-subspace curves as rounds accumulate, while they plateau, confirms the claim. Identical curves refute it. A second check sweeps the refresh period to find where gains appear. A third check measures how much of the accumulated update lies outside any single round's subspace, to verify that refreshing actually widens what the model learns.
References
- FedEx-LoRA: Exact Aggregation for Federated and Efficient Fine-Tuning of Large Language Models
- Fed-SB: A Silver Bullet for Extreme Communication Efficiency and Performance in (Private) Federated LoRA Fine-Tuning
- CoSA: Compressed Sensing-Based Adaptation of Large Language Models
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform
- New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property
- Block Subsampled Randomized Hadamard Transform for Nyström Approximation on Distributed Architectures
- FetchSGD: Communication-Efficient Federated Learning with Sketching
- FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
- Communication-efficient Distributed SGD with Sketching
- Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability