LLM 추론 비용과 TTFT를 80% 절감하는 프롬프트 캐싱(Prompt Caching)과 접두사 해시 트리 아키텍처

대규모 언어 모델(LLM) 기반의 프로덕션 애플리케이션(RAG 시스템, 코딩 어시스턴트, 멀티턴 AI 에이전트)을 운영할 때 전체 토큰 소비량의 80% 이상은 사용자의 단일 질문이 아닌 반복되는 시스템 프롬프트, 도구 스키마, 문서 컨텍스트 등 공통 접두사(Prefix)에서 발생합니다.

기존 추론 엔진은 매 요청마다 동일한 접두사 토큰들에 대해 트랜스포머의 사전 채우기(Prefill/Prompt Phase) 단계 연산을 처음부터 다시 수행했습니다. 이로 인해 최초 토큰 생성 지연 시간(TTFT, Time-To-First-Token)이 급격히 증가하고 고가의 GPU 연산 자원이 비효율적으로 소모되었습니다. 본 글에서는 이미 연산된 KV 텐서를 재사용하여 TTFT를 최대 80% 단축하고 API 호출 비용을 절감하는 프롬프트 캐싱(Prompt Caching)의 동작 메커니즘과 vLLM의 라딕스 트리(Radix Tree) 접두사 캐싱 아키텍처를 심층 분석합니다.

1. 프롬프트 캐싱의 핵심 원리: 어텐션 연산 재사용

트랜스포머 모델의 인과적 마스킹(Causal Masking) 특성상, 이전 토큰들의 Key와 Value 텐서는 이후 생성되는 토큰들에 영향을 주지만 앞선 토큰들의 KV 값 자체는 뒤따르는 토큰에 의해 변경되지 않습니다. 즉, 토큰 시퀀스의 접두사가 동일하다면 이전 요청에서 계산한 KV 캐시를 그대로 재사용할 수 있습니다.

• Prefill 단계 제거: 캐시된 접두사 토큰 구간에 대해서는 QK 내적 및 Softmax 연산을 수행하지 않고 메모리에서 KV 텐서만 복원하여 즉시 디코딩 단계로 진입합니다.
• TTFT(Time To First Token) 단축: 수천 토큰에 달하는 긴 프롬프트도 첫 토큰 생성까지의 지연 시간이 수 초에서 수백 밀리초 단위로 단축됩니다.
• 비용 절감: Anthropic, OpenAI 등의 상용 LLM 공급자는 캐시 히트(Cache Hit)된 입력 토큰에 대해 50~80%의 비용 할인 정책을 제공합니다.

2. Radix Tree 기반 접두사 캐시(RadixAttention) 데이터 구조

vLLM과 같은 최신 오픈소스 서빙 엔진은 효율적인 접두사 탐색과 캐시 메모리 관리를 위해 라딕스 트리(Radix Trie) 구조를 활용합니다. 공통 토큰 시퀀스는 트리의 간선(Edge)으로 압축 표현되며, 노드는 할당된 물리 메모리 블록 ID를 가집니다.

# Radix Tree 기반 접두사 KV 캐시 탐색 개념 구현체
from dataclasses import dataclass, field
from typing import List, Dict, Optional, Tuple

@dataclass
class RadixNode:
    token_subsequence: List[int] = field(default_factory=list)
    children: Dict[int, 'RadixNode'] = field(default_factory=dict)
    physical_block_ids: List[int] = field(default_factory=list)
    last_access_time: float = 0.0

class RadixPrefixCache:
    def __init__(self):
        self.root = RadixNode()

    def match_prefix(self, prompt_tokens: List[int]) -> Tuple[List[int], int]:
        """
        입력 프롬프트와 가장 길게 일치하는 캐시된 접두사의 물리 블록 ID 목록 및 매칭 길이 반환
        """
        curr_node = self.root
        matched_blocks = []
        token_offset = 0

        while token_offset < len(prompt_tokens):
            first_token = prompt_tokens[token_offset]
            if first_token not in curr_node.children:
                break

            child = curr_node.children[first_token]
            subseq_len = len(child.token_subsequence)
            
            # 토큰 부분 문자열 완전 일치 검증
            if prompt_tokens[token_offset : token_offset + subseq_len] == child.token_subsequence:
                matched_blocks.extend(child.physical_block_ids)
                token_offset += subseq_len
                curr_node = child
            else:
                break

        return matched_blocks, token_offset

위 아키텍처를 통해 새로운 프롬프트가 유입되면 라딕스 트리를 순회하여 가장 긴 공통 접두사(Longest Common Prefix)를 O(K)(K=일치 토큰 수) 시간 복잡도로 즉시 탐색하고, 매칭되지 않은 나머지 꼬리(Suffix) 토큰에 대해서만 Prefill 연산을 실행합니다.

3. 프로덕션 프롬프트 엔지니어링: 캐시 히트율 극대화 규칙

프롬프트 캐싱의 혜택을 온전히 누리기 위해서는 프롬프트 구조화 단계에서 접두사 불변성(Prefix Immutability)을 보장해야 합니다.

# 캐시 히트율을 극대화하는 프롬프트 구조 설계 예시
def construct_cachable_prompt(system_instructions: str, reference_docs: str, user_query: str) -> str:
    """
    규칙: 불변하는 정적 콘텐츠를 반드시 최상단에 배치하고, 가변 데이터는 최하단에 배치한다.
    """
    prompt_sections = [
        # 1. 고정 시스템 프롬프트 (Cache Hit 영역)
        f"[SYSTEM_INSTRUCTION]
{system_instructions}
",
        # 2. 참조 지식 베이스 / 규정 문서 (Cache Hit 영역)
        f"[REFERENCE_CONTEXT]
{reference_docs}
",
        # 3. 사용자 동적 입력 및 타임스탬프 (Cache Miss 영역 - 반드시 맨 뒤)
        f"[USER_QUERY]
{user_query}"
    ]
    return "
".join(prompt_sections)

4. 결론 및 도입 성과

프롬프트 캐싱은 대규모 문맥을 다루는 현대 생성형 AI 아키텍처에서 인프라 비용 절감과 사용자 체감 반응 속도 개선을 동시에 달성할 수 있는 가장 필수적인 최적화 기법입니다. 정적 컨텍스트의 전방 배치와 라딕스 트리 접두사 재사용 설계를 통해 대규모 에이전트 파이프라인의 경제성과 가용성을 대폭 향상시킬 수 있습니다.

출처 및 1차 공식 기술 문서

• Anthropic Official Documentation — Prompt Caching Architecture and Guidelines
• vLLM Official Documentation — Automatic Prefix Caching (RadixAttention)
• OpenAI Platform Documentation — Prompt Caching Mechanics