CacheWeaver: Prefix-Cache 재사용을 위해 RAG 증거를 재정렬하는 기술

무엇인가 (What): 2026년 6월 18일, 연구진은 **prefix-cache-aware evidence reordering (접두사 캐시 인식 증거 재정렬)**을 기반으로 구축된 프롬프트 계층 방법론인 CacheWeaver를 발표했습니다. 이 방법은 프롬프트에 나타나는 검색된 RAG 청크(chunks)의 _순서_만 변경하여, 서빙 엔진이 더 많은 **KV prefix cache (KV 접두사 캐시)**를 재사용할 수 있도록 합니다.

왜 필요한가 (Why): 검색 증강 서빙 (retrieval-augmented serving)에서 TTFT (time-to-first-token, 첫 번째 토큰 생성 시간)는 증거를 prefill (프리필) 하는 과정에 의해 좌우됩니다. 캐시된 접두사를 재사용하면 해당 작업을 건너뛸 수 있으며, CacheWeaver는 엔진의 변경 없이 단순한 시스템이 놓치고 있는 재사용 효율을 최대한 끌어냅니다.

이전 방식과의 차이 (vs prior): naive retrieval-order caching (단순 검색 순서 캐싱) 방식은 청크를 관련성 순서대로 배치하기 때문에, 각 프롬프트의 시작 부분이 캐시와 일치하는 경우가 드뭅니다. 반면 CacheWeaver는 동일한 청크들의 순서를 재배치하여 엔진이 실제로 재사용할 수 있는 부분인 **공유된 시작 접두사 (shared opening prefix)**를 극대화합니다.

비유하자면

따뜻하게 유지되는 선반(warming shelf) 위에 이미 절반 정도 조리된 주문들을 재사용하는 주방과 같습니다.

선반 트레이:  c1 c2 c3 | c4 c5     이미 조리됨
새 주문:     c1 c2 c3 | cX cY     방금 도착함
             └──────┘   └───┘
...

• 검색된 증거 청크 (retrieved evidence chunk) = 여러 코스로 구성된 주문 중 하나의 코스
• 모델에 전송되는 프롬프트 (the prompt sent to the model) = 순서대로 나열된 전체 코스 주문
• KV prefix cache = 이미 부분적으로 조리되어 있는 주문들이 놓인 따뜻한 선반
• 재사용 가능한 접두사 (reusable prefix) = 당신의 주문이 선반 위의 주문과 공유하는 시작 코스들
• CacheWeaver 재정렬 (CacheWeaver reordering) = 시작 부분이 선반의 내용과 일치하도록 동일한 코스들을 다시 접시에 담는 것
• TTFT (time-to-first-token) = 첫 번째 접시가 주방에서 나오는 데 걸리는 시간

용어 설명

TTFT (time-to-first-token) — 요청이 도착한 후 모델이 첫 번째 출력 토큰을 생성할 때까지 걸리는 시간입니다. 긴 RAG 프롬프트의 경우, 이는 거의 전적으로 prefill 시간이며, 엔진이 답변을 하기 전에 모든 증거를 읽어야 하기 때문입니다.

Prefill (프리필) — 추론의 첫 번째 단계로, 모델이 KV cache를 구축하기 위해 프롬프트 전체를 한 번에 처리하는 과정입니다. 그 비용은 프롬프트 길이에 따라 증가하며, 이것이 RAG 프롬프트에 많은 증거를 집어넣을 때 TTFT가 느려지는 이유입니다.

KV prefix cache (RadixAttention) — 서빙 엔진(Serving engines)은 프롬프트에 대해 계산된 KV를 저장하고, **정확히 동일한 토큰으로 시작하는 이후의 모든 프롬프트에 대해 이를 재사용(reuse)**합니다. SGLang의 RadixAttention은 이러한 공유 접두사(shared prefixes)를 트리 구조로 유지하며, vLLM은 고정된 블록을 해싱(hashing)하는 방식으로 이를 수행합니다.

Prefix (그리고 순서가 중요한 이유) — 재사용은 오직 **앞부분(front)**부터 토큰 단위로 이루어집니다. 시작 부분이 동일한 두 프롬프트는 그 시작 부분을 재사용하지만, 토큰이 달라지는 즉시 그 이후의 모든 내용은 다시 계산되어야 합니다. 따라서 증거(evidence)의 _순서(order)_가 얼마나 많은 부분을 재사용할 수 있는지를 결정합니다.

RAG (retrieval-augmented generation, 검색 증강 생성) — 답변하기 전에 시스템은 관련 문서를 검색하여 이를 증거로서 프롬프트에 붙여넣습니다. 검색기(retriever)는 이를 **관련성(relevance)**에 따라 순위를 매겨 반환하며, CacheWeaver는 바로 이 순서를 재정렬합니다.

Oracle ordering (오라클 정렬) — 미래의 전체 캐시 상태를 미리 알고 있을 때 선택할 수 있는 최적의 순서로, 실행 가능한 정책이 아닌 이론적 상한선(upper bound)을 의미합니다. CacheWeaver의 저렴한 탐욕적 선택(greedy choice)은 이 이상적인 상태의 **약 97.5%**에 도달합니다.

뉴스. 2026년 6월 18일, 연구진은 CacheWeaver를 발표했습니다. 이는 근거 기반(grounded) RAG 요청이 KV prefix cache를 최대한 많이 재사용할 수 있도록 검색된 증거의 순서를 재정렬하는 가벼운 프롬프트 계층(prompt-layer) 방법론입니다. 이 방식은 서빙 엔진이나 검색된 문서를 변경하지 않으며, 오직 프롬프트 내에서 청크(chunks)가 나타나는 순서만을 변경합니다. 세 가지 vLLM 설정에서 실험한 결과, 단순한 검색 순서 기반의 prefix caching 대비 첫 번째 토큰 생성 시간(median time-to-first-token)을 약 20~33% 단축했으며, 답변 품질의 저하 없이 **오라클 정렬(oracle ordering)이 제공할 수 있는 이득의 97.5%**에 도달했습니다. 논문 읽기 →

이미 절반쯤 조리된 주문들이 놓여 있는 **온장 선반 (warming shelf)**이 있는 주방을 상상해 보세요. 새로운 주문이 들어왔는데, 그 주문의 첫 몇 가지 코스 요리가 선반에 이미 놓여 있는 쟁반과 동일한 요리이며 동일한 순서로 구성되어 있습니다. 요리사는 처음부터 다시 시작하지 않습니다. 그들은 일치하는 쟁반을 가져와서 서로 다른 코스 요리만 조리하며, 첫 번째 접시는 훨씬 더 빨리 나갑니다. 이 모든 요령은 재사용이 엄격하게 앞에서부터 진행된다는 점입니다. 즉, 주문의 코스가 선반과 일치하지 않게 되는 순간, 그 이후의 모든 코스는 새로 조리되어야 합니다.

서빙 관점에서 보면, 각 코스는 **검색된 증거 청크 (retrieved evidence chunk)**이고, 주문은 **프롬프트 (prompt)**이며, 온장 선반은 **KV 접두사 캐시 (KV prefix cache)**입니다. 서빙 엔진은 프롬프트에 대해 이미 계산된 키(key)와 값(value)을 유지하며, 정확히 동일한 토큰으로 시작하는 이후의 모든 프롬프트에 대해 이를 재사용합니다. 하지만 이 일치 조건은 매우 엄격합니다. 앞부분의 토큰 하나만 바뀌어도 블록 해시 (block hash)가 더 이상 일치하지 않게 되어, 캐시 미스 (cache miss)가 발생하고 작업을 다시 수행해야 합니다.

여기에 검색(retrieval)이 만들어내는 문제점이 있습니다. RAG 검색기는 **관련성 (relevance)**에 따라 순위가 매겨진 청크를 반환하며, 그 순위는 거의 모든 질문에 대해 다릅니다. 따라서 _동일한 문서_를 가져오는 두 요청이라 할지라도 순서를 다르게 배치하게 되며, 결과적으로 프롬프트의 시작 부분이 거의 공유되지 않게 됩니다. 긴 RAG 프롬프트의 TTFT (Time To First Token)는 본질적으로 그 모든 증거를 프리필 (prefill)하는 데 걸리는 시간이기 때문에, 캐시 적중률이 거의 없는 상태는 GPU가 매 요청마다 수천 개의 증거 토큰을 매번 다시 읽어야 함을 의미합니다.

CacheWeaver의 접근 방식은 청크(chunk)의 순서를 자유 변수(free variable)로 취급하는 것입니다. 이 기술은 최근에 제공된 증거 시퀀스들의 **접두사 트리 (prefix tree)**를 유지하며, 각 입력 요청에 대해 가장 재사용 가능한 캐시된 접두사를 찾아낸 다음, 그에 맞춰 검색된 청크들을 재배치 (re-plates) 하는 그리디 (greedy) 알고리즘을 실행합니다. 재정렬이 전적으로 프롬프트 계층 (prompt layer)에서 발생하기 때문에, 서빙 엔진 (serving engine)과 검색 결과는 전혀 수정되지 않습니다. 또한 논문의 평가 결과에 따르면, 동일한 증거가 어떤 방식으로든 존재하고 단지 순서만 바뀌는 것이기 때문에 재정렬로 인한 답변 품질의 저하는 나타나지 않았습니다.

이 기술의 가치는 구체적인 수치를 통해 확인할 수 있습니다. 한 요청의 증거가 **5,000 토큰 (tokens)**만큼 프리필 (prefill) 된다고 가정해 봅시다. 프리필 비용은 GPU가 처리해야 하는 토큰 수에 거의 비례합니다. 이를 검색 순서 (retrieval order) 그대로 두면, 공유된 시스템 서문 (system preamble)과 운 좋게 일치하는 청크 하나만이 캐시와 일치하여 약 1,500 토큰만 재사용되고, 엔진은 나머지 3,500 토큰을 새로 프리필해야 합니다. 반면 CacheWeaver는 동일한 청크들을 재정렬하여 도입부가 캐시된 ~2,500 토큰 시퀀스와 일치하도록 만듦으로써, 새로 프리필해야 할 양을 2,500 토큰으로 줄입니다. 첫 토큰 시간 (TTFT, Time To First Token)은 재계산되는 부분에 따라 결정되므로, 3,500에서 2,500으로 줄어듭니다. 이는 약 29%의 절감을 의미하며, 이는 논문에서 보고된 20–33% 범위 안에 정확히 들어맞으며, 그리디 정책이 도달하는 것으로 나타난 오라클 (oracle) 대비 97.5% 수치에 근접합니다. (5,000 토큰 및 재사용 토큰 수치는 예시이며, 20–33% 및 97.5%는 CacheWeaver 논문에서 인용되었습니다.)

접근 방식	변경하는 것	Prefix 재사용	중앙값 TTFT
검색 순서 기반 Prefix 캐싱 (Retrieval-order prefix caching)	아무것도 아님 — 청크는 관련성 순서로 유지됨	두 순서가 우연히 일치할 때만	기준선 (baseline)
...
이것에 주목할 가치가 있는 이유는 어디에 위치하는지입니다. 새로운 어텐션 커널이나 더 작은 캐시가 아니라, 검색(retrieval)과 서비스(serving) 사이의 경계에서의 스케줄링 결정입니다. 검색-후-생성 파이프라인과 서비스 엔진을 두 개의 밀봉된 상자로 취급하는 것을 멈추면 얻게 되는 일종의 공짜 승리입니다. 증거가 같고, 엔진이 같고, 답변도 같습니다 — 단지 순서만 바뀌고 캐시가 나머지를 처리합니다.

더 깊이 알아보기: LLM 서비스(LLM Serving) → Prefix 캐싱 및 RadixAttention → Prefix 트리

관련 설명 자료 (Related explainers)

• Attention Once Is All You Need — 쿼리 전반에 걸친 영구 KV 캐시 —

이는 RAG 프롬프트 내에서 검색된 청크(chunks)의 순서를 재정렬하여, 서빙 엔진(serving engine)의 KV 접두사 캐시(KV prefix cache)가 프롬프트의 도입부를 최대한 재사용할 수 있도록 합니다. 서빙 엔진은 이전 프롬프트에 대해 계산된 키(keys)와 값(values)을 캐싱하며, 정확히 동일한 토큰으로 시작하는 이후의 모든 프롬프트에 대해 이를 재사용합니다. 하지만 검색(retrieval)은 관련성에 따라 순위가 매겨진 청크를 반환하며, 질문마다 순서가 거의 다르기 때문에 프롬프트가 도입부를 공유하는 경우는 드물고, 결과적으로 캐시 미스(cache miss)가 발생합니다. CacheWeaver는 엔진이나 검색된 문서를 건드리지 않고, 프롬프트 계층에서 동일한 청크들의 순서를 재배열하여 공유되는 도입부 접두사(opening prefix)를 극대화합니다.

왜 TTFT(Time-to-first-token)를 낮추나요?

긴 RAG 프롬프트의 TTFT(첫 번째 토큰 생성 시간)는 본질적으로 모든 증거를 프리필(prefill)하는 데 걸리는 시간입니다. 즉, 모델이 답변을 하기 전에 모든 청크를 읽어야 합니다. 프롬프트의 도입부가 캐싱된 접두사와 일치하면, 엔진은 해당 작업을 재사용하고 남은 토큰들만 프리필하므로, TTFT는 재계산해야 하는 부분에 따라 결정됩니다. CacheWeaver는 도입부의 재사용 가능성을 높임으로써 재계산이 필요한 부분을 줄이며, 이를 통해 세 가지 vLLM 설정 전반에서 중간값 TTFT를 약 20~33% 단축했습니다. 또한 답변 품질의 측정 가능한 손실 없이, 오라클 정렬(oracle ordering) 성능의 약 97.5%에 도달했습니다.

CacheWeaver는 접두사 캐싱(prefix caching) 및 RAG와 어떤 관계인가요?

CacheWeaver는 이 둘의 정확히 중간에 위치합니다. 접두사 캐싱(SGLang의 RadixAttention, vLLM의 블록 해싱)은 공유된 도입부를 재사용하는 서빙 측(serving-side) 메커니즘이며, RAG는 순위가 매겨진 증거를 프롬프트에 붙여넣는 검색 측(retrieval-side) 파이프라인입니다. CacheWeaver는 어느 쪽도 변경하지 않습니다. 대신 최근에 서빙된 시퀀스들의 접두사 트리(prefix tree)를 유지하고, 각 요청의 검색된 청크들을 가장 재사용 가능한 캐시 접두사에 맞춰 탐욕적(greedily)으로 재정렬하는 프롬프트 계층 스케줄러(prompt-layer scheduler)를 추가합니다. 이는 이미 선택된 청크들이 배치되는 순서만을 제어하기 때문에, 엔진의 캐싱 및 검색기의 랭킹(ranking)과 상호 보완적인 관계를 가집니다.

원문은 Learn AI Visually에 게시되었습니다.