Choosing LoRA Ranks on the Device from Gradient Sketches

When a phone or a small embedded board fine-tunes a language model, it usually trains a low-rank adapter. LoRA, the common choice, learns a weight change for each layer as the product of two thin matrices whose inner width is the "rank." Nobody knows the right rank ahead of time. Current federated systems either give every device and every layer the same guessed rank, or start large and prune downward over many rounds of server coordination. We propose that each device estimate, before adapter training starts, how many directions each layer actually needs. It does this by sketching the gradient that full fine-tuning would follow. It never forms that gradient matrix, and it treats the rank choice as spending a byte budget rather than as finding a spectral gap.

The idea comes from low-rank matrix recovery, where estimating an unknown rank is a mature problem. We borrow two lessons from that literature. The first is that a rank can be counted with cheap matrix-vector products instead of a full factorization, as in Fast methods for estimating the Numerical rank of large matrices. The second is that gap-based counting fails when singular values decay smoothly, which is the usual case for neural gradients. Our estimator therefore keeps only directions that reproduce across independent halves of the local data, and allocates rank across layers by marginal value per transmitted byte. If it works, a heterogeneous fleet gets per-layer, per-device ranks in one local pass, with no server SVD and no overspecified first rounds.

Core Claim

The claim is that a short streaming sketch of each layer's accumulated full-weight gradient, collected on the device during the first few local batches, predicts per-layer adapter rank well enough to match top-down adaptive allocation. Matching means within half a GLUE point of FedARA in federated non-IID fine-tuning, while sending fewer total bytes and running no server-side factorization. The same sketch also supplies a warm-start initialization. We test separately whether the rank choice or the initialization produces any gain.

Two terms need defining. "Non-IID" means each client's local data comes from a different distribution. A "sketch" is a small random projection that keeps a large matrix's dominant directions.

What exists and where this sits

The closest work is SLoRA. Its clients first train a sparse random mask. The server then runs a dense SVD on the aggregated deltas to initialize LoRA factors, and the resulting rank is fixed and uniform across clients and layers. SLoRA motivates this proposal because it shows that informed initialization closes much of the non-IID gap. It reports 58.6% on 20News with Albert, against 56.5% for LoRA and 58.17% for full fine-tuning. We differ in three ways: the estimate is computed on the client, it chooses a rank per layer and per device, and it never forms a dense matrix.

HETLORA lets clients hold different ranks, truncates a global adapter to fit them, and self-prunes locally. It reports that high-rank clients with low-complexity data inject noise. That observation is exactly what we try to predict up front instead of discovering through pruning. HETLORA's rank assignments are heuristic. We reuse its norm-weighted heterogeneous aggregation unchanged.

FedARA is the strongest adaptive competitor. It uses a three-factor adapter with explicit singular values, prunes ranks by server-computed importance scores, and drops whole modules whose ranks reach zero. It measures time and energy on Jetson Orin and Raspberry Pi 5. IGU-LoRA shows, in centralized training only, that instantaneous-gradient importance scores (AdaLoRA-style) are noisy and saturate, and it fixes this with integrated gradients and signal-to-noise tracking.

That IGU-LoRA result constrains our design, and we address it directly. It warns that a single gradient snapshot is a brittle signal. Our estimator therefore uses the accumulated gradient over many batches, not an instantaneous one, and accepts only directions that recur across data splits. Whether this is enough is the central empirical question.

From the rank-estimation side, three greedy methods grow rank incrementally from residuals: Riemannian Pursuit, Greedy Bilateral Sketch, and, in spirit, Matrix Completion from a Few Entries. Their spectral-trimming view explains why signal singular values separate from a noise bulk. We use the "count what the residual supports" logic but compute it once, before training, rather than interleaving rank growth with optimization.

We also deliberately do not build on Rank Overspecified Robust Matrix Recovery. Its guarantees need symmetric factorizations, Gaussian measurement operators and an ℓ1 loss, none of which hold for LoRA under cross-entropy.

Research Program

For a linear layer with weight size $d \times k$, the accumulated gradient over local tokens $t$ is $G=\sum_t \delta_t x_t^\top$. Here $x_t$ is the layer input and $\delta_t$ the backpropagated signal. We never form $G$. During backward hooks on the first $N$ local batches, the device updates a two-sided sketch, $Y \mathrel{+}= \delta_t (x_t^\top \Omega)$ and $Z \mathrel{+}= (\Psi\delta_t)x_t^\top$, where $\Omega$ and $\Psi$ are fixed random matrices of sketch width $s$. Memory per layer is $O((d+k)s)$, the same order as a rank-$s$ adapter. A small SVD of the sketched core then gives approximate singular values $\hat\sigma_{l,1}\ge\hat\sigma_{l,2}\ge\dots$ for layer $l$.

Two rules turn this spectrum into ranks. The first rule is a reproducibility filter for the unknown-rank problem when no gap exists. The device builds the sketch separately on two disjoint halves of its batches. It then counts the leading directions whose subspaces agree beyond what random subspaces of the same dimension would give. That count, $\bar r_l$, is an upper bound on how many directions the local data genuinely supports. This amounts to split-half cross-validation of the spectrum, and it replaces the spectral-valley threshold used by Fast methods for estimating the Numerical rank of large matrices. That threshold is known to fail on smoothly decaying spectra.

The second rule is budgeted allocation across layers. Given a device byte budget $C$, which covers the upload per round and adapter memory, we solve

$$\max_{r_l\le \bar r_l}\ \sum_l \sum_{i=1}^{r_l}\hat\sigma_{l,i}^2 \quad\text{s.t.}\quad \sum_l r_l(d_l+k_l)\le C.$$

In this objective, $r_l$ is layer $l$'s rank and $d_l+k_l$ is the number of adapter parameters one rank costs in that layer. Each layer's captured energy is concave in $r_l$ because the singular values are sorted. Greedily adding the rank with the largest $\hat\sigma^2_{l,i}/(d_l+k_l)$ is therefore optimal for this relaxation. Budget-limited devices stop early, and devices with rich budgets stop at $\bar r_l$. Layers whose $\bar r_l=0$ receive no adapter, so no backward pass runs through them, which is FedARA's module-dropping benefit obtained without pruning rounds. The sketch's top singular vectors optionally initialize the factors. The server aggregates heterogeneous ranks as HETLORA does, and a device may re-estimate every $T$ rounds as its data or budget shifts.

Baselines

The naive reference is uniform fixed-rank LoRA at the largest rank the weakest device fits, trained with the same federated optimizer. It is the "do nothing" point, and it is what practitioners actually ship. We run it at matched total uplink bytes, not matched rank, because a fair comparison must give it the same budget our method spends. Beating it means higher accuracy at equal bytes, or equal accuracy with fewer bytes.

The strongest existing method is FedARA (Adaptive Rank Allocation for Federated Parameter-Efficient Fine-Tuning of Language Models). It is the strongest competitor here because it already allocates rank per layer, drops modules, and was measured on the same edge hardware we target. Its reported results are an average accuracy gain of 6.95% to 8.49% over baselines under heterogeneous data, a 2.40× improvement in communication efficiency, and up to 48.90% less training time and 46.95% less energy on Jetson Orin and Raspberry Pi 5. Per-dataset numbers are not given in the file. We rerun it with its published pruning schedule, the same clients, partitions, rounds and learning-rate grid, and an equal tuning budget of the same number of trials. Beating it means matching its final accuracy within 0.5 points while sending fewer cumulative bytes, or reaching its accuracy in fewer rounds.

We also include three further baselines. HETLORA (Heterogeneous LoRA for Federated Fine-tuning of On-device Foundation Models) runs with its reported pruning threshold γ=0.99 and tier-based rank assignment. SLoRA (SLoRA) is compared on 20News with Albert, where the reported 58.6% is the target. As a centralized upper reference, IGU-LoRA's reported GLUE average with RoBERTa-large is 89.42, against 88.68 for AdaLoRA and 88.12 for LoRA (IGU-LoRA).

Three ablations isolate the key ingredient. The first uses the estimated ranks with random initialization, which separates rank choice from warm start. The second computes the exact dense SVD of $G$ instead of the sketch, on models small enough to allow it. The third drops the reproducibility filter and keeps only the budgeted allocation.

Why not just…?

Why not just pick a small uniform rank that fits the weakest device? The evidence says uniform ranks waste capacity on insensitive layers. FedARA and IGU-LoRA both find that deeper layers and feed-forward blocks need more rank. In heterogeneous fleets a lowest-common-denominator rank also caps the strong devices. That evidence comes from pruning methods, though, and a well-tuned uniform rank at matched bytes is a real threat. Our byte-matched uniform baseline settles it. If uniform rank comes within noise of our method, then per-layer estimation is not worth the complexity, and we will report that.

Why not just use FedARA-style top-down pruning, which already works? We concede that adapter memory is small next to backbone weights and activations. The "out of memory at round zero" argument for bottom-up methods is therefore weak, and we do not rest on it. The real costs of starting overspecified are communication and backward compute through modules that are later dropped. Pruning also needs server-side importance scores across many rounds. Cumulative bytes-to-accuracy curves and per-round energy on the Orin Nano and Raspberry Pi 5 will show whether a one-shot client estimate recovers FedARA's allocation more cheaply. The rank-correlation check below will show whether it recovers the same allocation at all.

Why not just compute the exact SVD, on the server as SLoRA does or on the device? For RoBERTa-sized layers, a dense per-layer gradient is a few megabytes and an exact SVD is affordable. This is why exact SVD appears as an ablation rather than as a straw man. The sketch only matters for large layers: for 4-bit Mistral-7B, a fp32 dense gradient of a 4096×14336 projection is about 235 MB per layer, which a small board cannot hold across all layers. The claim is not that the sketch beats exact SVD. It is that the sketch matches exact SVD where both run, and still runs where exact SVD cannot.

Why not just count rank with Hutchinson trace estimation and polynomial filters? That method, from Fast methods for estimating the Numerical rank of large matrices, shines when the rank runs into the hundreds or more and a gap exists. Its reported error on Erdos992 is under 0.1%. Adapter ranks are tens, which a width-128 sketch captures directly, and gradient spectra rarely have gaps. We include it as a secondary estimator only to confirm that it gives the same counts at higher cost.

Proposed Experiments

We use two protocols. The first is GLUE (RTE, MRPC, SST-2, QNLI, QQP, MNLI) under Dirichlet non-IID partitions, following FedPETuning, with RoBERTa-large. The second is 20News with Albert, following SLoRA. A scale test runs 4-bit Mistral-7B on MNLI, SST-2 and QQP, as in Riemannian Preconditioned LoRA, which reports 89.01 for its scaled optimizer. Clients are split into three budget tiers, emulated at the byte level and run physically on the Jetson Orin Nano and Raspberry Pi 5. Metrics are final accuracy, cumulative uplink bytes to target accuracy, wall-clock time and energy per round, peak device memory, and the time spent estimating rank.

Three decisive checks decide whether the idea stands. The first is predictive validity. For each layer, we find the oracle rank from a per-layer sweep on a centralized run: the smallest rank within 0.2 points of the best. The sketch-estimated $\bar r_l$ should reach a rank correlation with that oracle comparable to that of FedARA's final retained ranks. If early gradient spectra do not predict needed rank, the proposal fails, and we will publish that negative result.

The second check is heterogeneity. Clients with narrow local label distributions should receive lower estimated ranks. Forcing those clients to a higher rank should hurt global accuracy, which tests HETLORA's regularization claim directly and prospectively. The third check is attribution. The random-initialization ablation must keep most of the gain over uniform LoRA; otherwise the benefit is SLoRA-style warm starting, not rank estimation.