LM-Infinite: Simple On-the-Fly Length Generalization for Large Language Models

Chi Han, Qifan Wang, Wenhan Xiong, Yu Chen, Heng Ji, Sinong WangSubmission to ICLR 2024 · Withdrawn

TL;DR

Large Language Models (LLMs) notoriously break down and produce gibberish when evaluated on sequences longer than their pre-training length, even when using relative positional encodings. This paper identifies three out-of-distribution (OOD) failure modes—exploding attention logits, attention entropy dilution, and the loss of implicitly encoded initial tokens—and introduces LM-Infinite. Requiring zero fine-tuning or parameter updates, LM-Infinite combines a $\Lambda$-shaped attention mask with a distance bound to enable robust generation on sequences up to 128k tokens with $O(n)$ complexity and a 2.72× decoding speedup.

What Problem Does This Paper Address?

Most modern LLMs are pre-trained on fixed, relatively short context windows (e.g., 2,048 or 4,096 tokens) due to the quadratic $O(n^2)$ computational complexity of standard self-attention. When practitioners push these models to generate or process long documents, the models experience severe length generalization failures: generation degrades into incoherent repetitions, perplexity explodes, or computations output NaN values.

While relative position encodings (like RoPE and ALiBi) theoretically support arbitrary distances, they fail in practice on unseen lengths. Standard remedies like long-context fine-tuning are computationally prohibitive. The authors investigate why this degradation happens at the feature level and seek an on-the-fly, training-free solution.

Methods

Through theoretical analysis and empirical diagnostics, the authors identify three root OOD factors:

  1. Unseen Distances: Distinguishing unseen distances requires attention logits to diverge to infinity, producing out-of-distribution logit magnitudes.
  2. Unseen Number of Attended Tokens: As sequence length increases, standard softmax entropy scales as $\Omega(\ln n)$, flattening the attention distribution and diluting information.
  3. Loss of Implicitly-Encoded Absolute Positions: Even without absolute position embeddings, models use the initial sequence tokens as coordinate anchors in hidden space (visualized via PCA). Pure sliding-window attention drops these tokens, causing catastrophic degradation.

To resolve these issues without retraining, the authors introduce LM-Infinite, consisting of two lightweight modifications:

  • $\Lambda$-Shaped Attention Mask: Each token attends only to the initial $n_{\text{global}}$ tokens (a global anchor branch, typically 10–100 tokens) and the most recent $n_{\text{local}}$ tokens (a local sliding window set equal to pre-training length $L_{\text{pretrain}}$). All middle tokens are masked out.
  • Distance Limiting: For tokens in the global branch whose actual distance exceeds the training limit, the effective distance is clipped: $\min(d, L_{\text{pretrain}})$. In RoPE, this is achieved by freezing key rotations and rotating queries by a fixed angle corresponding to $L_{\text{pretrain}}$; in ALiBi, the negative bias offset is clipped to $-|m L_{\text{pretrain}}|$.

Datasets

The authors evaluated LM-Infinite on:

  • The Pile (ArXiv and OpenWebText2 subsets): Used to assess language modeling perplexity, negative log-likelihood (NLL), and generation quality (BLEU and ROUGE-LSum) on sequence lengths spanning 2k to 128k tokens across LLaMA-7B, Llama-2-7B, MPT-7B, and GPT-J-6B.
  • Passkey Retrieval: A synthetic long-context retrieval benchmark used to measure whether models can locate a hidden key buried inside long distraction texts.

Key Insights and Ideas

  • The Dilemma of Distant Logits vs. Entropy: You cannot simply let relative distances grow unboundedly. Either attention logits must explode toward infinity to maintain discriminability between long distances, or the distribution's entropy grows unboundedly and flattens the signal.
  • Initial Tokens Act as Attention Anchors: A naive local sliding window fails on LLMs because transformers implicitly encode global coordinates through the first few tokens. Preserving just 10 to 100 initial tokens ("attention sinks") stabilizes hidden-state representations across all layers.
  • Exact Distances Do Not Matter for Distant Context: Distant tokens primarily serve as representations of global context and anchor features rather than precise positional targets. Bounding relative distance to the model's training limit keeps internal activations squarely inside the pre-trained distribution.

Key Results

  • Perplexity Stabilization: LM-Infinite flattens the perplexity curves of LLaMA, Llama-2, GPT-J, and MPT-7B out to 128k tokens, whereas vanilla models spiked to catastrophic perplexity or failed with out-of-memory errors past ~32k.
  • Outperforming Fine-Tuning Baselines: On ArXiv and OpenWebText2 benchmarks, LM-Infinite achieved the best perplexity on 7 out of 9 context-length milestones, performing on par with models explicitly fine-tuned on long sequences (such as MPT-7B-Storywriter).
  • Efficiency Gains: On 32k-length sequences with Llama-2-7B, LM-Infinite provided a 3.16× encoding speedup and a 2.72× decoding speedup, maintaining $O(n)$ computational complexity and constant GPU memory per decoding step.
  • Generation Quality: On continuous 10k-token generation tests, LM-Infinite outperformed simple context truncation by ~5 BLEU points while using only 25% of the computation.

Limitations and Future Work

  • Information Loss in Middle Tokens: Because tokens in the middle region are masked out from direct self-attention, LM-Infinite relies on hierarchical propagation across layers. In fine-grained information retrieval (such as passkey retrieval), accuracy gradually decays over long sequences, reflecting a "lost-in-the-middle" phenomenon.
  • Future Directions: Developing mechanisms that allow LM-Infinite to selectively route or compress critical information from the masked-out middle region without re-introducing quadratic overhead or OOD positional artifacts.

Summary updated

Abstract

In recent years, there have been remarkable advancements in the performance of Transformer-based Large Language Models (LLMs) across various domains. As these LLMs are deployed for increasingly complex domains, they often face the need to follow longer user prompts or generate longer texts. In these situations, the length generalization failure of LLMs on long sequences becomes more prominent. Most pre-training schemes truncate training sequences to a fixed length. LLMs often struggle to generate fluent and coherent texts after longer contexts, even with relative positional encoding specifically designed to cope with this problem. Common solutions such as finetuning on longer corpora often involve daunting hardware and time costs and require careful training process design. To more efficiently extrapolate existing LLMs’ generation quality to longer texts, we theoretically and empirically investigate the main out-of-distribution (OOD) factors contributing to this problem. Inspired by this diagnosis, we propose a simple yet effective solution for on-the-fly length generalization, LM-Infinite. It involves only a $\Lambda$-shaped attention mask (to avoid excessive attended tokens) and a distance limit (to avoid unseen distances) while requiring no parameter updates or learning. We find it applicable to a variety of LLMs using relative-position encoding methods. LM-Infinite is computationally efficient with $O(n)$ time and space, and demonstrates consistent text generation fluency and quality to as long as 128k tokens on ArXiv and OpenWebText2 datasets, with 2.72x decoding speedup. We will make the codes publicly available following publication.
BibTeX
@misc{han2023lm,
  author = {Chi Han and Qifan Wang and Wenhan Xiong and Yu Chen and Heng Ji and Sinong Wang},
  title = {{LM-Infinite: Simple On-the-Fly Length Generalization for Large Language Models}},
  year = {2023},
  eprint = {2308.16137},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.16137},
}

Loading related content...

Figure