How do you calculate the FLOPs of a matrix multiplication?

For an (m×k) matrix multiplied by a (k×n) matrix, the standard convention counts each multiply and its accumulating add as 2 FLOPs, giving a total of 2×m×n×k FLOPs. Kaplan et al.’s "Scaling Laws for Neural Language Models" extends this to a full transformer: processing one token costs approximately 2N FLOPs forward (N being non-embedding parameters), and a full training step (forward plus backward) costs approximately 6N FLOPs per token.

What is GEMM and why does GPU tiling matter for it?

GEMM (General Matrix Multiply) is the standard name for the core dense matrix multiplication operation GPU hardware is built to accelerate. NVIDIA’s CUTLASS documentation describes high-performance GEMM kernels as decomposing the multiplication into tiles staged through fast on-chip shared memory and registers, so data loaded once gets reused across many output calculations instead of being re-fetched from slower memory repeatedly.

Did DeepMind actually find a faster way to do matrix multiplication?

Yes. DeepMind’s AlphaTensor, described in Fawzi et al.’s 2022 Nature paper, used reinforcement learning to discover an algorithm multiplying two 4×4 matrices using 47 scalar multiplications, improving on the 49 multiplications from applying Strassen’s algorithm recursively — though this specific 47-multiplication result applies to matrices over GF(2) (arithmetic modulo 2), not general real-valued matrices.

Does batching multiple requests together really improve LLM serving throughput?

Yes, substantially. Kwon et al.’s vLLM paper on PagedAttention reports 2-4x higher serving throughput compared to prior systems like FasterTransformer and Orca, at the same latency, achieved largely through more effective request batching and memory management.

← Back to the Intermediate level

AI & ML — ADVANCED

Matrix Multiplication at Scale: FLOPs, GEMM, and Faster Algorithms

The Intermediate level covered how a transformer layer and self-attention are built from matrix multiplication, and why GPUs parallelize it well. This level goes further: real FLOP-counting math for estimating a model’s training compute, how GPU GEMM kernels actually get their speed, a genuine algorithmic advance in matrix multiplication itself from DeepMind, and a real, cited throughput number for batching in production LLM serving.

The Quick Answer

An (m×k)·(k×n) matrix multiply costs 2×m×n×k FLOPs, by the standard convention of counting each multiply-add pair as 2 FLOPs. Kaplan et al.’s scaling laws paper extends that to whole transformers: roughly 2N FLOPs per token for a forward pass and roughly 6N FLOPs per token for a full training step, for a model with N non-embedding parameters — a formula that is only this clean because nearly all of that compute really is matrix multiplication. On the hardware side, GPU GEMM kernels get their speed by tilingthe multiply into blocks that reuse data from fast on-chip memory, and DeepMind’s AlphaTensor showed reinforcement learning can discover genuinely new, more efficient matrix multiplication algorithms — with real, verified but appropriately scoped results. And in production, batching requests together for serving delivers real, measured throughput gains, not just a theoretical benefit.

Counting FLOPs: From One Matmul to a Whole Model

FLOP-counting starts from the single matrix multiply: an (m×k)·(k×n) multiply needs m×n×k multiplications, and (with the standard convention of counting a multiply and its accumulating add together as 2 FLOPs) that’s a total of 2×m×n×k FLOPs. Kaplan et al. showed this scales up cleanly to an entire transformer, because a transformer’s compute really is dominated by matrix multiplies: processing one token costs approximately 2N FLOPs forward, and approximately 6N FLOPs for a full forward-plus- backward training step, where N is the model’s non-embedding parameter count. Try both calculations yourself:

GEMM and Tiling: How GPUs Get Their Speed

GEMM(General Matrix Multiply) is the standard name for the dense matrix multiplication operation GPU hardware and libraries like NVIDIA’s CUTLASS are built around. A naive implementation re-fetches data from slower memory constantly. NVIDIA’s CUTLASS documentation describes the real technique high-performance GEMM kernels use instead: decomposing the multiply into tiles that are loaded once into fast, on-chip shared memory and registers, then reused across many output calculations before being replaced. Try adjusting tile size below to see the effect on memory fetches:

Source: NVIDIA CUTLASS documentation, “Efficient GEMM in CUDA”

Can Matrix Multiplication Itself Be Made Faster?

Everything above assumes the standard, textbook way of multiplying matrices — but that isn’t actually the only way to do it. Multiplying two n×n matrices naively takes roughly n³ multiplications. Strassen’s algorithm, from 1969, found a way to cut that down using a clever recursive trick. In 2022, DeepMind’s AlphaTensor — trained with reinforcement learning to search for matrix multiplication algorithms rather than to directly perform the multiplication — discovered an algorithm using only 47 scalar multiplications for 4×4 matrices, an improvement over the 49 that Strassen’s approach gives when applied recursively. That specific 47-multiplication result is for matrices over GF(2), not general real-number matrices used in most neural network math — an important scope to keep straight rather than overclaiming. Compare the three approaches:

Batching’s Real Effect on Serving Throughput

The Intermediate level showed batching’s operation-count math. In production, that translates into a real, measured throughput difference — not just a theoretical efficiency argument. Kwon et al.’s vLLM paper on PagedAttention reports 2-4x higher serving throughput compared to prior systems (FasterTransformer and Orca), at the same latency, driven largely by more effective request batching combined with better memory management for the attention mechanism’s KV cache. Try the illustrative curve below, calibrated to land inside that real reported range:

Multi-Head Attention as Batched Matrix Multiplies

One more place batching shows up: inside a single attention layer. Multi-head attention runs several heads, each with its own Q/K/V weight matrices, on the same input. Because every head performs the exact same shape of computation and differs only in its weight values, real implementations don’t loop over heads one at a time — they batch all heads into one larger matrix multiply, the identical principle covered above applied at a smaller scale, inside a single layer instead of across a queue of requests:

Fun Fact

DeepMind trained AlphaTensor by framing matrix multiplication as a single-player game — the goal was to find the shortest correct sequence of scalar multiplications and additions that reproduces matrix multiplication exactly, discovered through the same style of reinforcement learning search used in game-playing systems, not through symbolic mathematical derivation.

Source: Fawzi et al., “Discovering faster matrix multiplication algorithms with reinforcement learning,” Nature 610 (2022)

Test Yourself

Using the convention that a multiply-add counts as 2 FLOPs, how many FLOPs does multiplying a (100×200) matrix by a (200×50) matrix take?

According to Kaplan et al.’s scaling laws paper, what is the approximate FLOP cost of a full training step (forward + backward) per token for a transformer with N non-embedding parameters?

What is the key idea behind tiling/blocking in a high-performance GPU GEMM kernel, per NVIDIA’s CUTLASS documentation?

What did DeepMind’s AlphaTensor paper (Fawzi et al., Nature 2022) actually demonstrate?

Per the vLLM (PagedAttention) paper, roughly how much did effective request batching and memory management improve serving throughput compared to prior systems at the same latency?

Brainstorm

No single correct answer here — think it through, then expand each one to see one way to reason about it.

The 6N FLOPs-per-token training estimate ignores attention’s cost, which scales with sequence length squared rather than staying proportional to parameter count. When would you expect that omission to matter most, and when would it barely matter?

AlphaTensor’s 47-multiplication result is specific to GF(2) arithmetic, not real numbers. Why might a result that doesn’t directly apply to standard neural network math still be a meaningful research contribution to this field?

GPU GEMM kernels get their speed partly from tiling matrix multiplies to fit fast on-chip memory. What do you think happens to a kernel’s performance if the chosen tile size is too large for a specific GPU’s on-chip memory capacity, versus too small?

The vLLM paper’s throughput gains come from a mix of batching and smarter memory management (PagedAttention) rather than batching alone. Why might it be misleading to attribute the whole 2-4x figure to matrix multiplication batching by itself?

Multi-head attention runs several heads with identical computation shapes but different weights, which lets real implementations batch them into one larger matrix multiply. Can you think of another place in a transformer where a similar "same shape, different weights" pattern might allow the same batching trick?