스트리밍 어텐션 (Streaming Attention)의 타이트한 경계(Tight Bounds)를 향하여

어텐션 (Attention) 메커니즘은 현대 트랜스포머 (Transformer) 아키텍처의 초석입니다. 하지만 그 표현력은 이차 시간 복잡도 (Quadratic runtime)와 선형 공간 사용량 (Linear space usage)이라는 대가를 치릅니다. 특히, 전통적인 트랜스포머 아키텍처는 다음 요소를 생성하기 위해 이전에 본 모든 입력 요소(토큰, tokens)를 명시적으로 저장합니다. KV 캐시 압축 (KV cache compression)으로 알려진 제한된 공간 내에서의 트랜스포머 구현 문제는 지난 몇 년 동안 많은 관심을 받아왔으며, 강력한 휴리스틱 (Heuristics)의 발전을 촉진했습니다. Haris 등의 최근 연구 (COLT'25)와 Kochetkova 등의 연구 (NeurIPS'25)는 KV 캐시 압축을 스트리밍 어텐션 근사 문제 (Streaming attention approximation problem)로 공식화하였으며, 불일치 이론 (Discrepancy theory)에 기반한 상한 (Upper bounds)과 정보 이론적 하한 (Information theoretic lower bounds)을 모두 제공했습니다. 그러나 해당 논문들은 상한과 하한 사이에 상당한 간극을 남겨두었습니다. 예를 들어, 그들의 알고리즘의 공간 사용량은 정밀도 파라미터 (Precision parameter)에 따라 증가하지만, 하한은 더 강력해지지 않습니다. 본 연구에서 우리는 스트리밍 어텐션 근사 문제를 재검토하고, 그 공간 복잡도 (Space complexity)에 대해 거의 타이트한 경계 (Nearly tight bounds)를 제공합니다. 알고리즘 측면에서, 우리는 커널 밀도 추정 (Kernel density estimation)을 위한 세 가지 서로 다른 방법 사이의 놀라울 정도로 긴밀한 상호작용을 통해 이 결과를 달성했습니다: 불일치 기반 코어셋 구축 (Discrepancy-based coreset constructions, 예: Charikar-Kapralov-Waingarten'24), 다항식 방법 (Polynomial method, 예: Greengard-Rokhlin'87, Alman-Song'23), 그리고 공간 분할 (Space partitioning, 예: Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). 하한 측면에서 우리의 주요 기술적 기여는 대량의 부가 정보 (Side information)를 가진 INDEX 문제를 사용하는 새로운 기법이며, 이것이 다른 고차원 기하학적 추정 문제 (High dimensional geometric estimation problems)에서도 유용하게 쓰이기를 기대합니다.