What is adaptive vector-quantized attention (AVQ-Attention)?

AVQ-Attention makes transformer attention cheaper by representing the keys with a small codebook of M codewords instead of comparing every query against all N keys, which drops attention's cost from O(N²) to O(MN). The 'adaptive' part is what makes it distinct: during the forward pass it scores which codewords receive the most attention and swaps those coarse parent codewords for finer pre-learned child codewords, spending extra resolution only where attention mass concentrates. Importance scoring, child insertion, and contribution replacement are fused into a tiled FlashAttention-style computation with custom Triton kernels, so the refinement stays within the same O(MN) budget rather than adding a second attention pass (arXiv:2607.12789).

Why does standard attention scale as O(N²)?

To produce each output token, attention compares the query against every earlier key and takes a weighted sum of the values. With N tokens, that is N comparisons per query and N queries, so the work grows with N², the square of the sequence length. This is why doubling the context roughly quadruples the attention cost, and why long context is the main place transformers get slow and memory-hungry. AVQ attacks that term directly: by comparing against M codewords instead of N keys, it replaces the N² factor with M×N, which is far smaller when M is much less than N.

How is AVQ different from KV-cache quantization or sparse attention?

They all try to make attention cheaper, but in different ways. KV-cache quantization stores each key and value in fewer bits — it shrinks each entry but still keeps one comparison per key, so the O(N²) count is unchanged. Sparse or windowed attention drops keys outside a window or below a threshold, which lowers the count but risks discarding a key that later mattered. AVQ does not discard any keys the way sparse attention does, but it does approximate them: it represents groups of keys with shared codewords and compares against those, then refines the codewords where attention concentrates. So it is a summarize-and-refine approach rather than a shrink-each-entry or drop-some-keys approach.

AVQ-Attention refines codewords where attention mass concentrates — Adaptive vector-quantized attention

TL;DR

What is it: The AVQ-Attention paper introduces adaptive vector-quantized attention — a way to cut attention's cost by representing the keys with a small set of codewords instead of comparing a query against every key, and then adding finer codewords only where attention actually lands.
Why it’s needed: Attention is the part of a transformer that weighs every earlier token, and it scales as O(N²) in the sequence length — a major reason long context gets slow and expensive.
vs previous: Plain full attention spends the same effort on every key, even though attention concentrates on some keys far more than others; earlier fixes like uniform codebooks give every region the same coarse resolution. AVQ instead makes codebook capacity a dynamic resource, refining detail only where attention mass concentrates, so complexity drops to O(MN) without starving the keys that matter.

Jargon

AVQ-Attention: Adaptive Vector-Quantized Attention, the method in this paper. It summarizes the keys into codewords, scores which codewords receive the most attention, and splits those into finer codewords — spending resolution where it matters. Runs inside a tiled attention kernel at O(MN) cost.
Vector quantization (VQ): Replacing a large set of vectors with a small codebook of representative ones, and standing in each original with its nearest codeword. It is the same idea used to shrink a photo to a fixed color palette.
Codeword / codebook: A codeword is one representative vector; the codebook is the collection of them (here, M of them). The query attends to the M codewords instead of the N keys, so cost scales with M, not N.
Attention mass: How much of the softmax attention weight lands on a given key or region. In practice it is very uneven — attention concentrates on some keys far more than others, which is exactly what AVQ exploits.
Parent / child codewords: AVQ starts with coarse parent codewords, then, for the ones that catch heavy attention, swaps in pre-learned child codewords that describe that region more finely. Only the hot regions get refined.
FlashAttention: The tiled attention algorithm that computes attention block-by-block in fast on-chip memory instead of writing the whole N×N score matrix out. AVQ's scoring and refinement are fused into this same tiled loop.
Triton kernel: A GPU kernel written in Triton, a Python-like language for custom GPU code. The authors implement importance scoring, child insertion, and contribution replacement as custom Triton kernels so the extra work stays on-chip.

The news. On July 14, 2026, researchers posted the AVQ-Attention paper (arXiv:2607.12789), targeting attention's O(N²) bottleneck. The idea: represent the keys with M codewords, score which codewords receive important attention during the forward pass, and replace selected coarse (parent) codewords with finer pre-learned child codewords where attention concentrates. Importance scoring, child insertion, and contribution replacement are fused into a tiled FlashAttention-style computation with custom Triton kernels, so complexity stays at O(MN) while resolution adapts to the text. AVQ-Attention keeps attention's cost near-linear by describing the keys with a few codewords and adding fine detail only where attention lands. Read the paper →

Picture the query as a reader scanning a huge map, deciding where to look next. A standard transformer reads that map the exhaustive way: to score the next token it looks back over every earlier key, one at a time, and compares the query against each. Standard attention compares the query against every single key, so doubling the length roughly quadruples the work — the O(N²) wall that makes long context slow. In the map picture, it is like inspecting every street in the country at full detail before deciding where to go, even though you only care about one neighborhood.

Here is the catch the paper leans on: much of that effort is spent on places the reader barely looks at. Much of attention's quadratic work goes to keys that barely matter, because the attention weights tend to concentrate on some keys far more than others. A uniform, evenly-spaced summary of the keys wastes resolution on the quiet countryside and, at the same time, under-serves the crowded intersections the query actually cares about. The resolution is spread evenly; the attention is not.

AVQ-Attention fixes the mismatch by making detail a resource you spend, not a constant you fix in advance. It first summarizes the keys into a small set of M codewords — coarse map tiles that each stand in for a neighborhood of keys — so the query compares against M tiles instead of N keys, and cost drops from O(N²) to O(MN). Then it does the adaptive part: during the forward pass it scores which codewords are catching heavy attention and, for just those, swaps the coarse parent tile for finer pre-learned child tiles — zooming in only on the blocks the query is staring at. Because all of this — the scoring, the child insertion, the replacement — is fused into one tiled attention kernel, the summary and the refinement never materialize a full N×N matrix.

That tiled setting is not incidental — it is what keeps the trick cheap. AVQ implements importance scoring, child insertion, and contribution replacement inside a FlashAttention-style block loop written as custom Triton kernels, so the codeword bookkeeping rides along in the same on-chip pass that already streams keys in tiles. The refinement is not a second attention pass bolted on; it happens inside the one tiled loop, so it stays within the same O(MN) budget instead of adding a pass.

Where it earns its keep

The win shows up in how many comparisons the query makes. Suppose a sequence is N = 4,096 tokens. Full attention compares each query against all 4,096 keys, so the score matrix is about N² ≈ 16.8 million entries per head (illustrative). Summarize those keys into M = 256 codewords and the query instead compares against 256 tiles: about M × N ≈ 1.05 million entries — roughly 16× fewer comparisons (illustrative, since it tracks the paper's O(N²) → O(MN) claim, arXiv:2607.12789). The adaptive step spends that saved budget wisely: instead of holding all 256 codewords coarse, AVQ keeps the quiet regions coarse and splits the few codewords soaking up the most attention into finer children, so the tokens the model actually reads get sharp resolution while the ignored bulk stays cheap. Comparing against 256 codewords instead of 4,096 keys is about 16× fewer comparisons, and the extra detail lands only where the query was already looking.

Way to cut O(N²) attention	What it does to the keys	Cost vs length	Main tradeoff
Full attention	keeps every key, compares the query against all of them	~O(N²)	exact, but the quadratic cost dominates long context
Sparse / windowed attention	drops keys outside a window or below a threshold	~O(N·k), k keys kept	cheap, but a wrongly-dropped key is gone (~setup-dependent, illustrative)
Scalar KV quantization	stores each key/value in fewer bits, same count	~O(N²), smaller constant	less memory per key, but still one comparison per key (~setup-dependent, illustrative)
Adaptive VQ attention (AVQ)	summarizes keys into M codewords, refines only the hot ones	~O(MN), M codewords (arXiv:2607.12789)	no key is dropped, but each is approximated by a shared codeword; recall depends on the codebook, refined where attention lands

Because the change lives in how the keys are represented, not in what the model knows, it reframes the quadratic problem. AVQ turns attention's O(N²) bottleneck into a budgeting question — spend the codebook's resolution where the model is actually looking — instead of a bigger-matrix one. Full attention pays for every key equally; AVQ pays a flat O(MN) for the summary and then buys detail, a few codewords at a time, exactly where the attention mass already is.

Goes deeper in: LLM Internals → Attention → Computing Attention Scores

Continue in trackFlashAttention — how tiled attention stays on-chip

Related explainers

AVQ cuts attention's O(N²) cost by summarizing keys into adaptive codewords; these siblings attack the same attention-and-KV cost from other angles — quantizing the cache, skipping keys, or shrinking each entry.

vLLM v0.20 — TurboQuant 2-bit KV cache — quantizes the KV cache to 2 bits per value, where AVQ instead replaces keys with shared vector codewords
SubQ 1.1 — Subquadratic sparse attention — cuts O(N²) by skipping low-attention keys entirely, where AVQ keeps every key but summarizes it into a codeword
InfoKV — Entropy-aware KV compression — makes each KV entry smaller so there is less to carry; complementary to AVQ's shared codebook

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based