Serving Language Models from Scratch

01Prefill is compute, decode is bandwidth

A request has two phases. Prefill runs every prompt token through the model at once; decode then produces one token per forward pass. Both do the same arithmetic per token, about 2 FLOPs per parameter plus the attention terms, but prefill does it for thousands of tokens against one read of the weights, and decode does it for one token per sequence against the same read. On the roofline, prefill sits far to the right of the ridge and decode far to the left, which is why a server batches sequences: every sequence added to a decode step costs only its own arithmetic and cache traffic, far less than the weight read it shares with the rest of the batch.^[1]

The 2N counts one multiply-add per weight per token; the attention term counts the score and value products over the context. Prefill of T tokens has F = 2NT plus attention over T², and M = b_wN plus the cache it writes. Arithmetic intensity F/M crosses the device's ridge P/W at the batch size where decode stops being memory-bound, if it ever does: the cache term grows with the batch too, so at long contexts the intensity levels off below the ridge.

02Where the memory goes

Weights take 2 bytes per parameter in bfloat16, which is 140 GB for a 70-billion-parameter model and the reason such models are split across devices.^[3] The KV cache comes next, and unlike the weights it grows with every token of every active sequence: two tensors per layer, one per key-value head, head-width wide, at the cache's precision. Grouped-query attention exists for this line of arithmetic: Llama 3 shares each key-value head among four query heads, so its 8B model stores 8 heads of cache per layer rather than 32, a quarter of the bytes per token of a same-sized multi-head model.^[4][5][6]

The sequence count is an upper bound: activations, CUDA graphs, the framework's workspace and fragmentation all come out of the same pool, which is why vLLM reserves a configured fraction of memory for the cache and preempts requests when it runs out.^[7]

03Continuous batching

Requests arrive at different times with different prompt and output lengths. Batching them as a fixed group means the group runs until its longest output finishes, with slots going idle as shorter ones complete and new arrivals waiting outside. Continuous batching schedules per step instead: when a sequence emits its end token, its slot is refilled from the queue on the next step, and a new request's prefill is folded into a step alongside everyone else's decode.^[10][11] TensorRT-LLM calls the same thing in-flight batching and describes exactly that mix of context-phase and generation-phase sequences in one batch; llama.cpp's server runs it by default across its parallel slots.^[11][8]

04Paged caches and shared prefixes

Continuous batching needs a cache that can grow and shrink per sequence. Reserving the maximum sequence length for every slot up front wastes whatever a sequence does not use, and a server does not know a sequence's final length when it starts. PagedAttention splits each sequence's cache into fixed-size blocks, 16 tokens per block in vLLM's design document, reached through a per-sequence block table, so a sequence takes blocks as it grows and the only unused space is the tail of its last block.^[12] Blocks also make sharing possible: vLLM hashes each full block by its tokens together with its parent block's hash, so two requests that begin with the same system prompt map the prompt's blocks to the same physical memory, with a reference count per block, a free queue ordered by last use, and eviction from its head when the pool runs out.^[13] The reuse skips the prefill of the shared prefix as well as its memory; llama.cpp's server likewise skips re-processing a prompt prefix it already holds in a slot's cache.^[8]

05Scheduling prefill against decode

Mixing phases in one step has a cost: a 4,096-token prompt admitted into a step with 32 decoding sequences turns that step from a 12 ms memory-bound one into a 226 ms compute-bound one, and every decoding user sees an 18× pause between two tokens. Chunked prefill bounds the damage by splitting the prompt across steps under a per-step token budget, which vLLM enables by default with decodes scheduled before any prefill tokens, and which TensorRT-LLM calls chunked context under its max_num_tokens limit of 8,192.^[7][11] A smaller budget keeps inter-token latency steady; a larger one gets the new request its first token sooner; vLLM's documentation names 2,048 for latency and above 8,192 for throughput.^[7]

06Speculative decoding

A memory-bound decode step has arithmetic to spare. Speculative decoding spends it on verification: a cheap draft proposes γ tokens, the target model scores all of them in one forward pass, and the longest prefix the target agrees with is kept, plus one token the target produces itself at the first disagreement or after a full match.^[14][1] With greedy decoding the output is exactly what the target alone would produce; with sampling, a rejection rule gives the same guarantee in distribution.^[14] Drafts come from a smaller model with the same tokenizer, from extra prediction heads on the target, or from n-gram lookup in the prompt itself, which TGI offers for code and repetitive text.^[15][16]

The expectation is Leviathan et al.'s Equation 1 for independent acceptances; the speedup divides by the round's cost. The gain exists only while a target pass over γ + 1 tokens costs about what a pass over one costs, which holds at small batch and not at large: TensorRT-LLM states that speedups are observable only at low batch sizes.^[15]

07A serving simulator, checked

One program, in both languages, holds the mechanisms above at toy scale and asserts their properties. A 16-block pool with 4-token blocks allocates block tables for prompts, shares full blocks whose chained hash is already cached, counts references, frees to the tail of an LRU queue in reverse order, and evicts cached content from its head, as vLLM's design document describes.^[13] Two requests sharing a 12-token system prompt are asserted to share three blocks and the pool is asserted to return to empty. A 40-request stream is then run through 8 slots under both batching policies, with continuous batching asserted to finish no later and with lower mean latency; 64 sequences are fitted into a token budget by reservation and by blocks; and 200,000 simulated rounds of speculative decoding at α = 0.8, γ = 4 are asserted to match the expectation formula within 0.02 tokens.

// A serving loop in miniature: a paged KV-cache block pool with prefix sharing and LRU eviction, continuous
// versus static batching over one request stream, and the speculative-decoding expectation checked by simulation.
// Build: g++ -std=c++20 -O2 -Wall -Wextra -Wpedantic -Werror serving.cpp && ./a.out
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <map>
#include <vector>

struct Rng {  // xorshift32 with a fixed seed
    uint32_t state = 9;
    double next() { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state / 4294967296.0; }
    int between(int low, int high) { return low + int(next() * (high - low + 1)); }
};

// ── Paged KV cache: fixed-size blocks, reference counts, content hashes chained through the prefix, LRU free queue.
constexpr int kBlockSize = 4;
struct Block { int referenceCount = 0; uint64_t hash = 0; bool cached = false; };
struct BlockPool {
    std::vector<Block> blocks;
    std::deque<int> freeQueue;                 // head = least recently used
    std::map<uint64_t, int> cachedBlocks;      // full-block hash → block id
    int cacheHits = 0, evictions = 0;
    explicit BlockPool(int count) : blocks(count) { for (int id = 0; id < count; ++id) freeQueue.push_back(id); }
    static uint64_t chainHash(uint64_t parent, const std::vector<int>& tokens, std::size_t begin, std::size_t end) {
        uint64_t hash = parent * 1099511628211ULL + 14695981039346656037ULL;   // parent hash first: a block's identity includes everything before it
        for (std::size_t i = begin; i < end; ++i) hash = (hash ^ uint64_t(tokens[i] + 1)) * 1099511628211ULL;
        return hash;
    }
    // Remove a block from the free queue (it is about to be referenced again).
    void touch(int id) { freeQueue.erase(std::find(freeQueue.begin(), freeQueue.end(), id)); }
    // Pop the least recently used free block; if it still holds cached content, that content is evicted.
    int popFree() {
        assert(!freeQueue.empty());
        const int id = freeQueue.front(); freeQueue.pop_front();
        if (blocks[id].cached) { cachedBlocks.erase(blocks[id].hash); blocks[id].cached = false; ++evictions; }
        return id;
    }
    // Allocate the block table for a prompt: full blocks whose hash is cached are shared, the rest come from the free queue.
    std::vector<int> allocate(const std::vector<int>& tokens) {
        std::vector<int> table; uint64_t parent = 0;
        const std::size_t fullBlocks = tokens.size() / kBlockSize;
        for (std::size_t block = 0; block < fullBlocks; ++block) {
            parent = chainHash(parent, tokens, block * kBlockSize, (block + 1) * kBlockSize);
            if (auto hit = cachedBlocks.find(parent); hit != cachedBlocks.end()) {
                if (blocks[hit->second].referenceCount++ == 0) touch(hit->second);   // in use again: keep it off the free queue
                table.push_back(hit->second); ++cacheHits; continue;
            }
            const int id = popFree(); blocks[id] = {1, parent, true}; cachedBlocks[parent] = id; table.push_back(id);
        }
        if (tokens.size() % kBlockSize) { const int id = popFree(); blocks[id] = {1, 0, false}; table.push_back(id); }   // partial last block: not cacheable yet
        return table;
    }
    // Release a table: blocks with no other users return to the free queue tail, last block first, keeping their cached content until evicted.
    void release(const std::vector<int>& table) {
        for (auto it = table.rbegin(); it != table.rend(); ++it) if (--blocks[*it].referenceCount == 0) freeQueue.push_back(*it);
    }
    int inUse() const { int count = 0; for (const Block& block : blocks) count += block.referenceCount > 0; return count; }
};

// ── Requests and the two batching policies.
struct Request { int id, arrival, prompt, output, remaining, start = -1, finish = -1; };
struct Outcome { int steps; double meanLatency, utilization; };
Outcome simulate(std::vector<Request> queue, int slots, bool continuous) {
    std::vector<Request> active, finished; int step = 0; long generated = 0;
    while (!queue.empty() || !active.empty()) {
        const bool canAdmit = continuous || active.empty();   // static batching waits for the whole batch to drain
        while (canAdmit && int(active.size()) < slots && !queue.empty() && queue.front().arrival <= step) { queue.front().start = step; active.push_back(queue.front()); queue.erase(queue.begin()); }
        for (Request& request : active) { --request.remaining; ++generated; if (request.remaining == 0) request.finish = step + 1; }
        for (auto it = active.begin(); it != active.end();) if (it->remaining == 0) { finished.push_back(*it); it = active.erase(it); } else ++it;
        ++step;
    }
    double latency = 0; for (const Request& request : finished) latency += request.finish - request.arrival;
    return {step, latency / finished.size(), double(generated) / (double(step) * slots)};
}

int main() {
    Rng rng;
    // 1. Block pool: two requests sharing a 12-token system prompt share its three full blocks; frees and evictions balance.
    BlockPool pool(16);
    std::vector<int> systemPrompt(12); for (int& token : systemPrompt) token = rng.between(0, 99);
    std::vector<int> first(systemPrompt), second(systemPrompt);
    for (int i = 0; i < 7; ++i) first.push_back(rng.between(0, 99));     // 19 tokens: 4 full blocks + 1 partial
    for (int i = 0; i < 5; ++i) second.push_back(rng.between(0, 99));    // 17 tokens: 4 full blocks + 1 partial, first 3 shared
    std::vector<int> tableFirst = pool.allocate(first), tableSecond = pool.allocate(second);
    assert(tableFirst.size() == 5 && tableSecond.size() == 5);
    assert(std::equal(tableFirst.begin(), tableFirst.begin() + 3, tableSecond.begin()));   // the shared prefix maps to the same blocks
    assert(pool.cacheHits == 3 && pool.inUse() == 7);                                   // 5 + 5 tables, 3 blocks shared
    pool.release(tableFirst); pool.release(tableSecond);
    assert(pool.inUse() == 0 && pool.freeQueue.size() == 16);
    std::vector<int> again = pool.allocate(first);                                       // everything full is still cached
    assert(pool.cacheHits == 7 && pool.inUse() == 5);
    pool.release(again);
    std::vector<std::vector<int>> churn;                                                // fill the pool with new content to force LRU eviction
    for (int round = 0; round < 4; ++round) { std::vector<int> prompt(16); for (int& token : prompt) token = rng.between(100, 199); churn.push_back(pool.allocate(prompt)); }
    assert(pool.evictions > 0 && pool.inUse() == 16);
    for (const auto& table : churn) pool.release(table);
    assert(pool.inUse() == 0);
    std::printf("block pool: %d cache hits, %d evictions, all blocks returned\n", pool.cacheHits, pool.evictions);

    // 2. Batching: the same 40 requests through 8 slots, admitted only between batches versus whenever a slot frees.
    std::vector<Request> stream; int clock = 0;
    for (int id = 0; id < 40; ++id) { clock += rng.between(0, 6); const int output = rng.between(8, 64); stream.push_back({id, clock, rng.between(16, 128), output, output}); }
    const Outcome fixed = simulate(stream, 8, false), rolling = simulate(stream, 8, true);
    std::printf("static batching: %d steps, mean latency %.1f steps, slot utilization %.2f\n", fixed.steps, fixed.meanLatency, fixed.utilization);
    std::printf("continuous batching: %d steps, mean latency %.1f steps, slot utilization %.2f\n", rolling.steps, rolling.meanLatency, rolling.utilization);
    assert(rolling.steps <= fixed.steps && rolling.meanLatency < fixed.meanLatency);

    // 3. Memory: reserving the maximum length per sequence versus paging, for 64 sequences of 50 to 500 tokens in a 32,768-token budget.
    const int budget = 32768, maxLength = 2048, blockSize = 16;
    int reservedFits = std::min(64, budget / maxLength), pagedFits = 0, blocksUsed = 0;
    for (int i = 0; i < 64; ++i) { const int length = rng.between(50, 500), blocks = (length + blockSize - 1) / blockSize; if ((blocksUsed + blocks) * blockSize > budget) break; blocksUsed += blocks; ++pagedFits; }
    std::printf("memory: %d sequences fit with reservation, %d with %d-token blocks\n", reservedFits, pagedFits, blockSize);
    assert(pagedFits > reservedFits);

    // 4. Speculative decoding: with γ drafts each accepted with probability α, a target pass yields (1 − α^(γ+1)) / (1 − α) tokens on average.
    const double alpha = 0.8; const int gamma = 4, trials = 200000; long tokens = 0;
    for (int trial = 0; trial < trials; ++trial) { int accepted = 0; while (accepted < gamma && rng.next() < alpha) ++accepted; tokens += accepted + 1; }   // +1: the correction or bonus token
    const double measured = double(tokens) / trials, expected = (1 - std::pow(alpha, gamma + 1)) / (1 - alpha);
    std::printf("speculative decoding: %.3f tokens per target pass measured, %.3f expected\n", measured, expected);
    assert(std::fabs(measured - expected) < 0.02);
    return 0;
}

// A serving loop in miniature: a paged KV-cache block pool with prefix sharing and LRU eviction, continuous
// versus static batching over one request stream, and the speculative-decoding expectation checked by simulation.
// Build: rustc --edition 2021 -O -D warnings serving.rs && ./serving
use std::collections::{HashMap, VecDeque};

struct Rng { state: u32 } // xorshift32 with a fixed seed
impl Rng {
    fn next(&mut self) -> f64 { self.state ^= self.state << 13; self.state ^= self.state >> 17; self.state ^= self.state << 5; self.state as f64 / 4294967296.0 }
    fn between(&mut self, low: i32, high: i32) -> i32 { low + (self.next() * (high - low + 1) as f64) as i32 }
}

// ── Paged KV cache: fixed-size blocks, reference counts, content hashes chained through the prefix, LRU free queue.
const BLOCK_SIZE: usize = 4;
#[derive(Clone, Copy, Default)]
struct Block { reference_count: usize, hash: u64, cached: bool }
struct BlockPool { blocks: Vec<Block>, free_queue: VecDeque<usize>, cached_blocks: HashMap<u64, usize>, cache_hits: usize, evictions: usize }
impl BlockPool {
    fn new(count: usize) -> BlockPool { BlockPool { blocks: vec![Block::default(); count], free_queue: (0..count).collect(), cached_blocks: HashMap::new(), cache_hits: 0, evictions: 0 } }
    fn chain_hash(parent: u64, tokens: &[i32]) -> u64 {
        let mut hash = parent.wrapping_mul(1099511628211).wrapping_add(14695981039346656037); // parent hash first: a block's identity includes everything before it
        for &token in tokens { hash = (hash ^ (token as u64 + 1)).wrapping_mul(1099511628211); }
        hash
    }
    // Remove a block from the free queue (it is about to be referenced again).
    fn touch(&mut self, id: usize) { let position = self.free_queue.iter().position(|&b| b == id).unwrap(); self.free_queue.remove(position); }
    // Pop the least recently used free block; if it still holds cached content, that content is evicted.
    fn pop_free(&mut self) -> usize {
        let id = self.free_queue.pop_front().expect("out of KV blocks");
        if self.blocks[id].cached { self.cached_blocks.remove(&self.blocks[id].hash); self.blocks[id].cached = false; self.evictions += 1; }
        id
    }
    // Allocate the block table for a prompt: full blocks whose hash is cached are shared, the rest come from the free queue.
    fn allocate(&mut self, tokens: &[i32]) -> Vec<usize> {
        let mut table = Vec::new(); let mut parent = 0u64;
        for chunk in tokens.chunks(BLOCK_SIZE) {
            if chunk.len() < BLOCK_SIZE { let id = self.pop_free(); self.blocks[id] = Block { reference_count: 1, hash: 0, cached: false }; table.push(id); break; } // partial last block: not cacheable yet
            parent = Self::chain_hash(parent, chunk);
            if let Some(&id) = self.cached_blocks.get(&parent) {
                if self.blocks[id].reference_count == 0 { self.touch(id); } // in use again: keep it off the free queue
                self.blocks[id].reference_count += 1; table.push(id); self.cache_hits += 1; continue;
            }
            let id = self.pop_free(); self.blocks[id] = Block { reference_count: 1, hash: parent, cached: true }; self.cached_blocks.insert(parent, id); table.push(id);
        }
        table
    }
    // Release a table: blocks with no other users return to the free queue tail, last block first, keeping their cached content until evicted.
    fn release(&mut self, table: &[usize]) {
        for &id in table.iter().rev() { self.blocks[id].reference_count -= 1; if self.blocks[id].reference_count == 0 { self.free_queue.push_back(id); } }
    }
    fn in_use(&self) -> usize { self.blocks.iter().filter(|block| block.reference_count > 0).count() }
}

// ── Requests and the two batching policies.
#[derive(Clone)]
struct Request { arrival: i32, remaining: i32, finish: i32 }
struct Outcome { steps: i32, mean_latency: f64, utilization: f64 }
fn simulate(mut queue: Vec<Request>, slots: usize, continuous: bool) -> Outcome {
    let (mut active, mut finished): (Vec<Request>, Vec<Request>) = (Vec::new(), Vec::new());
    let (mut step, mut generated) = (0i32, 0i64);
    while !queue.is_empty() || !active.is_empty() {
        let can_admit = continuous || active.is_empty(); // static batching waits for the whole batch to drain
        while can_admit && active.len() < slots && !queue.is_empty() && queue[0].arrival <= step { active.push(queue.remove(0)); }
        for request in active.iter_mut() { request.remaining -= 1; generated += 1; if request.remaining == 0 { request.finish = step + 1; } }
        let (done, still): (Vec<Request>, Vec<Request>) = active.drain(..).partition(|request| request.remaining == 0);
        finished.extend(done); active = still;
        step += 1;
    }
    let latency: f64 = finished.iter().map(|request| (request.finish - request.arrival) as f64).sum::<f64>() / finished.len() as f64;
    Outcome { steps: step, mean_latency: latency, utilization: generated as f64 / (step as f64 * slots as f64) }
}

fn main() {
    let mut rng = Rng { state: 9 };
    // 1. Block pool: two requests sharing a 12-token system prompt share its three full blocks; frees and evictions balance.
    let mut pool = BlockPool::new(16);
    let system_prompt: Vec<i32> = (0..12).map(|_| rng.between(0, 99)).collect();
    let mut first = system_prompt.clone(); let mut second = system_prompt.clone();
    for _ in 0..7 { first.push(rng.between(0, 99)); }  // 19 tokens: 4 full blocks + 1 partial
    for _ in 0..5 { second.push(rng.between(0, 99)); } // 17 tokens: 4 full blocks + 1 partial, first 3 shared
    let table_first = pool.allocate(&first); let table_second = pool.allocate(&second);
    assert!(table_first.len() == 5 && table_second.len() == 5);
    assert!(table_first[..3] == table_second[..3]); // the shared prefix maps to the same blocks
    assert!(pool.cache_hits == 3 && pool.in_use() == 7); // 5 + 5 tables, 3 blocks shared
    pool.release(&table_first); pool.release(&table_second);
    assert!(pool.in_use() == 0 && pool.free_queue.len() == 16);
    let again = pool.allocate(&first); // everything full is still cached
    assert!(pool.cache_hits == 7 && pool.in_use() == 5);
    pool.release(&again);
    let mut churn = Vec::new(); // fill the pool with new content to force LRU eviction
    for _ in 0..4 { let prompt: Vec<i32> = (0..16).map(|_| rng.between(100, 199)).collect(); churn.push(pool.allocate(&prompt)); }
    assert!(pool.evictions > 0 && pool.in_use() == 16);
    for table in &churn { pool.release(table); }
    assert!(pool.in_use() == 0);
    println!("block pool: {} cache hits, {} evictions, all blocks returned", pool.cache_hits, pool.evictions);

    // 2. Batching: the same 40 requests through 8 slots, admitted only between batches versus whenever a slot frees.
    let mut stream = Vec::new(); let mut clock = 0;
    for _ in 0..40 { clock += rng.between(0, 6); let output = rng.between(8, 64); let _prompt = rng.between(16, 128); stream.push(Request { arrival: clock, remaining: output, finish: -1 }); } // same draw order as the C++ initializer list
    let fixed = simulate(stream.clone(), 8, false); let rolling = simulate(stream, 8, true);
    println!("static batching: {} steps, mean latency {:.1} steps, slot utilization {:.2}", fixed.steps, fixed.mean_latency, fixed.utilization);
    println!("continuous batching: {} steps, mean latency {:.1} steps, slot utilization {:.2}", rolling.steps, rolling.mean_latency, rolling.utilization);
    assert!(rolling.steps <= fixed.steps && rolling.mean_latency < fixed.mean_latency);

    // 3. Memory: reserving the maximum length per sequence versus paging, for 64 sequences of 50 to 500 tokens in a 32,768-token budget.
    let (budget, max_length, block_size) = (32768, 2048, 16);
    let reserved_fits = (budget / max_length).min(64);
    let (mut paged_fits, mut blocks_used) = (0, 0);
    for _ in 0..64 { let length = rng.between(50, 500); let blocks = (length + block_size - 1) / block_size; if (blocks_used + blocks) * block_size > budget { break; } blocks_used += blocks; paged_fits += 1; }
    println!("memory: {} sequences fit with reservation, {} with {}-token blocks", reserved_fits, paged_fits, block_size);
    assert!(paged_fits > reserved_fits);

    // 4. Speculative decoding: with γ drafts each accepted with probability α, a target pass yields (1 − α^(γ+1)) / (1 − α) tokens on average.
    let (alpha, gamma, trials) = (0.8f64, 4i32, 200000);
    let mut tokens = 0i64;
    for _ in 0..trials { let mut accepted = 0i32; while accepted < gamma && rng.next() < alpha { accepted += 1; } tokens += (accepted + 1) as i64; } // +1: the correction or bonus token
    let measured = tokens as f64 / trials as f64;
    let expected = (1.0 - alpha.powi(gamma + 1)) / (1.0 - alpha);
    println!("speculative decoding: {:.3} tokens per target pass measured, {:.3} expected", measured, expected);
    assert!((measured - expected).abs() < 0.02);
}

08Where serving numbers mislead

Roofline estimates are floors. The first widget's step times assume perfect overlap and no kernel launch, synchronization, sampling or tokenization cost; real steps at small batch are often several times longer, which makes the memory-bound regime wider in practice than the arithmetic says.

Token streaming changes what latency means. TGI's documentation makes the point with a 1,000-token answer at 100 tokens per second: ten seconds to the full answer either way, but the first words arrive at once when tokens are streamed, and users can stop a generation that is going wrong.^[17] Time to first token and inter-token latency are the numbers users feel; end-to-end latency is the one batch jobs feel.

Prefix caching has a security surface. A cache shared between tenants lets a request learn, from its own latency, whether someone else recently sent the same prefix; vLLM's per-request cache salt exists to confine reuse to a trust group.^[13]

09What's next

This is the last page of the series. The Build a Language Model hub lays out every page, the order they build in and what each depends on, and the adjacent pages on convolutional networks and diffusion models apply the same training machinery to images.

10Sources

The engine documentation and design documents define the mechanisms and the defaults quoted; the model card and code define the cache shapes. Widget readouts report values computed in the page from the stated roofline model, simulated request streams and n-gram models fit to the embedded corpora.

1. Joao Gante, 2023. Assisted Generation: a new direction towards low-latency text generation, Hugging Face blog. Greedy candidate generation with a draft of the same tokenizer, verification in one target pass with left-to-right invalidation, the heuristic that starts at 5 candidates and adds 2 on a full match or subtracts 1 otherwise, and decode being memory-bound.
2. Andrej Karpathy. nanoGPT, model.py. The A100's 312 TFLOP/s bfloat16 peak used as the reference for utilization, and the 6N + 12·L·H·Q·T FLOPs count whose forward third this page uses.
3. Hugging Face. Optimizing LLMs for Speed and Memory, Transformers documentation. Weights at 2 bytes per parameter in bfloat16 (Llama-2-70b: 140 GB), the 80 GB ceiling of A100 and H100 parts, and multi-query and grouped-query attention as the architectural answers to cache size.
4. Meta, 2024. Meta Llama 3 model card. Grouped-query attention used in the 8B and 70B models for inference efficiency; sequences of 8,192 tokens.
5. Meta, 2024. llama3, llama/model.py. n_kv_heads separate from n_heads, with keys and values repeated across query heads at attention time; dim 4096, 32 layers, 32 heads as the defaults.
6. Meta. llama-models, models/sku_list.py. The Llama 3 8B architecture arguments: dim 4096, 32 layers, 32 query heads and 8 key-value heads.
7. vLLM contributors. Optimization and tuning, vLLM documentation. Chunked prefill on by default with decodes scheduled first, max_num_batched_tokens trading inter-token latency against time to first token, and preemption by recomputation when cache space runs out.
8. ggml contributors. llama.cpp server README. Parallel slots with continuous batching on by default, prompt caching with reuse, K and V cache types from f16 down to q4_0, and a draft model for speculative decoding.
9. Hugging Face. KV cache strategies, Transformers documentation. Dynamic, static, offloaded and quantized caches, and sliding-window layers whose cache stops growing at the window size.
10. Hugging Face. Text Generation Inference, README. Continuous batching of incoming requests, token streaming over server-sent events, Flash Attention and PagedAttention kernels, and quantized weights.
11. NVIDIA. TensorRT-LLM, Paged Attention, IFB, and Request Scheduling. Context-phase and generation-phase sequences in one batch, max_num_tokens (8,192 by default) as the per-step token budget, and chunked context so long prompts do not block generation.
12. vLLM contributors. vLLM paged attention, design document (paper: Kwon et al., 2023, arXiv:2309.06180). The key and value caches split into blocks of a fixed number of tokens per head, 16 in the example, addressed by physical block number.
13. vLLM contributors. Automatic prefix caching, vLLM documentation. Block hashes chained through the parent block's hash, reference counts, touching cached blocks on reuse, freeing in reverse order, LRU eviction from the head of the free queue, and per-request cache salts for isolation.
14. Yaniv Leviathan, Matan Kalman, Yossi Matias, 2023. Fast Inference from Transformers via Speculative Decoding, ICML 2023 (arXiv:2211.17192). The expected number of tokens per target pass, (1 − α^(γ+1))/(1 − α), under independent acceptances with probability α, and the lossless acceptance rule.
15. NVIDIA. TensorRT-LLM, speculative decoding. Draft/target with a shared tokenizer, speedups visible only at low batch sizes, EAGLE-3 drafters and tree-shaped drafts.
16. Hugging Face. Speculation, TGI documentation. Medusa heads and n-gram lookup as draft sources, with n-gram working best on code and repetitive text.
17. Hugging Face. Streaming, TGI documentation. Returning tokens as they are generated so that a 1,000-token answer at 100 tokens per second shows its first words immediately rather than after ten seconds.