O(N²)의 종말: Sparse Attention과 GGUF 양자화가 만드는 100만 토큰 시대의 기술적 원리

왜 O(N²)가 문제인가: 차원의 폭발과 현실적 제약

트랜스포머 아키텍처의 Self-Attention 메커니즘은 입력 시퀀스 길이 N에 대해 O(N²) 시간 복잡도를 가진다. 이는 1,000 토큰 처리에는 약 100만 회의 어텐션 연산이 필요하지만, 100만 토큰으로 확장하면 1조 회로 기하급수적으로 증가함을 의미한다. 이 차원의 폭발은 대규모 언어 모델이 장문 컨텍스트를 학습할 수 있는 아키텍처를 갖추었더라도, 실제 추론(Inference) 단계에서 현실적인 하드웨어 제약에 부딪히게 만드는 근본적 한계다. 특히 Apple Silicon 기반의 통합 메모리 구조를 가진 일반 개발자용 머신(예: M2 맥미니 16GB) 환경에서는 문제가 더욱 심각하다. FP16 정밀도의 밀도 어텐션에서 100만 토큰 KV-cache를 저장하려면 약 384GB의 RAM이 필요한데, 이는 16GB 환경의 24배에 달하는 수치다. 업계에서는 이미 오래전부터 이 메모리 병목이 장문 처리의 가장 큰 제약 요인으로 지적되어 왔다. Sparse Attention은 이 문제를 근본적으로 재구성한다. 모든 토큰이 모든 다른 토큰에 attention을 부여하는 대신, 사전 정의된 연결 패턴에 따라 일부 토큰만 참조하도록 설계한다. 이때 각 토큰이 실제로 attends하는 평균 슬롯 수를 k로 정의하면, 전체 어텐션 복잡도는 O(N²)에서 O(N·k)로 전환된다. k가 상수(예: 64~256 범위)라면 시퀀스 길이 N이 아무리 커져도 처리량은 일정하게 유지되므로, 이론상 무한한 확장성이 가능해진다.

Sparse Attention 패턴의 핵심 분류와 작동 원리

Sparse Attention은 적용 전략에 따라 크게 세 가지 패턴으로 분류되며, 각각 다른 트레이드오프를 제공한다. 첫 번째는 슬라이딩 윈도우(Sliding Window) 어텐션이다. 각 토큰이 자기 자신 중심의 ±w 범위 내 토큰에만 attention을 부여하는 방식으로, 로컬 컨텍스트(인접 문장, 구절 간 의존성)를 효율적으로 포착한다. Longformer 연구에서는 w=256으로 설정하여 O(N·w) 복잡도를 달성했으며, WikiText-103에서 perplexity 16.3이라는 경쟁력 있는 성능을 기록했다. 두 번째는 전역 토큰(Global Token) 패턴이다. CLS 토큰이나 특수하게 설계된 글로벌 토큰이 시퀀스 전체의 모든 위치에 attention을 부여한다. 이는 로컬 윈도우만으로는 놓칠 수 있는 장거리 의존성(예: 문서 시작 부분과 끝부분 간의 의미적 연결)을 포착하는 핵심 메커니즘이다. 연구에 따르면 전역 토큰 2개를 사용하는 것이 4개 이상을 사용하는 것보다 메모리 효율이 31% 높으면서도 장거리 재현율은 11% 더 우수했다. 세 번째는 블록 스파스(Block-Sparse) 패턴으로, 어텐션 행렬을 정사각형 블록 단위로 분할한 후 일부 블록만 활성화한다. BigBird 연구에서는 임의 블록(Random Blocks), 전역 블록(Global Blocks), 슬라이딩 윈도우의 3요소를 조합하여 이론상 무제한 시퀀스 길이를 처리할 수 있음을 증명했다. 4,096 토큰 환경에서 밀도 어텐션 대비 96%의 연산량 감소를 달성했으며, 이는 FlashAttention-2 대비 34% 더 높은 처리속도를 의미한다.

GGUF KV-Cache 양자화와 K-블롭 메모리 매핑의 시너지

Sparse Attention으로 계산 복잡도를 낮추는 것만으로는 부족하다. 남은 KV-cache 자체의 메모리 사용량을 줄이는 것이 16GB RAM 환경에서의 실용화를 위한 두 번째 핵심 열쇠다. GGUF(Generic Graph Unified Format) 포맷은 이를 위해 키-값 캐시를 4-bit(Q4_K_M 등) 또는 8-bit로 양자화하는 구조를 제공한다. FP16(16비트 부동소수점) 기준 100만 토큰의 KV-cache는 약 384GB를 차지하지만, Q4_K_M 양자화를 적용하면 약 96GB까지 압축된다. 여기에 스파스 어텐션으로 활성 슬롯 수 k=64로 제한하면, 실제 필요한 물리 메모리는 약 512MB 수준으로 급감한다. llama.cpp의 구현에서는 이를 K-블롭(K-Blob) 메모리 매핑 기술과 결합한다. K-블롭은 GGUF 모델 파일을 메모리 매핑(mmap)하여, 초기 로딩 시 전체 파일을 물리 메모리에 적재하지 않고 필요한 페이지만 선택적으로 로드하는 온디맨드 페이징(On-Demand Paging)을 구현한다. 100만 토큰 컨텍스트 처리에 실제로 필요한 물리 메모리는 약 6.8GB로, 16GB RAM 시스템에서 여유 공간을 충분히 확보할 수 있는 수준이다. 양자화 정밀도 선택은 중요한 트레이드오프를 수반한다. Q4_K_M은 최대 절감 효과를 제공하지만 FP16 대비 0.5~1.2%의 정확도 손실을 유발한다. Longformer 평가에서는 장문 QA 태스크에서 약 2.3%의 정확도 하락이 관찰되었다. 반면 Q5 양자화는 Q4 대비 3.2%의 정확도 개선 효과를 보이지만, 메모리 절감률이 60%에서 40%로 낮아져 대형 모델(13B 파라미터 이상)에서는 여전히 16GB 제한을 초과하여 OOM(Out Of Memory)이 발생한다.

한계점 및 주의사항

Sparse Attention과 GGUF 양자화의 결합은 강력한 기술이지만, 여러 현실적 한계가 존재한다. 첫째, 활성 슬롯 수 k가 1,024 이상으로 증가하면 스파스 어텐션의 오버헤드가 오히려 성능을 저하시킨다. 연구에 따르면 k≥1024 환경에서는 전체 어텐션 대비 8~12% 낮은 처리속도를 보이며, 이는 sparse 마스크 생성 및 라우팅 오버헤드가 계산 절감 효과를 상쇄하기 때문이다. 둘째, 레이어별 스파스 패턴 불일치 문제다. 트랜스포머의 저층(Low Layers)에서는 로컬 패턴(슬라이딩 윈도우)이 효과적이지만, 고층(High Layers)에서는 전역 패턴(Global Token)이 더 중요한 정보를 포착한다. 모든 레이어에 단일 패턴을 적용하면 정보 손실이 발생하며, 동적 레이어별 패턴 조정은 실시간 추론 속도를 저하시킨다. 셋째, 13B 파라미터 이상의 대형 모델은 Q4 양자화에서도 16GB 통합 메모리 환경에서 OOM(Out Of Memory)이 약 73%의 확률로 발생한다. 이는 모델 가중치 자체의 크기(K-블롭으로 일부 해결 가능)와 KV-cache 오버헤드가 합쳐져 사용 가능한 물리 메모리를 초과하기 때문이다. 넷째, 양자화 오차 전파 문제다. 4-bit 양자화는 FP16 대비 0.5~1.2%의 정확도 손실을 유발하며, 스파스 패턴이 이를 보완하지 못하면 최종 출력 품질이 저하된다. 특히 장문 QA 태스크에서는 약 2.3%의 추가 정확도 하락이 관찰되었다. 다섯째, 구현 복잡도 증가다. GGUF 메타데이터에 스파스 마스크를 인코딩하고 런타임에 올바른 연결 그래프를 구축하는 과정은 표준 밀도 어텐션 구현 대비 30~40%의 코드 증가를 유발한다. > 이 주제의 전체 맥락 방향성은 **8. 나는 더 이상 예전 방식으로 일하지 않는다.** 원본 글에 세밀하게 정리되어 있습니다. 더 깊게 탐구하고 싶다면 관련 내부 대표 문서(Pillar/Entity)를 참조하세요.

자주 묻는 질문