MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Authors: wang ning
Zekun Li
Tongxin Bai
Man Yao
Zhen Qin
Guoqi Li
Venue: ICML 2025 poster (2025)
Keywords: Fine-tune transformer to RNN; Linear attention; Linear Model;
Primary area: deep_learning->attention_mechanisms
TL;DR: Fine-tune transformer to RNN; Linear attention; Linear Model;

Abstract: Linear attention offers the advantages of linear inference time and fixed memory usage compared to Softmax attention. 
However, training large-scale language models with linear attention from scratch remains prohibitively expensive and exhibits significant performance gaps compared to Softmax-based models. 
To address these challenges, we focus on transforming pre-trained Softmax-based language models into linear attention models. 
We unify mainstream linear attention methods using a **high-order QK integration theory** and a **multi-level vocabulary decomposition**. 
Specifically, the QK integration theory explains the efficacy of combining linear and sparse attention from the perspective of information collection across different frequency bands. 
The multi-level vocabulary decomposition exponentially expands memory capacity by recursively exploiting compression loss from compressed states. 
Through detailed error analysis, we demonstrate superior approximation of Softmax attention achieved by our approach. 
To further improve performance and reduce training costs, we adopt a **soft integration strategy** with attention scores, effectively combining a sliding window mechanism. 
With less than 100M tokens, our method fine-tunes models to achieve linear complexity while retaining 99\% of their original performance. 
Compared to state-of-the-art linear attention model and method, our approach improves MMLU scores by 1.2 percentage points with minimal fine-tuning. 
Furthermore, even without the sliding window mechanism, our method achieves state-of-the-art performance on all test sets with 10B tokens.

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Ning Wang 123
Zekun Li 123 Tongxin Bai
Man Yao 12
Zhen Qin Guoqi Li
Abstract
1. Introduction
The attention mechanism has been the cornerstone of recent advancements in natural language processing, computer vision, and related fields. Current large language models (LLMs) (Touvron et al., 2023; Jiang et al., 2023) predomi- nantly leverage the Transformer architecture ( (Vaswani et al., 2017) with Softmax Attention, demonstrating remarkable performance. However, the Softmax Attention mechanism inherently suffers from quadratic complexity in both time and space during training. This issue is particularly pro- nounced during inference, where the KV cache grows lin- early with sequence length, leading to substantial compu- tational costs and memory overhead. These constraints significantly hinder efficient deployment in real-world ap- plications.
Linear attention offers the advantages of linear inference time and fixed memory usage com- pared to Softmax attention. However, training large-scale language models with linear atten- tion from scratch remains prohibitively expensive and exhibits significant performance gaps com- pared to Softmax-based models. To address these challenges, we focus on transforming pre-trained Softmax-based language models into linear atten- tion models. We unify mainstream linear attention methods using a high-order QK integration the- ory and multi-level vocabulary decomposition. Specifically, the QK integration theory explains the efficacy of combining linear and sparse atten- tion from the perspective of information collec- tion across different frequency bands. The multi- level vocabulary decomposition exponentially ex- pands memory capacity by recursively exploit- ing compression loss from compressed states. To further improve performance and reduce training costs, we adopt soft integration strategy with attention scores, effectively combining a sliding window mechanism. With less than 100M tokens, our method fine-tunes models to achieve linear complexity while retaining 99% of their original performance. Compared state-of-the-art linear attention model and method, our approach im- proves MMLU scores by 1.2 percentage points with minimal fine-tuning. Furthermore, even with- out the sliding window mechanism, our method achieves state-of-the art performance on all test sets with 1OB tokens.
To address this bottleneck, various linearized recursive mod- els (Zaheer et al., 2020; Katharopoulos et al., 2020; Chou et al., 2024; Zhang al., 2024b) have been proposed. These approaches aim to reduce the complexity of self-attention from quadratic to linear while keeping the KV cache size constant. This enables more efficient inference with fewer computational and memory resources. However, training linear model from scratch requires substantial resources and faces numerous challenges. Consequently, widely accepted and researched approach is to repurpose the pre- trained weights of Softmax iieettionbbasee LLMs into linear-complexity language models by fine-tuning (Kasai et al., 2021). This strategy not only conserves significant resources but also enables linear models to approach, and in some tasks surpass, the performance of their Softmax- based counterparts. The key to achieving this transformation lies in approximating Softmax Attention with minimal cost, either through functional or computational approximations.
Traditional linear attention models and state-space mod- els (SSMs) without gating mechanism, such as Lin- former (Wang al., 2020a), Performer (Choromanski et al., 2022). S4 (Gu al., 2022), RetNet (Sun al., 2023), and H3 (Fu et al., 2023), exhibit significant discrepancies from Softmax Attention due their inability to functionally ap- proximate the Softmax operation. This limitation makes it challenging to inherit pretrained weights. Recent re- search has introduced mechanisms such as gating to ap-
'qqual contribution 'Institute of Automation, Chinese Academy of Sciences "School of Artificial Intelligence, University of Chinese Academy of Sciences 'Bejjing Academy of Artifi- cial Intelligence TaapTap. Correspondence to: Tongxin Bai <txbai ac. Guoqi Li <guoqi.li@ia.ac.cn.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
proximate the functionality of Softmax Attention, leading to models like HGRN (Qin et al., 2023), Gated Linear At- tention (GLA) (Yang et al., 2024b), Gated Slot Attention (GSA) (Zhang et al., 2024b), Unified Optimal Linear Atten- tion (MetalA) (Chou et al., 2024), and Mamba (Gu & Dao, 2024). Among these, MetaLA provides a unified frame- work for analyzing existing linear models and demonstrates their potential for optimal approximation of Softmax At- observe that the model described above lacks the Softmax function's 's ability to capture both high-frequency and low-frequency information. By ana- lyzing the errors (appendix C) between Softmax Attention, GSA, and MetaLA, we find that GSA, due to its query- based compression of the key-value (KV) sequences, tends to focus on high-frequency information, or potentially in- troducing high-frequency noise. In contrast, the MetaLA family of linear attention methods primarily captures the low-frequency components of the original attention map. In addition, none of these methods efficiently enhance memory capacity, which could help reduce the error between linear models and Softmax Attention, which has infinite cache expansion.
restore LLM performance and save a lot of resources. However, these approaches often suffer from suboptimal convergence due to the significant gap between their linear models and Softmax Attention, and overfitting within the window. (3) Thus, we introduced SWA and solved the above problem. By maintaining both the key (K) and value (V) states, we retain the attention score during computation. This enables us to balance the historical information encoded by MVA with the current information from the SWA, named MVA-SW, achieving faster convergence, reduced resource requirements, and superior performance.
tention. However,
Using these methods, our linear model restores 99% of Mistral-7B's performance with fewer than 100M fine-tuning tokens. Compared to GSA, our MVA without using the sliding window outperforms it across all test sets using only half the training tokens.
perfooomma
2. Background and Preliminaries
2.1. Transformer
Transformer leverages Softmax Attention with uncom- pressed Key-Value (KV) cache. For an input sequence X E Raad the attention computation is defined as follows: Parallel Form:
Based on the above analysis, we propose three steps to continually reduce the error with Softmax Attention: (1) First, we propose using recursive sparse attention approach to focus on high-frequency information fitting, while em- ploying unified optimal linear attention to dominate the fitting of now-frequency information and suppress the high- frequency noise introduced by recursive sparse attention. In this way, we achieve unification and combination of re- cursive sparse attention and unified optimal linear attention. We refer to this approach of progressively combining differ- ent frequency bands as the Higher-Order QK Integration Theory. (2) After unifying the two most effective methods, we propose a unified approach for efficient memory capacity expansion: the Multi-Level Vocabulary Decomposition Method. All recursive attention mechanisms with linear complexity compress the infinitely growing KV sequences into fixed-size states, which inherently leads to information loss and error. By recursively compressing this error into a series of states, we achieve an exponential decrease in the expected error as the level increases. This results in a polynomial increase in memory capacity, significantly re- ducing the error compared to Softmax Attention. Compared to the Delta Rule, we store the Delta separately rather than directly adding it to the original state. We name the resulting attention mechanism MVA.
QKI VTTe
M 2) V,
O Attention Q2K, = Softmax
Recursive Form:
Kg = concat K2 kt),
Ve concat( concat(Ve-1,
!2 ddz
o Softmax
Vi
where Q = XW K = XWs, V = XW., with Q, K E Raxds and V Ruxd. M represents the mask, which is a causal mask for language models, i.c. lower triangular matrix filled with ones below the diagonal and -o elsewhere. In the recursive formulation, the subscript / denotes the input required for attention at timestep t. Specif- ically. K, E R Vi E Rixd, qt, kg E IR 1xds, and Dt 02 E R Ilxd.
The space and time complexity of training this formulation is quadratic. FlashAttention(Daao 2023) reduces the mem- ory complexity to nearly linear, but during inference, the KV cache size still grows linearly with sequence length, leading to significant memory overhead. This can even result in memory explosion for long sequences, making tasks infeasi- ble. Thus, various approaches, such as lincar attention and state-space models (SSMs), have been developed to address this issue by maintaining fixed-size state for inference.
Additionally, recent hybrid architectures such as Based (Arora et al., 2024), LoLCATs (Zhang et al., 2024a), and Distill to Mamba (Wang et al., 2025) offer promising solutions by combining sliding window attention (SWA) with linear attention or replacing specific layers of SSMs with attention mechanisms, which can significantly
2.2. Linear Attention
Linear Attention computes attention as follows:
2

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
(a)
(b)
(c)
MVD
HOI
MQVA-SW
K
K
B
An
Be
Ph
Wg
Be
MQVA
FO
FC)
(:)ss
SW
HOI
RO
(O)
V
MVD
k (0)
K
K (2)
Q
K (0)
B
A
Figure 1. (a) The Attention mechanism based on High-order QK integration (HOI), multi-level vocabulary decomposition (MVA) and sliding window attention (SW). (b) The original K and V sequences first decomposed to address the information loss caused by compressing them into fixed-size hidden states during recursion. By computing the difference between the original sequences and hidden states, estimate the information where QK sequences different orders are used for pseudo-querying and different frequencies information gathering. * element-wise multiplication, / element-wise division, @ is matrix multiplication.
and further compress it reduce this error. (c) is high-order QK integration Attention mechanism,
Parallel Form:
The gating mechanism provides input-dependent dynamic decay, emphasizing neighboring tokens and adjusting the decay size per step. This addresses attention dilution and im- proves the state update process with forgetting unimportant information.
0
Recursive Form:
St-1 + (bis) ot ot = d(:)).
2.2.2. META LINEAR ATTENTION (METALA)
MetaLA (Chou et al., 2024) unifies and optimizes linear attention with the following formulation:
where S. E xd,, Linear Attention maintains fixed- size state S,, achieving constant memory complexity during inference. However, it suffers from the issue of diluted atten- tion, where the model fails to focus effectively on relevant tokens. Many works address this by improving the function (Han et al., 2023; Choromanski et al., 2022) or introduc- ing additional mechanisms. Linear Attention also struggles to leverage positional biases (Su et al., 2023) that prioritize neighboring tokens and memory forgetting, leading to the development of Gated Linear Attention (GLA).
Parallel Form:
1 1-G
O = MetaLAA(Q,V.G) LA(Q o B, B .V) (2)
where B and G are defined as in GLA.
Recursive Form:
S. diag(oo) (1-
TT)T.e Te. or S..
2.2. 1. GATED LINEAR ATTENTION (GLA)
MetaLA uses fewer parameters while achieving superior performance. It can converge to existing Linear Attention, LinRNN, and SSM models under specific conditions. How- ever, MetaLA removes the K matrix. it introduces significant gap from Softmax Attention, hindering methods that rely on fine-tuning Softmax Attention weights. We pro- pose a solution to bridge this gap while unifying recursive sparse attention and delta-rule-ban mechanisms.
GLA (Yang et al., 2024b) introduces a gating mechanism to alleviate the limitations of Linear Attention:
Parallel Form:
K
0 GLA(Q, LA(Q B,
V).
(1)
B
where the 1-th row of B is defined as b, [1 Si. with being the i-th row of the gating matrix G = (XWW) Raxde
2.3. Recursive Sparse Attention
Recursive Form:
Recursive sparse attention compresses K and V se- quences incrementally. For example, Gated Slot Attention (GSA) (Zhang al., 2024b) is formulated as:
S. = diag(g:) k vz or S.S.
3

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Recursive Form:
hybrid architectures. Therefore, introduce hybrid attention mechanism with soft integration by attention scores that combines sliding window for processing current information and linear attention for handling historical infor- mation. By leveraging their respective attention scores, our method effectively balances contributions from historical and current information, further improving model perfor- mance on various tasks.
K,- (iag(s:) 1 (1 9 he, V. diag(se 1 (1 g+)
02 = Softmax V-
Parallel Form:
O= GSA(Q. K. V.G). GLA(SotmaxxGLA (Q. K. G.C,
(3)
3.1. High-order QK Integration
GSA retains the and V sequences, offering advantages for linearizing Softmax Attention while preserving its weights. Experimental results indicate that replacing Softmax with a perceptron (e.g., (-))) leads faster convergence and better performance. Our method also preserves K and V sequences while employing perceptron to replace Softmax, further incorporating a delta-rule-inspired mechanism to expand memory capacity exponentially.
In this section, we introduce the High-order QK Integra- tion Theory to unify and extend linear attention mecha- nisms, such as MetaLA, and recursively compressed atten- tion mechanisms, such as GSA. We begin by examining the original self-attention mechanism in full attention: eok'
Theorem 3.1. Given a self-attention mechanism expressed as e2KT the Taylor series expansion of the (i, -tt element is given by:
2.4. Delta Rule Memory Mechanism
Delta rule-based (Schlag et al., 2021) updates refine state transitions by querying existing states before updates:
eniy
Σ m!
(Bik)
Σ
Σ
II
(gaky))
sy!
m-
E
Fmn (aa) II (kgr))
Recursive Form:
nild k, = -g (ve-tigl)) ogld), or S.
Σ Fmo (1)) Ame, k) Ameu.
Kgt Amecki
The parallel form is detailed in related works. The delta rule updates states by incorporating only the new information, avoiding redundant accumulation.
where Amu E RR Xde is a matrix independent of and k and Fm,, (4:) = = o. Ams; q. T Ams.
This expansion reveals that attention scores can be expressed as higher-order terms of q and where the different pow- ers of h control the contributions from various frequency components. This observation is central to our high-order integration framework, where we explore how different fre- quencies of information can be selectively integrated.
3. Methodology
In this study, we propose two theoretical frameworks to ef- fectively integrate and extend existing linear attention mech- anisms (e.g., MetaLA) and recursive compression attention mechanisms (e.g.. Gated Slot Attention, GSA).
Next, we investigate the ability of linear models such as Metal. AA and recursively compressed attention models such as GSA to represent different types of information.
The first framework, termed High-order QK Integration Theory, introduces pseudo-queries of different orders, en- abling information collection varying frequencies while efficiently storing the retrieved information in the KV cache. This theoretical foundation provides unified perspective for integrating linear attention with recursive compression attention. Furthermore, inspired by the Delta Rule and the vocabulary decomposition techniques, we propose a Multi- level Quantized Vocabulary Decomposition method to efficiently enhance memory capacity.
Theorem 3.2 (High-order QK Integration). By indepen- dently setting different frequency components for queries (Q) and keys (K), linear models (e.g.. MetaLA) use low- frequency fixed polynomial Q queries over multi-frequency K polynomials, while recursive models (e.g., GSA) employ vurying-frequency polynomial Q queries over fixed K poly- nomials. This makes GSA more sensitive to high-frequency information. Thus, MetaLA's 's low treffreuency focus comple- ments GSA's 's figh-frey sensitivity, enabling a more balanced and effective attention mechanism.
To further substantiate our approach, we conduct error analysis comparing our method with full attention. The results demonstrate that the proposed techniques enable a more accurate approximation to full attention compared to existing methods. This improved approximation is particu- larly beneficial for the implementation of hybrid attention
Proof. We analyze the attention scores, temporarily neglect- ing the impact of Bn or treating B,, as learnale positional encodings and dynamic decay.

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
1. The calculation of linear attention can be expressed as:
3.2. Multi-level Vocabulary Decomposition
In recursive linear models, the challenge lies in efficiently compressing sequences that grow linearly into compact hid- den states. These models aim to retain critical information while minimizing memory requirements. Specifically, given the compressed states Kr = F(CK*) ) E mm and Vi E R=*d, some information from the original sequence is inevitably lost during the compression process. Here, C E mmxd is learnable matrix and K E x repre- sents the sequence of keys. The error introduced by this compression can be expressed as:
((gn) ((g))F(CK)))
If F is the identity function, the method reduces Linear Attention (LA). When F' takes non-linear form involving an exponential, such as I+e first-order information by propagating it all powers of K via fixed non-linear function.
_ in MetaLA, enhances the
Neglecting the denominator for simplicity, as its primary role is normalization (leaving more detailed analysis for future work). The (z. j)-th attention score of MetaLA is:
( = ((()) K("T) ")(? K((+) w (4)
E (Ca
Σ 11000
[Zoouw (Cw)
II (kx))
where S(A) is defined as:
S(A) {1 if Al the maximum in row
otherwise
where ((x) xW, the parameter W ensures that the shape of q is m. This formulation enables fixed Q query each frequency of K independently, effectively eliminating first-order approximation errors. By carefully designing (--) as a polynomial function, higher-order errors can also be mitigated. In addition, causal convolutions in these methods can be interpreted as zero-order integration.
The lost information compressed into K," where (0 is the original K. Iteratively applying this process, the error expectation can decay an exponential rate, by yielding series of states K(O)) (i S h, where h is the preset number of levels). Assuming a c-level recursion, the final error given by:
2. Similarly, the Gated Slot Attention (GSA) mechanism can be formulated as:
E = k(e+1) = (I-L)) = II x=0
L.)
II
W
(F(CK, F)CK),
2
(5)
Theorem 3.3 (Improved Memory Capacity). After recur- sions, the expected error E can be bounded as follows:
where ((qx) is replaced by Softmax(y,, (F,CKT Considering the numerator, while mitigating the impact of denominator by final linear mapping, the expanded form becomes, results in the expanded form:
| S E.
II Tb
Σ (Σ> al #1 Ai
> >..II.PAa < (TTtk.CT)) (P.(Cw)) "F,,))))) II (ka)
where 6 = n-m and J/a is determined by learnable param- elers that ensure convergence to a value less than 1.
amd
The analysis and proof are given in Appendix C.2.
By approximating Eizo Ko Co with an average ma- trix Ca, this can further rewritten as:
Theorem 3.3 demonstrates that the error can decrease at an exponential rate. Conversely, it also implies that the memory capacity can scale exponentially.
Σ Ar.
Σ
Σ Fol())) Ma
[I
II (C.) (C.))))F (C aww
The S-function in Equation 4 requires the use of the gather operation. However, consider replacing it with more efficient Softmax approximation. The term S(K (9) K (((()) can be implemented using two rounds of the GLA or GSA operator in parallel. Furthermore, multi-level parallelism can be combined with Equation 5 for implementation. To simplify and improve efficiency, we observe that replacing it with Softmax K KCTTCC or Softmax (CC yields comparable performance. The latter can be implemented using GLA(Softmax (KCT), G, K, G). Alternatively, a perceptron can approximate instead of Softmax.
Since s and u are at least 1, and C, represents at least second- order ky terms multiplied by k; itself, GSA primarily empha- sizes high-frreqence information from higher-order terms, while lacking adequate contributions from wwefrequency components. By integrating MetaLA, which complements these missing low-frequency details, more accurate approx- imation can be achieved, significantly reducing resource consumption and improving performance. For detailed er- ror analysis of GSA and its complementarity with MetaLA, please refer to the appendix C.
5

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
3.3. MVA
Further equivalence demonstrations with additional methods are provided in the appendix.
Using the theoretical foundations introduced above, we de- velop high-order QK Integration and multi-level vocab- ulary decomposition attention mechanism (MVA). In the experiment, we used a high-order QK integration method, where the low order is processed by a branch similar to Met- aLA and the high order is dominated by a branch similar to GSA, so that information of all frequencies can be processed more reasonably. The computation process is detailed as follows:
3.4. Integrating MVA with Sliding Window (MVA-SW)
To further enhance the proposed MVA method, we incorpo- rate the Sliding Window (SW) attention mechanism. The SW mechanism attention retains the distribution of the orig- inal attention, which allows us to significantly preserve performance while substantially reducing the training data required for convergence. Additionally, since our method reduces gap compared to Softmax, the historical attention scores retained are more consistent with the original atten- tion. Balancing the outputs of MVA and SW using the current and historical attention scores is thus both natural and reasonable. The computation process is detailed as follows:
k diag (1(9) (0())
[ +
(
v700 diag
(1)) (1) v (1- 10)
(9)
(9) (0) = Ut,
lit ((+1)) k/ ou
- w
K
Phictols @o ) ), Plga 0 (ark(t)) (
(6)
0, E, (iag(((()) (pp))) metala + (() [n(1)
out, Softmax (a((e(//))))))))) kt] ( mr]
p()) (9 (350) = a (c(ú) (1)
I+e
out,
- AAn)
whtt
pit
0r(x)= = x. (x(xx) =
E. plss
Be Bo + 3/.
Bn
output = diag
out, + diag
out,
Bo + Bn
Where C(0) Rdyxda For the explicit low-order branch, a ge E Rdd is applied to adjust its con-
weight matrix W tribution. This branch can fully replicate the core operation of MetaLA. For the high-order branch, we utilize a layer of perceptron to replace the Softmax function in GSA and a weight matrix ((()) E Rd, to adjust attention scores and determine its contribution, equivalent to the role of GSA. For vocabulary decomposition, we adopt the second parallelizable method:
where
B. exp(a:(k(tt-w) ) Ra,
(11)
Bn GLA(g + xla)), G,Iv,G)W
(12)
where Wa. E Rd.x1 and Ra E Rs=x1, And, Br. corre-
sponds to a weighted summation over the attention map:
Softmax KW(())
(1)
kc Ke;
W E IRde
((Softmax K,],,, WWs + (l.)))A.11 - An)))
The parameters W ((() wr(l are shared across all heads, resulting in a total parameter count of 3 x d x d, where d denotes the head dimension. Future work will consider introducing per-head parameters.
The process of balancing historical and current information based on the attention scores closely aligns with the behavior of the original attention mechanism. This alignment further reduces the approximation error, ensuring a more faithful representation of the original attention while preserving computational efficiency.
To further simplify, we express this as a linear attention operator. Leveraging the GLA operator notation, the process is as follows:
4. Experiments
Or = MVA A (0-m)) (0-m) C, Ws, Who: Wge): 2
In this work, we explore inheriting LLM weights and con- verting them into linear models. Specifically, we adopt the Mistral-7B model as the base LLM and evaluate the perfor- mance of MVA-SW and MVA. We use the In-evaluation- harness (Gao et al., 2024) tool to perform the test. For fine-tuning, we utilize LoRA (Hu et al., 2021) to achieve efficient fine-tuning, significantly reducing computational resources.
Iks. GLA(A, (0) ,11 1.0 (00((( (H 1), (1(2)))
PMetaLA, Gy ge POSA, = o !
0r = GLAA(Pmetala, + Pgssa: (1 - (1())) 1), (49))
6+tD - M400 GLA( W(2) (1 ))
Where i refers to the i-th level. Specific cases of MVA
reduce to well-known methods:
Metal MVA (gt, (0)) (0) (0)) (,,,,,00,0 0,0,7), T),
(9)
For MVA, we compare with the of GSA, as well as GLA, RetNet, and SUPRA (Mercat et al., 2024). which were benchmarked in the GSA paper. For MVA-SW, we
GSA- MVA (0) (0)
12 (()) 0,0. (10)
6

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Table 1. MVA-SW fine-tuning results.
Performance comparison across various 7B models. & denotes models using softmax-attention. denotes our results.
Size
Tokens
ARC,
ARC.
Hella.
PIQA
Wino.
NQ
TriviaQA
MMLU
Avg.
Shot(s)
5
5
Models trained from scratch (for reférence)
RWKV6
7B
1.4T
73.6
44.0
75.2
78.4
68.5
20.9
59.5
43.9
58.0
Mamba
7B
1.2T
77.6
46.8
77.8
72.3
25.4
66.2
33.2
60.0
Llama24
76.4
46.2
76.0
26.0
64.2
45.5
60.2
Gemma
81.5
74.0
24.3
63.7
63,2
65.0
Mistral
7B
80.8
54.0
81.1
80.6
74.0
29.7
70.3
62.4
66.6
Models finetuned from Mistral
SW-1281
+0.1B
80.1
73.8
28.6
69.8
52.1
65.0
GLA-SW-128f
+0.1B
75.4
46.7
74.4
78.5
64.0
13.9
49.2
30.2
54.1
GSA-SW-128F
7B
+0.1B
79.9
53,4
80.5
81.7
73.9
29.0
69.8
54.5
65.3
MVusSW(Ours)
7B
+0.1B
80.5
54.3
80.8
82.0
74.0
29.6
70.1
57.1
66.1
(OurS)(Oursf
7B
+2B
80.7
54.4
81.2
82.0
73.8
24.7
70.2
57.3
66.2
Furthermore, compared GSA and GLA, our approach achieves better performance recovery due to its smaller error relative Softmax Attention and the rationality of the soft combination mechanism. If continue training a large number of tokens we consider turning off the parameters of QKV and only consider the additional parameters introduced by training LA or truncating the reverse gradient information of SW and update only the information of LA. We froze the weights of QKV to train only the linear part to 2B tokens and its performance was slightly improved.
Table Performance comparison between Qwen2.5 models and their MVA-SW converted versions on MMLU, PIQA, and Hel- laswag benchmarks. Missing values are marked with "-".
Model
MMLU
PIQA
Hellaswag
1MMBB.5-
80.7
85.2
87.3
>> MVA-SW (14B)
77.3
83.8
86.8
Qwen2.5-32B
83.9
85.2
> MVA-SW (32B)
79.8
82.5
85.0
compare with LoLCATs, using identical fine-tuning parame- ters and window sizes for a fair comparison. In addition, we conduct experiments with GSA and GLAA combined with the sliding window, using different fine-tuning parameter configurations for a comparative study with our method.
4.2. Comparison with LoLCAT'
This experiment compares MVA-SW with LoLCATs. Un- like LoLCAT's, which require two-stage process, method achieves comparable performance using a sim- ple soft combination mechanism and straightforward fine- tuning. The experimental configuration matches Lol .CAT's, with a window size of 64. LoRA fine-tuning is applied to the QKV mapping parameters with a rank of 8. For MVA- specific parameters, full fine-tuning is applied, while other parameters remain frozen. The training length is 1K with learning rate of x 10-4 and batch size of 32K tokens. The results are presented in Table 3. In addition, we also investigated the effect of different fine-tuned datasets on MVA-SW and compared them with LoLCATs, as shown in Table Our method requires only half the fine-tuning tokens to outperform LoLCAT' on the MMLU tasks.
4.1. MVA-SW
This section evaluates MVA-SW with attention scores bal- ancing approach. The integration follows the soft combina- tion method described in Section 3.4, with a window size equal to the head dimension (thead = 128). This ensures that the computational complexity of adding the sliding window remains equivalent to linear Attention (O(nd)) while pre- serving more of the model's performance. For fine-tuning, use LoRA with the QKV mapping and FFN down proj parameters, setting the rank to 128, alternatively, tuning only the QKV mapping with rank of 8. Additionally, all parameters introduced by the linear attention part of MVA- SW are fine-tuned, while other parameters remain frozen. Optimization is performed using AdamW with a cosine learning rate schedule, an initial learning rate of x 10-5 20 steps of linear warmup, and training length of 1.5K due to GPU memory constraints, with batch size of M tokens. The dataset used is the SlimPajama corpus. The results are shown in Table and Table 2.
4.3. MVA
We replace the Attention mechanism in the Mistral model with MVA (MVA-SW without SWA), leaving the other com- ponents unchanged. The LoRA fine-tuning applied the QKV weights and the down-proj parameters in FFN, with rank of 256. In addition, we unfreeze the embedding and normalization parameters while keeping all other parame- ters frozen. The optimization uses Adam with a cosine learning rate schedule, an initial learning rate of 8 x 10-5
The results demonstrate that our method can recover most of the model's performance with a small number of tokens.

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Table 3.
Comparison hetween MVA-SW and Col.CATs.
Medd
Training Takens (B)
PigA
ARC-e
ARC- (morm)
HellaSwag (aurm))
Winggradee
MMLU (S-hot)
Asg.
Asg. (no MMLUU
Mastra TUI
K1.1
MI9
51.
$1.0
70.0
624
72.4
74.4
Mistnl TB SUPRA
100
904
73.9
43.8
77.1
70.3
34.2
64.0
09.9
Mistnl TN at CATs
0.04
81.5
81.7
549
80.7
74.0
514
70.7
74.5
Mistral 7B MW (Ours)
0.12
X2.
906
538
50.5
74,5
526
7088
74.4
Table 4. Performance comparison Alpaca- Clean and RedPajama datasets. All models derived from Mistral-7B.
Model
Training Data
PIQA
ARC-e
ARC-c
HellaSwag
Wino-grande
MMLU
Avg.
Avg. (w/ MMLU)
Mistral-7B (v0.1)
82.1
80.9
53.8
81.0
74.0
62.4
72.4
74.4
+ LoLCATs (rank=8)
AlpacaClcan (+40M)
81.5
81.7
$4,9
80.7
74.0
51.4
70.7
74,5
LoLCATs (rank-8)
RedPajama (+40M)
77.6
49.0
80.3
71.7
53.2
68.6
71.7
MVA-SW (rank=32)
AlpacaClean (+20M)
82.1
81.5
54.7
8122
74.1
52.2
70.7
74.4
-) MVA-SW (rank=8)
AlpacaClean (+40M)
82.3
81,9
57.6
80,2
74.0
51.6
71.2
75.2
MVA-SW (rank=8)
RedPajama (+40M)
82.5
81.5
55.7
79.7
72.9
52.4
70.8
74.5
Table 5. MVA (MVA-SW without SW) fine-tuning results with inherited Mistral model weights.
Performance comparison across various 7B models. & denotes models using softmax--tteeniinn denotes our results.
Size
Tokens
ARC,
ARC.
Hella.
PIQA
Wino.
NQ
TriviaQA
MMLU
Avg.
Shot(s)
0
0
0
0
5
5
5
Models trained from scratck (for reference)
Mistral
7B
80.8
54.0
81.1
80.6
74.0
29.7
70.3
62.4
66.6
Models finetuned from Mistral
7B
SUPRA
7B
+20B
74.6
42.3
74.8
80.1
67.4
28.0
RetNet
7B
+20B
73.3
39.9
72.9
77.8
66.1
16.2
43.0
26.1
51.9
GLA
7B
+20B
74.6
44.0
75.9
74.2
69.5
22.2
57.8
28.4
56.5
GSA
7B
+20B
75.9
43.9
76.5
78.7
70.1
23.4
60.7
32.4
$7.7
MVA(Ours)f
7B
+2.5B
75.7
44.9
76.0
80.4
69.7
21.2
59.1
30,2
57.2
MVA(Ours)f
7B
+10B
78.3
47.5
78.1
80.5
72.1
25.9
65.9
34.4
60.3
200 steps of linear warm-up, and a training length of 2K steps with a batch size 0.5M tokens. The dataset used is the SlimPajama (Soboleva al., 2023) corpus. The results shown Table 5.
Table 6. Inference efficiency comparison of MVA, GSA, and FlashAttention under different sequence lengths. OOM indicates out-of-memory errors.
Full Inf (6)
Full Inf
Pretill (s)
Lateney (msctoken)
Total
Seq Len
(GB)
Our MVA method achieves performance comparable to state-of-the-an art GSA after tne-tuning with 2.5B tokens. Af- ter fine-tuning with 1OB tokens, MVA surpasses GSA in all tasks. This demonstrates that our MVA introduces smaller errors compared to GSA and GLA, enabling a rapid recovery of the original Attention's performance. The effectiveness of this observation is further supported by ablation studies.
4K
0.14
0.77
0.125
98.8
15.32
8K
0.26
1,53
0.249
60.3
16.58
MVA
32K
16K
3.06
0.508
78.8
19.08
128K
5.08
24.44
7.156
58.1
54.14
4K
0.10
0.76
0.077
93.2
15.30
SK
1,53
0.153
10.9
16.55
16K
32K
6.11
24.07
64K
1.29
12.22
1,293
90.2
34,08
128K
2.66
24.44
5,102
38.7
$4,11
4K
0.05
1,26
0.056
21.7
L5.79
4.4. MVA Inference Efficiency
XK
16K
0.287
Table demonstrates the inference efficiency of MVA. In terms of memory consumption, MVA performs comparably to GSA. However, due to its vocabulary decomposition re- quirement, MVA exhibits slightly higher generation latency than GSA. A. Notably, both MVA and GSA significantly out- perform FlashAttention in all efficiency metrics and memory usage when the sequence length reaches 64K.
Attention
64K
32K
0.75
2.19
20.22
10.11
2,208
0.750
220.4
92.4
33.55
53.57
128K
00M
tention, while reducing the training resources. However, the standalone sliding window limited by its window size. Integrating MVA enhances its performance, achieving at least 5-point improvement MMLU tasks.
4.5. Ablation Studies
We investigate the contributions of hierarchical integration and multi-level vocabulary decomposition. First, replacing the Softmax function in GSA with a perceptron signifi- cantly improves performance. Integrating MetaLA further enhances performance, with our hierarchical integration out-
Finally, we examine the impact of incorporating the sliding window. The results show that adding a sliding window significantly preserves the performance of the original At-
8

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
behaviors allow our method exploit both perspectives for enhanced performance. In addition, multi-level vocabulary decomposition recursively reduces information loss, achiev- ing exponential memory capacity expansion and improving approximation accuracy for high-rank matrices.
Table Impact of sliding window on MVA-SW performance.
Component
MMLU
MVA-SW (soft bond)
57.1
MVA-SW (hard bond)
53.2
Sliding Window Only noSW
51.9
MVA outperforms GSA by 2.3 points with only half the training resources and consistently excels across all test sets. Unlike LoLCATs two steps, MVA-SW simplifies fine-tuning and achieves superior MMLU performance with fewer train- ing tokens, demonstrating its efficiency and effectiveness.
25.0
performing both GSA and MetaLA, achieving at least 3.3-point improvement ARC-Challenge and 0.9-poin improvement on ARC-Easy. Finally, replacing the mem- ory strategy with multi-level vocabulary decomposition fur- ther boosts performance, yielding a 1.9-point gain on ARC- Challenge and a 3.2-point gain on ARC-Easy. The results
Impact Statement
This paper presents work whose goal to transform pre- trained Softmax-based language models into linear attention models. This transformation technique utilises lower costs to train more efficient language models. Therefore this tech- nique might help democratize access of language models. Whether the efficient transformation would affect known problems, such as biased and harmful outputs of language models remains an unexplored research question.
Table 8. Ablation study results on ARC dataset. The table com- pares different methods and their performance on ARC, as well as the token budget (in billions). VD means vocabulary decomposi- tion.
Method
are cchallengge
arc.rasy
Tokens (li)
MVA w/3 3 order (GSA)
0,3389
0.6596
0.8
MVA w/ 3 order (GSA)
0.3763
0.6949
2.0
MVA 3 order (GSA-sigmoid)
0,3407
0.6732
0.8
Acknowledgements
MVA order (MetaLA)
0.3527
0.6987
0.8
MVA wfo VD (GSA+MetaLA)
0,3857
0.7075
0.8
This research is supported by the National Science and Technology Major Project of China (2022ZD0116316 16316),, This work was partially supported by National Natu- ral Science Foundation of China (62325603, 62236009, U22A20103), CAS Project for Young Scientists in Basic Research (YSBR-116), Beijing Science and Technology Plan (Z241 100004224011) 1). We also thankful to all the reviewers for their insightful comments and rigorous evaluation.
MVA VD (attn((,mk,mk))
0,3906
0.7210
0.8
MVA w/ VD (delta rule-like)
0.4044
0.7391
0.8
indicate that our method effectively combines the strengths of GSA and MetaLA, achieving substantial performance im- provements. Multi-level vocabulary decomposition further reduces the error relative to Softmax Attention.
Table Performance comparison of different models. Attention replacing Mistral-7B with training length of 2K and a gradient accumulation 128. VD means vocabulary decomposition and we 2-1evel word list decomposition.
References
Arora, S., Eyuboglu, S., Zhang, M., Timalsina, A., Alberti, S., Zinsley, D., Zou, J., Rudra, A., and Ré, C. Sim- ple linear attention language models balance the recall- throughput tradeoff, 2024. URL mittps://arae org/ abs /2w.2 18668.
Method
Memory Usage (GPU)
Time per Iteration
MetaLA
36317MiB
75.08 s/it
GSA
37619 MiB
81.67 sfit
MVA w/o VD
38885 MiB
82.18 sfit
MVA w/ VD
40096 MiB
105.79 s/it
Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The longmdocument transformer, 2020.
5. Conclusion
Child, R., Gray, S., Radford, A., and Sutskever, Gen- erating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019.
We propose a unified linear attention framework that in- tegrates MetaLA, GSA, and Delta Rule-inspired methods using oigh- QK integration and multi-level vocabulary decomposition theories.
Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., Belanger, D.. Colwell, L., and Weller, A. Rethinking attention with performers, 2022.
The high-order QK integration theory reveals that GSA fo- cuses on high-frequency information through higher-order QK-terms, while MetaLA captures low- www-ureuencyy informa- tion using lower-order -teems.. These complementary
Chou, Y., Yao, M., Wang, K., Pan, Y., Zhu, R., Zhong, Y.,
9

---

A., Foster, C., Golding, L., Hsu, J., Le Noac'h, A., Li, H., McDonell, K., Muennighoff, N., Ociepa, C., Phang, J., Reynolds, I.., Schoelkopf, H., Skowron, A., Sutawika, L., Tang, E., Thite, A., Wang, B., Wang, K., and Zou, A. A framework for few-shot language model evaluation, prggrrecords/ MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Qiao, Y., Wu, J. Xu, B., and Li, G. Metala: Unified opti- mal linear approximation softmax attention map, 2024. URL https::p///.mm /apps://arae aaaiiviiiii.i/.iia/aaaaaaaaaaeva /ttrg//bs/4411..4...
Jiang, A. Q.. Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., de las Casas, D., Bressand, F,, Lengyel, G., Lample, G., Saulnier, L., Lavaud, L. R., Lachaux, M.- A., Stock, P., Scao, T. L., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. Mistral 7b, 2023. URL https: //arxiv. org wwt//a/g////eeoee///..//eeeeeee/ aaa/a/a/333110 06825.
Dao, T. Flashattention-2: Faster attention with better par- allelism and work partitioniing, 2023. URL https: //arxiv.. orgg abs /tsb//2337 2307 08691.
Kasai, J., Peng, H., Zhang, Y., Yogatama, D., Ilharco, G., Puppas, N., Mao, Y., Chen, W., and Smith, N. A. Fine- tuning pretrained transformers into mns, 2021. URL https://azxiv.r http://axiiiiorra//////3333 13307
De, S., Smith, S. I.., Fernando, A., Botev, A., Cristian- Muraru, G., Gu, A., Haroun, R., Berrada, L.,, Chen, Y., Srinivasan, S., Desjardins, G., Doucet, A., Budden, D.,
Teh, Y. W., Pascanu, R., Freitas, N. D., and Gulcehre, C. Griffin: Mixing gated linear recurrences with lo- attention for efficient language models, 2024, URL https::/ //arxiv org/ abs/ 2402 19427.
Katharopoulos, A., Vyas, A., Pappas. N., and Fleuret, F. Transformers mns:: Fast autoregressive transformers with linear attention, 2020. URL https://arxiv
org/ abs 2006 16236.
Fu, D. Y., Dao, I., Saab, K. K., Thomas, A. W., Rudra, A., and Ré, C. Hungry hungry hippos: Towards language modeling with state space models, 2023. URL https:
Kitaev, N., Kaiser, E.,, and Levskaya, A. Reformer: The efficient transformer. In Proceedings of the International Conference on Learning Representations, 2020.
//arxiv. org/ abs/ 2212222111 14052.
Gao, L., Tow, Abbasi, B., Biderman. S., Black, S., DiPofi,
Mercat, J., Vasiljevic, I., Keh, S., Arora, K., Dave, A., Gaidon, A., and Kollar, T. Linearizing large language models, 2024. URL https: attpps:/arxiv..or htt/iaxxvvvvrr.//e.e /abs/ 2405.06648
Mohtashami, A. and Jaggi, M. Landmark attention: Random-access infinite context length for transform- ers, 2023. URL wwtthhttt///areeeee www.w/.rrggbb/bbeee 16300.
07 2024. URL //ttps::/zeenne 6060660..
Gu, A. and Dao, T. Mamba: Linear-time sequence mod- eling with selective state spaces, 2024. URL https: // //arxiv.oro abs/ 2abs/2300 2312. 00752.
Peng, B., Alcaide, E., Anthony, Q. Albalak, A., Arcadinho, S., Biderman, S., Cao, H., Cheng, X., Chung, M., Grella,
M., GV, K. K., He, X., Hou, H., Lin, J., Kazienko. P., Kocon, J.. Kong, J., Koptyra, B., Lau, H., Mantri, K. S. I., Mom, F., Saito, A., Song, G., Tang, X., Wang, B., Wind, J. S., Wozniak, S., Zhang, R., Zhang, Z., Zhao, Q., Zhou, P., Zhou, Q., Zhu, J., and Zhu, R.-J. Rwkv: Reinventing mns for the transformer era, 2023. URL bttps://arxiv.com wttp:o/p/abb....0000/00
Gu, A., Goel, K., and Ré, C. Efficiently modeling long sequences with structured state spaces, 2022. URL https://aad //axxiv../ivv///aa org/ abs/21l1 00396.
Gupta, A., Gu, A., and Berant, J. Diagonal state spaces are as effective as structured state spaces, 2022. URL ht https: / /aaxiiiii.. wwweiiioorrg//// abs////////// 2203. 4343.
Han, D., Pan. X., Han, Y.. Song, S., and Huang. G. Flatten transformer: Vision transformer using focused linear at- tention. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 5961-5971, October 2023.
Peng. H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N. A., and Kong, L. Random feature attention, 2021.
Peng, H., Kasai, J., Pappas, N., Yogatama, D., Wu, Z., Kong, L., Schwartz, R. and Smith, N. A. Abe: Attention with bounded-memory control, 2022. URL https:// arxiv. sxxiv.org/abs.t..o..o /21p/
Hanada, H., Hashimoto, N., Taji, K., and Takeuchi, Generalized low-rank update: Model parameter bounds for low-rank training data modifications, 2023. URL https: /awvv//rivvv.//////////eae//aaaa org/ abs /200..236...2 12670.
Qin, Z. Han, X., Sun, W., Li, D., Kong, L., Bares, N., and Zhong, Y. The devil linear transformer, 2022. URL https /ttp://aaxvv.v/. org/
10340.
Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang. S., Wang, L., and Chen, W. Lora: Low-rank adaptation of large language models, 2021. URL https: : /arxiiv. org/abss 2106.0000 0 09685.
Qin, Z., Yang, S., and Zhong, Hierarchically gated recur- rent neural network for sequence modeling, 2023. URL 04823.
24823
10

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Roy, A., Saffar, M., Vaswani, A., and Grangier, D. Efficient content-based sparse attention with routing transform- ers, 2020. URL https: http///axvvvv.ooooo www.aaiww......o.aooooooo wrtp://///aabb........o// 05997.
Wang, J., Paliotta, D., May, A., Rush, A. M., and Dao, T. The mamba in the Ilama: Distilling and accelerating hybrid models, 2025, URL https: atttps://arae http///axvvv.ooo abs 0ts/2408.1522
Schlag, I., Irie, K., and Schmidhuber, J. Linear transform- ers are secretly fast weight programmers, 2021. URL https: http://aaxvv.voo wttg/bs///a 2012.1012..0 11174.
Wang. S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity, 2020a.
Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity, 2020b, URL https: : http//axxvv..gggga.. 2206. 047688.0004.....
Shen, Z., Zhou, Y., Bai, R., and Li, J. Kernelized self- attention for generating long sequences. In arXiv preprint arXiv:2106. 132544 2021.
Yang, S., Kautz, J., and Hatamizadeh, A. Gated delta net- works: Improving mamba2 with delta rule, 2024a. URL 06464.
Smith, J. T. H., Warrington, A., and Linderman, S. W. Sim- plified state space layers for sequence modeling, 2023.
URL https:://// /att///axxie araai.iivv..... org/ abs/2208. 04933.
Yang. S., Wang. B., Shen, Y., Panda, R., and Kim, Y. Gated linear attention transformers with hardware-efficient training, 2024b. URL https: //aa/aavvvorrgro /bss/ 2312.06635.
Soboleva, D., Al-Khateeb, F., Myers, R., Steeves, J. R.,
Hestmess, J., and Dey, N. SlimPajama: A 627B token cleaned and deduplicated version of Red- Pajama. https: wttpww/.rrbbaaaa... www.eeebbaaa.ee/bogggg......
Yang, Wang, B., Zhang Y., Shen, Y., and Kim, Y. Par- &te rs1 110 - -rdd 1anan slimpajame 6276-22---- -amma-a-627bboo-eee (2eb-tooke--ceeanee--ee and- dedup allelizing linear transformers with the dent rule over se- the
2023. URL https:/
quence length, 2025. URL https: httpss://axxtt /arxiv..rgg//////............. abs abs/2406, 06484.
6627
Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding, 2023. /ttttts:///aiiiiie org/ abs/ 09864.
Yue, Z., Wang. Y., He, Z., Zeng, H., McAuley, J., and Wang, D. Linear recurrent units for sequential recommenda- tion, 2023. URL https: //tp://aaivvv.v/ org/ org/abs/220 abs/2310, 02367.
Sun, Y., Dong, L., Huang, S., Ma, S., Xia, Y., Xue, J., Wang, J., and Wei, F. Retentive network: A successor to transformer for large language models, 2023. URL https:
Yun, H., Han, W., and Kim, J. Global context transformer: The power of the word embeddings. In arXiv preprint arXiv:2106.0966 09600, 2021.
/atps://aaxxtee /ttp///aavvvv/aaa//ea/eeeeeaaava org/ abs///bs//// 2200. 08621.
Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q. Yang, L., and Ahmed, A. Big bird: Transformers for longer sequences. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin. H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17283-17297, Curran Associates, Inc., 2020. URL httpp:: hewp:rrocc..einnn...n....e.e..e. cc cc/sapee__iileepppprr/////// c8512a1 cc512211222244477551118823333333 pdf.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, I.., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I. Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R. Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, X., Xu, P., Yan, Z., Zarov, Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine-tuned chat models, 2023.
neurips.
Zhang, M., Arora, S., Chalamala, R., Wu, A., Spector, B., Singhal, A., Ramesh, K., and Ré, C. Lolcats: On low- rank linearizing of large language models, 2024a. URL https: httpss://aaxvvvcoo .rg/ abs / 2410.11.1 10254.
Zhang, Y., Yang, S., Zhu, R., Zhang. Y., Cui, L., Wang, Y., Wang, B., Shi, F., Wang, B., Bi, W., Zhou, P., and Fu, G. Gated slot attention for efficient linear-time sequence modeling, 2024b. URL https: // /arxivvv org. aba/ 2409.07
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L.., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems, pp. 1998-6008 2017.

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Zhu, L., Wang, X., Ke, Z., Zhang, W., and Lau, R. W. Biformer: Vision transformer with bi-level routing atten- tion. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), Pp. 10323-10333, June 2023.
12

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Table 10. Performance comparison long-context henchmarks (Qasper, NarrativeQA, QMSum). Top section shows models trained from scratch; bottom section shows methods fine-tund tuned from Mistral-7B.
Model
Qasper
NarrativeQA
QMSum
Models Trained from Scratch
RWKV6
9.2
14.4
1.1
Mamba
5.6
27.9
0.8
Mistral
25.8
25.1
5.0
Fine-tuned from Mistral-7B (20B tokens)
RetNet
11.1
0.0
0.0
GLA
18.4
17.2
9.0
GSA
18.8
19.2
10.0
MVA
20.7
20.4
GSA
MetaLA
MVA-1 level (no vocabulary decomposition)
MVA-2 level
Figure 2. Speed of convergence for different models.
A. Fine-tuning the loss curve
In this subsection, we show the convergence speed of MVA, MVA (wordless table decomposition), GSA, and Metal.A, as shown in Figure 2, it is obvious that the convergence speed of MVA is very fast and much better than GSA.In addition, we show the loss of the whole fine-tuning process of MVA, and our method is very stable in the fine-tuning process and the convergence tendency is very obvious, as shown in Figure 3.
A.1. MVA performance on long sequence tasks
We compared them on the long sequence tasks listed by GSA, as shown in Table 10.
B. Related Work
B.I. Linear Attention
Full attention in Transformers (Vaswani et al., 2017) and other efficient Attention (Zaheer al., 2020: Roy al., 2020; Mohtashami & Jaggi, 2023; Zhu et al., 2023; Kitaev et al., 2020; Child al., 2019; Yun al., 2021: Beltagy al., 2020) that can't be recursive requires KV cache that scales linearly with sequence length, resulting in significant computational and memory overhead during inference for long sequences. This limitation often makes it infeasible to process extremely long sequences. Linear attention (LA) (Katharopoulos et al., 2020; Shen et al., 2021) addresses this issue by replacing the softmax operation in attention with a kernel function and reordering operations. Specifically, it first computes Φ(K)V to obtain a fixed-size state S, and then computes ((Q) to produce the output. This method achieves linear complexity and
13

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
train/loss
MVA-noSW-10D
10
Step
0
5k
10k
15k
20k
Figure 3. Fine-tuned loss curves for MVA based Mistral-7B modeling.
enables inference with a fixed-size state, regardless of sequence length, by maintaining the state recursively.
However, linear attention has several issues, including insufficient focus on relevant tokens, the inability to crase outdated information during state updates, and lack of bias toward closer tokens. To address these problems, Gated Linear Attention (GLA) reintroduced gating mechanisms. During state updates, the gate selectively erases irrelevant information before incorporating data, which also introduces dynamic decay mechanism to emphasize local information. GLA parameterizes many linear Attention, SSM models, and other well-designed recursive models into their GLA form for uniform system-leve optimization. Building on GLA, MetaLA analyzed existing linear models, classifing current linear models into three categories: the LinFormer (Sun et al., 2023; Wang et al., 2020h; Qin et al., 2022), SSM (Gu & Dao, 2024; Gupta et al., 2022; Smith et al., 2023; Fu et al., 2023), and LinRNN (De et al., 2024; Hanada et al., 2023) and proposed four necessary conditions for optimal linear approximations to softmax attention. Based on these conditions, MetaLA achieves state-of-the-att performance among linear models.
Other approaches, such Flatten Transformer (Han al., 2023) and Performer (Peng et al., 2021), explore alternative kernel functions replace softmax for more focused attention. Additionally, non-attention architectures like SSM-based models (e.g., S4. H3 (Fu et al., 2023)), RetNet (Sun et al., 2023), RWKV-4 (Peng et al.. 2023), and HGRN (Qin et al., 2023), as well as LRU (Yue et al., 2023), can be viewed as special cases of GLA or MetaLA. some scenarios, these models converge to MetaLA. Despite these advancements, linear attention models often suffer from lack of figh-freuuency information, corresponding to the higher-order terms in the Taylor expansion of softmax. This limitation creates a significant gap with softmax attention, hindering their compatibility with existing LLM weights for fine-tuning. Consequently, recent research focuses on developing linear models that retain softmax while enabling recursive mechanisms.
B.2. Sparse Attention
Sparse attention methods, such as ABC and Gated Slot Attention (GSA) (Zhang et al., 2024b), retain the softmax function, preserving most of the frequency information in Q and K and achieving closer approximations to full softmax attention. ABC (Peng et al., 2022) introduces learnable pseudo-queries for compressing the KV sequences, storing fixed-size states. However, it lacks mechanisms to erase irrelevant information, leading to accumulation of unnecessary data. GSA addresses this by incorporating gating mechanism in the KV state updates, enabling controlled writes to the state and more efficient compression.
Although sparse attention methods approximate softmax more effectively, they lack sufficient freeueeyency information,
14

---

MVA: Lincar Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
introducing non-negligible errors. Combining linear and sparse attention approaches further reduce the gap with softmax attention. However, both approaches face challenges in efficiently expanding memory capacity. Inspired by the Delta Rule, our work introduces a mechanism to dynamically expand memory capacity.
B.3. Delta Rule Methods
Fast Weight Programmers (Schlag et al., 2021) proposed precise update mechanism that first queries the previous state using the current K, removes the queried information from the current input, and updates only with new information. This maximizes utilization of the limited state space. Parallels Delta Rule (Yang et al., 2025; 2024a) further parallelized this mechanism, significantly improving training speed.
B.4. Transformer-to-RNi Conversion
Linear models offer substantial advantages over full attention, including fixed-size state space and faster inference for longer tasks. However, training linear models from scratch demands significant resources. Transformer-to-NNe (T2R) (Kasai et al., 2021) conversion addresses this by fine-tuning existing LLM weights with softmax attention to transform them into linear models. Notable methods, such as SUPRA (Mereat al., 2024) and GSA, have demonstrated promising results. Recently, LoLCATs (Zhang et al., 2024a) proposed two-step process involving attention transfer and low-rank linearization (Hu al., 2021), combined with sliding window mechanism. This approach transforms LLMs into linear models with nearly linear complexity while preserving most of their performance.
C. Error Analysis with Softmax Attention
This section analyzes the error between our method and Softmax Attention, demonstrating that our approach achieves superior approximation in larger memory capacities compared to other methods. From Section 3.3, we know that the MVA method can fully converge to GSA and MetaLA. When they are optimal, the parameters (((6), w and w-(1) very small values, such that their impact on the output is negligible. Consequently, the solution space our method almost entirely encompasses the above two methods, and their unified combination enables convergence to better solutions. This unification ensures complementary convergence rather than mutual interference. The following provides detailed error analysis:
ke converge to
Original Attention:
= Softmax ((Q P) @ T
Our MVA computation is given by:
Qst Softmax (1(Q B)
K
o M) σ)
Ws + Ws+
B
(1-G) T
0 (((Qs) B)
2 MyV
C.1. Influence of High-order Integration
The error between method and Softmax Attention can be expressed follows:
(
(1-G)
Softmax (QQ P)(K o P) OM) v[((x
(1(Qs + B)
Focusing on the error between specific attention scores:
15

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
The expression ea5y can expanded as:
d II 1=1
enc
Σ
m
(qa) (kz))
(13)
m=0 m!!
81, 82
81 + mm
(gakk))
Σ
II
(14)
84!
Σ
Bst (())
II 1=1
(kz))
(15)
m=0 0= 010 m
Σ
Fst (a))
(k)))*
(16)
where Fz, (gx) [a.)"
The MetaLA can be further expressed as:
((g))e = Σ x = (OC))
(17)
= Σ d(e))
Σ Fal(Cu) 1=1
II (1bW))
(18)
Σ
Σ Fall))F((CC))
II (Nis)",
(19)
$1
where 6(x)= = x.
The error between Full Attention and MetaLA is given by:
(Falgu)) -
d II 1=1
c (((x))-(-())--- = Σ
(aC))
(kaa)*
(20)
This can be interpreted as using a fixed function to fit different powers of Fat (qu)) Since MetaL. adopts ((x) = x. it can only fit first-order information. To further reduce the error, Q needs to be extended higher powers. However, due the fixed power of the function, it can only eliminate fixed patterns of frequencies.
To minimize the error further, higher-order g terms need to be introduced for different powers of k. One method involves increasing the order of ie and querying with at least the same order of Q:
Σ (K)) ( Fa(K)... ... (K)
(21)
where different terms do not affect the lower-order terms, ensuring that this approach can achieve at least m--rder fitting, leaving only m + 1-order errors.
Another method is to avoid explicit summation by considering introducing dynamically varying powers of Q based on the powers of K. This requires embedding Q and K within a higher-order nonlinear function, such as (QKTF(X) Here, F(X) compresses KT to a fixed size, enabling linear complexity and recursive inference. This type of high-order nonlinear function enhances the previous method by introducing more powers for further approximating the original Attention but inevitably introduces significant high-frequency noise. GSA adopts this strategy, the GSA attention mechanism, given by:
Softmax (Q(FF(()))) (FFCC))))))))(()))))))
has its attention score at position (i,j) expressed as:
(o) c(u Db.
16

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Expanding this, obtain:
i Fa
Σ
Σ
exp
Σ
Fla(Cu) Kij
IIaa
(22)
1=1 Far(Cr)
Σ
Σ
Σ u!
48 Σ
te
II 133
(23)
where F(Ck.) is the transformation applied to the context. By approximating Ea_o Ko (K( as an averaged matrix Ca. where C. retains only higher-order k terms, the expression becomes:
Σ 81 18
(Fa
I
(24)
wt
u
Σ
Σ M91.
Ful
(T.
II
kiu
(25)
1=1
Focusing on the IT k3, basis, the terms involving q and C. have the same order. To mitigate the influence of figh-frequency noise introduced by II - kjt= GSA tends to prioritize high-frequency information. Thus, we consider incorporating methods such MetaLA or GLA to balance and supplement the information.
The discrepancy between GSA and Softmax Attention is given by:
e e( (P(CH )k.)
").ck)((k )(CCk])
(26)
d
Σ
Fa((g)) - Σ Σ
Fal(a) (Ca))
Fa((Cu)
II
K3
(27)
[=1
This represents a dynamic average approximation the full attention Fa(()) over g's various orders. Expanding GSA further:
d Fat(Ca) II t
Σ
Σ
Σ
Foue (e: ((C)
(28)
81 182
\11 Ma
d II kg
Σ
(F
(29)
$1 .g..
Introducing methods such MetaLA transforms the equation into MVA-no vocabulary decomposition, which can be expressed
(ø(g)) + ((Cn(()))(CC)F)(CCC.)) II kSr
(30)
The additional term d(4)) alleviates part of GSA's fitting pressure, suppressing high-frequency noise:
Far(g)) = (Fa(())) - <(q:)) (GC))
Compared to the original formulation:
Fa((g)) = Fa((.)) (F())
higher-order terms are similarly suppressed (ar()) decreases, mitigating high-frequency noise.
17

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
C.I.I. NOT USING THE TAYLOR SERIES EXPANSION
Consider not using the Taylor series expansion, directly with full Attention for differential exhaustion error analysis, the process is as follows: Original Attention:
e9ck
1+
ml! (2:k3 )m
1+
Σ
Fm(qi)k) (kakk) )m Σ +
m=udd
GSA Attention Scores:
Σ Eank
II tmi-j-1
ar(1 a1a)) = E Ce
(1 (1-a.))+ooolTi " (i a:(1-an))))
Sij
E + e + tt
(a +a20 ta,tn
[ai002 anl = In M e
n
where X = (X is the pseudo-inverse of X.
MetaLA Attention Scores:
((ai) IT ae k
Maj
1 1 WjW W
Rewriting the GSA scores
8tj = f.fl c. + (ka....)))))))
where ky represents a weighted approximation of the original ky due to limited memory capacity. The error between GSA and the original attention is:
Gj cbk c..7 cnit (c0(0) efaittemnnss)).
Using a Taylor expansion of (k) (k]- -kj) around the first-order term:
1 (x)))
because (fs) 1, we find that the error can be approximated as:
Gy J (k} - kg]
Introducing MetaL. further reduces the error, as:
Gj = q: (etkk +lg[(k] -kJ) el + (kg(.....)))
This result indicates that the use of (1(): Ja(ky,...,, ki) can effectively minimize the residual error. A similar analysis holds when including the denominator. Additionally, starting from MetaLA, the error can be expressed as:
1+ Σ (m (kyk))
m--
Σ Fa(a)((ykT)) + F(ky) - ((.))aa(k))
II on
mddd
A seeven
Σ (g) (kykk -
Σ (GG))))))+++(+))))(()()))))))))1
(ky
II (k)) --1-++1
a
wi=odd
tmi-j41
MetaLA first removes the first-order terms in the attention map related to 4. which is crucial because first-order terms contribute significantly to the overall attention mechanism's 's performance. Subsequently, GSA's dynamic weighted approxi- mation mitigates higher-order terms, limited by its memory constraints.
18

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
C.1.2. DYNAMIC DECAY
For gated attention models, use the following formulation:
G ).,)),,), B =
where Kn [Rxx is key tokens and C' E Rmxx is a learnable parameter representing m pseudo-query tokens to query Kn, with the results applied to Kn or V, sequences. Here, effectively defines the memory capacity. G, is gating matrix and Bn is decay matrix in 1, 2 and 3. For models like MetaLA, GLA, and GSA, G is typically sigmoid(C' ( ), and B, is exp(log( (, (UT) where U, an lower triangular matrix of shape n X n. For ABC, Fa is Softmax, and B, is exp(log(G; OO,) ), where a zero matrix of shape n x nt
For MetaLA, the memory mechanism is given by:
[B, (1-AA An)],
where 1 A, represents attention integration over V using first-order pseudo-query attention, and B,, adjusts this attention. Based on these characteristies, we define two attributes for MetaLA: first-order learnable pseudo-query attention over K and first-order adjustment- -haseeeett--- memory, referred to as complete first-order K integration method. Higher-order terms arise from powers of K, but the information primarily originates from first-order K.
For GSA, the mechanism involves [B, K,,),, and further processes [B, [,,,,, 7 to compute the final state. This corresponds to integrating K and V with first-order pseudo-query attention, then re-integrating V using the resulting K, Since this involves third-order terms of K, it is referred to complete third-order K integration method, albeit without branches for first-order and second-order K integration. Thus, we introduce Metal.A to complement first-order integration.
Causal convolutions in these methods can be interpreted as zero-order integration. Consequently, we propose a full-branch high-order integration method, detailed in the Appendix. In summary, high-order methods effectively approximate the higher-order terms of the Taylor expansion for Softmax attention.
C.2. Influence of Multi-level Vocabulary Decomposition
Theorem C.1 (Improved Memory Capacity). After c recursions, the expected error can be bounded as follows:
| < |
T
t=0
where E, n- and ny: is determined by learnable parameters that ensure convergence to value less than 1.
proof: For the GSA-like component in MVA. shown in Equation (11), if we remove the o(Q) branch and treat the matrix B as learnable relative positional encoding, the GSA branch output is:
0 = =SSftmaax ((QKT& @ M)F(K)) WsF(K) o M)V,
where F(K) E R= with m as the memory size and n as the sequence length. Considering extreme cases such as quantization functions or Softmax, F(K)'s row vectors approach one-hot distribution, effectively selecting specific elements from the attention map.
Extracting F(K) equivalently from the Softmax yields:
Softmax Softmax((QKT (M)(()) Softmax((QK" C K))
where:
F(Q, K) = [Softmax((QK' O "SotlllsaoaaaaX O M)F(K)),
and F(Q, K) has dimensions m.
Thus, the output becomes:
0 [So @ &
19

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Compared the original Softmax Attention output, this introduces dynamic low-rank matrix F(Q, K)) Ideally, if this matrix is equivalent to identity matrix, the error is zero. However, achieving this is challenging due rank limitations, and maximizing the matrix rank is essential to minimize the error.
We first consider the error term in the following form:
c= (Softmax((QK" @ -M)(FFQQ.KW5FF)) V.
Next, we decompose this error as:
c= SQft
④ M))( - F(Q, K)Ws Tp(((K)T DoMM M/ vo.
We focus reducing the above error term and approach this problem from two key aspects:
1. Reducing the Error from the Term (T - F(Q, K)))F(K)))
The term (I - F(Q, k))sF(K)T) involves the matrices:
F(Q, K) E Raxm
Ws T F(R) R
For large sequence lengths, the product F(Q, ())) E R results in a low-rank matrix of rank m. To minimize the error in this term, we aim to make this low-rank matrix close to the identity matrix, both terms of rank and numerical values.
Choice of the F-function
To ensure that the low-rank matrix approximates the identity matrix, we require the row vectors of the matrices F(Q, K)W's and F(K)W's E R=xm to be aligned in the same positions, with orthogonality between different positions. The simplest form of orthogonal matrices the identity vector. Although this might seem like a special case, it is a generalizable approach. After learning other orthogonal vectors for the matrices and F, the matrix W's can transform them into identity vectors. Moreover, the current methods using F and F exhibit a tendency to approach identity vectors.
Thus, the condition for numerical computation to approach the identity matrix suggests that the F-function should be extremal, such as the delta function or exponential functions. These functions make learning and convergence easier. Subsequently, normalization via a parameter matrix other methods can be applied, which results in extreme scaling of the matrix values, where dominant values approach 1, and other values approach O. This results in matrix K'), F(K)W's E Raxm that resembles the following form:
SU11
SU12
marvi
SUin
0
0
1
0
81/11
8U22
marvs
812n
0
0
>
:
50m1
marUm
8Umn
0 1
For the matrices A = F(Q, KOW's and B F(K)W's, the maximum values should appear the same positions to make the matrix approach the identity matrix T. This implies that corresponding rows must be similar, while different rows should ideally be orthogonal. For the matrix product ABT, the value at position (i,j) is given by:
(ABT)a Dij
Σ Caabye.
For the matrices and B approach the identity matrix, we need:
20

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
Σ Caraa 1.
However, this introduces additional error when the positions of the maximum values in different rows of and B coincide,
leading to E, 0zrba = I, while in the identity matrix, Σ, lij =
Ensuring Consistency in the Maximum Value Positions
To ensure that the maximum values occur at the same positions in both matrices A and B, we leverage the structure of the F(CKT) function used in MVA. Specifically, when the vector in K is most related to the "query token" in C, it will yield larger values, which are then amplified by the exponential function in F,, causing the corresponding position to take on the maximum value.
In our implementation, we use sigmoid and softmax functions with exponential methods. Additionally, more extreme approaches could involve directly assigning a value of to the most relevant position and 0 to other positions, as described in Section 3.2 with the Q-function.
For the matrix A = F(Q, K) which also depends on Q, compared to the function F(CKT) that is independent of Q the dynamic nature of A F(Q, K)W's can lead larger errors in certain scenarios. Therefore, future research will focus on incorporating recursive updates in F(CKT) allowing it to dynamically adjust based Q to generate orthogonal vectors at the same positions as those in A = F(Q, K-W's-
2. Exponential Power Increase of Memory Capacity for Rank Augmentation
For low-rank matrices, let us define:
T T= F(Q KY T F(K) Softmax(QK") - (1-Sigmidd (CT)) W)) "(1""""111111 (1-Sigmoid(KC) ))
The rank of the above matrix determined by the parameter matrix Rd simple way to increase the rank is to manually set the value of m in the matrix C, for example, C Rdd((2m), This method increases both the memory capacity and the rank to 2m, but it is inefficient. We propose an alternative approach using hierarchical structure, which, in the optimal case, results in exponential increase in the effective rank. We now turn to the hierarchical decomposition of K and V:
After hierarchical decomposition, we have:
( = " (Q.K (()
For simplicity, let us first consider the case where we do not use hierarchical decomposition during the recursive compression of K, and ignore the impact of "oftmax((QK" ( M)) for now. The error can be written as:
Softmax (QR M))V [Softmax((K
M)) Σ (0 ()) @ M v(
This simplifies to:
V - - (K) v =V -vV=
Σ v()
We begin by analyzing the case where the number of levels in the hierarchy is 2. Suppose C' E Rdxm, then the rank of T, is m.
First, the lower bound of the rank can at least represent a vector of length 2m without loss, since L, has rank m. When (ii V, the resulting matrix is the sum of L,, i.e., Lo + L,, which can achieve rank of 2m.
21

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
For the optimal case, where L has rank m., the matrix V is compressed into m directions: diag(() where La is the normalized matrix of row vectors from L,, and represents the amplitude of each row vector. Thus, diag(I) V can be treated generating directions.
Further, combining two levels corresponds to vector addition:
Ujx++ = -/; + off
When the generated vectors tixm+tj unequal, the number of directions generated is m², corresponding vector space of dimension m² In the general case, c-level hierarchical decomposition generate m directions, thus enabling precise expression in those directions, with an upper-bound error if the vectors are outside of those directions.
3. Error Analysis in Multi-level Decomposition
We proceed to provide a detailed error analysis to illustrate the advantage of multi-level decomposition. Suppose we use c levels of decomposition. Each level reduces the error introduced by the previous level. The vector V1() level is computed as:
v (Vli-1) -I
Ii- Ta-1 V(- W, =( L4 W-
Thus, the error introduced at the final level is given by:
E= -=+t)) = (1- -L.LVW
II
L)V II W
1=0
1=
We can now analyze the trend of the error in detail. The error consists of two main components:
Matrix compression error: Ii (I - L.). which represents the cumulative compression of the original vector V
through multiple low-rank projections. This term gradually diminishes the contribution of V.
Weight matrix transformation error: II Wi which reflects the impact of re-weighting the vector through the residuals at each level of decomposition.
The total error norm can be bounded as:
| S
I1
L;
VII
II W,
$ III [I
L,)I
Will
Error Trend Analysis
We now discuss the trend of the error under certain assumptions. To simplify the analysis, we make the following assumptions about the key matrices:
Low-rank matrix compression effect: We assume that the learnable matrix L; converges to the optimal low-rank approximation of the identity matrix, According to spectral norm analysis, we have:
6; || Li|l max (ar (I Li), .... T Li))
Here, 01(1 - L:) represents the singular values of the matrix / - Lg. In the optimal case, L, is similar to matrix with m ones on the diagonal and the rest being zeros, where the largest singular value is However, this is the worst-case scenario. As the number of levels increases, the probability this situation decreases, and thus the expected error becomes more representative.
22

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
The expected value of e is:
m n F||l
Lill]
We then analyze the effect of the weight matrices Wt:
W S %
Since W; learablee parameters, they tend to converge to eigenvalues less than 1, and thus the error will shrink %
decreases.
The overall error norm expectation can be recursively bounded as:
| < I c 7
Convergence Trend Discussion
The cumulative compression effect: The low-rank compression of the matrix L; gradually suppresses the energy V. and this suppression multiplicative. When e < 1 and does not increase with the error is exponentially decaying.
In partieular, when each level is set uniform size such that
constant value), have:
Il 1=0
4 c+1
This shows that as the number of levels increases, the error decays exponentially.
The effect of shrinking the weight matrices: The accumulation of weight matrices W; reduces the error. To ensure convergence of the error, " will become smaller through gradient learning, thereby further reducing the error.
Overall, the error norm converges as:
||||| s [IV IIVI (end
2=0
If eery has an upper bound p < the error will decay exponentially.
Numerical Upper Bound and Convergence Trend
If the values of & and are bounded by fixed upper bounds and 7, respectively, the error convergence rate can be expressed as:
|| s [[V](ey))*!
On the other hand, if e; and 7/s decrease gradually with (e.g., through optimization of the low-rank matrix L, and the weight matrices W,), the error decay may be faster than exponential decay. For instance, if F+T then:
II 1=0
E
(c+11 1)!
This represents super-exponential convergence.
Key Conclusions
23

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
1. Error Trend: The error is dominated by the cumulative compression factor [T L.), which exhibits exponential decay faster super-exponential decay, depending on the decay behavior of 6, and 7/s-
2.
Optimization Directions:
When selecting Li it is important to ensure that | - Lill remains sufficiently small, ideally decreasing gradually.
When choosing W,, it essential control ||i]| || so that it does not exceed certain range.
3. Practical Implications: Through careful design of Lg and W,, one can maintain compression efficiency while ensuring that the error converges rapidly. The trend of error reduction across levels becomes increasingly more pronounced.
D. Unification of linear models and their convergence
D.I. Unified Representations of Attention Mechanisms
We propose unified formulation of various attention mechanisms. Below, describe several key models in detail.
MetaLA:
MetaLA MVA(g ke) , ,C((), (00),,,,I),
(31)
(L))(, (1 ( (0) 1). 1 (0)
S 1 ())))),
(32)
where f( and _ represent adjustable functions dependent on (0)))
GLA:
GLA MVA(q, K/ ,
(0) (,00,,00,0000
00,0, fa = =1-2) 2),
(33)
0 GLA( (0) (0)
02 ( (k( (1)))) ))-
(34)
LA:
LA MVA (0)) (0)
-0, 0, 0, f, 1- 1z)x(x))
(35)
0 GLA(e, on (kg
(0) ) I))
(36)
GSA:
GSA extends higher-order interactions by introducing intermediate query gating mechanisms:
GSA MVA (0) Uy (0)
C(()) 0,50,00
(37)
Tk.t GLA(@, (0)) (1 f( )), 1 (k. (())),
(38)
Agm, Sigmoid (es, (ess, Ws v Softmax (()sm))))()))))))))))
(39)
GLA(qgme (1- f( (k( (0) f (1) (0)))
(40)
ABC:
ABC = MVA(g,, (000) 10t (0) -o, Ws. 0,0. = - Softmax (Cx)) ),
(41)
[ks GLA(gr, 1 (1 - ( (K! 1),
(42)
4gm, Softmax(qkes.
(43)
O: GLA GLA(Q (1 1(00) (k )), (0) T).
(44)
24

---

MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition
D.2. Delta-like Rule Approximation
Our approach leverages an approximate Delta Rule to maintain state information and minimize information loss during compression. The core idea is to preserve and update states iteratively based discrepancies between compressed and original sequences. Specifically, define:
(k W.x(( Wy
(45)
( W 1) o(k(())
(46)
80) o(W (W)z(
(47)
nnw = y00 + (1 - ((0)
(48)
w w(i-1) + (v. )11)) @ ((((1)).
(49)
To optimize for efficiency, we maintain auxiliary states, such as:
W
Uykk
(50)
instead of directly relying W(i+1), Although this prevents incremental querying of previous states, it introduces performance trade-offs. Our method focuses on the current state and its discrepancy, effectively compressing errors while enabling hierarchical aggregation for improved parallelism and scalability.
25


Reviews:
[{"review_id": "7WerFi3HRc", "reviewer": "Reviewer_Wmwj", "summary": "This work proposes an efficient Transformer alternative, which unifies existing architectures in the field GSA/GLA/MetaLA/Based with theory and combines their strengths to achieve performance improvements over strong baseline approaches at model scales of up to 7B parameters. The theory examines whether existing architectures tend to capture low or high frequency signals from input text.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback. Your suggestions have helped us refine our methodology and validation, especially regarding dataset selection. Below, we provide responses to each of your concerns.\n\n## 1. Essential References Not Discussed:\n1. **Conclusion:** We emphasise the importance of weighting LA with SWA based on attention score correlations in hybrid models. This is explicitly stated in our paper, along with supporting empirical validation.\n   \n   **Explanation:** Our baseline model indeed integrates linear attention with sliding window attention, as seen in prior work like Based and Infini-Attention. However, these methods typically rely on standard gating mechanisms. We argue that a more effective approach is to weight based on attention score correlations—our proposed soft fusion method. Upon further analysis, we recognize that LoLCATs also employ attention score weighting for linear and sliding window attention. However, our study was also conducted very early not later than LoLCATs, and our method extending softmax or sigmoid-based linear models is more natural and logical compared with the ordinary LA of LoLCATs. Notably, if full attention is computed recursively, both current and historical attention terms are weighted by attention scores. While LoLCATs apply this strategy, they do not explicitly highlight its significance. Furthermore, our approach preserves a softmax-like function, making our method more intuitive and theoretically sound.\n\n2. **Perceptron Mechanism:** We do not claim the perceptron mechanism as a novel contribution, as it has been widely studied. Instead, we employ it due to constraints in our GSA branch. Since the KV sequence is dynamically compressed to a fixed size, applying a simple softmax may no longer be optimal. Prior studies suggest that softmax acts as a relevance filter, enhancing focus on crucial tokens. However, given the severe compression in GSA or our method, more sophisticated information extraction mechanisms are necessary. This motivates our use of a perceptron, which we empirically validate.\n\n3. ** Prior Work:** Our method shares only minimal overlap with existing work, apart from the well-known Taylor expansion of \\(e^x\\), which is a natural and intuitive formulation. Nevertheless, these prior works provide valuable insights, and we would like to include them as references to strengthen the theoretical grounding of our approach.\n\n## 2. Addressing Weaknesses:\n1. **Comparison with LoLCATs on Alpaca-Clean Data:**  \n   LoLCATs did not use SlimPajama but rather Alpaca-Clean. We conducted experiments on Alpaca-Clean, and our results are as follows:\n   | Model              | Training Data  | PIQA | ARC-e | ARC-c | HellaSwag | Wino-grande | MMLU | Avg. | Avg. (w/o MMLU) |\n   |--------------------|---------------|------|-------|-------|-----------|-------------|------|------|-----------------|\n   | Mistral-7B (v0.1) | -             | 82.1 | 80.9  | 53.8  | 81.0      | 74.0        | 62.4 | 72.4 | 74.4            |\n| → LoLCATs (LoRA rank=8)  | AlpacaClean(+40M)   | 81.5 | 81.7  | 54.9  | 80.7      | 74.0        | 51.4 | 70.7 | 74.5 |\n| → LoLCATs (rank=8)| RedPajama(+40M)  | 80.1 | 77.6  | 49.0  | 80.3      | 71.7        | 53.2 | 68.6 | 71.7 |\n| → MVA-SW (rank=32)| AlpacaClean(+20M)| 82.1 | 81.5  | 54.7  | 81.2      | 74.1        | 52.2 | 70.7 | 74.4 |\n| → MVA-SW (rank=8)| AlpacaClean(+40M)| 82.3 | 81.9  | 57.6  | 80.2      | 74.0        | 51.6 | 71.2 | 75.2|\n| → MVA-SW (rank=8)| RedPajama(+40M)| 82.5| 81.5  | 55.7  | 79.7      | 72.9        | 52.4 | 70.8 | 74.5|\n\n   These results indicate that, unlike LoLCATs, which require a two-stage process, our method maintains strong performance across datasets with a single-stage fine-tuning approach. In particular, our approach to AlpacaClean fine-tuning performance is much better than LoLCATs.\n\n2. **Comparison of GLA/GSA:**  \n   We ensured a fair comparison in all evaluations. The advantage of our MVA (without sliding window) over GSA stems from the incorporation of information across different frequency scales and the extending of memory capacity. Additionally, when applying the method described in Section 3.4, we extended it to both GLA and GSA for a fair comparison.\n\n3. **MetaLA vs. Softmax:**  \n   The key limitation of MetaLA compared to softmax is the absence of a K matrix, which is replaced by a gated matrix. This substitution hinders the effective use of the original attention’s K matrix and introduces additional instability in training. Although our paper proposes mitigations, this deviation from standard attention mechanisms poses inherent challenges in fine-tuning convergence.\n\nLast but not least, thank you very much for your guidance and comments, so that we can improve our work!", "claims_and_evidence": "See strengths and weaknesses.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense.", "theoretical_claims": "Yes did not spot issues.", "experimental_designs_or_analyses": "See the strengths and weaknesses.", "relation_to_broader_scientific_literature": "This work competes with the strongest baseline approaches for efficient Transformer alternatives.", "essential_references_not_discussed": "- The weighted combination without recomputation from section 3.4 is already presented in LoLCATS, and it is proposed without sufficient attribution. This is not a new idea. The combination of linear attention plus short sliding window attention is presented in Arora et al., Simple linear attention models. \n\n- The idea of using a learned perceptron for the feature map is proposed in LoLCATS and Hedgehog, is this being suggested as a contribution? The writing should be clarified. \n\nApplying Theorem 3.1 Taylor polynomial for exp to produce the feature map for linear attention. Do these works share any overlap?\n- Keles et al., On The Computational Complexity of Self-Attention, 2022.\n- Arora et al., Simple linear attention models, ICML 2024.", "other_strengths_and_weaknesses": "**Strengths**\n\n- Strong experimental results in Table 3, where quality is better using less training data than strong baseline methods\n- Improved distillation method that just requires one step of training versus prior work that uses multiple stages\n- Theorem 3.2 is very interesting, with respect to about high vs. low frequency signal processing\n\n\n**Weaknesses**\n\nExperiments\n- Is SlimPajama used in LoLCATS? Would be worth understanding if the improvements are due to the dataset or due to the architecture. \n- Is the improvement over GLA/GSA due to the weighted-combination of softmax and linear attention without recompute from Section 3.4? Or do you apply the method in Section 3.4 for the baselines as well? \n\nEfficiency\n- What is the efficiency of MVA for longer sequences? \n\nAdditional analysis\n- Are there any empirical observations suggesting that the GSA and MetaLA pick up low-vs.-high frequency patterns? Not sure if this is observable? \n- How many decomposition steps are used and are there any ablations to understand that better? Compared to just hybridizing GSA and MetaLA?", "other_comments_or_suggestions": "Line 154: “However, as MetaLA removes the K matrix, it introduces a significant gap from Softmax Attention, hindering methods that rely on fine-tuning Softmax Attention weight” Could be explained more clearly. It is not clear why this is a limitation.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k0hwdMmY9U", "reviewer": "Reviewer_TChB", "summary": "The paper introduces MVA (Multi-level Vocabulary Attention), that uses high-order Query-Key (QK) integration with a recursive multi-level vocabulary decomposition to approximate Softmax attention. The paper combines sparse and linear attention, MVA achieves good performance upon finetuning on Mistral-7B.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We sincerely appreciate the time and effort you have taken to review our work. Your insightful suggestions have significantly helped us refine the clarity and presentation of our paper. Below, we address each of your concerns in detail.\n\n### 1. Clarification on Naming Conventions:\nWe sincerely apologize for any confusion caused by our last-minute modification of the naming conventions. Our advisor suggested that the abbreviation should follow a three-letter format, similar to GLA and GSA, as MQVA was considered too long. From the paper, it can be derived that **MQVA = MVA** and **MQVSWA = MVA-SW**. However, we acknowledge that our original presentation might have been unclear, and we have now carefully revised the notations and paper formatting to ensure clarity.\n\n### 2. Title:\nThank you for pointing out. We have now corrected the content in \\icmltitlerunning to match our paper’s title.\n\n### 3. Justification for Maintaining or Slightly Improving Performance with Additional Training Tokens:\nWe appreciate your suggestion to explicitly clarify why fine-tuning with more tokens maintains or slightly improves performance, as this requires a deeper understanding of the method. The reason is as follows: \n\nWhen combining **Sliding Window Attention (SWA)** with **Linear Attention** during fine-tuning, the two branches initially exhibit different learning distributions, with SWA being more dominant. As training progresses, performance first increases and then decreases due to the impact of Linear Attention on the final outcome. However, our method mitigates this issue by either **fine-tuning only the introduced additional parameters** or **selectively truncating gradient information**, effectively transforming the declining phase into a slow improvement and highlighting the advantages of our approach.\n\n### 4. Removal of Unused Equation Numbering:\nWe acknowledge that numbering equations that are not referenced in the main text may introduce unnecessary complexity. However, we intentionally retained some equation numbers because they facilitate discussions in group meetings and other research communications. That said, we recognize your expertise in academic writing and have followed your suggestion to remove some of the unreferenced equation numbers for a more formal and concise presentation.\n\n### 5. Notation Refinements:\nWe have revised our notation for clarity:\n- The previous notation has been updated to **$\\exp(\\cdot) R_d$**, where **$R_d \\in \\mathbb{R}^{s_w \\times 1}$**, **$s_w$** represents the window size and the values in the $R_d$ matrix are all 1.\n- We have replaced `sigmoid` with $\\sigma(\\cdot)$ and provided its mathematical definition for consistency.\n- The subscripts in our MetaLA equations have been adjusted following your recommendations, resulting in a much more concise and readable formula set. We truly appreciate your guidance in improving the mathematical presentation.\n\n### 6. Clarification of MVA-2 Level:\nAs noted in Section 3.2, **MVA-2 Level** employs multi-level vocabulary decomposition, where the vocabulary is recursively decomposed into two hierarchical levels.\n\n### 7. Explanation of With and Without SWA Comparisons:\nWe appreciate your suggestion to enhance the explanations in our table captions. We will carefully incorporate this feedback in future revisions. Below, we provide a rationale for the inclusion of both \"with\" and \"without SWA\" comparisons:\n\nCurrently, there are two primary research directions for converting full-attention models into linear models:\n1. **Hybrid architectures**, which combine **sliding window attention** and **linear attention** either at the intra-layer level or by selectively replacing different layers.\n2. **Pure linear attention models**, such as GSA, which do not mix different mechanisms.\n\nBoth approaches share a common challenge: the **inherent limitations of linear attention**. Since our method offers a theoretically superior approximation to full attention, it demonstrates advantages in both hybrid and purely linear settings.\n\nAnother important reason for including these comparisons is that **SWA preserves the original model’s local distribution within the window**, significantly reducing fine-tuning resource requirements while achieving higher performance. As a result, many recent approaches incorporate **sliding window attention or global window attention mechanisms**. However, researchers focused on linear models, such as those studying GSA, are particularly interested in evaluating the effectiveness of purely linear attention. Thus, our experiments on **MVA without SWA** serve to highlight the strengths of our linear component and provide valuable insights for researchers working in this domain.\n\nWe truly appreciate your constructive feedback, which has greatly contributed to the refinement of our paper. Your recommendation of *Handbook of Writing for the Mathematical Sciences* has been particularly beneficial.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No.", "experimental_designs_or_analyses": "See strengths and weaknesses", "relation_to_broader_scientific_literature": "See strengths and weaknesses", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Comments:\n1. Figure 1 doesn’t define the acronym MQVA. The figure is hard to read. \n2. Running title of the paper is “Submission and Formatting Instructions for ICML 2025”\n3. Why is increasing the number of finetuning tokens from 0.1B vs 2B doesn’t improve performance in Table 1? \n4. All the equations are numbered, even though most of them are not used/referenced.\n5. The code notation “sumexp(., dim=-1)” is not used formally unless defined. \n6. The equations (27)-(30) use code notation several times. Improving the notation would help in line 320. For instance, metala can be made MetaLA in the subscript, and sigmoid can be declared a mathematical operator in latex. Here’s a reference https://epubs.siam.org/doi/10.1137/1.9781611976106 \n7. What is MVA-2 level in Table 6.\n8. What is the purpose of Q in “MVA (MQVSWA without SWA)” in Table 3 title. The acronyms are very confusing.\n9. It would be great to have elaborate table titles with better explanation of the baselines and the observations. It would be better if  there is an explanation on why there are two tables, with and without SWA.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g0JSXdXYiW", "reviewer": "Reviewer_jLwJ", "summary": "The paper introduces MVA, a novel linear attention mechanism to bridge the gap with softmax attention. The proposed approach uses:\n1. High order QK integration theory - to integrate high and low frequency information to improve the approximation of softmax attention.\n2. Multi-level Vocabulary Decomposition - to recursively compress and store residual errors from previous attention states, thus reducing information loss.\n\nThe proposed approach is evaluated on multiple benchmarks, showing improvements over existing state-of-the-art linear attention methods such as GSA and MetaLA. MVA is able to achieve 99% of the original performance with less than 100M tokens, outperforming prior linearization techniques.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your insightful feedback and valuable support, which have greatly benefited us. Below, we provide further clarifications based on your suggestions. Thank you again for your guidance.\n\n1. **Scaling to Larger Models**  \n   Due to resource and time constraints, we are unable to conduct fine-tuning experiments on a 70B model. However, to approximate your suggestion, we have conducted experiments with MVA-SW on **Qwen2.5-14B-1M** and **Qwen2.5-32B**, as shown in the table below:\n\n   | Model               | MMLU  | PIQA  | Hellaswag |\n   |----|-------|-------|-----------|\n   | Qwen2.5-14B-1M  | 80.7  | 85.2  | 87.3      |\n   | → MVA-SW (14B)      | 77.3  | 83.8  | 86.8      |\n   | Qwen2.5-32B     | 83.9  | -     | 85.2        |\n   | → MVA-SW (32B)      | 79.8  | 82.5     | 85.0 |\n   Additionally, we have incorporated **MVA into Llama3-8B**, and the results are presented below:\n\n   | Model          | +Tokens | ARC-C | Winogrande | MMLU | TriviaQA |\n   |----------------|---------|-------|------------|------|----------|\n   | Llama3.1-8B    | -       | 79.7  | 60.5       | 66.7 | 77.6     |\n   | → MVA (8B)     | +4B     | 60.4  | 58.2       | 32.1 | 63.2     |\nDue to time constraints we have only carried out the above experiments, if you require additional experiments or more tests please let us know, we would be happy to talk to you again and receive your guidance, thank you very much!\n\n2. **LongBench Evaluation**  \n   For long-sequence tasks, we followed the benchmark selection in the GSA paper and conducted experiments on Qasper, NarrativeQA, and QMSum, all of which are part of LongBench except QuALITY. Consequently, we utilized the LongBench framework to ensure consistency across experiments when comparing against GSA and other methods. However, it appears that GSA may not have used LongBench directly for evaluation. As a result, there are slight discrepancies between our results on Mistral and those reported in the GSA paper. To ensure fair comparisons, we will adopt a normalization strategy: we will adjust the sampling procedure of our Mistral and MVA evaluations such that the resulting Mistral performance aligns more closely with the GSA-reported Mistral results. We will then conduct our MVA experiments under the same conditions.\n\n   | Model     | Qasper | NarrativeQA | QMSum |\n   |-----------|--------|------------|-------|\n   | **Models trained from scratch** |  |  |  |\n   | RWKV6    | 9.2    | 14.4       | 1.1   |\n   | Mamba    | 5.6    | 27.9       | 0.8   |\n   | Mistral  | 25.8   | 25.1       | 5.0   |\n   | **Finetuned from Mistral 7B on 20B tokens** |  |  |  |\n   | RetNet   | 11.1   | 0.0        | 0.0   |\n   | GLA      | 18.4   | 17.2       | 9.0   |\n   | GSA      | 18.8   | 19.2       | 10.0  |\n   | MVA      | **20.7** | **20.4** | 9.58 |\n\n3. **Loss Curve Analysis**  \n   We have added loss curves from fine-tuning different models in the https://anonymous.4open.science/r/icml25_mva-B2AB provided. The results indicate that **MVA exhibits the fastest loss convergence** compared to other methods such as **GLA, GSA, and MetaLA**. Additionally, as training progresses, the **loss of MVA gradually approaches that of Mistral**, further demonstrating its effectiveness. Please let us know if you need any other convergence curves, thank you very much!\n\nWe sincerely appreciate your constructive feedback, which has been instrumental in refining our work. Thank you again for your valuable time and insightful suggestions!", "claims_and_evidence": "Claims with sufficient support:\n1. MVA outperforms SOTA linear attention models like GSA and MetaLA: Results in Table 1 support the claim\n2. MVA improves memory efficiency by maintaining fixed-size states: Results in Table 6 support the claim\n\nClaims that require further justification:\n1. High order QK integration Theory improves both low-frequency and high-frequency attention: This is partially supported by theorems but it would be good to add empirical analysis of frequency bands.\n2. MVA-SW solves the convergence issues of hybrid architectures: A convergence study would strengthen the claim.", "methods_and_evaluation_criteria": "1.The proposed approach is evaluated against SOTA linear attention models such as GSA, MetaLA, RetNet and GLA. The paper evalautes 2. MVA on widely used language model benchmarks such as MMLU, ARC-E, HelloSwag, PIQA, Winogrande, TiriviaQA and NQ.\nFine-tuning results are shown for Mistral-7B, but it would be good to add a couple more such models and even larger models such as of size 30B, 70B etc.\n3. There is missing analysis on convergence or loss curves to support the claims made for MVA-SW.", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "1. There has been prior work to approximate softmax attention using linear attention such as MetaLA and GSA. MetaLA captures low frequency components while GSA captures high-frequency components, this paper combines both perspectives into a unified framework(Higher order QK-integration). \n2. Unlike Linformer, RetNet and MetaLA, which compress entire sequences into fixed-size states, MVA uses MVD to recursively store compression errors, leading to exponential memory capacity. \n3. LoLCATs combines SWA with linear attention, but requires two-stage fine-tuning. MVA-SW integrates SWA into the attention computation directly, reducing training overhead.\n4. Prior hybrid models require significant retraining when replacing softmax layers. MVA retains 99% of softmax-trained performance with minimal fine-tuning, making it more practical for real-world deployment.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is very well-written and easy to follow.\n2. The proposed approach is evaluated on various datasets and compared with SOTA approaches. \n3. There are enough ablation studies to support various claims.\n4. The proposed approach addresses a critical bottleneck in LLM scalability - quadratic complexity in softmax attention. MVA provides a scalable alternative with minimal loss in performance.\n\n\nWeaknesses:\n1. The proposed approach is not evaluates on models other than Mistral-7B. It would be good to add larger models with sizes 30B and 70B to see if the proposed approach scales to larger architectures.\n2. It would be good to add some long-context benchmarks.\n3. The paper lacks convergence analysis for MVA, so it would be good to add empirical results supporting that.", "other_comments_or_suggestions": "No", "questions_for_authors": "Same as weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ofMvTFkv7U", "reviewer": "Reviewer_4UAB", "summary": "This paper introduces MVA (Multi-level Vocabulary decomposition Attention), a linear attention mechanism built upon high-order query-keys integration theory and multi-level vocabulary decomposition. The authors unify popular linear attention methods under their theoretical framework and try to address the performance gap between linear attention and softmax attention. They propose methods to transform pre-trained softmax-based language models into linear models through fine-tuning. Their approach combines linear and sparse attention to capture information across different frequency bands, and uses multi-level vocabulary decomposition to expand memory capacity. The authors also introduce a soft integration strategy with sliding window attention. The paper claims their method can fine-tune models to achieve linear complexity while retaining 99% of original performance with fewer than 100M tokens, and outperforms state-of-the-art models on benchmarks with minimal fine-tuning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the insightful feedback and guidance provided. Based on your suggestions, we have made substantial improvements to our work.\n\n1. **Additional Experiments with MVA-SW on Qwen2.5-14B-1M and Qwen2.5-32B**  \n   We have conducted further experiments with MVA-SW on Qwen2.5 models and report the results below.\n\n   | Model               | MMLU  | PIQA  | Hellaswag |\n   |-|--|--|---|\n   | Qwen2.5-14B-1M  | 80.7  | 85.2  | 87.3      |\n   | → MVA-SW (14B)      | 77.3  | 83.8  | 86.8      |\n   | Qwen2.5-32B     | 83.9  | -     | 85.2        |\n   | → MVA-SW (32B)      | 79.8  | 82.5     | 85.0 |\n\n   We have also included results for **Llama3-8B with MVA**:\n\n   | Model         | +Tokens | ARC-C | Winogrande | MMLU | TriviaQA |\n   |--|---|--|---|-|---|\n   | Llama3.1-8B  | -       | 79.7  | 60.5       | 66.7 | 77.6     |\n   | → MVA (8B)   | +4B     | 60.4  | 58.2       | 32.1 | 63.2     |\n\n2. **LoRA Configuration Details**  \n   As suggested, we explicitly clarify the LoRA settings. Our method only requires replacing Full Attention in Mistral or Llama models with MVA-SW or MVA, followed by fine-tuning. The configurations are detailed in Sections 4.1, 4.2, and 4.3.  \n   - **MVA-SW (General Setting)**: Fine-tuning QKV and down_proj weights, with rank=128 and α=256 (default α=2×rank).  \n   - **MVA-SW (LoLCATs Setting)**: Fine-tuning only QKV weights, with rank=8 and α=16 (aligned with LoLCATs).  \n   - **MVA**: Fine-tuning QKV and down_proj weights, with rank=256 and α=512.\n\n3. **Inference Efficiency and Memory Usage**  \n   While inference efficiency and memory footprint are closely related to training efficiency in linear models, we acknowledge that our previous evidence was insufficient. To address this, we now report inference efficiency and memory usage across different sequence lengths.\n\n   ### Table: Inference Performance Comparison  \n\n   | Seq Len | Full Inf Time (s) | Full Inf Mem (GB) | Prefill Time (s) | Gen Latency (ms/token) | Total Mem (GB) |\n   |--|--|-|--|--|-|\n   | **MVA** |  |  |  |  |  |\n   | 4K   | 0.14  | 0.77  | 0.125  | 98.8  | 15.32 |\n   | 8K   | 0.26  | 1.53  | 0.249  | 60.3  | 16.58 |\n   | 16K  | 0.51  | 3.06  | 0.508  | 78.8  | 19.08 |\n   | 32K  | 1.08  | 6.11  | 1.090  | 78.8  | 24.09 |\n   | 64K  | 2.25  | 12.22 | 2.265  | 97.3  | 34.11 |\n   | 128K | 5.08  | 24.44 | 7.156  | 58.1  | 54.14 |\n   | **GSA** |  |  |  |  |  |\n   | 4K   | 0.10  | 0.76  | 0.077  | 93.2  | 15.30 |\n   | 8K   | 0.17  | 1.53  | 0.153  | 40.9  | 16.55 |\n   | 16K  | 0.32  | 3.06  | 0.315  | 48.5  | 19.06 |\n   | 32K  | 0.64  | 6.11  | 0.630  | 63.0  | 24.07 |\n   | 64K  | 1.29  | 12.22 | 1.293  | 90.2  | 34.08 |\n   | 128K | 2.66  | 24.44 | 5.102  | 38.7  | 54.11 |\n   | **Flash-Attention** |  |  |  |  |  |\n   | 4K   | 0.05  | 1.26  | 0.056  | 21.7  | 15.79 |\n   | 8K   | 0.11  | 2.53  | 0.116  | 27.5  | 18.54 |\n   | 16K  | 0.27  | 5.05  | 0.287  | 46.3  | 23.55 |\n   | 32K  | 0.73  | 10.11 | 0.750  | 92.4  | 33.55 |\n   | 64K  | 2.19  | 20.22 | 2.208  | 220.4 | 53.57 |\n   | 128K | OOM   | OOM   | OOM    | OOM   | OOM   |\n\nAs shown in the table, the Full Inf Time and Full Inf Mem correspond to inference using the entire sequence without KV cache. In contrast, the Prefill Time refers to inference where the sequence is first prefilled and subsequently decoded using the KV cache. The Gen Latency then represents the per-token decoding time in this cached scenario.  There may be minor fluctuations in the Prefill Time results due to the absence of prewarming during testing. However, the Gen Latency of the linear model should be close to a fixed value in theory but not in practice, probably due to some shortcomings of the triton operator in slicing and compiling at different lengths. **Overall, our method starts to dominate over flash-attention in all aspects at 64K length.**\n\n4. **Long Context Experiments**  \n   Following your suggestion, we evaluated our method on LongBench and compared it against GSA and other baselines.\n\n   | Model     | Qasper | NarrativeQA | QMSum |\n   |--|---|----|---|\n   | **Models trained from scratch** |  |  |  |\n   | RWKV6    | 9.2    | 14.4       | 1.1   |\n   | Mamba    | 5.6    | 27.9       | 0.8   |\n   | Mistral  | 25.8   | 25.1       | 5.0   |\n   | **Finetuned from Mistral 7B on 20B tokens** |  |  |  |\n   | RetNet   | 11.1   | 0.0        | 0.0   |\n   | GLA      | 18.4   | 17.2       | 9.0   |\n   | GSA      | 18.8   | 19.2       | 10.0  |\n   | **MVA**  | 20.7   | 20.4       | 9.58  |\n\n5. **Theoretical Proof Organization**  \n   We greatly appreciate your suggestions regarding the structure of our theoretical proofs. We have now revised the theoretical analysis to follow a structure similar to **MetaLA’s appendix**:  \n   - **Subsection → Proposition (or Lemma) → Proof → Discussion**  \n\n### Conclusion  \nWe are deeply grateful for your constructive feedback, which has significantly improved our research and manuscript.", "claims_and_evidence": "The claims about improving over existing linear attention methods are supported by experimental results in Tables 1-3, showing the MVA and MVA-SW variants outperforming previous methods. The theoretical claims regarding high-order QK integration and multi-level vocabulary decomposition are somewhat justified through the error analysis in the appendix.", "methods_and_evaluation_criteria": "+The proposed methods make sense for the problem of creating efficient linear attention mechanisms. The evaluation on standard benchmarks like MMLU, ARC, HellaSwag, etc. is appropriate for assessing language model capabilities. \n\n\n-However, the evaluation criteria are incomplete - there's no comparison of inference speed or memory usage during long-context generation, which is crucial for linear attention's practical benefits. They focus almost exclusively on accuracy metrics while neglecting efficiency metrics, inference speed, memory usage during generation. Also, the paper only evaluates on one base model (Mistral-7B), limiting the generalizability of the findings. The absence of long-context evaluation is particularly problematic given that KV cache efficiency is one of the main advantages of linear attention.", "theoretical_claims": "I checked some of the theoretical claims in the paper, particularly those related to high-order QK integration (Theorems 3.1 and 3.2) and multi-level vocabulary decomposition (Theorem 3.3). The paper provides some justification for these claims through expansions and error analyses, but the presentation is quite informal and difficult to follow. The proofs lack rigorous mathematical formalization, and many statements are presented as informal explanations rather than properly stated theorems with clear assumptions and conclusions, i.e., Assumption, Lemma, Theorem, Proof style. The error bounds in Theorem 3.3 look reasonable but would benefit from clearer exposition and more rigorous derivation. The Taylor series expansions used to justify the frequency-based interpretation are plausible but would be more convincing with empirical validation.", "experimental_designs_or_analyses": "The experiments use appropriate benchmarks and comparative baselines (GSA, GLA, RetNet, SUPRA). However, there are several issues with the experimental design:\n\n- The paper only evaluates on one base model (Mistral-7B), which limits generalizability.\n- There's no evaluation of inference speed or memory usage, which is crucial for linear attention models.\n- The paper lacks long-context evaluation, despite this being a primary motivation for linear attention.\n- The fine-tuning approach using LoRA is reasonable, but more details on hyperparameter selection and optimization would strengthen the experimental rigor.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-situated within the linear attention literature. The authors build upon previous work like MetaLA and Gated Slot Attention, extending these approaches through their high-order QK integration theory and multi-level vocabulary decomposition. The paper clearly acknowledges its relationship to prior techniques like the Delta Rule and recursive sparse attention. The comparison with LoLCATs shows awareness of concurrent hybrid approaches.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n- The paper provides a good background and summarization of linear attention methods, unifying them under a common theoretical framework that helps clarify the relationships between different approaches.\n- The performance results are promising, with MVA outperforming previous linear attention methods on benchmark tasks while requiring fewer training tokens. The multi-level vocabulary decomposition is an interesting approach to expanding the memory capacity of linear attention models.\n- The direction of converting pre-trained softmax models to linear attention models is important and practical, as it addresses a significant efficiency bottleneck in deploying LLMs.\n\nWeaknesses (some mentioned above, just make a summarization here):\n- The paper only evaluates on a single pre-trained model (Mistral-7B), making it unclear how well the approach generalizes to other model architectures or scales.\n- The introduction and explanation of MVA lacks sufficient detail for implementation - there's no clear step-by-step guide on how to transform a pre-trained LLM to MVA, which limits reproducibility.\n- Despite linear attention's main advantage being inference efficiency, the paper doesn't report any inference speed metrics or memory usage during generation, making it hard to assess the practical benefits.\n- The paper lacks any evaluation on long-context tasks where KV cache efficiency becomes the bottleneck, which is a critical use case for linear attention models.\n- The theoretical content, especially in the appendix, is poorly organized and lacks formal structure - claims should be presented as clear lemmas and theorems with explicit assumptions and conclusions.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper presents MVA, a new linear attention mechanism designed to efficiently approximate softmax attention by combining high-order query-key (QK) integration with multi-level vocabulary decomposition (MVD). The authors demonstrate that their method, with minimal fine-tuning on 100M tokens, retains up to 99% of the original model's performance while achieving linear complexity. Evaluations are conducted on Mistral-7B and other mid-sized models, comparing against recent baselines such as GSA, MetaLA, and LoLCATs.

The authors made significant improvements during the rebuttal period, including experiments on larger models (Qwen2.5-14B and 32B, Llama3-8B), LongBench evaluation, convergence analysis, and a detailed breakdown of inference latency and memory usage.

All reviewers acknowledge that the results presented in the paper are strong or interesting, especially after the author response. The main concern raised in favor of rejection is the quality of the writing. While this concern is valid, I believe the paper should be accepted, provided the authors make a concerted effort to significantly improve the writing and clarity in the final version.
Decision: Accept (poster)