O(n²) 병목

제곱 비용은 상수 계수로 달랠 문제가 아니야

어텐션 점수 행렬의 크기는 n × n이야. 시퀀스 길이가 1K면 원소가 백만 개지만, 100K가 되면 100억 개로 불어나. 최종 출력에 이 행렬을 남기지 않더라도 표준 구현은 softmax를 계산하는 동안 이를 다뤄야 해. 저장 방식을 바꿔도 O(n²·d) 연산은 남기 때문에 계산량과 메모리 부담이 모두 시퀀스 길이의 제곱에 비례해 커져.

이건 영리한 구현만으로 없앨 수 있는 사소한 불편이 아니야. 문맥을 두 배로 늘리면 어텐션 비용은 네 배가 돼. 8K에서 128K로 16배 늘리면 연산량은 256배가 되지. 어느 순간부터는 GPU 메모리에 담기지 않고, 메모리 문제를 넘겨도 실행 시간을 감당하기 어려워져.

FlashAttention이 고친 것과 남겨 둔 것

FlashAttention(Dao et al., 2022, FlashAttention-3는 2024)은 이 시대의 가장 중요한 시스템 연구 가운데 하나야. 어텐션 행렬의 타일을 GPU 안의 빠른 SRAM에 머물게끔 계산 순서를 바꿔, 느린 HBM과 데이터를 끊임없이 주고받는 일을 줄여. FlashAttention-3는 Hopper의 비동기 TMA 복사와 FP8 양자화를 활용해 H100 이론 성능의 약 85%까지 끌어냈어.

하지만 FlashAttention이 줄인 것은 상수 계수야. O(n²·d)라는 계산 복잡도는 그대로 남아 있어. 실전에서 벽을 만나는 지점을 멀리 밀었을 뿐, 벽 자체를 허문 건 아니지. 백만 토큰 문맥을 처리하려면 더 나은 커널만이 아니라 다른 알고리즘이 필요해.

실제 한계는 어디서 드러날까

학습할 때는 문맥 창을 늘리다가 OOM 오류로 만나고, 추론할 때는 긴 문맥 서비스의 처리량이 무너지는 모습으로 만나. 소비자용 하드웨어에서는 훨씬 가혹해. 2025년 연구에서 Transformer는 24GB 소비자용 GPU로 약 25K 토큰을 넘지 못했지만, 비슷한 규모의 SSM은 같은 카드에서 220K 토큰 이상을 처리했어. 이 격차가 나머지 퀘스트의 출발점이야.

Code

fp16 어텐션 행렬의 메모리 증가·python

def attention_bytes(seq_len, n_heads=32, dtype_bytes=2):
    # Score matrix: heads * n * n entries, 각 entry `dtype_bytes` 바이트
    return n_heads * seq_len * seq_len * dtype_bytes

for n in [1024, 4096, 32_768, 131_072, 1_000_000]:
    gb = attention_bytes(n) / (1024 ** 3)
    print(f'{n:>10} tokens -> {gb:>8.2f} GB attention matrix')
# 1024       -> 0.06 GB
# 4096       -> 1.0 GB
# 32768      -> 64.0 GB     <-- 이미 단일 H100 80GB 초과
# 131072     -> 1024.0 GB
# 1000000    -> ~59 TB

Exercise

로컬에서 실행할 수 있는 Hugging Face Transformers 모델을 하나 골라 봐. Llama 3.2 1B라면 노트북에서도 충분해. attn_implementation="eager", "sdpa", 그리고 하드웨어가 지원한다면 "flash_attention_2"를 차례로 설정하고 시퀀스 길이 512, 4K, 32K에서 프리필 지연 시간을 측정해. 로그-로그 축에 지연 시간과 시퀀스 길이를 그리면 긴 시퀀스에서 세 구현의 기울기가 모두 2에 가까워져야 해. 그 기울기가 커널과 무관하게 남는 O(n²) 특성을 보여 줘.