4–5 Minute Detailed Architecture: Attention Mechanisms & LLM Inference Optimization

Target Duration: ~3.5 to 5 minutes (~700–900 spoken words)
Course Context: CS 794: Systems for Machine Learning | Prof. Mythili Vutukuru
Structure: 5 Architectural Stages covering KV Caching in nanoGPT, Masking Bug Fixes, Radix-Tree Prefix Sharing, CUDA FlashAttention Tiling, and Empirical Benchmarking.


🎙️ Complete Architectural Presentation Script

To explain the architecture and systems contributions of this project, I divide my work into five core stages: the autoregressive decoding bottleneck, KV cache lifecycle management in nanoGPT, the radix-tree shared-prefix cache, custom CUDA FlashAttention with online softmax tiling, and hardware performance profiling.


Stage 1: The Autoregressive Decoding Bottleneck & KV Caching

In standard autoregressive Transformer inference, generating output tokens is an iterative process. At each step, the model predicts the next token conditioned on all past tokens.

In a naive implementation like baseline nanoGPT, generating token $T+1$ re-passes the entire sequence of $T$ tokens through all 12 transformer layers. In every self-attention layer, the Query, Key, and Value projections are re-computed for all previous tokens, even though the historical tokens have not changed. This results in quadratic cumulative compute: $\sum_{t=1}^T \mathcal{O}(t) = \mathcal{O}(T^2)$ FLOPs.

To resolve this, I implemented Key-Value (KV) caching inside `CausalSelfAttention`. I separated generation into two distinct phases:

This converted the per-step cost from $\mathcal{O}(T)$ to $\mathcal{O}(1)$, reducing total generation compute from $\mathcal{O}(T^2)$ to $\mathcal{O}(T)$. In our benchmarks, this yielded a 29.1x speedup in late-stage decode step latency on GPU and a 9.8x overall wall-clock speedup on CPU.

(Hook: Deep dive into Topic 01: KV Caching & Decoding Dynamics)


Stage 2: Causal Masking Subtleties & Chunked-Prefill Bug Fixes

While implementing KV caching and preparing for prefix sharing, I identified two critical masking bugs in `CausalSelfAttention.forward` when handling chunked prefill (when a sequence chunk of length $1 < T < T_{ctx}$ is processed on top of an existing cache):

  1. Non-Flash Attention Crash: The existing code sliced `self.bias[:, :, :T, :T]` (shape $T \times T$). But when appending to an existing cache, the attention score matrix has shape $T \times T_{ctx}$. Because $T \neq T_{ctx}$, PyTorch raised a non-broadcastable dimension error and crashed.
  2. PyTorch SDPA Silent Mask Corruption: The FlashAttention path used `is_causal = (T == T_ctx)`. For a suffix chunk, $T < T_{ctx}$, so `is_causal` evaluated to `False`. As a result, PyTorch applied no mask at all, allowing tokens inside the suffix chunk to illegally attend to future suffix tokens. This did not crash, but silently produced corrupted logits!

I unified the masking formulation with one exact formula: given an already-cached prefix length $P = T_{ctx} - T$, query row $i$ may attend to key columns $0 \dots P+i$. This handles full prefill ($P=0$), single-token decode ($T=1$), and chunked prefill ($1 < T < T_{ctx}$) uniformly and was verified with token-identical greedy tests across both CPU and CUDA.

(Hook: Deep dive into Topic 02: Causal Masking & Chunked Prefill)


Stage 3: Radix-Tree Shared-Prefix KV Cache (Multi-Query Serving)

In real-world LLM workloads—such as customer support bots, few-shot prompting, or agentic tool use—batches of requests share a long common system prompt. Standard batch inference prefills this shared prefix independently for every single query, wasting compute linearly with batch size.

To eliminate this redundancy, I built a Radix-Tree Shared-Prefix Cache (`radix_cache.py`):

In our experiments with 8 prompts sharing a 256-token prefix, radix-tree reuse achieved a 1.25x GPU speedup and a 2.03x CPU speedup over independent processing. However, this introduced a clear architectural trade-off: radix sharing requires keeping multiple branch cache snapshots resident simultaneously, increasing peak GPU memory (544 MB vs 496 MB).

(Hook: Deep dive into Topic 03: Radix-Tree Shared-Prefix Cache)


Stage 4: Custom CUDA FlashAttention with Online Softmax Tiling

Even with KV caching, standard attention is bottlenecked by the GPU Memory Wall. In standard multi-head attention, computing $\text{softmax}(Q K^T / \sqrt{d}) V$ materializes the entire $N \times N$ score matrix in High Bandwidth Memory (HBM). For sequence lengths like $N=4096$, this matrix requires gigabytes of memory and repeated DRAM round-trips over the 192 GB/s memory bus.

To solve this at the hardware level, I implemented a custom FlashAttention kernel in CUDA C++ (`PA4/flash.cu`):

On our RTX 3050 GPU, at $N=4096$, standard attention crashed with a CUDA Out-Of-Memory error trying to allocate 6 GB of VRAM. Our FlashAttention kernel completed in 180.8 ms using only 594 MB of allocated memory, while achieving a 2.76x speedup at $N=2048$.

(Hook: Deep dive into Topic 04: CUDA FlashAttention & Online Softmax)


Stage 5: Hardware Profiling & Roofline Analysis

Finally, profiling our implementation yielded critical systems insights into LLM inference:

(Hook: Deep dive into Topic 05: Benchmarks & Hardware Trade-offs)


Key Challenge Faced & How We Overcame It

The main challenge was managing memory and numerical stability across asynchronous GPU boundaries while maintaining exact correctness.

In the CUDA FlashAttention implementation, online softmax requires computing running row maximums. When initializing the device buffer `d_m`, standard `cudaMalloc` does not zero-initialize, and initializing to `0.0f` clipped negative dot-product scores from the first K/V tile, corrupting the attention weights. I solved this by writing a dedicated initialization kernel `init_neg_inf` setting all entries to $-1\times 10^{20}$.

Furthermore, managing thread block barrier synchronizations (`__syncthreads()`) required extreme precision: one barrier was mandatory after loading K and V tiles into shared memory, and a second barrier was required after the inner loop over Q tiles finished to prevent faster warps from overwriting shared memory before other threads finished reading.

In nanoGPT, the challenge was tracking token offsets across branched prefix caches without memory leaks. I implemented clean snapshot interfaces (`get_kv_cache`/`set_kv_cache`) and built a standalone verification suite (`verify_radix_cache.py`) that verified token-for-token equality between radix-shared generation and independent generation across both PyTorch SDPA and manual attention.