Database-Optimized Inference

If Chapter 12 introduced the database analogy, this chapter turns it into an engineering playbook. A transformer at inference time already behaves like a tiny, very fast, highly specialized database engine. It has a bounded working set called the KV cache. It appends new records one token at a time. It repeatedly scans historical rows to answer the current query. It projects one hidden vector against a vocabulary table and picks the best row. And when multiple users arrive at once, the server becomes a scheduler juggling sessions, cache residency, and latency goals. Once you describe the problem that way, decades of database intuition become directly useful.

That does not mean a transformer should be literally rewritten as PostgreSQL with matrix kernels bolted on. The value is more practical than that. Database engineers already know how to think about fixed-capacity stores, append logs, checkpoints, materialized views, eviction policies, connection pools, query planners, constraint enforcement, and cost models. Those same questions appear in inference serving. When should we precompute? When should we cache? When should we approximate? What should be evicted when memory fills? How do we recover or branch state cheaply? Those are database questions, and modern inference stacks answer them every millisecond.

1. The context window as bounded storage

The first useful reframing is to stop talking about “context” as though it were an abstract cloud of meaning. In inference code, context is concrete state. Every decoded token creates keys and values at every layer. Those tensors are indexed by position and then revisited by later tokens during attention. The maximum context length is therefore not just a modeling hyperparameter. It is the capacity limit of a persistent store. If a model supports 128K tokens, then each layer owns a position-indexed table with room for 128K rows of key-value data and no more.

// conceptual schema
kv_cache[layer][position] = {
    key_vector,    // [n_kv_heads, d_head]
    value_vector   // [n_kv_heads, d_head]
}

// more implementation-like shape
keys   : [n_layers, n_kv_heads, max_context_length, d_head]
values : [n_layers, n_kv_heads, max_context_length, d_head]

That schema has all the traits database people recognize immediately. Capacity is fixed by max_context_length. Writes are append-only during a generation session. Reads are mostly range reads over the prefix [0, current_position]. The store is partitioned by layer, and often by KV head as well. The primary key is effectively (layer, position). Because position is monotonically increasing, the data structure behaves much more like a time-series store or append-only log than like a random-update heap table. This is why paging, compaction, checkpointing, and eviction analogies land so naturally here: the underlying mechanics are already close.

The engineering consequence is brutal but clarifying. Once the cache is full, you cannot keep pretending all history is equally affordable. Something must happen: evict old rows, compress them, summarize them, or refuse the request. This is exactly why context extension work is not merely a modeling story. It is a storage-management story. The “long context problem” is partly a memory-capacity problem wearing an NLP costume.

KV bytes ≈ n_layers × max_context_length × n_kv_heads × d_head × 2 × bytes_per_element

That formula is the rough storage bill. The factor of two is for keys and values. For a 32-layer model with grouped-query attention, long contexts, and FP16 storage, the result becomes large fast. Once you write the cost down explicitly, questions about page size, fragmentation, sharing, reuse, and eviction stop feeling optional. They are the core of the serving problem.

If you were building the first production version of a serving stack, the important insight is not that one eviction policy is universally best. It is that the policy should be explicit, measurable, and workload-dependent. Chat workloads with highly local turn-taking often tolerate sliding windows well. Retrieval-heavy prompts with distant anchors do not. Once you state the problem in storage terms, the next step is obvious: measure hit value by position, then choose the cheapest policy that preserves quality for your actual traffic.

2. Prefix caching as materialized views

Common prefixes are the highest-ROI inference optimization that many teams initially underuse. System prompts, tool instructions, policy text, and few-shot exemplars often repeat across thousands of requests. Without caching, the model redoes the entire prefill every time. In database terms, that is like rerunning a complex join for every query even though the first 2,048 rows of the plan are identical. The obvious database fix is a materialized view: compute once, persist the result, and reuse it until the underlying data changes.

For transformers, the reusable artifact is not the output text. It is the prefix KV state. Run the shared prefix through the model once, store the per-layer key and value tensors produced at the end of that prefix, and later requests can begin from the divergence point. That converts repeated prefill from “project every prefix token through every layer again” into “attach an existing checkpoint, append the request-specific tail, and continue.” The savings can be dramatic because prefill is where the repeated prompt length hurts most.

PrefixKey key = hash(model_id,
                     tokenizer_id,
                     rope_config,
                     token_ids[0:prefix_len]);

if (prefix_cache.contains(key)) {
    PrefixState p = prefix_cache.get(key);
    attach_kv_pages(session, p.kv_pages);
    current_pos = p.prefix_len;
} else {
    run_prefill(token_ids[0:prefix_len]);
    prefix_cache.put(key, snapshot_kv_state(prefix_len));
}

The practical details matter. The hash key must include not just token IDs, but everything that makes the resulting KV state semantically different: model revision, tokenizer revision, rope scaling configuration, and sometimes quantization mode if that changes runtime representation. On a hit, the cheapest implementation is not always a raw memcpy of the entire prefix cache. Systems such as paged-attention runtimes often map or reference existing KV pages into a new session and only copy on write if the session later diverges. That turns prefix caching into state sharing, not just state duplication.

Memory budgeting still matters. Materialized views can fill your buffer pool if every prefix is unique. The common answer is a second-level LRU or LFU policy over prefix objects themselves. Keep the hot prefixes, evict cold ones, and size the cache so that shared system prompts survive while one-off prompts fall out naturally. In many production traces, a small number of very common prefixes dominate traffic, so even a modest prefix cache buys a large fraction of the total available win.

A concrete example makes the magnitude clear. Suppose your application uses a 2,048-token system prompt plus 64 user tokens. The first request pays for all 2,112 prefix-and-tail tokens. The next request with the same 2,048-token prefix pays only for the 64 new tokens plus any response generation. In practice that can save roughly 95 percent of the repeated prefill compute. Exact gains depend on batching, kernel fusion, and whether you can share pages rather than copy them, but the basic conclusion almost never changes: repeated prefixes are a gift, and materializing them is usually the first optimization worth shipping.

3. Delta chains and incremental execution

Once you accept that inference state is persistent state, the next question is how to represent changes cheaply. A generation session does not rewrite its whole cache every token. It appends tiny deltas: one new position per layer. That is structurally identical to a write-ahead log. The stable past exists already. Each new token contributes a small incremental record saying, in effect, “for layer 17 at position 912, here are the new key and value vectors.” Framing it that way suggests checkpointing, replay, and branching strategies immediately.

The simplest scheme is periodic checkpoint plus replay. Every so often, persist a full session state snapshot. Between checkpoints, persist only appended token deltas. If the session must be paused, migrated, or recovered after a worker failure, reload the last checkpoint and replay the recent deltas. For short conversations, replay cost is negligible. For very long sessions, checkpoint interval becomes a classic systems trade-off: more checkpoints cost more storage and write bandwidth up front, fewer checkpoints make recovery slower later.

Branching is where the database analogy becomes especially concrete. “Regenerate” or “what if I take a different tool call?” are fork operations. The new branch should share the historical prefix and diverge only from the first new token onward. If you full-copy the entire KV cache on every branch, you pay an absurd amount of memory bandwidth and storage for mostly identical state. A copy-on-write page model is vastly better: shared pages remain shared until one branch writes beyond the fork point.

struct SessionState {
    Checkpoint* base_checkpoint;
    DeltaLog* delta_log;         // appended token records
    PageRef* kv_pages;           // refcounted pages
    int verified_pos;            // last committed token
};

SessionState fork_session(SessionState* parent) {
    SessionState child = *parent;
    incref_pages(child.kv_pages);
    child.delta_log = clone_tail_metadata(parent->delta_log);
    return child;
}

Speculative decoding fits this same pattern beautifully. A draft model proposes several tokens ahead, like a branch predictor guessing future instructions. The main model verifies those proposed tokens in a batch. If they match, commit the corresponding KV deltas and advance the verified position. If they disagree, roll back to the last verified point and discard the speculative tail. In other words, speculative decoding is speculative execution with transactional commit and rollback semantics. Thinking about it that way makes correctness criteria much clearer than hand-waving about “faster generation.”

The immediate implementation lesson is to separate verified state from tentative state. Once you have that distinction, rollback, branching, and speculative decode all become variations of the same mechanism. Without it, teams end up scattering ad hoc flags and partial buffers through the codebase. Database systems learned long ago that logs, checkpoints, and copy-on-write are cleaner abstractions. Inference engines benefit from the same discipline.

4. Query planning for attention

Attention is the most database-looking part of inference because it is literally a repeated query over stored history. The new token produces a query vector. The KV cache provides keys and values. The engine computes compatibility scores, normalizes them, and blends payload rows into an answer. In its default form, this is a full scan over all prior positions. That is exact and easy to reason about, but as context grows it also becomes the central question for long-context efficiency: do we really need to compare against every row every time?

SELECT weighted_sum(v.value_vector)
FROM kv_cache k JOIN kv_cache v ON k.position = v.position
WHERE k.layer = current_layer
  AND k.position <= current_position
ORDER BY dot_product(query, k.key_vector) DESC
-- with soft aggregation via softmax instead of hard selection

That pseudo-SQL is imperfect but useful. Keys act like indexable descriptors. Values are the payload rows. The current token issues a query against all historical rows up to the causal frontier. Standard attention performs the equivalent of a full table scan because every key must receive a dot product before softmax can normalize the scores. At sequence length T, each new decode step pays O(T) score work per head for the current query position, plus value aggregation over the same candidate set. For small contexts that is fine. For very long contexts it dominates latency.

Database people immediately ask the natural follow-up: can we build an index? The answer is yes, but only with caveats. Learned attention relevance is not a stable scalar column like “customer_id.” It is a dynamic dot product against a changing query vector. That means any index over keys must be approximate, query-time aware, and cheap to maintain as new rows append. Locality-sensitive hashing, coarse quantization, clustering, and anchor-based routing are all candidates, but they trade exactness for less scan work.

The most practical planning rule is this: do not build a fancy attention index until you have evidence that full scans are the bottleneck at your target context lengths. Query planners only help when scan cost is large enough to dominate. Under 4K or 8K contexts on modern hardware, exact full scans are often simpler and good enough. At 64K or 128K, candidate pruning starts to look a lot more attractive. The transition point is empirical, which is why database-style cost modeling matters. You need latency curves by context length, not ideology.

5. Vocabulary projection as table scan

After the final transformer block, the model takes one hidden vector and scores it against every vocabulary row through the lm_head. That is not merely analogous to a table scan. It is a table scan. If the vocabulary has 32K, 64K, or 128K entries, the engine computes one score per row, then chooses the best candidates for sampling or argmax. For large vocabularies, this stage can be a meaningful slice of decode latency, especially when the hidden width is large and batch size is small.

logits = h_t × W_vocab^T

cost per token ≈ vocab_size × d_model multiply-adds

If vocab_size = 128,000 and d_model = 4,096, a single output projection asks for roughly 524 million multiply-adds before you even sample. Database people again ask the obvious question: can we avoid scoring every row? Sometimes yes, but the answer depends on how much accuracy you are willing to trade and what side information you can use for pruning.

One subtle point matters here: maintaining a top-k heap during the scan does not by itself reduce the number of dot products. It reduces sort cost and lets you stream the best candidates without materializing a full sorted list. To early-exit safely, you need upper bounds. For example, if vocabulary rows are grouped into blocks with precomputed norm bounds or centroid bounds, you can skip blocks whose best possible score cannot beat the current kth candidate. That turns “top-k heap” from a selection trick into an actual query optimization.

// staged vocabulary filtering
approx_logits = int4_matvec(hidden, approx_W_vocab);   // cheap broad pass
candidates = top_k(approx_logits, 1000);
exact_logits = fp16_matvec_subset(hidden, W_vocab, candidates);
next_token = sample(exact_logits);

In practice, staged filtering is often the most believable approximate design because it preserves exactness where it matters most: the final candidate set. Clustered routing can be faster, but it is easier to catastrophically miss a good token. A staged low-precision prefilter is more forgiving because the shortlist can be oversized. Again, the database lesson applies cleanly: first use a cheap filter to reduce the search space, then spend expensive exact work only where selectivity says it matters.

There is also a memory-locality angle. A full dense lm_head scan touches a very large weight matrix every token, which can make the decode path sensitive to bandwidth and cache reuse. Subset rescoring reduces not only arithmetic but also the number of rows that must be revisited in full precision. On modern accelerators that difference is sometimes as important as the FLOP reduction itself, because the hot path is often a problem of feeding weights efficiently rather than merely multiplying them.

6. Batch processing as connection pooling

Serving many users at once is not one long inference. It is a multiprogrammed system. Each active request has its own session state, chiefly its own KV pages and scheduler metadata. That makes multi-user inference look a lot like database connection handling. The server accepts work, allocates a slot, tracks session-local state, and tries to maximize throughput without letting one request monopolize the machine.

Continuous batching is the serving equivalent of admitting new queries whenever executor slots free up instead of waiting for a whole synchronized batch boundary. Dynamic batching groups compatible requests so one kernel launch can advance many sessions at once, even if those sessions arrived at different times. Under the hood, the scheduler is deciding which connections get serviced next, which sessions can share a batch shape, and whether a long-running response should be preempted so a short interactive request can jump ahead.

Once stated this way, familiar scheduling policies reappear: fairness, priority queues, admission control, and preemption. Short prompts may deserve latency priority. Long offline jobs may be scheduled for throughput. Memory admission matters because accepting a session without enough KV capacity is like accepting a transaction without enough buffer pages. Modern serving frameworks already encode these decisions. The database framing simply gives them names engineers already know how to reason about.

A practical serving stack usually needs two allocators, not one. The first allocator manages execution slots: which sessions will advance on the next kernel launch. The second allocator manages KV residency: which pages belong to which session, which pages are shared because of prefix caching, and whether there is enough free capacity to admit one more request without forcing bad eviction. Engineers sometimes optimize batching logic while ignoring page allocation policy, then wonder why throughput collapses under bursty traffic. The real system bottleneck is often not arithmetic occupancy but fragmented or overcommitted session state.

The good news is that these policies are composable. You can run continuous batching for throughput, reserve a few high-priority slots for latency-sensitive work, and still use shared prefix pages underneath both. That stack of policies sounds complicated only until you realize it is the same structure used in mature data systems: admission control at the front door, pooled workers in the middle, and explicit state residency rules below them.

7. Grammar-constrained decoding as schema validation

Structured generation is where constraint enforcement stops being metaphorical and becomes literal. If the output must be valid JSON, XML, SQL, or code matching a known grammar, then not every token is legal at every step. Inference can exploit that by masking out invalid tokens before sampling. This is the same spirit as a database CHECK constraint or schema validator: do not let invalid state commit to the output stream in the first place.

The implementation is usually a deterministic automaton or parser state machine tracking which next characters or token prefixes are legal. After the model produces logits, the decoder intersects the model's candidate set with the grammar's valid set. Invalid tokens receive -∞ or a very large negative mask so their probability becomes zero after softmax. The model therefore never wastes probability mass on syntactically impossible continuations, and downstream code never needs to reject and retry malformed outputs as often.

GrammarState g = grammar_state;
TokenMask allowed = valid_next_tokens(g);

for (int tok = 0; tok < vocab_size; ++tok) {
    if (!allowed[tok]) logits[tok] = -INFINITY;
}

next = sample(logits);
grammar_state = advance(grammar_state, next);

This is one of the rare optimizations that helps both reliability and, sometimes, speed. Reliability improves because the decoder never walks into impossible syntactic states. Speed can improve because fewer bad continuations need to be explored or repaired. The caveat is that the mask computation itself must be efficient. Character-level grammars need token-level projection tables, otherwise legal-string logic can become slower than the logits pass it is supposed to help.

8. Cost model and expected gains

Database engineers do not trust optimizations without a cost model, and inference engineers should behave the same way. Every trick above moves cost between compute, memory, approximation error, and implementation complexity. Some wins are workload-specific. Prefix caching explodes in value when prefixes repeat and does nothing when every prompt is unique. Approximate attention can be transformational at 128K context and pointless at 4K. Speculative decoding can slash latency but may reduce throughput if verification overhead and draft-model costs are poorly tuned.

The table is intentionally blunt. The speedup ranges are not universal constants. They are order-of-magnitude expectations meant to guide prioritization. Prefix caching is usually the easiest large win because it removes obviously duplicated work. Streaming top-k or staged vocabulary filtering is modest but accessible. Attention approximation and speculative decoding can be spectacular, but only when the surrounding serving stack is mature enough to support them well.

Most importantly, these optimizations interact. Prefix caching reduces prefill cost, which may make decode cost more visible. Better batching can hide some per-token overheads, which changes whether speculative decoding is worth it. Aggressive KV eviction can shrink memory pressure, which allows larger active batches, which changes throughput curves. That is why cost modeling must be empirical. You do not optimize “the transformer” in general. You optimize a specific workload on a specific serving stack with a measurable traffic mix.

For that reason, profile by phase rather than by model alone. Separate tokenization, prefill, decode, vocabulary projection, grammar masking, scheduler wait time, and page-allocation overhead. Then bucket the results by prompt length and output length. Otherwise you will average unlike workloads together and obscure the real plan choice. A server whose p50 traffic is short and repetitive may want aggressive prefix caching and almost no attention approximation. A server dominated by long retrieval sessions may want the opposite. Cost-based optimization begins with honest histograms.

9. What this is not

This chapter is not claiming that transformers should be reimplemented as general-purpose databases. Dense linear algebra, fused kernels, and accelerator-friendly layouts still dominate the execution story. Nobody wants a literal SQL engine in the hot path of matrix multiplies. The database language is useful because it names recurring systems problems clearly, not because it replaces the numerical core.

It is also not claiming that every optimization here always helps. Many of them only matter above certain context lengths, below certain latency targets, or under certain traffic distributions. A badly implemented index can be slower than a full scan. A poorly tuned speculative decoder can do extra work and still miss its predicted tokens. An overgrown prefix cache can thrash memory. Database veterans already know this lesson: the existence of an optimization pattern does not guarantee positive value on every workload.

If you were implementing this yourself...

Start with the boring, high-return changes. First, profile prefill and decode separately. If repeated prefixes exist, ship prefix caching before you touch anything more exotic. It is the closest thing this chapter has to a free lunch. Second, if vocabulary projection is nontrivial in your latency profile, add a streaming top-k or staged shortlist path. Third, only introduce KV eviction once memory pressure is a real bottleneck; until then, exact retention is simpler and safer. Fourth, consider speculative decoding only when user-visible latency matters more than maximal throughput and you can afford the engineering complexity of verification, rollback, and draft-model tuning.

And measure everything. The database analogy is powerful precisely because it encourages cost-based thinking instead of vibe-based thinking. A theoretical speedup that vanishes under real memory traffic, real batching, or real prompt distributions is not a speedup. The whole point of this mental model is to make inference engineering feel less magical and more operational. Once you see the context window as a bounded store, many serving decisions stop looking novel. They start looking like familiar systems work, just accelerated, tensorized, and pointed at language.