A2SF: Accumulative Attention Scoring with Forgetting Factor for Token Pruning in Transformer Decoder

Hyun-rae Jo, Dongkun ShinarXiv 2024 · DOI · arXiv

Abstract

Large Language Models (LLMs) are increasingly constrained by the memory requirements of the Key-Value (KV) cache, which stores intermediate states for every token in a sequence. While token pruning methods like H2O attempt to mitigate this by retaining tokens with high Accumulative Attention Scores (A2S), they are fundamentally biased toward older tokens due to the causal masking inherent in Transformer decoders. This "seniority bias" leads to the retention of early, potentially irrelevant tokens at the expense of critical recent context. We introduce A2SF (Accumulative Attention Scoring with Forgetting Factor), a novel pruning mechanism that incorporates an exponential decay factor to balance the importance of old and new tokens. Our evaluations across multiple LLMs and benchmarks demonstrate that A2SF significantly improves accuracy—by up to 7.8% for LLaMA 2—compared to existing state-of-the-art pruning techniques.

1. Introduction

The efficiency of Transformer-based decoders, such as GPT and LLaMA, is often limited by the memory and bandwidth requirements of the Key-Value (KV) cache. As sequence lengths grow, the cache size increases linearly, leading to substantial GPU memory consumption and creating a bottleneck during inference.

To address this, researchers have proposed token pruning techniques that identify and retain only the most important tokens. A prominent approach is H2O, which uses Accumulative Attention Scores (A2S) to identify "Heavy Hitter" tokens. However, A2S is flawed in the context of causal decoders. Because decoders can only attend to preceding tokens, the first token in a sequence is attended to by every subsequent token, while the most recent token is only attended to once. This creates a massive seniority bias, where early tokens accumulate high scores regardless of their semantic value. Consequently, models often prune useful recent tokens while keeping useless older ones.

Comparison of attention score distributions. Notice how LLaMA with H2O (b) is heavily skewed toward early tokens compared to BERT (a). A2SF (c) restores balance.

2. Methodology: A2SF

We propose A2SF, which modifies the attention score accumulation process by introducing a Forgetting Factor ($\alpha$). Instead of a simple summation of all past attention scores, A2SF applies an exponential decay mechanism. Each time a new token is generated, the accumulated scores of all previous tokens are multiplied by $\alpha$ (where $0 < \alpha \le 1$).

Mathematically, the score for a token $k$ at step $n$ is calculated as: $$A_{n,k} = \sum_{q=1}^n \alpha^{n-q} \times S_{q,k}$$

This approach is inspired by the Ebbinghaus Forgetting Curve, a psychological model describing how information is lost over time. By decaying past scores, the accumulated values for older tokens eventually converge rather than growing indefinitely. This puts "old" and "new" tokens on a level playing field, allowing the pruning algorithm to select tokens based on their actual relevance to the current context.

3. Experimental Evaluation

We evaluated A2SF across several prominent Large Language Models, including LLaMA-7B, LLaMA-2-7B, OPT-2.7B, and OPT-6.7B. The models were tested on seven commonsense reasoning benchmarks: OpenbookQA, Winogrande, PiQA, COPA, MathQA, ARC-easy, and ARC-challenge. These evaluations were performed in both 0-shot and 1-shot settings using the lm-eval-harness framework.

4. Results and Discussion

A2SF consistently outperformed existing baselines, particularly at high compression ratios. On LLaMA 2 7B with a cache ratio of 0.2 (80% pruning), A2SF improved average accuracy by 7.8% in 1-shot and 5.1% in 0-shot settings compared to H2O.

Accuracy curves across different cache ratios. A2SF (purple) consistently outperforms H2O (red) and Local Attention (green), staying closer to the "Full" cache baseline (blue dashed).

4.1 Key Insights

  • Fairness and Accuracy: By resolving the imbalance caused by causal masking, A2SF selects tokens that are more representative of the "Ideal" attention mask—the mask achievable with infinite memory.
  • Resilience of the Sink Token: Even with a forgetting factor, the initial token (the "Attention Sink") typically maintains a high score because it receives consistent attention. A2SF preserves this critical token naturally without requiring hard-coded rules.
  • Importance of Recent History: We found that low $\alpha$ values (0.1 to 0.3) often yielded the best results, suggesting that immediate context is a superior predictor of token importance for many tasks.
  • Task-Specific Memory Requirements: Interestingly, benchmarks like MathQA performed better with higher $\alpha$ values. This indicates that mathematical reasoning requires the model to maintain a "longer memory" to track variables or numbers introduced earlier in the prompt.

5. Conclusion and Future Work

A2SF addresses a fundamental limitation in token pruning for Transformer decoders by mitigating the seniority bias caused by causal masking. By introducing a forgetting factor, A2SF enables more accurate token selection and significant memory savings.

Future research could explore Adaptive Forgetting Factors, where $\alpha$ is dynamically adjusted for different layers or attention heads. Additionally, integrating A2SF with other compression techniques, such as quantization or low-rank decomposition, could lead to even greater efficiency in large-scale model deployment.

Summary updated

Abstract

Recently, large language models (LLM) based on transformers are facing memory bottleneck issues due to KV cache, especially in long sequence handling. Previous researches proposed KV cache compression techniques that identify insignificant tokens based on Accumulative Attention Scores and removes their items from KV cache, noting that only few tokens play an important role in attention operations. However, we have observed that the existing Accumulative Attention Score is not suitable for the transformer decoder structure. In the decoder model, the number of times the Attention Score accumulates varies depending on the order of token appearance due to the effect of masking, causing an uneven comparison between tokens. To solve this, we propose Accumulative Attention Score with Forgetting Factor (A2SF) technique, which introduces a Forgetting Factor in the Attention Score accumulation process. A2SF applies a penalty to the past Attention Score generated from old tokens by repeatedly multiplying the Forgetting Factor to the Attention Score over time. Therefore, older tokens receive a larger penalty, providing fairness among different ages of tokens. Through the fair comparison among tokens, we can more effectively select important tokens. We have verified the accuracy improvement through A2SF in the OPT and LLaMA models and A2SF improves the accuracy of LLaMA 2 by up to 7.8% and 5.1% on 1-shot and 0-shot.
BibTeX
@misc{jo2024sf,
  author = {Hyun-rae Jo and Dongkun Shin},
  title = {{A2SF: Accumulative Attention Scoring with Forgetting Factor for Token Pruning in Transformer Decoder}},
  year = {2024},
  eprint = {2407.20485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.20485},
}
Figure