LLM Inference & Serving

Strata: Hierarchical Context Caching for Long-Context LLM Serving

Xie, Z., Xu, Z., Zhao, M., An, Y., Mailthody, V. S., Mahlke, S., Garland, M., Kozyrakis, C.

arXiv 2025 (2508.18572)

An engineering dissection of Strata — a hierarchical context caching framework for long-context LLM serving. Covers why loading offloaded KV cache from CPU/SSD becomes the bottleneck, GPU-assisted I/O to defeat KV cache fragmentation, decoupled layer-first vs page-first layouts, the HiRadixTree, and cache-aware scheduling (delay-hit deferral, balanced batches, bubble filling) that lift TTFT up to 5x over vLLM+LMCache and 3.75x over TensorRT-LLM.

• Identifies the real long-context bottleneck: once the KV cache is offloaded to CPU DRAM or SSD, loading it back is I/O-bound — up to 74% of prefill time is spent stalled on transfers, not compute
• GPU-assisted I/O replaces cudaMemcpyAsync with a CUDA kernel that spawns thousands of threads, saturating PCIe with tiny fragmented KV pages while confining itself to as few as 2 CUDA blocks (<5% prefill interference)
• Decouples memory layout across tiers — layer-first on the GPU for compute, page-first on host/disk for large contiguous transfers — with a near-free on-the-fly transform, cutting disk load latency up to 4x
• A cache-aware scheduler over an extended HiRadixTree defers delay hits, forms compute-balanced batches to hide loading, and fills leftover bubbles with decode work — up to 5x lower TTFT vs vLLM+LMCache and 3.75x vs TensorRT-LLM, with no short-context regression

MOONCAKE: A KVCache-centric Architecture for Serving LLM Chatbot

Qin, R., Li, Z., He, W., Cui, J., Ren, F., Zhang, M., Wu, Y., Zheng, W., Xu, X.

USENIX FAST '25

An engineering dissection of MOONCAKE — the KVCache-centric disaggregated serving platform behind Moonshot AI's Kimi chatbot. Covers why prefill and decoding are split into separate clusters with different SLOs (TTFT vs TBT), the disaggregated MOONCAKE Store that pools CPU/DRAM/SSD/RDMA into a global KVCache, the cache-aware scheduler (Conductor), chunked pipeline parallelism for long context, and how trading more storage for less computation lifts effective request capacity by 59-498% while staying within SLOs.

• Splits serving into a prefill cluster optimized for Time To First Token (TTFT) and a decoding cluster optimized for Time Between Tokens (TBT), each with its own objective and constraints
• Pools underused CPU, DRAM, SSD and RDMA across the GPU cluster into MOONCAKE Store — a distributed global KVCache that reuses cached prefixes instead of recomputing them
• A cache-aware global scheduler (Conductor) routes on prefix-cache hit length and queue time, not just load, and rejects requests predicted to miss their SLO with HTTP 429
• Increases effective request capacity by 59-498% over vLLM baselines while complying with SLOs; serves >100 billion tokens a day for Kimi

FlashInfer: Engineering a Customizable, Block-Sparse Attention Engine for LLM Inference Serving

Ye, Z., Chen, L., Lai, R., Lin, W., Zhang, Y., et al. (University of Washington / NVIDIA / CMU / OctoAI)

arXiv 2501.01005 · Engineering Implementation

Engineering dissection of FlashInfer's attention engine for LLM inference serving: block-sparse KV cache, composable formats, attention composition, JIT CUDA templates, and load-balanced GPU scheduling.

• Reframes serving-time attention as an engineering problem distinct from training: the math is identical, but shapes, KV-cache layouts, and variants are unpredictable — so a kernel is not enough and an engine is needed
• Traces the block-sparse (BSR) representation end to end: a page table is literally a block-sparse matrix, sparsity lives only in how the KV address j is computed, and every path converges to one dense FlashAttention kernel after the shared-memory load
• Explains attention composition (the ⊕ operator over [O, LSE] states) as the permission slip for arbitrary KV chunking — associative, commutative, and why the schedule still pins one deterministic reduction order
• Walks the CUDA implementation concretely: a BSR-indexed attention kernel, gather-into-shared-memory with LDGSTS/TMA, tile-size heuristics, the JIT functor template (FlashSigmoid), and the CPU-plans/GPU-computes load-balancing scheduler that stays CUDAGraph-compatible

SGLang: Efficient Execution of Structured Language Model Programs

Zheng, L., Yin, L., Xie, Z., Sun, C., Huang, J., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, I., Gonzalez, J. E., Barrett, C., Sheng, Y.

NeurIPS 2024

An engineering dissection of SGLang — a frontend language plus co-designed runtime for executing structured LLM programs. Covers the programming model (gen/select/fork/join), RadixAttention for automatic KV cache reuse via a tree-structured LRU cache, longest-shared-prefix-first cache-aware scheduling, the compressed finite state machine for fast constrained decoding, API speculative execution, and how these lift throughput up to 6.4x and cut latency up to 3.7x over vLLM, Guidance, and LMQL.

• Splits LLM serving into a frontend language (a Python-embedded DSL with gen, select, fork, join) and a co-designed backend runtime (SRT), which can be used together or independently
• RadixAttention keeps the KV cache of finished requests in a tree-structured LRU cache, so any later request sharing a prefix reuses that computation instead of recomputing it — the first system to do automatic multi-level prefix sharing
• A cache-aware, longest-shared-prefix-first scheduler provably reaches the optimal cache hit rate (DFS order) and in practice hits ~96% of it; a compressed finite state machine decodes multiple constrained tokens in a single forward pass
• Up to 6.4x higher throughput and up to 3.7x lower latency than vLLM, Guidance, and LMQL across agent, reasoning, JSON, RAG, and multi-turn chat workloads, with under 0.3% RadixAttention overhead

TensorRT-LLM: Inside NVIDIA's LLM Inference Serving Engine — KV Cache, Paged Attention & In-Flight Batching

Engineering Implementation

An engineering dissection of TensorRT-LLM — how NVIDIA's LLM inference serving engine turns paged KV cache, in-flight batching, and a two-level scheduler into throughput under a fixed memory budget.

• Reframes LLM serving as a memory-allocation problem: paging, block reuse, eviction, and scheduling are all decisions about a fixed KV-cache budget before they are decisions about compute
• Separates prefill (compute-bound) from decode (memory-bandwidth-bound) and derives why batching raises arithmetic intensity while KV-cache capacity caps how far you can batch
• Walks the two-level scheduler — CapacitySchedulerPolicy (kMAX_UTILIZATION / kGUARANTEED_NO_EVICT / kSTATIC_BATCH) then the micro-batch scheduler with context-before-generation packing
• Maps every concept to real TensorRT-LLM source: capacityScheduler.h, microBatchScheduler.h, kvCacheManager.h, the executor enums in types.h, and the PyTorch _torch/pyexecutor backend

vLLM & PagedAttention: Efficient Memory Management for LLM Serving

Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C.H., Gonzalez, J.E., Zhang, H., Stoica, I.

SOSP '23 · arXiv 2309.06180

An engineering dissection of vLLM and PagedAttention — the serving system that treats the KV cache like OS virtual memory. Covers why the KV cache (not compute) is the throughput bottleneck, how contiguous allocation wastes 60-80% of it to fragmentation, how PagedAttention stores the cache in non-contiguous blocks addressed through a block table, how that enables copy-on-write sharing for parallel sampling and beam search, and how near-zero memory waste turns into 2-4x higher throughput than FasterTransformer and Orca.

• Identifies that LLM serving is memory-bound: on a 13B model the KV cache is ~30% of A100 memory, grows and shrinks per request, and its inefficient management — not compute — caps the batch size
• PagedAttention stores each sequence's KV cache in fixed-size blocks that need not be contiguous in GPU memory, addressed through a per-request block table — the OS paging idea applied to attention
• Blocks are reference-counted, so a shared prompt is stored once and copied only on divergence (copy-on-write), giving up to 55% memory saving on beam search
• Near-zero KV cache waste (96.3% useful vs 20.4-38.2% in prior systems) lets vLLM batch 2-4x more requests, yielding 2-4x higher throughput at the same latency

LLM.int8(): 8-bit Inference for Large Transformers Without Losing Accuracy

Dettmers, T., Lewis, M., Belkada, Y., Zettlemoyer, L.

NeurIPS 2022 · arXiv 2208.07339

An engineering dissection of LLM.int8() — the 8-bit matrix multiplication scheme that halves inference memory for transformers up to 175B parameters with zero performance degradation. Covers why single-scale quantization breaks at scale, absmax vs zeropoint quantization, vector-wise quantization, the emergent outlier-feature phenomenon that appears at 6.7B, and the mixed-precision decomposition that isolates ~0.1% of dimensions into 16-bit while the rest run in Int8.

• Loads a 16/32-bit 175B checkpoint, converts the feed-forward and attention-projection layers to Int8, and serves it immediately with no accuracy loss — putting OPT-175B/BLOOM on a single consumer-GPU server
• Vector-wise quantization uses a separate scaling constant per row of the input and per column of the weight, so one outlier can only spoil its own inner product — not the whole tensor
• At ~6.7B parameters a phase shift makes large-magnitude outlier features appear in all layers; they occupy only ~6 hidden dimensions yet removing them raises perplexity by 600-1000%
• Mixed-precision decomposition routes the ~0.1% outlier dimensions through a 16-bit matmul and the other 99.9% through Int8, retaining ~50% memory savings

TurboQuant: Near-Optimal Low-Bit Vector Quantization — Random Rotation, QJL, KV Cache Compression & SimpleMem Integration

Zandieh, A., Daliri, M., Hadian, M., Mirrokni, V. (Google Research / DeepMind / NYU)

arXiv 2504.19874

Engineering dissection of TurboQuant near-optimal vector quantization: random rotation, Lloyd-Max scalar quantization, QJL residual coding, unbiased inner-product estimation, KV cache compression, and a proposed SimpleMem integration.

• Separates two distinct goals — minimizing MSE reconstruction error vs. preserving inner products — and shows why an MSE-optimal quantizer is biased for inner products (the 2/π bias at 1 bit)
• Traces every matrix multiplication end to end: random rotation y = Πx, Lloyd-Max scalar quantization on Beta-distributed coordinates, QJL sign(Sr) on the residual, and reconstruction x̂ = Πᵀŷ + (√(π/2)/d)·‖r‖·Sᵀ·qjl
• Explains TurboQuant_prod's two-stage design (MSE at b−1 bits + 1-bit QJL on the residual) and why the combined inner-product estimator is provably unbiased and within a ≈2.7× constant of the information-theoretic lower bound
• Includes a runnable educational NumPy implementation with tests, memory-footprint math, and a clearly-labelled proposed integration of TurboQuant into SimpleMem's dense semantic-memory retrieval layer