Discrepancy Rounding for Fixed-Budget Adapter Consolidation

Modular continual learning keeps a large pretrained network frozen and adds a small adapter for each new task. The most common adapter is LoRA (low-rank adaptation), a weight update written as a product of two thin matrices. The approach avoids forgetting, but memory and routing cost grow linearly with the number of tasks. Methods that keep memory constant work by squeezing all past updates into one fixed-size adapter, and they use heuristics to decide what survives the squeeze. This proposal treats that squeeze as a rounding problem with a provable error. Split every task's update into rank-one pieces, called atoms. Then choose a fixed number of atoms to keep, and rescale them, so that one guarantee holds for every task at once: on that task's inputs, the consolidated update stays close to the task's own update in operator norm. The operator norm is the largest amount a matrix can stretch any input, so it bounds the worst-case output deviation.

The tool for this guarantee comes from matrix discrepancy theory, the study of how to choose signs $x_i \in \{\pm 1\}$ so that a signed sum of matrices stays small. Its central open question is the matrix Spencer conjecture. Generic random rounding loses a $\sqrt{\log d}$ factor in dimension $d$, and the conjecture asks whether that factor can be removed. The factor has been removed when the matrices have low rank (Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank). The consolidation problem lands in that low-rank regime naturally. A related compression result from quantum autoencoders, that lossless compression is possible exactly when the ensemble's rank fits the latent dimension, supplies a predictor of how many tasks a fixed budget can hold before the error must grow.

Why the obvious combination is wrong, and what replaces it

The research file reports no paper connecting matrix discrepancy to continual-learning parameter growth. The first idea that comes to mind is to assign a sign to each task's update and sum them. That idea fails on its face. Negating a task's update is task negation, which TAK uses deliberately for unlearning, so no consolidation method may flip a task's sign. Signs only make sense as decisions about rounding. The classical route from discrepancy to sparsification uses them that way. Each surviving atom receives a sign. Atoms signed $+1$ have their weight doubled, atoms signed $-1$ are dropped, and the signs are balanced so that half the atoms survive each round. The error introduced in one round is exactly a signed matrix sum $\sum_j x_j w_j A_j$, and keeping that sum small is the discrepancy problem. Repeating the halving step $\log_2(M/R)$ times reduces $M$ atoms to a budget of $R$ atoms. Because the scale halves each round, the errors from successive rounds form a geometric series, so their total is dominated by the last few rounds.

There is a second reason the naive version is not the right problem. Approximating the plain sum of all task updates in operator norm at rank $R$ is already solved optimally by truncating the singular value decomposition (SVD) of the sum. Discrepancy has nothing to add there. It becomes useful when many norms must be controlled at the same time. Let task $k$ have an input covariance $C_k$, and let $T$ be the reference update obtained by keeping every task's adapter. We want the consolidated update $\hat W$ to satisfy

$$\max_{k \le N} \big\| (\hat W - T)\, C_k^{1/2} \big\|_{\mathrm{op}} \le \varepsilon .$$

Each block $(\hat W - T)C_k^{1/2}$ is a rectangular matrix, so we replace it by its symmetric dilation, the block matrix with the rectangular block in the off-diagonal positions and zeros on the diagonal. Placing the $N$ dilated blocks on the diagonal of one large matrix turns the maximum over tasks into a single operator norm, because the operator norm of a block-diagonal matrix is the largest block norm. The large matrix has dimension $d \approx 2N(m+n)$ for a weight matrix of size $m \times n$. Each atom enters as a symmetric matrix of rank at most $2N$. The quantity balanced in each halving round is therefore a sum of $M$ low-rank symmetric matrices, which is a matrix-Spencer-type instance.

This target differs from plain truncated SVD in a concrete way. A task whose update has small singular values, or whose inputs occupy a direction that other tasks ignore, can be wiped out by SVD truncation of the sum. Under the per-task objective, the same loss shows up directly as a large block norm.

Core Claim

We claim three things. First, low-rank continual updates make a natural instance of block-diagonal matrix discrepancy. Second, halving-based discrepancy rounding gives a fixed-rank consolidated adapter whose worst per-task operator-norm error is provably smaller than generic random rounding by about a $\sqrt{\log(N(m+n))}$ factor. The rate comes from a non-commutative Khintchine (matrix concentration) bound for randomized rounding, compared with log-free bounds in the low-rank regime. Third, this worst-case per-task error is a better predictor of retained accuracy than the global error that SVD truncation minimizes. The third claim is empirical and is the one most likely to fail, so we test it first.

Research Program

The method has two parts.

Rounding. We tried to verify two conditions and could not settle them from the file alone. The first is whether every halving round satisfies the rank-versus-count condition of Bansal et al., which requires rank at most $M/\log^3 M$. The second is whether its polynomial-time procedure carries over to weighted, balanced colorings. In the late rounds, when few atoms remain, the condition clearly fails. We therefore plan a hybrid. The early rounds use a partial-coloring step built on the mirror-descent approach of A new framework for matrix discrepancy. That approach moves a fractional sign vector from zero toward $\pm 1$ while tracking a spectral potential. It also fixes signs a constant fraction at a time, as in the partial-coloring lemmas. Once the atom count is close to $R$, the last rounds switch to an exact small optimization.

A precise theorem statement is the first theoretical deliverable. It must address whether the rank-$2N$ dilated atoms satisfy the needed condition for the $M$ atoms that actually occur. The "compress or color" bound of Hopkins, Raghavendra and Shetty gives $O(\sqrt{n})$ under a Frobenius-norm condition instead of a rank condition. It serves as the fallback guarantee when atoms are high-rank after whitening by $C_k^{1/2}$.

Capacity diagnostic. Stack the whitened atoms and normalize their Gram matrix into a unit-trace positive semidefinite matrix $\rho$. Two quantum-autoencoder results then translate directly. Huang et al. show that compression is lossless exactly when the rank of $\rho$ is at most the latent dimension. Ma et al. show that achievable fidelity is set by the sum of the largest eigenvalues. Here the analogous quantity is the eigenvalue mass beyond index $R$. It lower-bounds the error any rank-$R$ consolidation can reach, whatever the rounding method. Tracking this tail as tasks arrive turns the vague question of how many tasks a single adapter can absorb into a measurable curve. Our prediction is that accuracy collapses on any method once the tail mass passes a threshold. Before that point, discrepancy rounding should beat randomized rounding by about the predicted factor. We present the quantum results as an analogy that supplies the right statistic. We do not claim the physics carries over.

Side memory. One honest limitation remains. Evaluating per-task norms requires some summary of each $C_k$. We store a rank-$s$ sketch of each covariance, which costs $O(N(m+n)s)$ memory at training time only. Inference parameters stay fixed at rank $R$. We report how results change with $s$. We also test an online variant that discards old sketches after a fixed window, following the sequential settings of Optimal Online Discrepancy Minimization and Online Algorithms and Lower Bounds for Average-Case Matrix Discrepancy.

Positioning

Three constant-memory methods motivate this work, and each relies on a heuristic at the point where we propose a guarantee. SLAO merges updates into one LoRA. It re-orthogonalizes one factor and decays the other by $1/\sqrt{i}$, but it gives no bound on the accumulated operator-norm drift and remains sensitive to task order. LoDA splits updates into shared and isolated subspaces using second-moment statistics, and it documents the "null space trap": forcing new updates into directions unused by old tasks blocks transfer. Our objective permits overlap between tasks and controls interference by norm, so it sidesteps that trap by construction. EWC-LoRA regularizes a single shared LoRA with Fisher information projected onto the product of its two factors, and its Fisher estimates go stale over long sequences.

TAK supplies part of our toolkit. It controls interference with Kronecker-factored curvature under a linearization assumption, and those Kronecker factors are an inexpensive replacement for our $C_k$ that we test directly.

Two papers constrain the design. SLAO's finding that the two LoRA factors behave asymmetrically suggests that atoms should come from the product $\Delta W$, not from either factor alone. Treating the factors symmetrically is a known failure mode.

Baselines

The naive reference is uniform averaging of task updates, scaled by one over the number of tasks. Its strongest published figure is TAK's report for naive task arithmetic: 80.2% absolute accuracy on the 8 Vision benchmark with CLIP ViT-B/16. At the other end, multi-branch LoRA keeps a separate frozen adapter for each task and receives oracle task identity. It grows linearly in memory, it defines the reference update $T$, and it gives an upper bound that no fixed-budget method should exceed.

The most direct competitor is rank-$R$ truncated SVD of $T$. It is optimal for the global operator norm, so it is exactly the method our per-task objective must beat. It needs no extra memory and no tuning.

The strongest published methods in the file are as follows. On ImageNet-A with 10 tasks, LoDA reports 62.59% last accuracy with a ViT backbone and EWC-LoRA reports 59.89% final accuracy with ViT-B/16. On the 8 Vision task-arithmetic benchmark, TAK reports 88.3% with ViT-B/16. For SLAO, no reported result found on Lacuna for any scalar on the 5-task text classification benchmark, the 15-task sequence, or SuperNI. We will rerun SLAO ourselves.

Fairness rules apply to every comparison. All methods share the same frozen backbone, the same per-task LoRA training (fixed rank, fixed steps, fixed seeds), and the same consolidation budget, measured as inference parameters of rank $R$. Every method gets the same hyperparameter search budget on a held-out ordering of tasks. Each result is averaged over at least five task orderings.

Two ablations isolate the key ingredients. The first keeps our fractional relaxation and per-task blocks but replaces discrepancy signs with independent random signs. This isolates the log-factor claim. The second keeps discrepancy rounding but uses only the global norm, without per-task blocks. This isolates the multi-norm objective.

We will count the proposal as successful under two conditions. On ImageNet-A, in the same 10-task setup, it must exceed truncated SVD and the random-sign ablation in last accuracy. It must also match or exceed LoDA's 62.59% within the spread across seeds. On long sequences, it must show a smaller gap from oracle multi-branch LoRA than SLAO and EWC-LoRA, with lower order sensitivity measured by maximum order-normalized performance disparity (MOPD) on SuperNI.

Why not just…?

Why not just keep one adapter per task, since adapters are small? For ten tasks, that is the right answer, and we report it as the upper bound. The case for consolidation rests on budget-limited regimes: hundreds of tasks, on-device deployment, or no reliable task identity at test time. In those regimes the routing machinery itself grows with the task count and adds latency, as CoPE discusses. If multi-branch LoRA with a learned router matches oracle routing at our longest horizons, the practical case narrows to strict memory budgets, and we will say so.

Why not just truncate the SVD of the summed update? It is optimal for one global norm and blind to which task each direction serves. Our first experiment checks whether that blindness costs anything. If the global SVD error predicts per-task accuracy loss as well as our block-maximum error does, then the multi-norm objective is unnecessary. We would then report a negative result, not change the metric after the fact.

Why not just optimize a rank-$R$ adapter directly by gradient descent on the maximum per-task error? This is the most serious threat. It targets the same objective and could match us in accuracy. We run it with an identical compute and tuning budget. If it matches, our contribution shrinks to a certified error bound and a capacity diagnostic, and the rounding procedure is no longer a better algorithm. If it falls behind, the likely causes are nonsmooth max-of-norms landscapes and dependence on initialization. Its variance across seeds will show which.

Why not just project each new update into the null space of past tasks? LoDA reports that this blocks positive transfer and exhausts capacity over long sequences, and its shared-plus-isolated split outperforms pure isolation. We include LoDA itself, not raw projection, as the stronger representative of this family.

Proposed Experiments

The decisive first check is predictive validity. On the 8 Vision task-arithmetic benchmark with CLIP ViT-B/16, we generate many consolidated adapters at varying ranks using several methods. For each, we measure the per-task operator-norm error and the per-task accuracy drop. We then compare rank correlations for three predictors: the block-maximum error, the global error, and TAK's curvature-weighted error. If the block-maximum error does not predict accuracy loss, we stop and report that.

The second check is the main comparison, run under the baseline protocol above. It covers ImageNet-A with 10 tasks, ImageNet-R with 20 tasks, CIFAR-100 with 10 tasks, the 5-task text classification benchmark, the 15-task GLUE/SuperGLUE/IMDB sequence, and SuperNI.

The third check tests the capacity law. We build long synthetic streams by concatenating the vision tasks with ImageNet-R splits, and sweep the budget $R$. We test whether the eigenvalue-tail statistic predicts the task count at which each method's accuracy falls off sharply.

The fourth check measures how close practice comes to theory. We plot the ratio of random-sign error to discrepancy-sign error against $\log(N(m+n))$ to see whether the predicted $\sqrt{\log}$ separation appears at realistic sizes, or whether the advantage is only a constant factor.