arXiv:2606.07205v1 cs.DS

스트리밍 어텐션을 위한 정밀한 경계(Tight Bounds) 제시

Towards Tight Bounds for Streaming Attention

Justin Y. Chen, Ying Feng, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, Boris Prokhorov

제출 2026-06-05

한국어 초록

어텐션 메커니즘은 현대 트랜스포머 아키텍처의 핵심 요소입니다. 그러나 그 표현력은 2차 시간 복잡도와 선형 공간 사용량이라는 비용을 수반합니다. 특히, 고전적인 트랜스포머 아키텍처는 다음 요소를 생성하기 위해 이전에 본 모든 입력 요소(토큰)를 명시적으로 저장합니다. 제한된 공간에서 트랜스포머를 구현하는 문제는 KV 캐시 압축(KV cache compression)으로 알려져 있으며, 지난 몇 년간 큰 관심을 받아 강력한 휴리스틱(heuristics) 개발을 촉진했습니다. Haris et al., COLT'25와 Kochetkova et al., NeurIPS'25의 최근 연구들은 KV 캐시 압축을 스트리밍 어텐션 근사 문제로 공식화하여, (불일치 이론에 기반한) 상한과 정보 이론적 하한을 모두 제공했습니다. 그러나 해당 논문들은 상한과 하한 사이에 상당한 격차를 남겨두었습니다. 예를 들어, 이들의 알고리즘의 공간 사용량은 정밀도 매개변수에 따라 증가하지만, 하한은 더 강해지지 않습니다. 본 연구에서 우리는 스트리밍 어텐션 근사 문제를 다시 살펴보고, 그 공간 복잡도에 대한 거의 정밀한(nearly tight) 경계를 제공합니다. 알고리즘 측면에서, 우리는 커널 밀도 추정을 위한 세 가지 서로 다른 방법인 불일치 기반 코어셋 구성(예: Charikar-Kapralov-Waingarten'24), 다항식 방법(예: Greengard-Rokhlin'87, Alman-Song'23), 그리고 공간 분할(예: Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20) 사이의 놀라울 정도로 긴밀한 상호작용을 통해 이 결과를 달성했습니다. 하한 측면에서, 우리의 주요 기술적 기여는 다량의 사이드 정보(side information)와 함께 INDEX 문제를 사용하는 새로운 기법으로, 이 기법이 다른 고차원 기하학적 추정 문제에서도 유용할 것으로 기대합니다.

원문 초록

The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger. In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.07205v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.16003v1cs.CL공통 태그 Computational Efficiency, kv cache compression

PAIR: 읽기-추론 융합을 통한 메모리 효율적이고 빠른 추론

PAIR: Memory-Efficient and Fast Inference with Reading--Reasoning Fusion

문맥 기반 질의응답에서 단일 대형 모델을 근거 추출과 답변 추론 모두에 사용하는 것은 상당한 메모리와 연산량을 요구합니다. 기존 접근 방식들은 단일 모델 내에서 정확도와 효율성을 맞바꿉니다. 본 연구에서는 효율적인 추론을 위한 다중 모델 접근 방식을 제안합니다. 제안 방법인 PAIR는 서로 다른 크기의 두 모델을 각각 근거 추출과 답변 추론에 활용합니다. 더 작은 Reader 모델이 전체 문맥을 처리하고 유지하는 반면, 더 큰 Reasoner 모델은 문맥에 직접 어텐션을 수행하지 않고 질문과 생성된 시퀀스만을 봅니다. 이러한 기능들은 로짓(logit) 수준에서 융합됩니다. 각 토큰마다 Reader와 Reasoner가 모두 예측을 생성하며, 이들의 로짓이 하나로 결합되어 단일 다음 토큰 예측 모델처럼 동작합니다. 미세조정(fine-tuning)을 통해 성능을 더욱 향상시킵니다. HotpotQA에서 32B Reasoner를 적용한 PAIR는 동일한 32B 모델의 전체 문맥 정확도를 96% 유지하면서도 KV 메모리는 약 4분의 1만 사용합니다. 45.7K 토큰 문맥에서 PAIR는 동일한 GPU 상의 전체 문맥 32B 모델 대비 최대 3.2배 높은 엔드투엔드 처리량을 달성합니다. 또한 PAIR는 평가된 토큰 감소 베이스라인 대비 정확도-메모리 및 정확도-처리량 간의 상충 관계를 개선합니다. 이러한 정확도 보존 특성은 Qwen2.5, OLMo-3, Gemma-3 모델 패밀리 전반에 걸쳐 일반화됩니다.

arXiv:2610.03198v1cs.AI공통 태그 Computational Efficiency, kv cache compression

KV$^2$: 자체 정제형 키-값(KV) 캐시

KV$^2$: A Self-Refining KV Cache

키-값(KV) 캐시의 메모리 점유 공간은 긴 문맥(long-context) 모델의 실용적 활용을 제약하며, 사전 채움(prefilled)된 단일 문맥이 이후 여러 다양한 질의를 처리해야 할 때 비용의 대부분을 차지합니다. 이러한 재사용 환경에서 질의 무관(query-agnostic) 압축은 비용과 품질 간의 트레이드오프를 가집니다. 경량 추정기는 연산 비용이 저렴하지만 정확도가 낮고, 전체 문맥 재구성 점수 산정 방식은 더 정확하지만 전체 프롬프트(prompt)를 다시 처리해야 합니다. 본 연구에서는 선택적 재구성을 기반으로 한 질의 무관 KV 캐시 압축 기법인 KV$^2$를 소개합니다. KV$^2$는 먼저 경량 프록시 점수 산정기를 사용하여 문맥 내 유익한 토큰을 식별한 다음, 이 하위 집합만을 다시 처리하여 최종 축출(eviction) 점수를 계산합니다. RULER, Needle-in-a-Haystack, LongBench 벤치마크에서 KV$^2$는 예산이 빠듯해질수록 기준선(baseline) 대비 마진(margin) 격차를 넓힙니다. 2%의 KV 캐시 예산을 사용한 RULER 16K에서 차상위 기준선 대비 평균 점수를 40%p 이상 향상시켰으며, LongBench에서는 2%~10% 예산 전반에 걸쳐 전체 문맥 재구성 방식보다 압축 단계의 실행 시간 및 피크 메모리를 낮추면서도 가장 높은 평균 점수를 달성했습니다. 따라서 재사용 가능한 KV 캐시 압축은 전체 문맥을 다시 처리할 필요가 없습니다. 본 연구의 코드는 https://anonymous.4open.science/r/KVsquared-0B97 에서 확인할 수 있습니다.

arXiv:2610.01230v1cs.AI공통 태그 Computational Efficiency, kv cache compression

HHR: 효율적인 LLM 생성을 위한 계층적 해시 검색

HHR: Hierarchical Hash Retrieval for Efficient LLM Generation

효율적인 긴 문맥 추론(inference)은 대규모 언어 모델(LLM)에 필수적이지만, 극심한 연산 병목 현상을 유발합니다. 해시 기반 검색은 쿼리(query)와 키(key)를 이진 코드로 인코딩하고 해밍 거리(Hamming distance)를 사용하여 키를 선택함으로써 효율적인 대안을 제공합니다. 그러나 이는 해밍 거리와 어텐션(attention) 관련성 사이에 심각한 불일치를 초래합니다. 쿼리-키 로짓(logit)은 방향 유사도와 특징(feature) 크기에 함께 의존하는 반면, 해시 이진화는 크기 정보를 버리기 때문에 낮은 로짓 키의 위양성(false-positive) 검색과 높은 로짓 키의 위음성(false-negative) 누락을 모두 유발합니다. 이러한 실패를 해결하기 위해, 본 논문에서는 기하학 인식 키 라우팅(Geometry-Aware Key Routing, GKR)과 학습된 해시 투영(Learned Hash Projection, LHP)을 통해 점진적으로 검색 정확도를 향상시키는 coarse-to-fine 프레임워크인 계층적 해시 검색(Hierarchical Hash Retrieval, HHR)을 제안합니다. GKR은 헤드별 직교 변환을 학습하여 특징 크기를 재분배하고 더 변별력 있는 페이지 수준 로짓 경계를 도출함으로써, 중요한 후보를 보존하면서 낮은 로짓 키의 효과적인 가지치기(pruning)를 가능하게 합니다. 그런 다음 LHP는 미세 단위(fine-grained) 검색을 위해 해밍 거리를 실제 쿼리-키 관련성 순위와 정렬하는 헤드별 투영 공간을 학습합니다. GKR과 LHP를 결합함으로써 HHR은 위양성을 억제하고 위음성을 복구하여 해시 기반 희소 어텐션(sparse attention)의 충실도를 크게 향상시킵니다. 다양한 LLM 및 벤치마크에 걸친 광범위한 실험을 통해 HHR이 기존 방법들보다 우수한 성능을 달성함을 입증합니다. 예를 들어 LongBench에서 HHR은 평균 점수를 1.10점 향상시키며, 128K 문맥 길이에서 Llama-3.1-8B-Instruct 기준 최대 3.30배의 디코딩 속도 향상과 2.83배의 엔드투엔드 속도 향상을 달성합니다. 코드는 https://github.com/lianjunl13-sudo/HHR 에서 공개되어 있습니다.

arXiv:2609.28116v1cs.LG공통 태그 Density Estimation, Computational Efficiency

스크레이프오프 층(Scrape Off Layer) 플라즈마 시뮬레이션을 위한 확률적·기하 인지 신경망 대리 모델

Probabilistic and Geometry Aware Neural Surrogate of Scrape Off Layer Plasma Simulations

토카막 경계 플라즈마 시뮬레이션을 위한 고속 대리 모델(surrogate)은 일반적으로 전역 운전점(operating point)을 셀 값들의 평탄화된 벡터로 매핑하는 결정론적 회귀기이다. 디버터 탈부착(divertor detachment) 전이 근처에서는 정상 상태(steady state)가 단일 값으로 안정적으로 정해지지 않는다. 점 추정(point estimate)은 질적으로 서로 다른 플라즈마 상태들에 걸쳐 평균을 내야 하며, 신뢰도에 대한 어떠한 언급도 없이 결과를 내놓는다. 더욱이 평탄화된 벡터 표현은 SOLPS-ITER 메시의 기하학적 구조를 버린다. 본 연구는 이 두 가지 문제를 모두 다룬다. 우리는 곡선형(curvilinear) 메시를 셀 인접성을 보존하고 정확히 역변환되는 배치를 가진 세 개의 고정 크기 이미지 텐서로 펼쳐, 합성곱 신경망(convolutional network)이 정보 손실 없이 기하 구조 위에서 동작할 수 있도록 한다. 이후 민감도가 높은 시스템에 적합한 조건부 플로 매칭(conditional flow matching) 모델을 이 표현 위에서 학습한다. 그 결과 민감한 운전점에서도 여러 개의 그럴듯한 결과를 포착하는 효율적이고 확장 가능한 대리 모델을 얻는다. 가스 퍼프(gas-puff) 스캔을 따라, 예측 분포는 초기 레짐 전이(regime transition)를 지나면서 고온 모드와 저온 모드로 갈라진다. 크기가 알려진 분기(bifurcation)를 주입한 합성 데이터에 대한 추가 검증에서도, 모델이 두 분기의 평균이 아니라 두 분기를 각각 복원함을 확인한다.

arXiv:2609.25778v1stat.ML공통 태그 Density Estimation, Computational Efficiency

매개변수 예산 하에서 루프 추정의 통계적 이득

Statistical Gains from Looped Estimation under Parameter Budgets

인공지능에서 메모리 수요가 증가함에 따라 더 적은 학습 가능 매개변수로 학습하려는 동기가 커지고 있다. 본 연구는 반복(iteration)마다 매개변수를 공유하며 하나의 적합된 연산자를 반복 적용하는 루프 추정기(looped estimator)가 동일한 매개변수 예산 하에서 통계적 정확도를 향상시킬 수 있는지 묻는다. 이에 대응하는 기존의 비공유(untied) 추정기는 각 반복마다 별도의 매개변수를 사용한다. 일반적인 가능도(likelihood) 모델에 대해, 루프 시브(sieve) 최대 가능도 추정에 대한 제곱 Hellinger 위험의 상한과, 튜닝된 비공유 모델군에 대한 미니맥스 하한을 확립한다. 이 경계들은 매개변수-반복-정확도 간의 트레이드오프를 드러낸다. 즉, 반복 계산은 매개변수를 추가하지 않고도 근사를 개선할 수 있으나, 계산 비용과 적합된 함수 클래스의 복잡도를 증가시킨다. 알려진 Hölder 매끄러움을 갖는 목표 함수에 대해, 루프 잔차 순방향 신경망(residual feedforward network)과 특정한 post-layer-normalized 트랜스포머(Transformer)는 유계 실수 매개변수의 개수를 고정한 채로 로그 인자를 제외하고 미니맥스 다항 수렴률을 달성한다. 충분히 큰 고정 예산에서는 표본 크기가 증가함에 따라 루프 방식의 최악 사례 위험이 0으로 수렴하는 반면, 최적의 비공유 방식의 최악 사례 위험은 0으로부터 일정 수준 이상 떨어진 채로 유지된다. 명시된 예산 증가 조건 하에서는 루프 대 비공유 위험 비율 또한 0으로 수렴한다. 가우시안 및 라플라스 회귀, 이진 응답, 에너지 기반 밀도 추정을 통해 이론을 예시한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.