Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Large language models achieve superior performance on tasks that require extended reasoning, but long chains of thought make the KV cache a severe memory bottleneck. Existing KV cache compression methods share one paradigm: score each cached token by some estimate of how much it will matter later, and keep the top-scoring ones. We show that the selection signal contributes almost nothing. Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no score at all; across four models and six reasoning tasks it matches the strongest prior evictor while serving 32-43% higher throughput than it in vLLM deployment. Controlled experiments explain this by showing that 1) the prompt is the fragile part of the cache, and most of the gap between selectors is just whether their selection signal happened to keep it; 2) the reasoning trace protects itself against eviction with redundancy at two levels, in the text (the model restates what it still needs as it works) and across attention heads (each keeps its own copy of the trace), so once the prompt is safe, a random draw retains enough copies of what the model still needs, and no score is required to pick them. Our code is publicly available at https://github.com/SalesforceAIResearch/Random-Attention.

한 줄 요약

Random Attention은 KV 캐시에서 무작위 추출을 통해 기존 선택 신호를 대체하면서도 성능을 유지하고 처리량을 32–43% 증가시킨다.

핵심 기여도

Random Attention은 KV 캐시에서 토큰을 점수 없이 무작위로 추출하며, Qwen3-4B, 14B, 32B 및 Phi-4-reasoning 모델에서 기존 최고 성능과 유사한 결과를 보임.
vLLM 배포 환경에서 32–43% 더 높은 처리량(tokens per second)를 달성.
기존 선택 신호가 정확도에 거의 기여하지 않음을 실험적으로 입증.
프롬프트 보호가 성능 차이의 주요 요인임을 밝힘.

핵심 아이디어

기존 KV 캐시 추방 방법은 각 토큰에 점수를 매겨 중요한 토큰을 유지하는 방식을 따랐다. 그러나 본 연구는 이 점수 신호가 정확도에 거의 기여하지 않음을 밝혔다. Random Attention은 프롬프트를 보호하고, 각 어텐션 헤드 내에서 토큰을 무작위로 추출함으로써 KV 캐시를 관리한다. 이는 어떤 점수 계산도 하지 않으며, 처리량을 크게 향상시킨다. 연구는 두 가지 핵심 통찰을 제시한다: 첫째, 프롬프트는 캐시에서 가장 취약한 부분이며, 이 보호 여부가 성능 차이의 주요 원인이다. 둘째, 추론 과정은 텍스트 내부와 어텐션 헤드 간에 중복되어 저장되며, 이 중복성 덕분에 무작위 추출도 충분한 정보를 유지할 수 있다.

기술적 접근법

**Random Attention 알고리즘**: 프롬프트는 보호하고, 각 어텐션 헤드 내에서 토큰을 무작위로 추출. 점수 계산 없이 처리.
**모델**: Qwen3-4B, 14B, 32B 및 Phi-4-reasoning.
**데이터셋**: 수학, 과학, 코드 태스크 6개 포함.
**배포 환경**: vLLM을 통해 32–43% 더 높은 처리량(tokens per second) 달성.
**제어 실험**: 프롬프트 보호 여부에 따라 성능 차이가 발생함을 확인. 중복 저장 구조를 통해 무작위 추출도 충분한 정보 유지 가능.

주요 결과

**모델 성능**: 4개 모델과 6개 추론 태스크에서 Random Attention은 기존 최고 기준과 유사한 정확도를 달성.
**처리량**: vLLM 배포 환경에서 32–43% 더 높은 tokens per second.
**비교 실험**: 60개 기준 비교 중 31개에서 Random Attention이 우수함. 유일한 예외는 Qwen3-32B의 코드 추론 태스크로, 이는 프롬프트 길이 때문임.
**프롬프트 보호**: 모든 방법이 프롬프트를 보호하면 대부분의 성능 차이는 사라짐.

의의 및 한계

Random Attention은 KV 캐시 추방 문제를 순위 매기기 문제에서 벗어나, 프롬프트 보호와 중복 저장 구조에 집중함으로써 새로운 관점을 제시한다. 이는 추론 모델의 배포 효율성을 크게 향상시키며, 새로운 선택 신호가 기존 기준을 넘어서야 한다는 기준을 제시한다. 그러나 코드 태스크에서 프롬프트 길이가 캐시 예산을 소모하는 한계가 있으며, 단일 언급된 희귀 사실은 콘텐츠 기반 신호 없이 복구하기 어렵다는 점도 지적된다.

실용적 활용

Random Attention은 메모리 예산 하에서 추론 모델을 배포할 때 기본 추방 정책으로 사용할 수 있으며, vLLM과 같은 배포 프레임워크와 호환된다. 특히, 추론 성능을 유지하면서 처리량을 향상시켜야 하는 산업적 응용(예: 대규모 모델 서비스, 실시간 추론)에 유용하다.