Series · 4 parts
Complexity Theory Meets AI
Token costs, quadratic attention, generate-and-verify and self-consistency, each explained with the algorithms and complexity ideas every computer-science graduate already knows.
- Why AI Tokens Are So Expensive — and What Actually Makes Them Cheaper
Why LLM inference costs what it does: compute-heavy prefill, bandwidth-bound decode, KV-cache pressure, and where prompt caching actually helps.
15 Jul 2026 · 14 min read
- The Quadratic Wall: The Algorithmic Race to Beat O(n²) Attention
Attention is O(n²) in sequence length. FlashAttention cuts the memory it moves and materialises; sparse, linear, and state-space models like Mamba cut the arithmetic exponent itself — one algorithms story about beating the quadratic.
22 Jul 2026 · 13 min read
- Generate-and-Verify: What P vs NP Teaches Us About AI Reasoning
The NP asymmetry — hard to find, easy to check — is the same asymmetry behind test-time compute, verifiers, and agent loops. Generation is the search; verification is the cheap certificate.
29 Jul 2026 · 11 min read
- Self-Consistency Is Just Probability Amplification
Self-consistency — sample several answers, take the majority vote — is the probability-amplification trick from randomized algorithms: if each sample beats a coin flip and errors are independent, a few votes drive error down fast.
5 Aug 2026 · 11 min read