Language models process million-token prompts up to 1.8 times faster

The authors accelerate input processing by grouping attention candidates by similarity, recovering more relevant entries than position-based grouping at nearly the same speed.

Independent

Jeongmin Brian Park · Wen-mei Hwu

Research Digest·3 November 2026·2 min read

Illustration: Language models process million-token prompts up to 1.8 times faster

In one line

Routing each query through a causal inverted-file index over indexer keys recovers more of the exhaustive top-k than block-based selection at higher prefill throughput.

Before you read this

Two ideas this paper builds on

sparse attentionSelectively attending to only the most relevant positions or tokens to reduce computational overhead.41 papers →kv cache compressionReducing the size of the key-value cache in transformers via selective retention, low-rank updates, or adaptive compression.59 papers →

Read it as

Long-context models read hundreds of thousands of tokens at once. keeps this affordable by having a small indexer score every earlier token and hand each query a short list of the best ones to read, but at a million tokens that choosing costs more than the attention itself.

This work instead groups tokens by how similar they are, not by position, and looks each query up in an inverted-file index, the kind of lookup table search engines use to jump straight to likely matches. A query only sees groups built from tokens before it.

That recovers far more of the true best keys than position-based grouping and raises long-context accuracy by up to 18.4 percentage points, while staying faster than scoring every key.

How it works

before and after

RSS

The Daily Edition

The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.

Concepts

sparse attention inverted-file indexing long-context processing retrieval augmented generation kv cache compression