이 글은 NeurIPS 2024에 올라온 논문 SGLang: Efficient Execution of
Structured Language Model Programs를 정리한 글이다.
1. Introduction
1.1 해결하려는 문제: “왜 LLM Program을 위한 시스템이 필요한가”
LLM의 활용 양상이 단순한 채팅에서 multi-call, control flow가 결합된 프로그램적 사용으로 빠르게 전환되고 있다. ReAct agent, Tree-of-Thought (ToT), Branch-Solve-Merge 등 대부분의 프롬프팅 기법은 다음 두 가지 공통 속성을 가진다.
•
다수의 LLM 호출이 control flow와 엮여 있음: 한 task를 풀기 위해 여러 generation call을 chaining
•
구조화된 입출력: JSON Schema 등 외부 시스템과 통합되기 위한 structured I/O 필요
이런 프로그램들을 논문에서는 “LM Program”으로 정의한다. 그러나 이를 작성 및 실행하는 기존 시스템(예: 이 논문이 쓰일 당시의 vLLM)은 두 가지 측면에서 비효율적이다.
(1) 프로그래밍 측면: 문자열 조작, 프롬프트 튜닝, 출력 파싱, 멀티모달 입력 처리, 병렬화 메커니즘 구현 등을 모두 수동으로 처리해야 함 → 단순한 프로그램조차 가독성이 매우 낮아짐
(2) 실행 측면: vLLM 같은 SOTA 추론 엔진들은 워크로드의 종류나 특성을 인지하지 않도록(Workload-agnostic) 설계되어 있어 LM Program이 가진 구조적 특성을 활용하지 못한다. 대표적인 비효율 두 가지:
•
KV cache 재사용 부재: 같은 system prompt나 few-shot example을 공유하는 다수의 호출이 있어도, 기존 엔진은 request 처리가 끝나면 KV cache를 폐기 → prefix가 동일한 다른 호출에서 동일한 prefill 연산 반복
•
Constrained decoding의 token-by-token 한계: JSON schema 같은 정규식 제약이 있을 때, 다음 token이 사실상 결정되어 있는 구간에서도 매 step마다 forward pass를 수행
1.2 제안하려는 방법론
Fig 1. System architecture: An interpreter executes language primitives with optimized runtime
SGLang은 Frontend language + Co-designed runtime의 통합 시스템으로 세 가지 핵심 기여를 제시한다.
•
RadixAttention: KV cache를 Radix Tree 기반 LRU cache로 관리, 모든 prefix 공유 패턴을 자동으로 탐지 및 재사용
•
Compressed Finite State Machine: Regex로부터 구성한 FSM에서 하나의 forward pass로 다중 token decoding
•
API Speculative Execution: Multi-call 프로그램에서 stop condition을 무시하고 미리 생성, template과 매칭되면 뒤에 이어질 API call 생략
이 글에서는 RadixAttention과 Compressed FSM 두 가지 기술에 대해서 집중적으로 서술하고자 한다.
2. Method
2.1 RadixAttention
2.1.1 왜 Radix Tree인가
Fig 2. KV cache sharing examples: Few-shot learning, Self-consistency, Multi-turn chat, Tree-of-Thought
KV cache는 self-attention의 key-value tensor를 prefill 단계에서 계산한 결과물로, prefix가 동일한 모든 sequence에서 재사용 가능하다는 특성을 가진다. 그러나 LM Program에서 발생하는 prefix 공유 패턴은 단순하지 않다.
Fig 3. Trie Tree vs Radix Tree
Radix Tree는 Trie(트라이)의 공간 효율적인 변형으로, 하나의 edge에 단일 문자가 아닌 가변 길이 토큰 시퀀스를 라벨링할 수 있다. SGLang은 이 자료구조를 채택하여 다음과 같이 KV cache를 관리한다.
2.1.2 동작 예시
Fig 4를 통해 RadixAttention의 동작 원리를 설명할 수 있다.
Fig 4. Examples of RadixAttention operations with an LRU eviction policy (1~5)
•
(2) → (3): 동일 prefix 발견 시 KV cache 재사용 + 새 turn은 child node로 append함
•
(3) → (4): 새로운 chat session이 일부 prefix만 공유 → 노드 split함
•
(4) → (5): 메모리 한계 도달 ⇒ LRU에 따라 가장 오래 안 쓰인 leaf 제거(evict)
Fig 4. Examples of RadixAttention operations with an LRU eviction policy (6~7)
•
(7): 같은 few-shot example을 공유하는 batch query ⇒ 하나의 공유 노드로 묶임
Fig 4. Examples of RadixAttention operations with an LRU eviction policy (8~9)
•
(9): self-consistency sampling - 같은 question에서 여러 answer를 sampling함
2.1.3 Cache-Aware Scheduling
Cache hit rate는 Request 처리 순서에 직접적으로 의존한다. FCFS(First-Come First-Served) 방식은 서로 다른 prefix request 사이를 빈번히 전환하여 cache thrashing을 유발한다.
SGLang은 Longest-Shared-Prefix-First 스케줄링을 도입한다.
Theorem 3.1: 캐시 크기가 최대 request 길이 이상일 때, radix tree는 DFS 순서로 방문하면 최적의 cache hit rate를 달성하며, longest-shared-prefix-first는 DFS와 동치이다.
2.1.4 Frontend-Runtime Co-design
SGLang의 또 다른 차별점은 frontend interpreter가 runtime에 hint를 미리 전달한다는 점이다. fork() primitive(프리미티브) 실행 시 frontend는 prefix를 먼저 보내 트리에 정확히 삽입되도록 유도하고, 이후 분기된 prompt를 전송한다. 이는 단순한 자료구조 최적화를 넘어 언어 설계와 시스템 설계가 통합된 결과로, Ablation study에서 “No Frontend Hint” 조건이 유의미한 성능 저하를 보임으로써 이 기술의 필요성이 검증되었다.
2.2 Compressed Finite State Machine
2.2.1 문제 정의
JSON Schema 등 정규식 제약 하에서 출력하는 경우, 기존 시스템은 regex → FSM 변환 후 매 token마다 다음 상태에서 허용되는 token을 logit mask로 강제한다. 그러나 다음과 같은 비효율이 존재한다.
Fig 5. The decoding process of normal and compressed FSMs
{"summary": " 같은 이미 정해진 시퀀스의 경우 다음 token이 사실상 한 가지로 결정되어 있음에도, 기존 시스템은 한 token씩 forward pass를 수행한다.
2.2.2 Compressed FSM 동작 원리
Fig 6. Comparison of decoding using Compressed FSM versus normal FSM
Normal Decode With FSM. 파란색 상자(Decode)들을 보면 모델이 {”name: “라는 정해진 포맷을 출력하는 과정이다. 기존 FSM은 { 뽑고 Forward Pass, \n 뽑고 Forward Pass, _ 뽑고 Forward Pass … 무려 9번의 파란색 블록(Forward Pass 연산)을 거친다. 정답이 이미 정해져 있는 JSON Schema 구간인데도 매번 다음 글자가 무엇일지 GPU 연산을 하고 있는 연산 낭비 현상이다.
Jump-Forward Decode With Compressed FSM. 주황색 상자(Jump-Forward)가 바로 SGLang이 도입한 기술의 결과이다. SGLang 엔진은 컴파일 단계에서 FSM 지도를 미루 쭉 훑어보고 “name”: “까지 정해진 구간임을 판단한다. 이런 정해진 구간인 상태 노드들을 하나의 거대한 문자열로 압축(Compress)해 버린다. 그 결과, LLM에게 확률 계산을 시키지 않고 엔진이 직접 {\n "name": “ 뭉텅이를 한 방에 출력해 버린다 (Jump-Forward).
3. Evaluation
3.1 실험 설정
항목 | 내용 |
모델 | Llama-2-7B/70B, Mixtral-8x7B, LLaVA-v1.5-7B (image), LLaVA-NeXT-34B (video), GPT-3.5 |
하드웨어 | AWS EC2 G5 (NVIDIA A10G 24GB), 일부 A100 (80GB) |
베이스라인 | Guidance v0.1.8 (llama.cpp), vLLM v0.2.5, LMQL v0.7.3 (HF Transformers) |
워크로드 | MMLU 5-shot, HellaSwag 20-shot, ReAct, Generative Agents, Tree-of-Thought (GSM-8K), Skeleton-of-Thought, LLM Judge (BSM), JSON Decoding, Multi-turn Chat (short/long), DSPy RAG |
3.2 End-to-End Performance
Fig 7. Normalized throughput on Llama-7B models
SGLang이 모든 워크로드에서 baseline 대비 최대 6.4x throughput을 달성했다. 특히 Tree-of-Thought, Skeleton-of-Thought, LLM Judge 같이 prefix sharing 기회가 많은 워크로드에서 격차가 크다.
3.3 Ablation Study
조건 | 의미 | 시사점 |
No Cache | 캐시 사용 안 함 | 최악 — RadixAttention의 가치 입증 |
No Tree-Structure | 단순 hash table 기반 캐시 | Tree 구조가 multi-level sharing에 필수 |
FCFS Schedule | 도착 순서대로 처리 | Cache-aware scheduling의 효과 검증 |
Random Schedule | 무작위 순서 | 스케줄링이 throughput에 직결됨 |
No Frontend Parallelism | Interpreter 병렬화 비활성 | 언어-runtime 통합이 성능에 영향 |
No Frontend Hint | fork hint 미전송 | Co-design의 가치 입증 |
Full Optimization | 모두 활성화 | 모든 구성요소가 함께 작동할 때 최적 |
RadixAttention의 오버헤드는 거의 무시할 수 있는 수준이다. ShareGPT 데이터셋에서 100 request 처리에 74.3초 중 tree 관리에 0.2초(<0.3%)만 사용된다. 이는 RadixAttention을 default로 활성화해도 무방함을 의미한다.
Compressed FSM은 JSON decoding 단독에서 1.6x throughput 향상에 기여하며, FSM preprocessing을 batch에 걸쳐 재사용하지 않으면 오히려 2.4x 느려진다는 점도 확인된다.
“50대의 추교현이 20대의 추교현에게 감사할 수 있도록 하루하루 최선을 다해 살고 있습니다.”
The End.