당신이 고급 레스토랑을 운영하고 있다고 상상해 보세요. 처음 몇 명의 손님이 도착했을 때는 서비스가 번개처럼 빠릅니다. 하지만 홀이 가득 차고 손님들이 복잡한 코스 요리를 주문하기 시작하면, 주방의 속도가 느려지기 시작합니다.

문제는 요리사의 숙련도가 부족해서가 아니라, 조리 공간이 어수선하기 때문입니다. 손님의 주문을 추적하기 위해 요리사는 손님이 12코스 테이스팅 메뉴를 주문하든 단순히 물 한 잔을 주문하든 상관없이, 모든 테이블마다 거대하고 전용인 쟁반을 예약해 둡니다. 그 쟁반들 대부분은 비어 있지만, 주방의 모든 공간을 차지하고 있어 새로운 주문을 시작하는 것을 방해합니다.

LLM (Large Language Model) 시스템에서 이러한 "어수선함"은 **TTFT (Time to First Token, 첫 번째 토큰 생성 시간)**의 급증으로 나타납니다. 수백만 명의 사용자가 있는 제품에서 이러한 지연 시간(latency)은 치명적인 결함이 됩니다.

해결책을 이해하려면, LLM이 추론(inference) 중에 실제로 어떻게 "생각"하는지 살펴봐야 합니다.

응답의 두 단계
긴 프롬프트를 입력하고 엔터를 누르면, 시스템은 **Prefill Phase (프리필 단계)**에 진입합니다. 모델은 요청에 대한 수학적 표현을 구축하기 위해 입력 전체를 처리합니다. 이는 compute-bound (연산 중심) 작업으로, 순수한 처리 능력에 달려 있습니다.

그다음 **Decoding Phase (디코딩 단계)**가 이어집니다. LLM은 자기회귀(autoregressive) 방식, 즉 한 번에 하나의 토큰을 생성하기 때문에, 다음에 올 내용을 결정하기 위해 이미 처리한 모든 내용을 끊임없이 되돌아봐야 합니다. 이는 memory-bound (메모리 중심) 작업입니다.

KV Cache 문제
매번 새로운 단어가 나올 때마다 전체 대화를 다시 계산하는 것을 피하기 위해, 우리는 **KV Cache (KV 캐시)**를 사용합니다. 이는 이전 토큰들의 "keys"와 "values"를 GPU의 VRAM에 저장합니다.

전통적으로 시스템은 모델의 최대 컨텍스트 길이(maximum context length)를 기준으로 VRAM의 연속적인 블록을 예약합니다. 만약 제한이 2048 토큰이라면, 사용자가 단지 "Hello"라고만 입력했더라도 2048개를 위한 공간을 예약합니다.

이는 내부 단편화(Internal Fragmentation) (예약된 블록 내부의 낭비 공간)와 외부 단편화(External Fragmentation) (새로운 요청에 충분히 큰 연속적인 블록이 없음)로 이어져, GPU가 동시에 처리할 수 있는 사용자 수를 심각하게 제한합니다.

PagedAttention 등장
PagedAttention을 도서관 아카이브라고 생각해 보세요. 연구자 한 명에게 거대하고 빈 10권짜리 바인더 세트를 주고 선형적으로 채우도록 지시하는 대신, 사서가