Setup & the O(n²) wall·9 min

Watch recompute crawl

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage watch-recompute-crawl --watch

Recompute re-attends over the entire growing sequence every step: at step k the sequence is n = prompt_len + k tokens long, and a causal attention pass scores every pair (i, j) with j ≤ i — that's n(n+1)/2 score entries. Watch the count climb quadratically. This is the enemy the rest of the course beats — and the baseline op-count we contrast against in the capstone.

The crawl (promptLen=4)

step 0   n=4    pairs = 4·5/2  = 10
step 1   n=5    pairs = 5·6/2  = 15
step 2   n=6    pairs = 6·7/2  = 21
step 3   n=7    pairs = 7·8/2  = 28
step 4   n=8    pairs = 8·9/2  = 36
                              ^ each step redoes all the earlier work, plus more

What to build

Your task

Implement runRecomputeProfile

Implement recomputeProfile(promptLen, nSteps) in src/kvcache.ts and wire it through runRecomputeProfile in tests/adapters.ts. Return the per-step count of causal score pairs the recompute path touches: for step k (0-indexed), n = promptLen + k and the count is n(n+1)/2. The result is a length-nSteps array. This is pure integer math — no weights, no forward pass.

tests/adapters.ts

export function runRecomputeProfile(promptLen: number, nSteps: number): number[] {
  // -> per-step causal-pair counts; step k uses n = promptLen + k, count = n(n+1)/2
}

Step k is the (k+1)-th token

Step k generates the token at the end of an n = promptLen + k length sequence, so the first step (k = 0) already attends over the whole prompt — count promptLen·(promptLen+1)/2, not 0 or 1. The most common mistake is starting n at promptLen + 1 (counting the about-to-be-added token before it exists). Use n = promptLen + k.

Why n(n+1)/2 and not n²

The causal mask zeroes the upper triangle, so a length-n pass scores only the lower triangle plus the diagonal: n(n+1)/2 pairs, which is ≈ n²/2. The quadratic growth is the point — the constant factor doesn't change the curve.

How it's graded

Your per-step counts are compared integer-exact against fixtures/recompute_profile.json — one wrong entry fails. No tolerance: this is pure arithmetic, so it either matches the closed form or it doesn't.

Run the grader The memory bill