기술 요약: 예측 기반 KV-Cache 관리 (PBKV) 를 통한 동적 에이전트 워크플로우의 효율적 서빙

1. 문제 제기

대형 언어 모델 (LLM) 기반 멀티 에이전트 시스템은 복잡한 작업을 협력하는 에이전트들의 시퀀스 (예: Planner, Coder, Tester) 로 분해합니다. 이러한 에이전트들은 상당한 컨텍스트를 공유하여 Key/Value(KV) 캐시 재사용에 큰 기회를 제공합니다. 그러나 기존 추론 엔진 (예: vLLM, SGLang) 은 일반적으로 시간적 지역성을 가정하는 최근 사용되지 않은 (LRU) 정책에 의존합니다. 에이전트 워크플로우에서는 캐시 재사용이 시간적 근접성이 아닌 워크플로우의 구조적 특성에 의해 결정됩니다. 캐시 항목은 도구 호출이나 루프 반복과 같은 여러 에이전트 호출 동안 유휴 상태로 남아 있다가 재사용될 수 있으므로, LRU 는 이를 조기에 제거해 버립니다.

KVFlow 와 같은 대안적 접근법은 "실행까지의 단계 (steps-to-execution)"에 따른 제거를 결정하기 위해 **정적이며 사전 정의된 에이전트 단계 그래프 (전역 DAG)**를 가정합니다. 이 가정은 런타임 컨텍스트에 따라 호출되는 에이전트 순서가 달라지는 현실적인 동적 워크플로우에서는 실패합니다 (예: Tester 가 조건부로 재시도 루프를 트리거하거나 Retriever 가 새로운 하위 쿼리를 생성하는 경우).

핵심적인 과제는 다음과 같이 두 가지입니다:

1. 예측 가능성: 에이전트 워크로드는 LLM 디코딩으로 인해 본질적으로 확률적이어서 미래의 에이전트 호출을 예측하기 어렵습니다.
2. 오류 비용: 예측 오류의 비용은 불균형적으로 큽니다. 멀티 에이전트 환경에서 캐시 미스는 전체 워크플로우 컨텍스트에 걸쳐 누적된 수만 개의 토큰을 다시 프리필 (re-prefill) 해야 하게 만들 수 있습니다.

본 논문은 다음과 같은 질문을 던집니다: 예측 오류에 강건하면서도 불완전한 예측기로부터 지속적으로 혜택을 받을 수 있는 동적 멀티 에이전트 시스템을 위한 KV-Cache 관리 프레임워크를 어떻게 설계할 수 있을까요?

2. 방법론: PBKV 시스템

저자들은 기존 KV-Cache 항목의 재사용 가치를 평가하기 위해 미래 에이전트 호출을 예측하는 PBKV(예측 기반 KV-Cache 관리) 시스템을 제안합니다. PBKV 는 GPU 메모리와 호스트 메모리 (HiCache 를 통해) 로 구성된 2 계층 저장 계층에서 작동하며, 세 가지 주요 구성 요소로 이루어져 있습니다:

A. 워크플로우 예측기

정적 그래프를 가정하는 대신, PBKV 는 각 활성 워크플로우에 대한 다음 $K$개의 에이전트 호출을 예측하기 위해 상보적인 신호를 융합하는 예측기를 사용합니다.

• 아키텍처: GraphSAGE 기반의 예측기는 유도적 (inductive) 이므로 런타임에서 보지 못한 워크플로우 접두사에 대해 일반화할 수 있습니다.
• 신호 융합:
  1. 토폴로지 인식 에이전트 임베딩 ($h_{cur}$): 오프라인 추적에서 파생된 전역 호출 그래프 $G$에서 현재 에이전트의 신원과 그 이웃을 인코딩합니다.
  2. 어텐션 기반 히스토리 집계 ($h_{path}$): 스케일된 점곱 어텐션을 사용하여 워크플로우 접두사를 요약하며, 다른 경로를 통해 동일한 에이전트에 도달한 워크플로우들을 구분합니다.
  3. 시맨틱 신호 ($h_{txt}$): 마지막 프리필 토큰의 포스트-노름 은닉 상태를 재사용하여 요청별 의도를 포착하며, 접두사는 동일하지만 목표가 다른 요청들을 구분합니다.
• 출력: 예측기는 자기회귀적 오류 누적을 방지하기 위해 단일 순전파 (forward pass) 에서 향후 에이전트들에 대한 $K$개의 확률 분포를 방출합니다.

B. 선두 조회 (Lookahead) KV-Cache 제거

PBKV 는 단순한 시간적 휴리스틱을 "선두 조회 재사용 점수"에 기반한 계층적 제거 정책으로 대체합니다.

• 라이프사이클 인식 회수: 종료된 워크플로우와 관련된 캐시 노드 ("은퇴한 캐시") 는 결정론적으로 식별되어 재사용 가능성이 0 이므로 가장 먼저 제거됩니다. 이는 예측 품질과 무관하게 기본적인 개선을 제공합니다.
• 점수 기반 활성 제거: 활성 캐시의 경우 예측된 재사용 가치를 기반으로 연속적인 점수가 계산됩니다:
  $$\text{Score}(c) = \sum_{k=1}^{K} \gamma^{k-1} \sum_{w \in \mathcal{W}_{act}(c)} s_w^{(k)} \cdot A_w(c) \cdot P_w^{(k)}$$
  여기서:
  • $A_w(c)$는 접근 지표입니다 (워크플로우 $w$의 어떤 에이전트가 노드 $c$에 접근했는지).
  • $P_w^{(k)}$는 단계 $k$에서 $c$에 접근하는 에이전트를 호출할 예측 확률입니다.
  • $s_w^{(k)}$는 누적 생존 확률입니다 (워크플로우가 종료되지 않음).
  • $\gamma < 1$은 신뢰할 수 없는 장거리 예측을 할인하기 위한 신뢰도 감소 인자입니다.
• 계층적 전략: 시스템은 활성 캐시를 건드리기 전에 은퇴한 캐시 (점수 = 0) 를 제거하는 것을 우선시합니다. 이는 우아한 저하를 보장합니다. 예측기가 불완전하더라도 시스템은 라이프사이클 인식으로부터 혜택을 받고, 정확하다면 다단계 선두 조회를 활용합니다.

C. 보수적 프리페칭

전송 지연을 숨기기 위해 PBKV 는 재사용될 가능성이 높은 캐시를 호스트 메모리에서 GPU 로 능동적으로 로드합니다.

• 보수적 원칙: 프리페칭은 그렇지 않으면 유휴인 GPU 공간(자유 공간 + 은퇴한 캐시)과 유휴 PCIe 대역폭(순수 디코드 배치 중) 으로 제한됩니다.
• 위험 회피: PBKV 는 프리페치된 데이터를 위한 공간을 마련하기 위해 활성 캐시를 절대 제거하지 않습니다. 이는 예측 오류로 인해 성능이 기준선 이하로 저하되는 것을 방지하기 위해, 추측적 이득을 위해 알려진 가치가 있는 캐시를 대체하지 않도록 합니다.
• 순위 매기기: 엄격한 예산 하의 탐욕적 휴리스틱을 사용하여 1 단계 재사용 가치 (식 1) 로 후보들을 순위 매깁니다.

3. 주요 기여

1. 형식화: 본 논문은 멀티 에이전트 서빙에서의 KV-Cache 관리를 미래 접근 패턴 예측 문제로 형식화하여, 이 환경에서의 예측기 설계 지침 (다중 신호 융합, 다단계 지평) 을 제공합니다.
2. PBKV 프레임워크: 저자들은 계층적 제거(결정론적 라이프사이클 회수 + 확률적 선두 조회 점수) 와 보수적 프리페칭을 결합한 시스템을 제안합니다.
3. 이론적 보장: 본 논문은 PBKV 의 성능이 예측 오류에 대해 **리프시츠 연속적 (Lipschitz-continuously)**으로 저하됨을 증명합니다. 구체적으로, 제거 비용 후회는 예측 오류에 선형적으로 묶여 있어 불완전한 예측기가 있더라도 우아한 저하를 보장합니다.
4. 구현 및 평가: PBKV 는 HiCache 가 적용된 SGLang 에서 구현되었으며 다양한 워크로드와 LLM 에 대해 평가되었습니다.

4. 실험 결과

실험은 세 가지 벤치마크에서 수행되었습니다: HoVer(사실 확인, 동적 루프), SWE-bench(코드 생성, 재시도 루프), FinanceBench(정적 워크플로우). 사용된 모델에는 Qwen3-14B 와 Qwen3-32B 가 포함되었습니다.

• 동적 워크플로우:
  • PBKV 는 LRU 대비 종단 간 지연 시간에서 최대 1.85 배의 속도 향상과 KV-Cache 히트율에서 2.55 배의 개선을 달성했습니다.
  • "라이프사이클 인식 제거 (PBKV-LAE)"만으로도 LRU 대비 히트율을 1.66 배 향상시켜 단순한 라이프사이클 신호의 가치를 입증했습니다.
  • 전체 시스템 (PBKV-HE + 프리페칭) 은 LRU 가 약 10% 로 떨어지는 심한 메모리 압박 하에서도 높은 히트율 (~50-60%) 을 유지했습니다.
• 정적 워크플로우:
  • 정적 FinanceBench 워크로드에서 PBKV 는 SOTA 기준인 KVFlow보다 지연 시간에서 1.26 배, 히트율에서 1.39 배 더 우수한 성능을 보였습니다. 저자들은 이를 PBKV 의 라이프사이클 인식 제거 (활성 캐시의 조기 제거 방지) 와 재사용 점수의 워크플로우 간 집합에 기인합니다.
• 강건성:
  • 민감도 분석 결과, 약한 예측기 백본 (예: R-GCN, Markov 모델) 을 사용하더라도 PBKV 는 LRU 와 예측이 없는 변형 (PBKV-LAE) 보다 일관되게 우월한 성능을 보였습니다.
  • 보수적 프리페칭은 안정적인 향상을 제공한 반면, 중등도의 예측 노이즈 하에서 공격적인 프리페칭 (활성 캐시 제거) 은 역효과를 낳았습니다.

5. 중요성과 주장

본 논문은 기존 정적 가정 (KVFlow) 이나 시간적 휴리스틱 (LRU) 이 실패하는 동적 에이전트 워크플로우 서빙에서 PBKV 가 중요한 격차를 해소한다고 주장합니다.

• 최적성보다 강건성: 저자들은 PBKV 가 에이전트 시스템의 본질적 불확실성에 강건하도록 설계되었음을 강조합니다. 결정론적 안전장치 (라이프사이클 회수) 와 보수적 추측 (유휴 리소스에서만 프리페칭) 을 결합함으로써, 불완전한 예측이 성능을 해치지 않도록 보장합니다.
• 우아한 저하: 리프시츠 연속성에 대한 이론적 증명은 PBKV 의 성능이 안정적임을 확립합니다. 예측기 정확도가 향상됨에 따라 성능은 선형적으로 향상되지만, 정확도가 낮다고 해서 치명적인 실패를 초래하지는 않습니다.
• 일반화 가능성: 예측기는 플러그인 모듈로 설계되었습니다. 시스템의 설계 원칙 (계층적 제거, 보수적 프리페칭) 은 사용된 특정 예측기와 무관하므로, 이 프레임워크는 향후 워크플로우 예측의 발전으로부터 혜택을 받을 수 있습니다.

저자들은 PBKV 가 동적 및 정적 워크로드 전반에 걸쳐 LRU 와 최첨단 정적 인식 기준선보다 현저히 우월한 성능을 발휘하여, 멀티 에이전트 서빙에서 예측 기반의 보수적 캐시 관리의 유효성을 입증했다고 결론지었습니다.