Continuous Batching Analysis

Continuous Batching 심층 분석

Dynamic Scheduler · Decode Slot Refill · Chunked Prefill · PagedAttention · Fairness vs Throughput

Continuous batching은 디코딩 배치를 '한 번 고정하고 끝날 때까지 유지'하는 대신, 토큰이 끝나는 순간마다 빈 슬롯을 새 요청으로 즉시 채우는 동적 스케줄링 기법입니다. 디코딩이 메모리 바운드인 LLM 서빙에서는 이 단순한 정책 차이가 GPU 활용도와 처리량을 크게 바꾸며, 오늘날 vLLM류 엔진의 기본 운영 모드가 되었습니다.

ORCA는 iteration-level scheduling과 selective batching으로 같은 문제를 먼저 풀었고, vLLM은 chunked prefill로 decode 우선 정책을 조정하며, TensorRT-LLM은 in-flight batching과 chunked context로 이를 제품화합니다. 이 문서는 정적 배치의 낭비 → 연속 배치 루프 → prefill/decode 간섭 → 비교/분석 → 장단점 → 관련 기술의 순서로 분석합니다.

실제 운영에서는 스케줄러만 잘 짠다고 끝나지 않습니다. 빈 슬롯을 다시 채우는 속도와 함께 KV cache를 얼마나 잘 회전시키는지, 긴 prefill을 얼마나 잘게 쪼개 decode와 공존시키는지, 그리고 SLA가 다른 요청 사이에서 fairness를 어떻게 유지하는지가 전체 체감 성능을 좌우합니다.

1. 왜 정적 배치로는 디코딩 GPU를 충분히 채우지 못하는가

디코딩은 시퀀스마다 매 스텝 한 토큰씩만 전진하므로, 어떤 요청은 빨리 끝나고 어떤 요청은 오래 남습니다. 정적 배치는 한 번 배치를 묶은 뒤 끝날 때까지 유지하므로, 짧은 요청이 먼저 끝난 자리는 배치 종료 전까지 비어 있게 됩니다.

이 빈 슬롯은 곧 GPU 메모리 대역폭의 낭비입니다. 특히 온라인 서빙처럼 요청 길이가 크게 다를 때는 배치 내부의 tail request 하나가 전체 배치를 오래 붙잡아 GPU utilization을 떨어뜨립니다.

그림 1. 정적 배치와 연속 배치의 슬롯 재활용 차이

Decode는 메모리 바운드

디코딩 단계는 이미 계산된 KV 캐시를 읽어 다음 토큰 하나를 생성하므로, FLOP보다 메모리 이동이 병목이 됩니다. 따라서 같은 시간에 더 많은 시퀀스를 active set에 담아두는 것이 처리량과 거의 직결됩니다.

2. 핵심 개념

• 요청(request) / 시퀀스(sequence): 서버 입장에서는 한 클라이언트 요청이 하나의 시퀀스입니다.
• ready queue: 아직 실행되지 않았거나 다음 기회를 기다리는 요청 집합입니다.
• active set: 현재 decode step에 참여 중인 요청 집합입니다.
• slot refill: 완료된 요청이 빠진 자리로 새 요청을 즉시 채워 넣는 동작입니다.
• token budget: 한 번의 iteration에 넣을 수 있는 토큰 수 제한입니다(max_num_batched_tokens, max_num_tokens).
• KV budget: 새 요청을 받아들일 수 있는 메모리 여유입니다. 결국 admission은 compute보다 memory 문제에 가깝습니다.
• fairness: 짧은 요청을 계속 우대하면 긴 요청이 밀리고, 큰 요청을 유지하면 짧은 요청의 TTFT가 나빠집니다.

3. Continuous Batching의 핵심 루프

연속 배치는 각 decode step 이후 finished request를 제거하고, 비어 있는 slot 수만큼 ready queue에서 새 요청을 끌어와 active set을 보충합니다. 즉 배치가 '세션 단위'가 아니라 '토큰 스텝 단위'로 재구성됩니다.

이때 스케줄러는 어떤 요청을 남기고 어떤 요청을 들일지, prefill을 지금 수행할지 다음 턴으로 미룰지, active sequence budget과 KV cache budget을 어떻게 나눌지를 매번 판단해야 합니다.

1. 현재 iteration의 decode를 실행합니다.
2. 완료된 요청을 즉시 제거합니다.
3. 남은 budget을 계산해 ready queue에서 새 요청을 뽑습니다.
4. prefill은 필요하면 chunk로 나눠 decode 사이에 끼워 넣습니다.
5. 다음 iteration에서 다시 같은 과정을 반복합니다.

그림 2. ready queue -> active set -> finished slot refill로 이어지는 스케줄러 루프

Queue와 Active Set

핵심 상태는 ready queue, active decode set, 그리고 free slot/KV block pool입니다. 요청 admission은 결국 'compute slot'이 아니라 'KV cache를 감당할 수 있는가'의 문제와 결합되므로, 배치 스케줄러는 메모리 관리자와 분리될 수 없습니다.

4. Prefill과 Decode를 섞을 때의 문제

긴 프롬프트의 prefill은 연산집약적이고, decode는 메모리집약적입니다. 둘을 같은 배치 안에 섞으면 TTFT는 좋아질 수 있지만, 큰 prefill이 디코딩의 inter-token latency를 흔들 수 있습니다.

그래서 최신 엔진들은 긴 prefill을 여러 chunk로 나누어 decode step 사이에 끼워 넣는 chunked prefill을 사용합니다. 이는 throughput만 극대화하는 대신 latency도 함께 제어하려는 타협입니다.

Chunked Prefill / Chunked Context

• vLLM은 chunked prefill로 큰 prefill을 여러 chunk로 나눠 decode와 같은 batch에 넣습니다.
• TensorRT-LLM은 chunked context를 통해 context phase를 여러 iteration으로 나누고 generation phase와 함께 처리합니다.
• 두 방식 모두 긴 프롬프트가 전체 배치를 오래 점유하는 문제를 줄이고, mixed workload에서 ITL을 안정화합니다.

그림 3. giant prefill과 chunked prefill의 차이

5. 비교/분석

Continuous batching은 일반적으로 throughput(tokens/s)과 GPU utilization을 크게 올리지만, 그 대가로 스케줄링 복잡도와 fairness 문제가 생깁니다. 짧은 요청을 너무 자주 우대하면 긴 요청이 굶고, 반대로 큰 배치를 유지하려고 기다리면 TTFT가 나빠집니다.

즉 continuous batching은 단순한 batching trick이 아니라, throughput·TTFT·ITL·tail latency 사이의 multi-objective control 문제입니다. admission control, chunked prefill, prefix caching 같은 보완 기법이 함께 필요한 이유가 여기에 있습니다.

그림 4. throughput 개선과 latency/fairness trade-off

6. 장단점

7. PagedAttention과의 결합

연속 배치가 잘 동작하려면 request slot만이 아니라 KV cache도 세밀하게 재활용되어야 합니다. 그렇지 않으면 짧은 요청이 빠져도 그 자리에 남은 연속 메모리 조각을 새 요청이 바로 쓸 수 없어 외부 단편화가 생깁니다.

PagedAttention은 KV를 고정 크기 block으로 쪼개 이 문제를 해결하고, continuous batching은 그 block pool을 높은 회전율로 사용합니다. 오늘날 LLM 서빙 엔진에서 두 기법이 거의 항상 함께 언급되는 이유입니다.

그림 5. 연속 배치 스케줄러와 KV 메모리 관리자의 결합

이 결합 구조는 오프로딩이나 prefix caching 같은 상위 기능에도 그대로 이어집니다. 즉 continuous batching은 단독 기법이라기보다, KV block allocator와 admission policy 위에서 작동하는 운영 계층으로 보는 편이 정확합니다.

8. 관련 기술

그림 6. KV block 추상화가 오프로딩과 메모리 티어링으로 확장되는 방식

그림 7. 실전 서빙 스택에서 연속 배치 스케줄러가 차지하는 위치

9. 핵심 정리

Continuous batching의 본질은 '배치를 오래 유지하는 것'이 아니라 '빈 자리를 토큰 단위로 즉시 다시 쓰는 것'입니다. 디코딩이 메모리 바운드라는 사실 때문에 이 정책은 처리량에 매우 큰 영향을 줍니다.

다만 실제 시스템에서는 prefill 간섭, fairness, active KV budget, prefix sharing까지 함께 다뤄야 하므로, continuous batching은 스케줄러 한 줄짜리 최적화가 아니라 서빙 엔진의 운영 철학에 가깝습니다. ORCA의 iteration-level scheduling, vLLM의 chunked prefill, TensorRT-LLM의 in-flight batching은 같은 문제를 서로 다른 엔진에서 풀어낸 사례입니다.

그림 8. 정적 배치가 tail request 때문에 GPU를 놀리는 이유

그림 9. 매 iteration마다 ready queue와 active set을 재구성하는 스케줄러 루프

그림 10. giant prefill과 chunked prefill의 latency 차이

그림 11. 연속 배치가 개선하는 지표와 새로 생기는 운영 비용

핵심은 throughput 하나만 올리는 것이 아니라, decode 중심 워크로드에서 슬롯 회전율과 메모리 회전율을 동시에 끌어올리는 것입니다. 그래서 continuous batching을 평가할 때는 tokens/s만이 아니라 TTFT, ITL, tail latency, KV 사용률을 함께 봐야 합니다.