Skip to content

hrx: prefill attention cost grows 0.0331 ms per KV token — find where the slope comes from #1989

Closed

Description

@bong-water-water-bong

Follow-up to #1517, which is closed as measured.

#1517 named two levers for the prefill FLASH_ATTN_EXT kernel. Both were measured small on gfx1151 (pi-i679, 11-09; summary by cl-hrxkern on #1517): the rescale lever is below noise (ceiling about 1.5 % of the attention dispatch), and the LDS staging of the score tile is at most 5 % of the attention dispatch, about 3 % of prefill.

What remains unexplained is the measured slope of 0.0331 ms per KV token in the attention dispatch. This issue is for attributing that slope (per-dispatch timing against KV length, then the kernel stage that scales with it) and fixing what it points at.

Acceptance: a measured attribution of the slope on gfx1151, and either a kernel change with before/after numbers or a measured reason it cannot be reduced.

Activity

  1. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern (owner-assigned) — first attribution: the slope is the flash-attention kernel's own per-key cost, and about 40 % of it is a rate drop that sets in at long key counts. One clean run; the follow-up that would say why was void.

    Method

    FLASH_ATTN_EXT alone on HRX0, in the model's layout (token-major Q, K, V permuted as llama.cpp builds them), Qwen3-4B's geometry (32 query heads, 8 KV heads, head size 128), planned on ggml_flash_attention_f32_f16_wmma — the kernel the model's prefill uses. Nine computes per point, first two dropped, minimum reported. One gpu-hold ticket, power mode performance. This is a local probe, not in any tree yet.

    Result (512 query tokens, one layer)

    keys ms (min) µs per key from the previous row TFLOPS
    512 0.322 13.3
    1,024 0.512 0.37 16.8
    2,048 1.066 0.54 16.1
    4,096 2.806 0.85 12.3
    8,192 6.304 0.85 10.9

    At 256 query tokens the same drop appears one step later (15.1 TFLOPS at 4,096 keys, 11.7 at 8,192).

    What it says about the 0.0331 ms

    • The model-level slope is 0.0331 ms per KV token per 512-token graph over 36 layers, i.e. 0.92 µs per key per layer. The op alone measures 0.85 µs per key per layer above about 2,048 keys. So roughly 92 % of the slope is this one dispatch; nothing else in the graph needs explaining.
    • At the kernel's best measured rate (about 16 TFLOPS, up to 2,048 keys) the same arithmetic costs 0.52 µs per key per layer. That part is the work itself: 32 heads × 512 queries × 256 multiply-adds per key.
    • The remaining 0.33 µs per key, about 40 % of the slope, is the kernel running at 11–12 TFLOPS instead of 16 once the key count is large. That is the reducible part, and it is worth up to about 1.5× on the attention term at long context.

    What I do not know yet

    Why the rate drops. It depends on both the query count and the key count, which fits "the K/V stream a row of workgroups shares no longer stays cached" (per KV head, K + V is 1 MB at 2,048 keys and 4.2 MB at 8,192) better than a fixed code-path switch at a key count. That is a hypothesis.

    I ran the experiment that would separate the two (same arithmetic per key with head size 64 × 16 KV heads, which halves the per-head stream, on a finer key grid). That run is void: the same point (512 queries, 2,048 keys) that took 1.07 ms in the table above took 2.48 ms and then 4.41 ms within one ticket, and rates jumped between 3 and 12 TFLOPS non-monotonically. The box was at load 20 and the device is shared with standing servers; sub-10 ms dispatches are too short to survive that. I am not reading anything from it.

    Next

    1. Repeat the head-size comparison with longer measurements per point (many computes inside one timing window, alternating the two geometries) so a shared box cannot reorder them.
    2. If the stream-size reading holds, the lever is the order in which the kernel walks keys against queries (so a block of keys is reused by more query rows while it is resident). If it does not, look for the path difference above 2,048 keys.
    3. Put the probe in the tree as a tool beside tools/fa_ratio.py, so the next row is one command.
  2. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — second run, with a design that survives a shared box, and it corrects my first comment: up to 8,192 keys the slope is essentially the arithmetic. The rate drop is real but starts later, and it tracks how much K/V the dispatch has to read.

    Method change

    Each point is now timed over a 150 ms window of back-to-back computes, and three geometries are interleaved across six rounds, so load on the box hits all of them alike. Same op, same layout, same kernel (ggml_flash_attention_f32_f16_wmma). One gpu-hold ticket, power mode performance, load average 18 at the start. Minimum of six rounds shown; the medians are within 3–8 % of it.

    Result, 512 query tokens, one layer (TFLOPS; ms in brackets)

    keys model geometry: head 128, 8 KV heads, 32 query heads same arithmetic, no sharing: head 128, 32 KV heads, 32 query heads head 64, 16 KV heads, 64 query heads
    1,024 11.6 (0.740) 8.7 (0.991) 9.2 (0.930)
    2,048 12.5 (1.374) 8.6 (2.001) 9.2 (1.864)
    3,072 12.4 (2.072) 9.1 (2.823) 9.2 (2.804)
    4,096 12.2 (2.810) 7.6 (4.531) 8.3 (4.167)
    6,144 11.8 (4.357) 7.3 (7.028) 6.6 (7.858)
    8,192 11.4 (6.022) 6.8 (10.146) 6.7 (10.289)
    16,384 8.1 (16.912) 6.4 (21.468) 6.1 (22.555)

    What I am correcting

    In the first comment I said the kernel runs at about 16 TFLOPS up to 2,048 keys and that about 40 % of the slope is a drop from that rate. That does not reproduce. Under sustained, interleaved timing the low-key points sit at 11.6–12.5, not 16, and the rate at 8,192 keys is only 9 % below the best point. The 16 came from short bursts of nine computes; I should not have built a fraction on it.

    What the data supports

    1. For the model's geometry, the per-key cost is flat from 2,048 to 8,192 keys: 0.70–0.78 µs per key per layer, against 0.67 µs for the arithmetic at this run's best rate. The model-level 0.92 µs (fit over 0–7,680 keys) is therefore almost all arithmetic at the device's sustained rate; I can attribute at most about 10 % of it to a rate change in that range.
    2. Beyond 8,192 keys the cost per key nearly doubles (1.33 µs per key from 8,192 to 16,384; 8.1 TFLOPS). That is the range hrx: long-context decode 9.70 tok/s at 18.8k ctx (prefill 74-93) vs 31.15 / 459 on a gfx1151 fork — same GGUF, same hour, short-prompt parity 28.6 vs 28.9 #679 lives in.
    3. The rate follows how much K/V the dispatch reads, not the arithmetic. With the same multiply-adds per key but four times the K/V bytes (32 KV heads instead of 8, so no query head shares a stream), the kernel is 30–40 % slower at every key count. With half-size heads and twice as many KV heads the drop arrives at 4,096–6,144 keys instead of after 8,192.

    So the reducible part of the slope is K/V memory traffic at long key counts, not something in the per-block bookkeeping. That is consistent with #1517's two levers measuring small.

    Limits

    • Absolute rates are from a shared box at load 18; the comparison between columns is what the interleaving protects, not the absolute TFLOPS.
    • I have not measured cache or memory counters, so "memory traffic" is inferred from the geometry comparison, not observed directly.
    • One layer's op in isolation; in the model 36 of these run per graph with other dispatches between them.
    • Nothing between 8,192 and 16,384 keys, so I do not know where in that range the drop starts.

    Next

    1. Fill in 8,192–16,384 and go to 32,768 for the model geometry, to place the knee and see whether the cost keeps rising.
    2. Then the lever that fits the evidence: how many times the K/V stream is fetched per dispatch. The candidates are the workgroup order (so query tiles sharing a KV head run adjacent in time across all four of its query heads) and a blocked walk over keys. Each gets a before/after on this same probe.
    3. Land the probe as a tool so these rows are one command.
  3. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — the drop at long key counts is not a smooth memory limit. It is a slow regime that specific key counts fall into and their neighbours do not, at the op level and in the model. That is a cheaper kind of problem.

    All on HRX0 under gpu-hold, same probe as before (150–200 ms windows, 5–6 interleaved rounds), model geometry (head 128, 8 KV heads, 32 query heads).

    1. With few query tokens there is no drop at all

    query tokens 16,384 keys 20,480 24,576 28,672 32,768
    64 9.8 11.1 11.2 11.1 11.2
    128 11.3 11.2 11.2 11.2 10.8
    256 8.1 10.8 10.5 10.1 8.1
    384 8.1 10.5 10.1 8.5 7.9
    512 8.2 7.6 9.7 5.8 8.0

    (TFLOPS, minimum of five rounds; medians within 0.3.) A memory-bandwidth limit would cost the same per multiply-add at 64 query tokens as at 512. It does not.

    2. One step of 256 keys switches it on and off

    query tokens 16,128 16,384 16,640 32,512 32,768 33,024
    256 11.9 8.2 11.9 11.6 8.0 10.8
    512 11.4 8.3 11.5 10.4 8.0 5.5

    Exactly at the power of two the kernel loses about 30 %; 256 keys either side it is back. At 512 query tokens several other key counts are slow as well (18,432: 7.5; 20,480: 7.8; 28,672: 5.8; 33,024: 5.5).

    3. It is not K against V

    Allocating 4 KiB, or 1 MiB + 4 KiB, of padding between the K and V buffers changes nothing: 8.2 at 16,384 and 32,768 with or without it, two alternating rounds each.

    4. The model shows the same two regimes

    llama-bench -p 24576 -n 0 -b 512 -ub 512 on Qwen3-4B Q4_K_M with GGML_HRX_HOST_GAP_VERBOSE=1, three passes of 48 graphs, 656 tok/s overall. Per-graph replay.wait (ms), a graph and its two neighbours:

    KV before the graph pass 1 pass 2 pass 3
    14,336 829 893 961
    14,848 651 722 822
    15,360 832 865 1,026
    15,872 711 713 784
    16,384 867 986 1,045
    23,040 1,368 1,469 1,409
    23,552 996 1,111 1,079

    Three graphs in the long range are 15–27 % faster than both neighbours in all three passes. Over 0–24k keys the fitted slope is 0.0522 ms per KV token, against the 0.0331 this issue was filed with (fitted over 0–7.7k).

    Reading

    • Up to about 8k keys the slope is the arithmetic (previous comment, unchanged).
    • Above that, most 512-token graphs run in a slow regime and a few do not. If every long-context graph ran at the rate of the fast ones, those graphs would take 15–27 % less time. That is the size of the lever, measured in the model, not projected.
    • The trigger depends on the key count to within 256 keys and on the query count, and not on where K and V sit relative to each other. The one input whose row stride is the key count is the mask (one row per query token, 2 × keys bytes apart), so rows that land on the same cache sets is my working explanation. It is not proven: I have eliminated K/V placement, not demonstrated the mask.

    Not established

    • The mapping between "KV before the graph" in the model and the op's key count (padding, the compact-mask path) — I have not lined the fast model graphs up with the fast op points, and they do not obviously coincide.
    • Pass-to-pass noise in the model run is about ±10 %; the three fast graphs stand out beyond that, smaller effects would not.
    • No cache counters.

    Next

    1. The direct test of the mask reading, in the kernel: stage the mask tile once per key block instead of reading 16 strided rows, and rerun tables 1 and 2. If the slow points disappear, that is the fix and its before/after.
    2. If they do not, the same tables with the dispatch's query-tile count varied, to see whether it is workgroup phasing rather than a stride.
    3. Line up the model's key count with the op's, so the model check for the fix is a prediction rather than a search.
  4. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — the slow regime is located: it is the transposed copy of V that the dispatcher makes for 256+ query tokens, not the attention kernel's arithmetic and not the mask. A first fix removes it at 256 query tokens; at 512 it is mixed, so nothing is up for review yet.

    What was ruled out, by measurement

    • The mask. With the kernel's mask reads replaced by constants (local hack, my probe's mask is all zeros), every slow point is still there: 8.4 TFLOPS at 16,384 keys, 8.0 at 32,768. My "mask rows alias" explanation from the previous comment is wrong.

    • Not transposing at all. A local switch that keeps V row-major (A = today, B = row-major, alternated, ms per dispatch):

      query tokens keys A B B / A
      256 16,384 8.53 5.89 0.69
      256 32,768 17.13 12.69 0.74
      512 8,192 6.03 6.72 1.12
      512 24,576 20.80 45.53 2.19
      512 32,768 33.91 83.91 2.47

      At 512 query tokens the row-major path is up to 2.5× slower, so the transpose earns its place; the problem is how the transposed buffer is laid out.

    Where it is

    For query tokens >= 256 and keys >= 512, prepare_flash_attention_value() runs ggml_copy_transpose_f16 over the whole V of the layer (keys × 1,024 values) before every attention dispatch, and the attention kernel then walks that buffer across channels. Its 1,024 rows sit exactly 2 × keys bytes apart. Every slow point so far is a key count that makes that distance a multiple of 4,096 bytes; 256 keys either side, it is not.

    First fix, and its result

    Local branch (not pushed): the transposed buffer gets a pitch of keys + 32 when keys is a multiple of 64, written by the transpose kernel and read by the attention kernel through two new config values. test-backend-ops -o FLASH_ATTN_EXT -b HRX0: 388/388 with the change.

    A = packed pitch (today), B = spread pitch, alternated twice, minimum ms per dispatch:

    query tokens keys A B B / A
    256 16,128 5.66 5.61 0.99
    256 16,384 8.34 6.10 0.73
    256 16,640 5.78 5.74 0.99
    256 28,672 11.55 10.64 0.92
    256 32,768 16.55 12.89 0.78
    512 12,288 11.47 10.79 0.94
    512 16,128 11.62 13.86 1.19
    512 16,384 16.31 16.75 1.03
    512 20,480 22.31 20.40 0.91
    512 24,576 20.42 28.19 1.38
    512 28,672 40.39 31.01 0.77
    512 32,768 33.46 43.86 1.31
    • 256 query tokens: fixed. The two power-of-two points come down to the neighbours' level and nothing else moves by more than 8 %.
    • 512 query tokens: not fixed. Some points improve, others that were fast get slower. A pitch that is an odd multiple of 64 bytes is not the right rule there; 512 queries is the common batch size, so this is not shippable as it stands.

    What I know and do not

    • Known: the cost lives in the layout of the transposed V; the mask and K/V placement are out; the pitch is a working lever at 256 queries.
    • Not known: the rule for 512 queries. The packed pitch is fast there at 16,128 and 16,640 keys and slow at 16,384, 18,432, 20,480, 28,672 and 32,768, which a single stride-modulo rule does not explain. Two dispatches may be interacting (the query-chunked launch), or the transpose's own write pattern matters as much as the read.
    • The second B round of the last table ran under a load spike (medians roughly double the minimums); the minimums agree with round one.

    Next

    1. Sweep the pitch itself at 512 query tokens (a handful of pads at four key counts), timing the transpose and the attention dispatch separately, to find which of the two the layout hurts.
    2. With a rule that holds at both 256 and 512, the model check: the 24k-token prefill from the previous comment, before and after.
  5. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — a fix is up: 1bit-MONSTER/llama.cpp#289 at 2cd6c63. Qwen3-4B prefill at 24,576 tokens goes from 723 / 755 tok/s to 937 / 924 tok/s (about +26 %), 8,192 tokens from 1,545 / 1,600 to 1,766 / 1,768, and 512 and 2,048 tokens do not move.

    The pitch sweep I planned settled the 512-query case differently than I expected: no pitch helps there, but running 512 query tokens as two 256-token launches over the one transposed V does, and with the spread pitch the op then costs a flat 0.65–0.77 µs per key from 4,096 to 32,768 keys (before: 0.72–1.41). So the change is two things: the spread pitch (fixes the power-of-two key counts) and 256-token launches from 4,096 keys up.

    Against this issue's acceptance: the attribution is measured (previous comments; the slow regime is in the transposed-V step, not the kernel's arithmetic), and there is a change with before/after numbers. What stays open until the pin moves: the model rows at the engine pin, and the explanation of why 256-token launches are faster, which I have measured but not explained. Limits are listed in the PR.

  6. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — pin warning. llama.cpp#289 merged at its first commit (139ccd741 on 1bit/hrx-vulkan-patched), which has a defect I found after it was reviewed: the attention kernel is recompiled for every distinct key count, so a real long-prompt run is slower cold (53 s against 33 s for a 9,230-token prompt in one loaded-box measurement) even though llama-bench shows the gain. The fix is llama.cpp#291. Please do not move the engine pin to any fork commit at or after 139ccd741 until #291 is in. The current pin (50d28600a) is not affected.

  7. bong-water-water-bong commented on Nov 10, 2026

    @bong-water-water-bong
    CollaboratorAuthor

    cl-hrxkern — pin warning lifted. llama.cpp#291 merged; the fork tip 2293f95ea has #289 with its fix, and is safe to pin. Avoid only 139ccd741 and cf5febf04 themselves.

    Evidence at the exact tree of 2293f95ea (my build of db20acb has the identical tree, fbd157400…; gfx1151, gpu-hold), for whichever pin bump carries Fixes #1989:

    • test-hrx-fa-transposed-value 8/8, test-backend-ops -o FLASH_ATTN_EXT -b HRX0 388/388.
    • Qwen3-4B, 9,230-token prompt, cold, fresh process: 8.80 s with the old layout, 8.85 s with the new; greedy text identical.
    • Qwen3-4B llama-bench -p 24576 -b 512 -ub 512 -r 3, tok/s per repetition: new 791 / 847 / 871 and 698 / 995 / 1,001; old layout 385 / 500 / 557 in the same ticket on a busy box. The quieter earlier ticket (same code, base 50d28600a): old 701 / 822 / 822 and 711 / 813 / 815, new 860 / 980 / 1,021, 866 / 1,067 / 1,074 and 856 / 1,067 / 1,062.

    Against the acceptance: the slope is attributed (arithmetic up to about 8k keys; above that a slow regime in the transposed-V step of the dispatch), and there is a change with before/after (about +28 % warm prefill at 24k tokens, no change at 512 and 2,048). cl-hrxnan has the next pin bump; I asked on #1962 that it carry Fixes #1989. If no bump is open by my next pass I will open one.

    Not explained, and stated in the PRs: why 256-token launches beat one 512-token launch at long key counts.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions