🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

본 논문은 경량화된 Chunked Hash Tree를 활용하여 배치 크기와 접두사 동질성 간의 균형을 최적화하는 강화 학습 기반의 접두사 인식 스케줄러인 Feather를 소개하며, 기존 최첨단 스케줄러 대비 KV 캐시 접근 오버헤드를 줄여 LLM 추론 처리량을 2~10 배 향상시킵니다.

원저자: Saksham Rathi, Preeti, Mythili Vutukuru

게시일 2026-05-08

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Saksham Rathi, Preeti, Mythili Vutukuru

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

상상해 보세요. 한 명의 사서 (GPU) 가 동시에 수천 명의 다른 사람들 (요청) 로부터 질문을 받아야 하는 매우 바쁘고 고속의 도서관을 운영한다고 가정해 봅시다.

대형 언어 모델 (LLM) 세계에서는 사서가 생성하는 단어 하나하나마다 거대한 '문맥' (Key-Value 캐시) 책을 읽어야 합니다. 이 논문은 현재 질문을 조직하는 방식이 비효율적이라고 주장합니다. 왜냐하면 이 방식이 사서가 한 번에 몇 개의 질문을 처리하는지에 얼마나 집중하는지보다, 그 질문들이 얼마나 유사한지에 더 초점을 맞추기 때문입니다.

이들이 제시한 해결책인 Feather의 이야기를 간단한 개념으로 나누어 설명해 보겠습니다.

1. 문제: '북적거리는 버스' vs '가족 단체'

현재 대부분의 시스템은 여행을 효율적으로 만들기 위해 가능한 한 많은 사람을 버스 (배치) 에 태우려고 합니다. 그들은 '선착순' 규칙을 사용합니다.

문제점: 만약 500 명의 낯선 사람들을 버스에 태우면, 그들은 모두 500 개의 서로 다른 목적지를 원합니다. 운전자는 500 개의 서로 다른 정류장에 멈춰야 하며, 끊임없이 방향을 바꿔야 합니다. 이는 혼란스럽고 느립니다.
발견: 저자들은 같은 거리에 사는 (공통된 '접두어'를 가진) 100 명의 작은 그룹을 태우면 운전자가 멈추지 않고 그 거리를 곧장 달려갈 수 있음을 발견했습니다. 버스가 꽉 차지는 않았더라도, 운전자가 핸들을 계속 돌릴 필요가 없기 때문에 여행이 훨씬 빨라집니다.

핵심 통찰: 서로 다른 곳으로 가는 거대한 무리보다, 같은 곳으로 가는 작은 무리가 더 낫습니다. 이를 **접두어 동질성 (Prefix Homogeneity)**이라고 합니다.

2. 구식 방식: '나무 등반가'

기존 시스템 (SGLang 등) 은 거대하고 복잡한 가족 나무 (Radix Tree) 를 살펴봄으로써 누가 같은 조상을 공유하는지 확인하여 이러한 그룹을 찾으려 합니다.

문제점: 이 나무를 타고 올라가서 일치하는 대상을 찾는 것은 컴퓨터의 '뇌' (CPU) 에 많은 시간과 에너지를 소모합니다. 실제로 나무를 타고 올라가는 데 걸린 시간이 사서가 실제로 질문에 답하는 데 걸린 시간과 거의 비슷할 때도 있었습니다. 마치 10 분 동안 운전하기 위해 승객들을 정리하는 데 10 분을 쓰는 것과 같습니다.

3. 해결책: 'Feather'

저자들은 두 가지 문제 모두를 해결하는 새로운 스케줄러인 Feather를 구축했습니다.

Part A: '조각화된 해시 트리 (CHT)' – 똑똑한 체크리스트

거대한 가족 나무를 타고 올라가는 대신, Feather 는 교묘한 단축경을 사용합니다.

유추: 사람의 이름의 모든 글자를 확인하는 대신, 주소의 처음 몇 개의 '조각'만 확인한다고 상상해 보세요.
작동 원리: Feather 는 긴 텍스트를 작은 블록 (조각) 으로 나누고 각 블록에 고유한 '지문' (해시) 을 부여합니다. 그리고 현재 사용 중인 지문의 간단한 목록을 유지합니다.
장점: Feather 는 즉시 "아, 이 새로운 요청은 이미 버스에 타고 있는 그룹과 같은 지문을 가지고 있군"이라고 파악할 수 있습니다. 이는 매우 빨라 CPU '뇌'가 거의 땀 한 방울 흘리지 않습니다. 티켓을 확인하기 위해 책 전체를 읽는 대신 바코드 스캐너를 사용하는 것과 같습니다.

Part B: '강화 학습 (RL)' – 똑똑한 지휘자

Feather 는 유사한 그룹을 찾는 것뿐만 아니라, 언제 사람을 더 태우는 것을 멈출지 학습합니다.

딜레마: 버스에 계속 사람을 태우다 보면, 결국 다른 거리에 사는 사람을 태워야 할지도 모릅니다. 만약 그 사람을 태우면 전체 그룹이 엉망이 되어 속도가 떨어집니다.
학습: Feather 는 시행착오를 통해 배운 똑똑한 지휘자처럼 행동합니다. "내가 한 명 더 태우면 우리가 속도를 잃을지도 모른다. 지금 버스를 보내고 다음 그룹을 기다리는 게 낫겠다."
결과: 이는 버스가 가득 차는 것과 모두 같은 거리에 있는 것 사이에서 균형을 맞추며, 배치를 시작할 완벽한 순간을 동적으로 결정합니다.

4. 결과: 도서관 속도 향상

저자들이 Feather 를 테스트했을 때:

속도: 사람들이 유사한 질문을 할 때, 기존 최선 방법보다 시스템이 2 배에서 10 배까지 빨라졌습니다.
안전성: 질문들이 모두 완전히 다르면 (공통된 거리가 없으면), Feather 는 혼란스러워하지 않았습니다. 그저 기존 방법과 똑같이 잘 수행했을 뿐입니다.
효율성: 컴퓨터 메모리 내의 '교통 체증'을 줄여, 사서가 책 페이지를 가져오기 위해 오가야 하는 횟수가 줄어들었습니다.

요약

Feather는 AI 요청을 조직하는 새로운 방법입니다. 가능한 한 많은 요청을 단일 배치에 밀어 넣는 대신, 유사한 요청들을 그룹화합니다 (같은 목적지로 가는 가족처럼) 그리고 이러한 그룹을 찾기 위해 초고속이고 저에너지인 방법을 사용합니다. 이동이 매끄럽고 빨라지도록 그룹에 사람을 더 추가할 때를 정확히 언제 멈출지 학습합니다.

이 논문은 이 접근 방식이 비싼 새로운 하드웨어가 필요 없이 단순히 '교통'을 더 똑똑하게 조직함으로써 AI 응답 시간을 크게 단축한다고 주장합니다.

기술 요약: Requests of a Feather Must Flock Together

문제 정의

대규모 언어 모델 (LLM) 추론은 자동 회귀 디코딩 단계에서 근본적으로 메모리 병목 현상에 직면합니다. 생성된 각 토큰은 이전 모든 토큰의 키 - 값 (KV) 캐시에 주의를 기울여야 하므로, GPU 메모리에 있는 전체 KV 캐시를 매 단계마다 완전히 스캔해야 합니다. 기존 연구는 GPU 활용도를 높이기 위해 배치 크기를 극대화하는 데 초점을 맞춰 왔으나, 본 논문은 **접두사 동질성 (prefix homogeneity)**이라는 중요하지만 간과된 트레이드오프를 식별합니다.

실제 워크로드 (예: 퓨샷 프롬프팅, 시스템 프롬프트, RAG) 에서 요청들은 종종 상당한 공통 접두사를 공유합니다. 기존 추론 엔진 (vLLM 및 SGLang 등) 은 이러한 공유 접두사를 감지하고 KV 캐시를 재사용하기 위해 라디스 트리 또는 해시 구조를 활용하여 주로 메모리 발자국을 줄입니다. 그러나 현재 스케줄러들은 메모리 접근 패턴에 미치는 접두사 이질성의 영향을 고려하지 않은 채 배치 크기 극대화 또는 메모리 제거 최소화에 우선순위를 둡니다.

저자들은 이질적인 배치 (서로 다른 접두사를 가진 요청들을 포함하는 배치) 가 GPU DRAM 접근에서의 공간적 및 시간적 지역성을 방해하여 대역폭 활용도가 낮아지고 처리량이 감소한다고 입증합니다. 반면, 접두사 동질적인 배치 (모든 요청이 공통 접두사를 공유하는 배치) 는 효율적인 하드웨어 프리페칭과 캐시 재사용을 가능하게 합니다. 본 논문은 기존 스케줄러가 중간 크기의 동질적인 배치가 더 크지만 이질적인 배치보다 성능이 뛰어날 수 있다는 점을 인식하지 못한다고 주장합니다. furthermore, 접두사 공유를 감지하는 데 사용되는 메커니즘 (예: 라디스 트리 탐색) 은 GPU 실행 시간과 비슷하거나 종종 초과하는 prohibitive 한 CPU 오버헤드를 초래합니다.

방법론

본 논문은 배치 크기와 접두사 동질성 사이의 트레이드오프를 최적화하도록 설계된 접두사 인식 스케줄러인 Feather를 소개합니다. Feather 는 두 가지 주요 구성 요소를 통합합니다:

1. 청크 해시 트리 (CHT)

전통적인 라디스 트리 탐색의 높은 CPU 오버헤드를 해결하기 위해 Feather 는 청크 해시 트리 (Chunked Hash Tree) 라는 경량 데이터 구조를 사용합니다.

메커니즘: 토큰 단위 비교 대신, 요청은 고정 크기 토큰 청크에 대한 누적 해시의 벡터로 표현됩니다.
효율성: CHT 는 활성 배치의 "작업 집합 (working set)" 해시와 대기 중인 요청들을 "누락된 개수 (missing count, 활성 배치로 아직 커버되지 않은 청크 수)" 순으로 정렬한 최소 힙을 유지합니다.
복잡도: 이를 통해 스케줄러는 $O(\log W)$ 시간 (여기서 $W$ 는 대기 중인 요청 수) 에 배지에 추가할 최적의 후보 요청을 식별할 수 있으며, 이는 깊이 우선 라디스 트리 탐색의 $O(W \times T)$ 또는 $O(E)$ 복잡도보다 훨씬 개선된 것입니다.
연산: CHT 는 지연 힙 업데이트와 점진적 팁 (tip) 유지를 활용하여 오버헤드를 최소화하면서 효율적인 삽입, 최적 요청 찾기, 활성 배치에 요청 추가, 완료된 요청 제거를 지원합니다.

2. 강화 학습 (RL) 배치 정책

Feather 는 배치 형성의 최적 중단점을 결정하기 위해 RL 기반 정책을 사용합니다.

트레이드오프: 더 많은 요청을 추가하면 GPU 활용도 (더 큰 배치 크기) 가 증가하지만, 접두사 동질성이 희석되어 (메모리 지역성 감소) 부정적인 영향을 미칠 수 있습니다.
상태 및 행동: 스케줄러는 현재 배치 크기, 공유 접두사 깊이의 감소량 ( $\Delta$ ), 그리고 새로운 접두사 깊이를 공유하는 대기 요청 수 ( $w$ ) 를 관찰합니다. 그런 다음 추가할지 중단하여 배지를 전송할지 결정합니다.
정책: 저자들은 정적 휴리스틱, 컨텍스트 밴딧 (UCB), Q-러닝의 세 가지 정책을 평가합니다. 목표는 디코드 처리량으로 정의된 보상을 극대화하는 것입니다.
적응성: RL 정책은 "적당한" 배치를 형성하도록 학습합니다. 즉, GPU 를 활용하기에 충분히 크면서도 메모리 지역성을 극대화하기에 충분히 동질적인 배치입니다. 이는 워크로드 강도와 접두사 공유 패턴에 따라 동적으로 적응합니다.

주요 기여

중요한 트레이드오프의 식별: 본 논문은 접두사 동질성이 배치 크기 단독보다 디코드 처리량의 더 강력한 결정 요인임을 확립합니다. 배지에 단 하나의 다른 요청이 포함되더라도 지역성을 방해하고 처리량을 거의 2 배 감소시킬 수 있음을 보여줍니다.
CPU 오버헤드의 정량화: 저자들은 최신 접두사 감지 메커니즘 (SGLang 의 라디스 트리 탐색 등) 이 전체 지연 시간의 50~90% 에 달하는 CPU 오버헤드를 초래하여 접두사 재사용의 이점을 사실상 무효화할 수 있음을 밝혔습니다.
Feather 스케줄러: CHT 데이터 구조와 RL 기반 배치 정책을 통합한 Feather 의 설계 및 구현. Feather 는 vLLM 과 SGLang 모두에 통합되었습니다.
하드웨어 독립성: 특정 하드웨어 튜닝이 필요한 접두사 인식 어텐션 커널과 달리, Feather 는 스케줄링 계층에서 작동하므로 기존 어텐션 커널 및 하드웨어 구성과 호환됩니다.

결과

평가 작업은 Llama 3 8B, Qwen, LongChat 13B 와 같은 모델을 사용하여 다양한 워크로드 (L-Eval, LongBench) 에 대해 NVIDIA RTX 6000 Ada 및 A100 GPU 에서 수행되었습니다.

처리량 향상: 1K 에서 10K 토큰까지 공유 접두사를 가진 워크로드에서 Feather 는 기존 스케줄러 (vLLM 의 FCFS, SGLang 의 LPM/DFS-W) 보다 2~10 배 높은 엔드투엔드 처리량을 달성합니다.
접두사 민감도: 800 개의 요청을 8 개의 접두사 그룹으로 나누어 실험한 결과, 100 개 요청씩 8 개의 동질적인 배치로 처리할 때 더 크고 이질적인 배치로 처리하는 것보다 거의 2 배 높은 처리량을 보였습니다.
오버헤드 감소: Feather 의 CHT 는 긴 시퀀스에 대해 DFS 기반 접근 방식보다 접두사 감지 오버헤드를 최대 1000 배까지 줄입니다. 스케줄링 오버헤드는 GPU 실행 시간의 1% 미만으로 유지되는 반면, 기존 접근 방식은 GPU 실행 시간을 초과할 수 있습니다.
강건성: 워크로드에 접두사 공유가 없는 경우 Feather 는 현상 유지 (FCFS) 와 동등한 성능을 발휘하여 비공유 시나리오에서 성능 저하가 없음을 보장합니다.
커널과의 비교: Feather 는 커널 자체를 수정하지 않음에도 불구하고 (PAT 과 같은) 전문화된 접두사 인식 어텐션 커널보다 성능이 뛰어나거나 동등하여, 스케줄링 수준의 최적화가 커널 수준의 최적화와 마찬가지로 효과적임을 입증합니다.

의의

본 논문은 효율적인 LLM 서빙을 위해 배치 크기 극대화만으로는 더 이상 충분하지 않다고 주장합니다. 현대 디코딩 단계의 주요 병목 현상은 접근 지역성에 크게 영향을 받는 메모리 대역폭입니다. "배치 크기 극대화"에서 "접두사 동질성 최적화"로 초점을 전환함으로써 Feather 는 하드웨어별 커널 수정 없이도 상당한 성능 향상을 가능하게 합니다.

이 연구는 공유 접두사를 찾는 비용 (CPU 오버헤드) 이 현재 시스템의 숨겨진 병목 현상이었다는 점을 강조합니다. Feather 의 경량 CHT 와 적응형 RL 정책은 컴퓨팅 활용도와 메모리 지역성 사이의 동적 균형을 달성할 수 있음을 보여주며, 실제 LLM 추론 워크로드의 처리량과 지연 시간을 모두 크게 개선합니다. 저자들은 Feather 를 vLLM 및 SGLang 저장소에 기여하여 오픈소스로 공개할 계획입니다.