Lil: 긴 디코딩 단계에서 사후 학습 희소 어텐션 알고리즘을 적용할 때, '적은 것이 더 적다' 현상

Lil: Less is Less When Applying Post-Training Sparse-Attention Algorithms in Long-Decode Stage

대규모 언어 모델(LLM)은 다양한 복잡한 작업에서 뛰어난 성능을 보이며, 점점 더 많은 곳에 배포되고 있어 추론 효율성에 대한 요구가 높아지고 있습니다. 기존 연구에서는 추론 과정을 일반적으로 '프리필(prefill)' 단계와 '디코딩(decode)' 단계로 나누는데, 디코딩 단계가 전체 지연 시간의 대부분을 차지합니다. 디코딩 단계의 시간 및 메모리 복잡성을 줄이기 위해, 다양한 희소 어텐션 알고리즘이 제안되었습니다. 본 논문에서는 실험적 및 이론적 분석을 통해, 희소 어텐션이 역설적으로 전체적인 복잡성을 증가시킬 수 있음을 보여줍니다. 정보 손실은 종종 훨씬 더 긴 시퀀스를 유발하며, 우리는 이러한 현상을 '적은 것이 더 적다(Less is Less)' (Lil)라고 명명합니다. Lil 문제를 완화하기 위해, 희소 디코딩 과정에서 정보 손실이 정보 이득을 초과하는 지점을 감지하는 조기 중단(early-stopping) 알고리즘을 제안합니다. 제안하는 조기 중단 알고리즘은 추론 토큰 소비량을 최대 90%까지 줄이면서, 추론 집약적인 벤치마크에서 정확도 저하가 2% 미만으로 발생하는 것을 확인했습니다.

Large language models (LLMs) demonstrate strong capabilities across a wide range of complex tasks and are increasingly deployed at scale, placing significant demands on inference efficiency. Prior work typically decomposes inference into prefill and decode stages, with the decode stage dominating total latency. To reduce time and memory complexity in the decode stage, a line of work introduces sparse-attention algorithms. In this paper, we show, both empirically and theoretically, that sparse attention can paradoxically increase end-to-end complexity: information loss often induces significantly longer sequences, a phenomenon we term ``Less is Less'' (Lil). To mitigate the Lil problem, we propose an early-stopping algorithm that detects the threshold where information loss exceeds information gain during sparse decoding. Our early-stopping algorithm reduces token consumption by up to 90% with a marginal accuracy degradation of less than 2% across reasoning-intensive benchmarks.