Attention Mechanisms & LLM Inference Optimization

Course Project | CS 794: Systems for Machine Learning | Prof. Mythili Vutukuru

A comprehensive technical reference and interview preparation hub for Attention Mechanisms & LLM Inference Optimization. This project explores key systems optimizations for autoregressive Transformer inference, implemented and benchmarked across PyTorch (nanoGPT) and custom CUDA C++ kernels:


📚 Speeches & Documentation Modules

Page Type Target Duration Core Focus & Architectural Concepts
intro.html Elevator Pitch 1–2 mins High-level executive pitch covering KV caching, radix-tree prefix sharing, and CUDA FlashAttention with quick-fire interview follow-up Q&A.
detailed.html Architecture Speech 4–5 mins Full end-to-end walkthrough covering the autoregressive decoding bottleneck, KV cache lifecycle, chunked prefill masking bugs, radix-tree DFS caching, CUDA FlashAttention tiling, and empirical Roofline analysis.
topic_01_kv_caching_and_decoding_dynamics.html Deep Dive 2–3 mins Why un-cached decoding incurs $\mathcal{O}(T^2)$ cumulative compute, how `cache_k`/`cache_v` decoupling enables $\mathcal{O}(1)$ step latency, tensor shapes, and transient memory doubling in naive `torch.cat`.
topic_02_causal_masking_and_chunked_prefill.html Deep Dive 2–3 mins Causal self-attention semantics across prefill, single-token decode, and chunked prefill ($1 < T < T_{ctx}$); fixing the non-flash broadcast crash and the SDPA silent mask corruption.
topic_03_radix_tree_shared_prefix_cache.html Deep Dive 2–3 mins Radix-tree construction with node splitting, DFS prefix traversal, per-block KV cache snapshotting (`get_kv_cache`/`set_kv_cache`), and trading memory for prefill compute.
topic_04_flash_attention_cuda_and_online_softmax.html Deep Dive 3–4 mins The memory wall in standard attention, CUDA shared memory tiling ($B_r \times B_c$), online softmax running statistics ($m$, $l$), output accumulator rescaling, and barrier synchronization.
topic_05_benchmarks_and_hardware_tradeoffs.html Deep Dive 2–3 mins Benchmark methodology, wall-clock timing vs peak memory, why GPU speedups are smaller at small batch sizes (kernel launch overhead), and Roofline model (compute-bound prefill vs memory-bound decode).
topic_06_production_serving_and_paged_attention.html System Extensions 2–3 mins From nanoGPT to production inference engines: PagedAttention (vLLM) block tables, RadixAttention (SGLang) LRU eviction, Multi-Query/Grouped-Query Attention (MQA/GQA), and KV cache quantization.
pytorch_knowledge.html Interview Q&A 3–4 mins PyTorch fundamentals and KV caching internals: 4D tensor shapes `[B, nh, T, hs]`, `view` vs `transpose` strides and contiguity, caching lifecycle in `model.py`, causal masking across phases, CPU vs CUDA memory mechanics, `torch.no_grad()`, and allocator overheads.

🏗️ System Architecture: The Two Optimization Pillars

Pillar 1: Model-Level Autoregressive Optimizations (nanoGPT)
Pillar 2: Hardware-Level Kernel Optimization (Custom CUDA FlashAttention)

📊 Key Benchmark Results Summary

1. KV Caching Speedup (nanoGPT, 123.7M Params, Batch Size 1)

Device Prompt Length Generated Tokens Baseline (No Cache) KV Cached Speedup Peak Memory Note
CPU 32 32 1059.7 ms 435.1 ms 2.44x 985.6 MB RSS (dominated by weights)
CPU 128 64 5581.5 ms 905.3 ms 6.17x 985.7 MB RSS
CPU 256 64 9922.3 ms 1009.4 ms 9.83x 985.7 MB RSS
CUDA (RTX 3050) 32 32 197.2 ms 174.4 ms 1.13x 489.9 MB alloc
CUDA (RTX 3050) 128 64 669.0 ms 325.3 ms 2.06x 513.3 MB alloc
CUDA (RTX 3050) 256 64 1080.8 ms 340.4 ms 3.18x 521.0 MB alloc
CUDA (Decode Step) Context 1024 Per Decode Step Full Recompute ($O(T)$) Incremental ($O(1)$) Up to 29.1x Per-token latency decoupling

2. Radix-Tree Shared-Prefix Reuse vs Independent Processing (8 Prompts, Suffix=16, Output=4)

Device Shared Prefix Length Independent (Redundant) Radix-Shared (Reused) Speedup Peak GPU Allocated
CPU 32 572.5 ms 494.2 ms 1.16x 985.6 MB RSS
CPU 128 1032.7 ms 576.4 ms 1.79x 985.7 MB RSS
CPU 256 1524.5 ms 752.3 ms 2.03x 985.8 MB RSS
CUDA (RTX 3050) 32 181.1 ms 167.5 ms 1.08x 510.5 MB alloc
CUDA (RTX 3050) 128 207.5 ms 175.8 ms 1.18x 521.7 MB alloc
CUDA (RTX 3050) 256 257.4 ms 206.3 ms 1.25x 544.2 MB alloc

3. Custom CUDA FlashAttention vs Standard Attention (RTX 3050, Batch=8)

Sequence Length ($N$) Standard Attention (HBM Matrix) FlashAttention (SRAM Tiling) Speedup Standard Memory Flash Memory
512 11.60 ms 6.19 ms 1.87x 321.4 MB alloc 90.1 MB alloc
1024 37.43 ms 16.33 ms 2.29x 946.1 MB alloc 162.1 MB alloc
2048 141.33 ms 51.12 ms 2.76x 3349.1 MB alloc 306.1 MB alloc
4096 CUDA OOM (Tried 6.0 GB) 180.87 ms Scales to completion Exceeds 6 GB VRAM 594.1 MB alloc

⚖️ Core Engineering Trade-Offs

Optimization Primary Benefit Hardware Cost / Trade-off Systems Resolution
KV Caching Eliminates $O(T^2)$ redundant compute; decouples decode step latency from past history. Trades memory for compute: $2 \times L \times H \times d \times T \times \text{bytes}$ per sequence. Transient allocation churn if using `torch.cat`. Pre-allocated static ring buffers or PagedAttention (vLLM) block tables.
Radix-Tree Shared Prefix Prefills common system prompts once across batched user queries; saves prefill FLOPs. Holds multiple active branch KV snapshots in VRAM simultaneously; increases peak memory (544 MB vs 496 MB). LRU cache eviction policy for branch nodes (RadixAttention / SGLang).
CUDA FlashAttention Eliminates $O(N^2)$ global memory score matrix; prevents OOM at long context; reduces HBM memory traffic. Higher arithmetic intensity; requires careful thread block synchronization and shared memory budget management. SRAM block tiling ($B_r=32, B_c=32$) and online numerical normalization.