참석하기 전에 미리 살펴보세요: 효율적인 LLM 추론을 위한 스케치-앤-워크 희소 어텐션

Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference

자기-어텐션은 사전 채우기(prefill) 및 디코딩 단계 모두에서 긴 컨텍스트를 가진 LLM 추론의 계산 및 메모리 비용을 지배합니다. 이러한 문제를 해결하기 위해, 저희는 훈련 없이 적용 가능한 희소 어텐션 방법인 스케치-앤-워크 어텐션(Sketch&Walk Attention)을 소개합니다. 스케치-앤-워크는 경량 스케치를 사용하여 저렴한 어텐션 점수 근사를 얻은 다음, 토큰 간의 직접적인 상호 작용을 넘어 어텐션 영향을 포착하는 워크 메커니즘을 통해 이러한 추정치를 레이어 전체에서 집계합니다. 누적된 워크 점수는 상위 k개의 어텐션 블록을 선택하는 데 사용되며, 이는 사전 채우기 및 디코딩 단계 모두에 적용 가능한 단일의 훈련 없이 동작하는 알고리즘과 함께 동적 희소성을 가능하게 합니다. 다양한 모델과 작업에서, 스케치-앤-워크는 20%의 어텐션 밀도에서 거의 손실 없는 정확도를 유지하며, 특정 환경에서는 밀집 어텐션보다 약간 더 나은 성능을 보일 수 있으며, 최대 6배의 추론 속도 향상을 달성합니다.

Self-attention dominates the computational and memory cost of long-context LLM inference across both prefill and decode phases. To address this challenge, we introduce Sketch&Walk Attention, a training-free sparse attention method that determines sparsity with lightweight sketches and deterministic walk. Sketch&Walk applies Hadamard sketching to get inexpensive approximations of attention scores, then aggregates these estimates across layers via a walk mechanism that captures attention influence beyond direct interactions between tokens. The accumulated walk scores are used to select top-k attention blocks, enabling dynamic sparsity with a single training-free algorithm that applies uniformly to both the prefill and decode phases, together with custom sparse attention kernels. Across a wide range of models and tasks, Sketch&Walk maintains near-lossless accuracy at 20% attention density and can slightly outperform dense attention in some settings, while achieving up to 6x inference speedup.