Target Duration: ~60–90 seconds (~190–230 spoken words)
Course Context: CS 794: Systems for Machine Learning | Prof. Mythili Vutukuru
Goal: Deliver a crisp, confident overview connecting model-level KV caching in nanoGPT with kernel-level CUDA FlashAttention, highlighting empirical speedups and memory scaling.
“In my Systems for Machine Learning course project under Professor Mythili Vutukuru, I worked on optimizing LLM inference, focusing on reducing computation and memory usage.
I worked on three parts.
First, I implemented KV caching in nanoGPT to reduce redundant computation during autoregressive decoding. By storing and reusing the Keys and Values of previously processed tokens, the model computes attention only for the newly generated token instead of recomputing attention for the entire sequence. This achieved up to 29.1× GPU speedup and 9.8× CPU speedup.
Second, I worked on sharing KV caches across prompts with common prefixes. In applications where multiple prompts start with the same system instructions, the model would otherwise repeat the same prefill computation. I designed a radix-tree-based cache to store and reuse the KV states for shared prefixes, achieving a 1.25x GPU speedup.
Finally, I implemented FlashAttention in CUDA to reduce the memory required for attention. Instead of creating the entire attention matrix in GPU memory, I processed it in smaller tiles and used online softmax to compute the result incrementally. This reduced the auxiliary memory requirement from $\mathcal{O}(N^2)$ to $\mathcal{O}(N)$.
Through this project, I learned how transformer inference works internally, how redundant computation affects performance, and how to optimize GPU workloads by balancing computation, memory usage, and data movement.”
Answer: Without caching, to generate token $T+1$, the model passes all preceding $T$ tokens through the entire network. At each self-attention layer, it recomputes Key and Value projections for all past tokens. Generating $N$ tokens requires $1 + 2 + 3 + \dots + N = \frac{N(N+1)}{2}$ token forward passes, which is $\mathcal{O}(N^2)$ FLOPs. With KV caching, previous Keys and Values are kept in VRAM, so each new step only computes projections for the single new token ($\mathcal{O}(1)$ step cost, $\mathcal{O}(N)$ total).
Answer: An RTX 3050 has massive parallel compute capacity. At batch size 1 and short sequence lengths (32–256 tokens) on a 124M parameter model, the GPU is severely under-utilized and dominated by fixed Python dispatch and CUDA kernel launch overheads. Because the un-cached baseline was already running quickly on GPU, removing FLOPs yielded ~3.2x total wall-clock speedup. On CPU, which is purely compute-bound, the reduction in FLOPs translated directly into a 9.8x wall-clock speedup.
Answer: When prefilling a suffix chunk of length $T$ on top of an already-cached prefix of length $P$ (where $1 < T < T_{ctx}$), the standard code set `is_causal = (T == T_ctx)`. Because $T < T_{ctx}$, this evaluated to `False`, causing PyTorch's SDPA to apply no causal mask at all. Suffix tokens could silently attend to future suffix tokens. I fixed this with a unified formula: row $i$ of queries attends to columns $0 \dots P+i$ where $P = T_{ctx} - T$, handling full prefill, single-token decode, and chunked prefill uniformly.
Answer: Standard attention computes $S = Q K^T$ and writes the entire $N \times N$ score matrix to global HBM. For $N=4096$, that matrix requires gigabytes of memory and multiple read/write passes. FlashAttention loads small tiles ($B_r \times d$ and $B_c \times d$) into fast on-chip SRAM. It uses the online softmax algorithm to maintain running row maximums ($m$) and row sums ($l$) of size $N$, incrementally updating the output accumulator. The $N \times N$ matrix is never materialized in HBM, reducing auxiliary global memory from $\mathcal{O}(N^2)$ to $2N$ floats.
Answer: The radix tree splits nodes when prompts share only a partial token prefix. During depth-first traversal, we forward the shared prefix chunk through nanoGPT, snapshot the per-block KV cache tensors, and pass them to child branches. When multiple user prompts share a system prompt, the system prompt is evaluated once rather than re-prefilled for every prompt, saving prefill latency.