Introduction

LLM의 입력 길이를 늘리려는 시도는 attention의 quadratic cost와 정면으로 충돌하기 때문에, long-range context는 architectural 변경, training 방법론, 그리고 평가 방법론까지 동시에 다루지 않으면 풀리지 않는 문제입니다. 본 글에서는 (1) attention 자체를 대체하거나 압축하는 architecture, (2) 외부 메모리 또는 recurrence를 사용하는 접근, (3) train length를 넘어선 길이로 extrapolate 하기 위한 positional encoding 변형, (4) long context를 평가하기 위한 benchmark, (5) 실제 LLM이 long context를 어떻게 사용하는지에 대한 분석 연구를 묶어서 정리합니다.

State Space Models

attention을 대체하는 가장 유력한 흐름 중 하나입니다. continuous-time linear dynamical system을 sequence layer로 사용해, sequence length에 대해 linear time으로 동작합니다.

Efficiently Modeling Long Sequences with Structured State Spaces (S4), ICLR 2022

TL; DR: HiPPO 기반의 structured state matrix를 활용해, state space model을 long sequence에서 안정적으로 학습 가능하게 만든 모델입니다.

기존 문제: vanilla SSM은 long sequence에서 학습이 불안정하거나 메모리 효율이 떨어졌습니다. 그렇다고 attention을 그대로 두면 길이에 대해 quadratic cost가 발생합니다.

논문의 접근: state matrix A를 normal-plus-low-rank 구조로 제약하여, convolution kernel을 FFT 기반으로 효율적으로 계산할 수 있게 했습니다. Long Range Arena의 Path-X (16k length) 에서 transformer 계열이 chance level에 머무르던 task를 처음으로 풀어냈습니다.

개인 의견 :

Simplified State Space Layers for Sequence Modeling (S5), ICLR 2023

TL; DR: S4의 SISO(single-input single-output) head 구조를 MIMO 구조로 통합하고 parallel scan으로 단순화한 후속 연구입니다.

논문의 접근: S4가 head별로 독립적인 SISO state를 두던 것을, 하나의 MIMO state로 통합하고 diagonal-only state matrix로 단순화했습니다. 결과적으로 LRA에서 평균 87.4%, Path-X 98.5%로 SOTA를 갱신했습니다.

개인 의견 :

Mamba: Linear-Time Sequence Modeling with Selective State Spaces, 2023

TL; DR: SSM의 state transition을 input-dependent하게 만들어 transformer에 준하는 language modeling 성능을 처음으로 보여준 모델입니다.

기존 문제: 기존 SSM은 LTI(linear time-invariant) system으로 모든 토큰에 동일한 state transition을 적용했기 때문에, content-dependent한 selection이 필요한 task (e.g. selective copying, induction head) 에서 transformer에 비해 뒤처졌습니다.

논문의 접근: state space의 B, C, Δ parameter를 input-dependent하게 만들어 token별로 어떤 정보를 state에 누적할지 선택할 수 있게 했습니다. parallel scan을 SRAM-aware하게 구현한 hardware-aware kernel로, 실제 wall-clock에서도 transformer 대비 큰 우위를 보입니다.

개인 의견 :

Compressed / Low-rank Attention

attention matrix를 low-rank 또는 kernel approximation으로 대체하여 quadratic cost를 줄입니다. accuracy-efficiency tradeoff가 비교적 명시적입니다.

Linformer: Self-Attention with Linear Complexity, 2020

TL; DR: key/value의 length 차원을 학습된 projection matrix로 압축하여 attention complexity를 O(n)으로 낮춥니다.

논문의 접근: K, V (∈R^{n×d})를 P_K K, P_V V (∈R^{k×d})로 projection합니다. self-attention matrix가 low-rank라는 empirical observation에 기반합니다.

개인 의견 :

Rethinking Attention with Performers, ICLR 2021

TL; DR: softmax kernel을 random feature map으로 unbiased approximate 하여 attention을 linear time으로 계산합니다.

논문의 접근: softmax(QK^T)V를 φ(Q)(φ(K)^T V) 형태로 reformulate합니다. naive random feature는 negative variance 문제가 있어, FAVOR+(Fast Attention Via positive Orthogonal Random features)로 stable한 feature를 구성했습니다.

개인 의견 :

Nyströmformer, AAAI 2021

TL; DR: Nyström 방법으로 attention matrix를 landmark token에 대한 sub-block들로 근사합니다.

개인 의견 :

Perceiver: General Perception with Iterative Attention, ICML 2021

TL; DR: 작은 latent array를 두고, cross-attention으로 long input을 latent로 압축한 뒤 그 위에서 self-attention을 반복합니다.

논문의 접근: attention complexity를 O(n×k)와 O(k^2)의 합으로 분리하여 input length n과 모델 capacity k를 decouple합니다. 입력 modality에 거의 의존하지 않는 general purpose backbone으로 제안되었습니다.

개인 의견 :

Memory-augmented

명시적인 memory tensor를 두고 그 위에 read/write를 학습합니다. context window를 architectural하게 확장하는 대신, 외부 buffer에 정보를 저장하는 접근입니다.

Compressive Transformers for Long-Range Sequence Modelling, ICLR 2020

TL; DR: Transformer-XL의 segment cache를 한 단계 더 압축하여, old hidden state를 잃지 않고 더 긴 context를 유지합니다.

논문의 접근: Transformer-XL이 가장 오래된 segment를 그냥 drop하던 것을, learnable compression(conv 1D, max pooling 등)을 거쳐 더 작은 compressed memory로 옮긴 뒤 보관합니다. PG-19 같은 book-length corpus를 함께 제안했습니다.

개인 의견 :

Recurrent Memory Transformer, NeurIPS 2022

TL; DR: segment 단위로 sequence를 처리하되, 양 끝에 memory token을 두고 다음 segment로 전달하는 recurrent 구조입니다.

논문의 접근: segment 양 끝에 read memory token, write memory token을 두고, write token이 다음 segment의 read token으로 복사됩니다. 이렇게 하면 attention pattern을 그대로 둔 채 segment 간 정보 전달이 가능합니다.

개인 의견 :

Memformer: A Memory-Augmented Transformer for Sequence Modeling, AACL 2022

TL; DR: external memory bank에 read/write attention을 두어 linear time으로 long sequence를 처리합니다.

개인 의견 :

Recurrent / Hybrid

attention과 recurrence를 결합해, parallel training은 살리되 long range로 갈 때만 recurrent state를 사용합니다.

Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context, ACL 2019

TL; DR: segment-level recurrence와 relative positional encoding으로 fixed-length context의 한계를 우회한 고전적 연구입니다.

논문의 접근: 직전 segment의 hidden state를 cache로 가져와 현재 segment의 attention key/value에 concat합니다. relative positional encoding으로 segment 경계에서 발생하는 position 충돌을 해결합니다.

개인 의견 :

Retentive Network: A Successor to Transformer for Large Language Models, 2023

TL; DR: retention mechanism으로 attention의 parallel form, recurrent form, chunkwise form을 모두 동등하게 표현 가능하게 만든 hybrid 구조입니다.

논문의 접근: softmax 대신 exponentially decaying retention을 사용해, 학습 시에는 parallel form으로, inference 시에는 recurrent form으로 동작하도록 했습니다.

개인 의견 :

Hungry Hungry Hippos (H3): Towards Language Modeling with State Space Models, ICLR 2023

TL; DR: SSM과 multiplicative gating을 결합하여 attention 없이 language modeling을 수행합니다. Mamba의 직접적 선조에 해당하는 연구입니다.

개인 의견 :

Hyena Hierarchy: Towards Larger Convolutional Language Models, ICML 2023

TL; DR: long convolution + element-wise gating을 implicit하게 parameterize하여 attention 없이 long context를 처리합니다.

논문의 접근: convolution kernel 자체를 작은 MLP로 implicit하게 정의하여, kernel size를 sequence length 만큼 키워도 parameter는 sub-linear로 유지합니다.

개인 의견 :

Sparse Attention

attention pattern 자체를 sparse하게 만들어 quadratic cost를 sub-quadratic으로 줄입니다.

Longformer: The Long-Document Transformer, 2020

TL; DR: sliding window + dilated window + 일부 global token으로 attention pattern을 구성합니다.

개인 의견 :

Big Bird: Transformers for Longer Sequences, NeurIPS 2020

TL; DR: sliding window + global token + random attention의 조합으로, sparse attention이 universal sequence function approximator임을 이론적으로 증명했습니다.

논문의 접근: 임의의 sparse pattern이 아니라, global token을 통한 hub & spoke 구조 + 약간의 random connection으로 정보가 모든 token 쌍에 도달할 수 있음을 그래프 이론적으로 보였습니다.

개인 의견 :

Positional Encoding / Length Extrapolation

context window를 늘리는 architectural 변경 없이, 학습된 모델이 더 긴 input을 다루게 만드는 접근입니다.

ALiBi: Train Short, Test Long, ICLR 2022

TL; DR: positional embedding 대신 attention score에 거리 비례 linear bias를 더해, train length를 넘는 input에 대한 extrapolation을 가능하게 했습니다.

논문의 접근: query-key 거리 j에 대해 score에 -m·j (m은 head별 고정 slope) 를 더합니다. 학습 시 보지 못한 거리에 대해서도 monotonic decay가 유지되어, 별도의 fine-tuning 없이 더 긴 context로 일반화됩니다.

개인 의견 :

Extending Context Window of Large Language Models via Positional Interpolation, 2023

TL; DR: RoPE 기반 모델의 position index를 train length로 rescale (interpolate) 하여, 짧은 fine-tuning만으로 context window를 확장합니다.

논문의 접근: position index n을 n·(L_train/L_target)으로 scaling 하여 model이 학습한 frequency domain을 그대로 유지합니다. extrapolation은 frequency domain을 벗어나기 때문에 빠르게 망가지지만, interpolation은 학습된 영역 안에 머물기 때문에 stable합니다.

개인 의견 :

Hierarchical / Gated

hierarchical structure나 gating으로 long sequence를 처리합니다.

LongT5: Efficient Text-To-Text Transformer for Long Sequences, NAACL 2022

TL; DR: T5에 transient global attention과 local attention을 결합한 sparse attention을 도입해 16k 길이 input을 처리합니다.

개인 의견 :

Mega: Moving Average Equipped Gated Attention, ICLR 2023

TL; DR: exponential moving average (EMA) 와 gated attention을 결합하여 long-range dependency를 모델링합니다.

개인 의견 :

Benchmarks

long-range dependency 평가를 위한 대표 benchmark들입니다.

Long Range Arena (LRA): A Benchmark for Efficient Transformers, ICLR 2021

ListOps, byte-level text classification, image classification (pixel-level), Pathfinder, Path-X, retrieval로 구성된 1k–16k length benchmark. SSM 계열의 장점을 가장 잘 드러내는 평가 도구로 자리 잡았습니다. Path-X (16k 픽셀 시퀀스에서 두 점이 연결되어 있는지 판별) 가 가장 어려운 task로, 오랫동안 어떤 transformer 변형도 chance 이상의 성능을 내지 못했습니다.

LAMBADA, ACL 2016

마지막 단어를 예측하기 위해 paragraph 전체 context가 필요한 cloze-style task. discourse-level 이해도를 측정하는 고전적인 벤치마크입니다.

LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding, ACL 2024

QA, summarization, few-shot learning, code completion 등 다양한 task를 4k–32k length로 묶은 bilingual (영어/중국어) benchmark.

Needle-in-a-Haystack

Greg Kamradt의 repo에서 시작된 평가 방법으로, 긴 distractor context의 임의 위치에 정답 문장(needle)을 심어두고 retrieval 능력을 측정합니다. depth × context length의 grid로 결과를 시각화하는 컨벤션이 일반화되었습니다.

Behavior / Analysis

architecture가 아니라, 실제 모델이 long context를 어떻게 사용하는지에 대한 분석 연구들입니다.

Lost in the Middle: How Language Models Use Long Contexts, TACL 2024

TL; DR: 긴 context의 중간에 정답이 있을 때 LLM 성능이 양 끝(처음/끝)에 비해 크게 떨어지는 U-shape 현상을 정량적으로 보였습니다. 100k context를 광고하는 모델들도 동일한 패턴을 보입니다.

개인 의견 :

In-context Learning and Induction Heads, Anthropic 2022

TL; DR: in-context learning 능력의 상당 부분이 특정 attention head 패턴(induction head — [A][B]...[A]→[B] pattern을 복사하는 head)에서 비롯된다는 mechanistic 분석입니다.

개인 의견 :

A Controlled Study on Long Context Extension and Generalization in LLMs, 2024

TL; DR: position interpolation, NTK scaling 등 다양한 context extension 방법을 동일한 protocol로 비교하여, exact fine-tuning 기반 방법이 학습 범위 내에서는 효과적이지만 extrapolation은 여전히 어렵다는 점을 보고했습니다.

개인 의견 :

Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models, 2024

context length 확장 기법을 architectural, training, inference 관점으로 정리한 survey입니다.