KV 캐시 논문들의 주장과 달리 LRU 방식을 넘어서기는 생각보다 어렵습니다

1. 이게 뭔가요?

인공지능(AI) 서비스가 이전 대화나 코딩 내용을 메모리에 저장해 두는 '접두어 캐시' 환경에서, 가장 오래 쓰지 않은 데이터를 먼저 지우는 기본 방식(LRU)을 넘어서려는 최신 최적화 기법들의 실효성을 검증한 실험 보고서입니다. 작성자는 실제 코딩 도구인 클로드 코드(Claude Code)의 393개 세션에서 수집된 68,266건의 요청과 문케이크(Mooncake) 시스템의 23,608건 요청 기록을 바탕으로 정밀한 가상 시험 환경을 구축해 세 가지 개선 알고리즘을 시험했으나 모두 기본 방식을 이기지 못했습니다.

2. 왜 화제인가요?

최근 학계에서는 사용자가 생각을 멈춘 대기 시간 동안 캐시 유효 시간(5분)이 지나 데이터가 지워지는 현상이 막대한 연산 비용 낭비를 부른다며, 복잡한 사용자 복귀 예측 알고리즘을 도입해야 한다고 주장해 왔습니다. 그러나 실제 용량 압박이 심한 서버 환경을 측정해 보니, 데이터가 지워지는 진짜 원인은 사용자의 오랜 유휴 시간이 아니라 AI가 불과 2초 안팎의 간격으로 도구를 연속 호출하며 대규모 작업 데이터를 쏟아내 메모리 한계를 초과했기 때문이었습니다. 이 글은 서비스가 처한 물리적 제약 조건을 잘못 짚으면 학계에서 추천하는 정교한 예측 알고리즘이 전혀 힘을 쓰지 못한다는 사실을 실증적 수치로 증명하여 시스템 최적화 방향을 바로잡아 줍니다.

3. 핵심 내용

AI 언어 모델이 글을 읽고 답할 때 이전 계산 결과인 키-값(KV) 캐시를 메모리에 남겨 두고 재사용하면 매번 처음부터 다시 연산하지 않아도 되므로 응답 속도가 대폭 빨라지고 서버 운영비가 절감됩니다. 현재 vLLM, SGLang 같은 주요 고성능 서빙 엔진들은 트리 형태의 데이터 구조(라디스 트리)를 활용하며, 메모리가 찰 때 가장 오래 쓰이지 않은 말단 노드부터 지우는 LRU-leaf 방식을 기본 규칙으로 쓰고 있습니다. 학계 일각에서는 AI 에이전트 작업 도중 공백 시간이 길어지면 LRU가 잠시 멈춘 세션과 완전히 끝난 세션을 구분하지 못해 비효율적이라고 비판해 왔습니다. 이에 작성자는 사용자가 곧 돌아올 확률을 베이즈 통계로 추정하는 생존 예측(H), 뒷부분 토큰일수록 계산량이 급증하는 물리적 특성을 반영한 재계산 비용 모델링(C), 여러 세션을 조금씩 깎아내는 대신 특정 세션 하나의 꼬리 데이터를 통째로 정리하는 일관 세션 삭제(G)라는 세 가지 기법을 구현해 비교 실험을 진행했습니다.

실험 결과는 예상과 완전히 달랐습니다. 캐시 용량을 8,000블록, 20,000블록, 50,000블록으로 늘려가며 AgentX 40개 세션(4,751건 요청)을 시험한 결과, LRU-leaf 방식의 적중률(각각 83.48%, 93.92%, 95.76%)에 비해 새 알고리즘들은 요소를 더할 때마다 성능이 연속해서 하락했습니다. 세 요소를 모두 결합한 HCG 방식의 적중률은 각각 68.63%, 78.89%, 91.40%로 크게 떨어졌고, LRU 대비 실제 재계산 비용 손실률 역시 8,000블록에서 -81.0%, 20,000블록에서 -207.8%, 50,000블록에서 -66.8%로 가장 저조했습니다. 가장 적게 쓰인 것을 지우는 LFU-leaf 기법 역시 최대 -447.1%의 극심한 성능 악화를 보였습니다. 가장 확신을 가졌던 세션 단위 정리(G)마저 성능을 가장 크게 떨어뜨렸습니다.

이러한 실패는 에이전트 작업 부하의 실제 작동 특성 때문이었습니다. 수집된 393개 세션을 분석한 결과, 요청 사이 대기 시간의 중간값은 불과 2.1초였고 입력 토큰의 중간값은 88,768토큰에 달했습니다. 선행 연구(AgentSysBench)는 5분 유효 시간 만료로 인한 데이터 삭제가 전체 캐시 생성 토큰의 55.9%, 총비용의 31.5%를 차지한다고 보고했으나, 용량이 40,000블록(약 1,070만 토큰 분량)으로 한정된 이번 실험에서는 5분이 넘는 공백 뒤에 일어난 재계산 비중이 전체의 17.5%에 불과했습니다. 반면 10초 이내의 지극히 짧은 간격으로 들어온 요청이 전체 재계산 토큰의 33.1%를 차지했습니다. AI가 2.1초 간격으로 도구를 쉴 새 없이 호출하면서 메모리 용량을 순식간에 채워버렸기 때문에, 5분의 유효 시간이 끝나기도 전에 용량 부족으로 데이터가 먼저 밀려난 것입니다. 실제로 300초 유효 시간(TTL)을 적용한 시험 결과는 모든 캐시 크기에서 LRU-leaf와 1바이트의 차이도 없이 100% 동일하게 나타났습니다. 대기 간격이 2.1초로 극단적으로 짧은 상황에서는 거의 모든 세션이 '곧 돌아올 세션'으로 분류되므로, 생존 여부를 예측하는 알고리즘이 데이터를 선별해 낼 여지 자체가 없었습니다.

작성자는 두 연구 결과가 모순되는 것이 아니라 시스템이 마주한 물리적 제약 조건이 서로 다르기 때문이라고 설명합니다. 고객별 캐시 용량이 사실상 무제한으로 주어져 타이머 만료로만 데이터가 지워지는 대형 상용 API 환경(TTL 제약)에서는 선행 연구의 31.5% 수치와 생존 예측 기법이 들어맞습니다. 그러나 자체 서버의 메모리 용량이 꽉 차서 데이터를 밀어내야 하는 환경(용량 제약)에서는 용량 부족 압박이 유효 시간을 압도하므로, 유휴 시간을 예측해 최적화하려는 시도가 무의미해집니다.

연구 과정에서 가상 시험 도구의 치명적인 결함도 발견되었습니다. 미래의 모든 요청을 미리 알고 지우는 이론상 최강의 알고리즘(벨라디)이 LRU에 패배하는 기현상이 나타난 것입니다. 긴 데이터 사슬을 캐시에 넣는 과정에서 방금 집어넣은 앞쪽 접두어를 스스로 지워버리는 가상 도구의 오류 때문이었습니다. LRU는 방금 들어온 데이터가 최신 시간 도장을 받아 우연히 이 문제를 피했으나, 다른 알고리즘들은 자멸하고 있었습니다. 실제 엔진처럼 현재 처리 중인 데이터 사슬에 고정 표시(참조 카운트 핀)를 걸어 보호해야만 올바른 비교가 가능합니다.

실험의 한계점도 명확합니다. 이 연구는 약 1,070만 토큰 작업 대비 4만 블록이라는 용량 제약 환경을 가정한 시뮬레이션이며, 실제 GPU 하드웨어 실행 과정의 지연 시간이나 처리량은 다루지 않았습니다. 또한 AgentX 데이터는 세션 간 공통 프롬프트 공유가 반영되지 않는 구조였고, 393개 세션과 1시간 분량의 데이터는 전 세계 모든 사용 환경을 대변하지 못합니다. 사람이 중간에 결과를 직접 확인하고 승인하느라 대기 시간이 훨씬 긴 작업 환경에서는 생존 예측 기법이 유효할 가능성도 남아 있습니다. 실험에 사용된 코드는 파이썬 기본 기능으로만 작성되어 누구나 내려받아 재현할 수 있습니다.

4. 나에게 어떤 영향이 있나요?

AI 인프라를 설계하고 운영하는 엔지니어와 기업은 캐시 관리 정책을 고르기 전에 시스템이 '메모리 용량 부족'에 직면해 있는지, 아니면 '시간 만료(TTL)'로 데이터가 지워지는 환경인지 정확히 진단해야 합니다. 메모리 용량 부족이 주된 문제라면 사용자 대기 시간을 예측하는 복잡한 알고리즘을 얹는 대신 데이터 압축, 다계층 저장소 구성, 캐시 진입 제어, 작업량 단위를 고려한 작업 일정 관리 등에 자원을 투입하는 것이 훨씬 현명합니다. 아울러 새로운 캐시 기법을 제안하는 연구자들은 기존 LRU 방식이 실제 현장에서 대단히 강력한 기준선임을 인정하고, 핀 고정 처리 등 시험 환경에 결함이 없는지 철저히 점검해야 합니다.