Low-Rank Approximation for Sparse Attention in Multi-Modal LLMs

Lin Song, Yukang Chen, Shuai Yang, Xiaohan Ding, Yixiao Ge, Ying-Cong Chen, Ying Shan

Introduction

The computational complexity of the self-attention mechanism, which grows quadratically ($O(N^2)$) with sequence length, remains a primary bottleneck for Transformer-based Large Language Models (LLMs). This scaling issue limits the feasibility of processing long documents or high-resolution images. Sparse attention—attending only to a subset of tokens—is a promising solution but faces two main hurdles: the "efficiency paradox," where identifying important tokens requires computing the full attention map, and the "pre-training gap," where switching to sparsity during fine-tuning degrades performance.

Methodology: LoRA-Sparse

The proposed LoRA-Sparse framework overcomes these limitations through low-rank approximation and a novel training objective.

Low-Rank Approximation

Instead of computing attention in high-dimensional space, LoRA-Sparse projects Queries (Q) and Keys (K) into a low-rank space ($r \ll d$). A "mini" attention map is calculated in this space to identify the top $s\%$ most significant query-key pairs. Only these pairs are then computed in the full-dimensional space, significantly reducing the total floating-point operations (FLOPs).

Order-Mimic Training

To ensure the low-rank projections accurately identify important tokens, the authors introduce Order-Mimic Training. This strategy uses a soft-margin loss to force the low-rank layers to rank token importance in the same order as the original full-attention model. This alignment allows the model to maintain the performance of dense attention while operating at high sparsity levels.

Architecture comparison between standard attention and the proposed low-rank sparse attention with Order-Mimic training.

Experimental Results

The researchers evaluated LoRA-Sparse across multi-modal reasoning (ScienceQA, GQA), long-context modeling (PG19), and general NLP benchmarks.

Accuracy and Efficiency

LoRA-Sparse reduces self-attention computation by over 50% while maintaining or even improving accuracy. For instance, on the ScienceQA benchmark, the model achieved an accuracy of 68.4%, outperforming the 67.6% baseline. This suggests that sparse attention can act as a denoising step, removing "noise" from irrelevant tokens.

Accuracy vs. sparse ratio on the ScienceQA benchmark, demonstrating that LoRA-Sparse often exceeds baseline performance.

Long-Context Performance

On the PG19 dataset, LoRA-Sparse demonstrated stable perplexity for sequences up to 16,384 tokens. This is a significant improvement over standard LLaMA models, which typically struggle beyond their 2,048-token training limit. On general NLP tasks like the ARC-Challenge, the model improved the baseline from 45.6% to 47.3% while using half the attention compute.

Conclusion

LoRA-Sparse provides a practical and efficient path for adapting pre-trained LLMs to sparse attention. By leveraging low-rank manifolds to identify token importance, the method achieves significant computational savings and performance gains. Future work will focus on hardware-level optimizations, such as specialized CUDA kernels, to translate these theoretical FLOP reductions into real-world wall-clock speedups.

Summary updated

Abstract

This paper focuses on the high computational complexity in Large Language Models (LLMs), a significant challenge in both natural language processing (NLP) and multi-modal tasks. We propose Low-Rank Approximation for Sparse Attention (LoRA -Sparse), an innovative approach that strategically reduces this complexity. LoRA -Sparse introduces low-rank linear projection layers for sparse attention approximation. It utilizes an order-mimic training methodology, which is crucial for efficiently approximating the self-attention mechanism in LLMs. We empirically show that sparse attention not only reduces computational demands, but also enhances model performance in both NLP and multi-modal tasks. This surprisingly shows that redundant attention in LLMs might be non-beneficial. We extensively validate LoRA -Sparse through rigorous empirical studies in both (NLP) and multi-modal tasks, demonstrating its effectiveness and general applicability. Based on LLaMA and LLaVA models, our methods can reduce more than half of the self-attention computation with even better performance than full-attention baselines.
BibTeX
@inproceedings{song2024low,
  author = {Lin Song and Yukang Chen and Shuai Yang and Xiaohan Ding and Yixiao Ge and Ying-Cong Chen and Ying Shan},
  title = {{Low-Rank Approximation for Sparse Attention in Multi-Modal LLMs}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2024},
  doi = {10.1109/cvpr52733.2024.01306},
}
Figure