🤖 AI

Recency/Frequency Adaptive KV Caching for Large Language Model Serving

이 논문은 전통적인 LRU 정책에 내재된 워크로드 간섭을 완화하기 위해 캐시 공간을 동적으로 할당하는 최신성/빈도수 적응형 KV 캐싱 전략을 제안하며, 이를 통해 다양한 LLM 추론 워크로드에서 히트율과 첫 번째 토큰 생성 시간(time-to-first-token)을 크게 개선한다.

원저자: Yang Shen, Meghana Madhyastha, Robert Underwood, Bogdan Nicolae, Randal Burns

게시일 2026-06-23

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yang Shen, Meghana Madhyastha, Robert Underwood, Bogdan Nicolae, Randal Burns

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 아주 바쁘고 속도가 빠른 도서관을 운영하고 있다고 상상해 보세요. 이곳에서는 똑똑한 로봇 사서(대규모 언어 모델)가 사람들이 이야기를 쓰거나, 질문에 답하거나, 대화를 나누는 것을 돕습니다.

빠르게 작업하기 위해, 이 로봇은 가장 최근의 그리고 가장 중요한 정보들을 바로 옆 책상 위에 '컨닝 페이퍼' 형태로 보관합니다. 기술 세계에서는 이를 **KV 캐시(KV Cache)**라고 부릅니다. 이것은 로봇이 다음 단어를 써 내려갈 때마다 대화 내용이나 긴 문서를 처음부터 다시 읽어야 하는 수고를 덜어줍니다.

하지만 로봇의 책상은 작습니다. 한 번에 놓을 수 있는 컨닝 페이퍼의 페이지 수가 정해져 있죠. 책상이 가득 차면, 로봇은 새로운 페이지를 위한 공간을 만들기 위해 기존의 페이지 몇 장을 버려야 합니다.

문제점: "최근 들어온 것이 먼저 나간다"는 실수

현재 대부분의 로봇 사서는 LRU(Least Recently Used)라는 단순한 규칙을 사용합니다. 이는 마치 이렇게 말하는 것과 같습니다: "가장 오랫동안 손대지 않은 페이지를 버리겠다."

이 방식은 모든 사람이 순서대로 같은 책을 읽고 있다면 괜찮습니다. 하지만 현실 세계는 복잡합니다:

"핫(Hot)"한 문서: 만약 50명의 서로 다른 사람들이 동일한 특정 긴 기사에 대해 질문한다고 가정해 봅시다. 로봇은 그 기사를 계속 읽고 있지만, 그 기사가 '방금 전'에 본 것은 아니라는 이유로 LR고 규칙은 그 기사를 책상에서 치워버릴 수 있습니다. 그러다 51번째 사람이 똑같은 기사에 대해 질문하면, 로봇은 그 전체 내용을 처음부터 다시 읽어야 합니다. 매우 느려지겠죠!
"신선한" 대화: 채팅 중에는 긴 대화 기록이 있을 수 있습니다. 로봇은 당신이 방금 한 말을 기억해야 합니다. 비록 당신이 이전에 했던 말이라 할지라도 말이죠.

기존의 규칙(LRU)은 너무 경직되어 있습니다. 그것은 무엇이 빈번하게 질문되는 것(핫스팟)인지, 아니면 단순히 최근에 한 번 본 것인지 구분하지 못합니다.

해결책: "적응형 책상"

이 논문의 저자들은 ARC(Adaptive Replacement Cache)라고 불리는 더 똑똑한 시스템을 만들었습니다. 이것은 로봇 사서에게 두 개의 특별한 구역이 있고, 이 구역의 크기가 실시간으로 변할 수 있는 책상을 주는 것과 같습니다:

"방금 본 것" 구역 (최신성): 로봇이 방금 전 만졌던 페이지들을 담습니다.
"매우 인기 있는 것" 구역 (빈도): 로봇이 여러 번 보았던 페이지들을 담습니다.

학습 방법:
이 시스템에는 "유령 선반(Ghost Cache)"이라는 비밀스러운 장치가 있습니다. 이 선반은 실제 페이지를 들고 있지는 않지만, 책상 위에 있었으나 버려진 것들의 목록을 가지고 있습니다.

만약 로봇이 페이지를 버렸는데, 직후에 누군가 다시 그 페이지를 찾는다면, 시스템은 "유령 선반"을 통해 이를 확인합니다.
그러면 시스템은 깨닫게 됩니다: "앗! 내가 실제로 인기 있는 것을 버렸구나. 다음에는 '매우 인기 있는' 구역에 보관했어야 했어."
그래서 시스템은 자동으로 "방금 본 것" 구역을 줄이고 "매우 인기 있는" 구역을 확장하여, 다음번에 인기 있는 항목이 들어올 자리를 만듭니다.

이는 마치 스마트한 온도 조절기처럼 학습하는 것과 같습니다: "아침에는 춥기 때문에 거실을 데워야지. 하지만 오후에는 모두가 주방에 모이니까, 열기를 그쪽으로 옮겨야겠어." 시스템은 사용자들이 실제로 무엇을 하고 있는지에 따라 메모리 공간을 '최신성'과 '빈도' 사이에서 끊임없이 조정합니다.

연구 결과

연구진은 이 새로운 "적응형 책상"을 두 가지 유형의 작업에 대해 기존의 "LRU 책상"과 비교 테스트했습니다:

문서 질문: 사람들이 긴 기사에 대해 질문하는 경우 (퀴즈 쇼와 같은 상황).
실제 채팅: 챗봇과의 실제 대화를 시뮬레이션하는 경우.

결과:

더 나은 메모리 적중률: 새로운 시스템은 적절한 페이지를 더 자주 책상 위에 유지했습니다. 문서 테스트에서 "적중률"(정보를 다시 읽지 않고 찾아내는 비율)을 최대 **10.8%**까지 향상시켰습니다.
더 빠른 답변: 로봇이 재독(re-read)을 덜 하게 됨에 따라 답변 속도가 빨라졌습니다. 문서 테스트에서 첫 단어가 나오는 시간(First Token Latency)이 최대 12.6% 감소했고, 실제 채팅 테스트에서는 약 2% 감소했습니다.
적응력: 작업의 성격이 변할 때(예: 많은 사람이 하나의 문서에 대해 질문하는 상황에서 많은 사람이 각기 다른 채팅을 하는 상황으로 변할 때), 시스템은 구역의 크기를 자동으로 조정하여 새로운 상황에 맞췄습니다.

핵심 요점

이 논문은 로봇의 메모리 관리를 유연하게 만드는 것—즉, '새로운 것'과 '인기 있는 것' 사이의 균형을 맞추는 것—이 어떻게 AI 시스템을 더 큰 컴퓨터 없이도 훨씬 더 빠르고 효율적으로 만들 수 있는지 보여줍니다. 이는 기존의 하드웨어가 더 열심히 일하는 대신, 더 똑똑하게 일하도록 만드는 소프트웨어 업그레이드입니다.

기술 요약: 대규모 언어 모델 서빙을 위한 최신성/빈도 적응형 KV 캐싱

문제 정의
대규모 언어 모델(LLM) 서빙 시스템은 모델의 크기와 컨텍스트 길이가 증가함에 따라 제한된 GPU 메모리 용량에 부담을 주는 키-값(KV) 캐시 관리 문제에 직면해 있습니다. 프리픽스 캐싱(prefix caching)과 재사용은 중복 계산을 줄이고 처리량을 개선하는 데 매우 중요하지만, 기존의 관리 전략은 주로 최소 최근 사용(LRU) 제거 정책에 의존합니다. 저자들은 LRU가 실제 LLM 워크로드에서 발견되는 다양하고 복잡한 액세스 패턴을 처리하기에는 불충분하다고 주장합니다. 구체적으로, LRU는 강한 시간적 지역성(최근 액세스)을 보이는 요청과 서로 다른 사용자 또는 세션 전반에 걸쳐 빈번하게 액세스되는 "핫스팟(hotspots)"을 구분하지 못합니다. 이러한 한계는 서로 무관한 워크로드가 서로의 캐시를 밀어내게 만들어, 특히 문서 기반 질의응답(QA)이나 다회차 대화 시나리오에서 히트율을 저하시키고 지연 시간을 증가시킵니다.

방법론
이러한 한계를 해결하기 위해, 본 논문은 적응형 교체 캐시(Adaptive Replacement Cache, ARC) 알고리즘을 vLLM 서빙 프레임워크에 통합하는 방안을 제안합니다. 이 방법론은 최근에 액세스된 항목과 빈번하게 액세스된 항목 사이에 캐시 공간을 동적으로 할당하는 하이브리드 최신성-빈도 전략을 도입합니다.

핵심 기술 구성 요소는 다음과 같습니다:

이중 큐 구조 (Dual-Queue Structure): 캐시는 논리적으로 두 개의 큐로 나뉩니다.
- L1 (최신성 큐): 한 번 액세스된 항목을 포함합니다 (물리적 캐시 $T1$ 과 고스트 캐시 $B1$ 으로 구성).
- L2 (빈도 큐): 여러 번 액세스된 항목을 포함합니다 (물리적 캐시 $T2$ 와 고스트 캐시 $B2$ 로 구성).
- 최신성 큐에 있는 항목은 두 번째 히트 발생 시 빈도 큐로 승격됩니다.
고스트 캐싱 (Ghost Caching): 시스템은 제거된 항목의 전체 KV 블록이 아닌 메타데이터만을 저장하는 "고스트 캐시"( $B1$ $B 1$ 및 $B2$ $B 2$ )를 활용합니다. 이 캐시들은 제거된 이력을 추적합니다.
- 메인 캐시에서는 미스(miss)가 발생했지만 고스트 캐시에서 히트(hit)가 발생하면, 이는 피드백 신호 역할을 합니다. $B1$ 에서의 히트는 최신성 큐( $T1$ )가 너무 작다는 것을 시사하며, $B2$ 에서의 히트는 빈도 큐( $T2$ )의 확장이 필요함을 시사합니다.
동적 파티셔닝 (Dynamic Partitioning): 고스트 캐시 히트를 기반으로, 알고리즘은 고정된 총 캐시 크기를 유지하면서 물리적 캐시 $T1$ 과 $T2$ 의 크기를 동적으로 조정합니다. 이를 통해 시스템은 새로운 핫스팟의 등장이나 사용자 활동 패턴의 변화와 같은 워크로드 변화에 적응할 수 있습니다.
통합 (Integration): 이 전략은 현대적인 서빙 시스템에서 사용되는 페이지드 어텐션(paged attention) 메커니즘에 맞춰 KV 블록 단위(예: 16 토큰)로 작동합니다. 이는 파라미터가 필요 없는(parameter-free) 방식으로 설계되었으며, vLLM의 이비터(evictor) 모듈과 직접 통합됩니다.

주요 기여

적응형 제거 정책: 본 논문은 단순한 최신성 기반 정책을 넘어 동적인 하이브리드 접근 방식을 도입함으로써, LLM 서빙에 ARC를 적용한 첫 사례를 소개합니다.
워크로드 적응성: 이 방법은 수동 튜닝 없이도 최근 액세스 패턴과 빈번한 액세스 패턴 사이에서 캐시 자원을 자동으로 균형 있게 배분하는 능력을 보여줍니다.
해석 가능성: 학습 기반 예측기를 위해 훈련이 필요한 학습 기반 접근 방식과 달리, 이 방법은 액세스 이력에 따라 캐시 공간이 어떻게 할당되는지에 대한 명확한 해석 가능성을 제공합니다.
오픈 소스 구현: 저자들은 커뮤니티 사용 및 추가 연구를 위해 vLLM과 통합된 오픈 소스 구현을 제공합니다.

실험 결과
저자들은 두 가지 주요 워크로드 유형을 사용하여 제안된 방법과 표준 vLLM LRU 베이스라인 및 정적 이중 큐 변형(DBL)을 비교 평가했습니다.

합성 문서 QA (Synthetic Document QA): QuALITY 및 WikiQA 데이터셋을 사용하고 Zipf 분포 기반의 요청 샘플링을 적용했습니다.
- 히트율 (Hit Rate): LRU 대비 최대 10.8%(QuALITY) 및 7.8%(WikiQA) 향상되었습니다.
- 첫 토큰 생성 시간 (TTFT): 최대 12.6%(QuALITY) 및 7.9%(WikiQA) 감소했습니다.
- 이러한 개선은 제거 결정이 더 빈번하게 발생하는 작은 캐시 크기에서 가장 두드러졌습니다.
실제 대화 (Real-World Conversation): Qwen-Bailian 익명 데이터셋의 트레이스(43,058개 요청)를 사용했습니다.
- 히트율: 1.1%~2.1% 개선되었습니다.
- TTFT: 1.0%~2.0% 감소했습니다.
- 연구 결과, 적응형 크기 조절은 캐시 크기가 커질수록 정적 정책이 놓치는 장기적인 워크로드 변화를 포착함으로써 더욱 유익해지는 것으로 나타났습니다.
배치 추론 (Batch Inference): QuALITY 데이터셋에서 배치 크기를 변화시키며 실험한 결과, LRU 대비 ARC의 상대적 우위가 지속되었으며 배치 크기가 커질수록 약간 증가하여 5~7%의 TTFT 감소를 유지했습니다.

의의 및 주장
본 논문은 적응형 KV 캐시 관리가 LLM 서빙 성능을 향상시키기 위한 실용적이고 효과적인 메커니즘이라고 주장합니다. 단순한 최신성을 넘어 재사용 패턴을 포착함으로써, 제안된 방법은 다양한 워크로드에서 캐시 히트율을 높이고 지연 시간을 줄입니다. 저자들은 자신들의 접근 방식이 배치 추론에도 잘 일반화되며, 학습 기반 예측기의 오버헤드 없이 복잡하고 변화하는 액세스 패턴을 처리할 수 있는 미래 시스템의 토대를 제공한다고 강조합니다. 이 연구는 캐시 자원의 동적 파티셔닝이 실제 운영 환경에서 더 효율적인 LLM 배포를 위한 중요한 단계임을 시사합니다.

문제점: "최근 들어온 것이 먼저 나간다"는 실수

해결책: "적응형 책상"

연구 결과

핵심 요점

기술 요약: 대규모 언어 모델 서빙을 위한 최신성/빈도 적응형 KV 캐싱

유사한 논문