[Performance]: [GPU] PagedAttention with 2-4 query tokens per sequence (speculative decoding verify) is ~8x slower than single-token decode at the same context

OpenVINO Version

2026.4.0-22789-fcadb5bc340 (nightly wheel, releases/2026/4)

Operating System

Windows System

Device used for inference

iGPU

OpenVINO installation

PyPi

Programming Language

Python

Hardware Architecture

x86 (64 bits)

Model used

https://huggingface.co/OpenVINO/Qwen3.5-9B-int4-ov (openvino_language_model.xml + paged_attention_transformation)

Model quantization

Yes

Target Platform

Intel Core Ultra 7 255H, Arc 140T iGPU (driver 32.0.101.8991), 32 GB RAM

Performance issue description

Speculative decoding verifies k+1 tokens of one sequence in a single forward, so PagedAttentionExtension gets 2-4 query tokens for a sequence with a long past_len. On GPU that forward is much slower than single-token decode over the same KV cache, and the gap grows with context:

context	1 query token	3 query tokens
8k	78 ms	113 ms
32k	85 ms	166 ms
slope	0.3 ms / 1k tokens	2.2 ms / 1k tokens

(full model, u8 KV, one sequence, median of 20 forwards). 2 and 4 query tokens cost the same as 3, and the gap is larger with u8 KV than with f16, so it is not KV bandwidth. Isolating the 8 PagedAttentionExtension ops shows the same: 7.7 ms (1 token) vs 63 ms (2-4 tokens) at 32k.

Cause, as far as I can see in src/plugins/intel_gpu/src/graph/impls/ocl_v2/sdpa/paged_attention_opt.cpp: the GENERATE stage (pa_gqa_single_token: GQA read-once, 256-token partitions) is used only when the number of query tokens equals the number of sequences. Any sequence with ≥ 2 new tokens sends the forward to the MIXED stage (pa_multi_token / pa_sdpa_micro_mixed), which has neither, so every speculative-decoding step at long context pays a full unpartitioned scan.

Expected: a forward with a few query tokens per sequence should cost close to the single-token forward (same KV read). Suggestion: handle MIXED subsequences with a small number of new tokens (≤ 4-8) with the single-token kernels, query token i with key limit past_len + i + 1. Feeding the tokens as k single-token subsequences from the caller side is not a workaround: it only reaches pa_single_token (no GQA) and changes the outputs.

Related: #37880 (CM PA backend), #34644 (tree-mask speculative decoding on GPU, same MIXED path). Neither covers this case.

Step-by-step reproduction

1. paged_attention_transformation(model, False, False) on the model above; compile on GPU with KV_CACHE_PRECISION=u8, INFERENCE_PRECISION_HINT=f16.
2. Prefill one sequence to 8192 and 32768 tokens (1024-token chunks of random inputs_embeds).
3. Time a forward with T=1 and T=3 new tokens (past_lens=[L], subsequence_begins=[0,T], max_context_len=L+T, same block table).
4. T=1 grows ~0.3 ms per 1k tokens of context, T=3 ~2.2 ms per 1k. A standalone script (8 PA ops, no model) is available on request.

Issue submission checklist

• I'm reporting a performance issue. It's not a question.
• I checked the problem with the documentation, FAQ, open issues, Stack Overflow, etc., and have not found a solution.
• There is reproducer code and related data files such as images, videos, models, etc.