KV

The model computes key and value vectors when it processes a token. Quail saves the vectors in GPU memory as KV for reuse in later requests.

This page explains three forms of reuse:

• KV rewind reuses one document's KV for successive questions or join partners.
• Prefix sharing reuses KV between documents that begin with the same tokens.
• KV retention keeps document KV available across separate operators.

See Execution for how requests use KV in a batch.

Paged KV

Quail stores KV in pages of 16 tokens. The session allocates an arena, which is the GPU memory pool holding those pages.

Each document has a list of page IDs. Several documents can reference the same page when they share a prefix. A page becomes free when no document holds a reference to it.

The number of available pages depends on GPU memory remaining after model weights and execution memory are reserved. See physical plan settings. The arena implementations are PageArena and KVArena.

KV rewind

Quail puts each question after the document in the prompt. After reading the answer, it discards the question's KV while keeping the document's KV. The next question can then use the same document state.

For a filter with several predicates:

1. Process the document and first question.
2. If the document passes, keep its KV and remove the question's KV.
3. Process the next question using the saved document KV.
4. Release document KV when the document fails or no later work needs it.

For example, imagine that a filter's first predicate keeps 1,000 reviews. Each review has 300 tokens, and the second question has 50 tokens. The second predicate processes 50,000 new tokens with KV rewind, compared with 350,000 if it must process every review again.

A join reuses anchor KV in the same way. It adds a partner's tokens, evaluates the pair, and removes the partner's KV before reusing the anchor for other partners. A compatible classification can also reuse document KV from earlier pipeline stages.

The code calls KV rewind "chain mode".

Prefix sharing

Documents sometimes begin with identical token sequences. For example, imagine a table containing agent traces saved after each turn. A later trace includes earlier turns, so those rows share a prefix.

Quail can compute the prefix once and let other documents reference its KV pages. The prefix sharing rule enables sharing when estimated compute savings exceed additional KV write costs.

The sharing plan

Because Quail has the input documents before GPU execution, it can plan which prefixes to share. It sorts documents by token sequence and compares adjacent documents to find common prefixes.

Only complete pages are shared. Quail also leaves the final token of each document to be computed so the request can produce its output.

PrefixTree stores the sharing plan:

When the preceding document also reuses the entire shared prefix, Quail follows parent links to the document that supplies those pages.

For example, suppose three rows contain the first 1,000, 1,400, and 1,900 tokens of one trace. With 16-token pages, their sharing plan is:

order = [0, 1, 2]
parent = [None, 0, 1]
shared = [0, 992, 1392]

If the required KV remains available, Quail processes 1,916 document tokens: 1,000 for the first row, 408 for the second, and 508 for the third. Without sharing, it processes 4,300 document tokens. Question tokens are additional work in both cases.

Execution

The executor admits documents in the planned order. A document waits for its parent to start, then references the parent's shared pages without copying their KV. Quail keeps those pages while waiting documents need them.

Sharing has these limits:

• If the parent is skipped or its required KV is unavailable, the document computes the prefix again.
• Documents can share KV only on the same GPU.
• A filter with a row limit disables sharing to preserve row order.

See Borrowing for admission decisions.

KV retention

A separate operator may need a document that an earlier operator already processed. For example, two joins may use the same table as their anchor. Retaining that table's document KV can avoid processing the anchors again.

The KV retention rule records which later operators can reuse KV. The executor keeps selected KV within a memory limit that reserves space for two forward passes.

When the retention pool is full, Quail removes the KV with the lowest priority. Priority is estimated future compute savings per page:

priority = probability_of_reuse * recompute_seconds / pages

The probability estimates whether a later operator will read the document. recompute_seconds estimates the time to process it again. pages is its KV page count. If a later operator needs removed KV, it computes the document again.

See cost/retention.py for priorities and capacity, and planner/retention.py for the retention schedule.

Quail's KV reuse is inspired by community work, including vLLM Automatic Prefix Caching and SGLang RadixAttention.