Key-Value (KV) Cache Storage Protocol (KVSP): Indexing, Placement, Prefetch, and Migration for Distributed Inference

1.1. Problem Statement

The KV cache of a transformer model holds, for every processed token and every layer, the key and value vectors used by attention. It lets each decoding step reuse earlier computation, but it imposes three costs on serving systems:¶

• Footprint: the cache grows linearly with context length and batch size and quickly exhausts accelerator memory, which limits both concurrency and maximum context length.¶
• Request-bound lifetime: when the cache is discarded at the end of each request, requests that share a long system prompt or document prefix recompute the same state, which increases the time to first token.¶
• Swap cost: moving cache contents between accelerator memory, host memory, and storage is slow when done synchronously and stalls computation.¶

Serving systems address these costs by keeping caches beyond the lifetime of a request, storing them in several tiers, and reusing them across requests and instances [PAGEDATTENTION] [MOONCAKE]. These systems are currently built as single-vendor stacks. When the scheduler, the inference engines, and the cache tiers come from different implementers, or span administrative boundaries within an operator, every pair of components needs agreement on the same questions: which caches are interchangeable, what a block is called, where its copies are, how long a copy will stay, which instance should serve the next request, and how to continue a session when an instance fails. [I-D.li-cats-kv-cache-distribution] states these needs as requirements. This document specifies a protocol that meets them.¶

1.2. Protocol Overview

KVSP defines:¶

• a Compatibility Descriptor and its digest, the Compatibility ID, which state when two caches can substitute for each other (Section 4.1);¶
• Block Keys computed as a keyed hash chain over token identifiers, so that a key names a block together with its entire prefix and cannot be inverted by parties that lack the scope key (Section 4.2);¶
• a KV Block Container format that supports retrieval of a range of layers (Section 4.3);¶
• an Index Service that records replicas, including which layers of a block reside in which storage tier (Section 6.1);¶
• instance status reports and an instance lifecycle including draining and sleeping (Section 6.3);¶
• prefetch directives with eviction-protecting leases, which let a placement controller load caches into an instance before the request arrives (Section 6.5);¶
• session checkpoints that let another instance resume a session after a failure (Section 6.8); and¶
• a resharding procedure for caches split by token range across a parallel group, which keeps shards in place when they stay on the same instance (Section 6.9).¶

1.3. Scope

KVSP standardizes the information exchanged between components and the obligations attached to it. It does not standardize attention kernels, memory allocators, eviction policies, or the scheduling policy of the placement controller; it standardizes the inputs that such a policy consumes and the directives it issues. Inference requests themselves (for example, chat completion APIs) are out of scope. Bulk block transfer uses HTTP by default; other transports such as Media over QUIC Transport [I-D.li-kvcache-efficient-transmission] or RDMA [I-D.li-rdma-kvcache-transfer-optimization] can be used where available.¶

1.4. Relationship to Other Work

Computing-Aware Traffic Steering (CATS) [I-D.ietf-cats-framework] steers requests to service instances using computing and network metrics. The instance status and lookup estimates of KVSP can serve as additional inputs to such steering, as described in [I-D.li-cats-kv-cache-distribution]. Naming Things with Hashes [RFC6920] defines hash-based identifiers; KVSP uses a keyed construction instead, because plain hashes of short token sequences can be inverted by enumeration (Section 10).¶

4.1. Compatibility Descriptor and Compatibility ID

A KV cache produced under one configuration is only valid for another computation if the model weights, the tokenizer, and every parameter that affects the stored tensors are identical. The Compatibility Descriptor is a JSON object with the following members, all REQUIRED unless stated otherwise:¶

model:

A string naming the model. It is part of the identity, so all parties MUST use the same string for the same model.¶

model_digest:

"sha-256:" followed by the lowercase hex SHA-256 [RFC6234] of the model weights, computed over the weight files concatenated in ascending byte order of their file names.¶

tokenizer_digest:

"sha-256:" followed by the lowercase hex SHA-256 of the tokenizer definition file.¶

adapters:

OPTIONAL array of adapter digests, in the same form as model_digest, in the order of application. The member MUST be absent when no adapter is applied; an empty array is not allowed.¶

layers, kv_heads, head_dim:

Integers describing the cache geometry.¶

kv_dtype:

The element type of the stored cache, from the "KVSP Element Types" registry (Section 11.2.3).¶

positional:

The positional encoding variant, from the "KVSP Positional Encodings" registry, optionally followed by ";" and parameters in the registered syntax. Parameters that are absent take the defaults of the model, and a descriptor MUST include them whenever the model is run with non-default values.¶

block_tokens:

The block size B in tokens.¶

layout:

The layout identifier for codec "raw" (Section 4.3); this document defines "kvsp-layout-1".¶

The Compatibility ID is:¶

   compat_id = SHA-256( "KVSP-COMPAT-1" || 0x00 || JCS(descriptor) )

where JCS is the JSON Canonicalization Scheme [RFC8785] and || denotes concatenation. The Compatibility ID is carried as hex32. Two caches MUST NOT be substituted for each other unless their Compatibility IDs are equal. Implementations MUST compute the Compatibility ID from the descriptor rather than accept it from a peer without verification whenever the descriptor is available.¶

4.2. Scopes and Block Keys

Each scope has a Scope Key of at least 32 random octets, shared by the principals of the scope through means outside this document. The Scope ID is:¶

   scope_id = first 16 octets of
              SHA-256( "KVSP-SCOPE-1" || 0x00 || scope_key )

The Block Key of block i of a token sequence t[0], t[1], ... is defined recursively, with K[-1] equal to 32 zero octets:¶

   K[i] = HMAC-SHA-256( scope_key,
                        "KVSP-BLOCK-1" || 0x00 || compat_id ||
                        K[i-1] ||
                        uint32(t[i*B]) || ... || uint32(t[i*B+B-1]) )

HMAC is defined in [RFC2104]. compat_id is the 32 raw octets, and uint32() is the token in four octets in network byte order. Because K[i] covers K[i-1], a Block Key identifies the whole prefix [0, (i+1)*B) and not only the tokens of block i. Only complete blocks have keys; the tokens after the last complete block are not shared. Block Keys are carried as hex32.¶

A deployment that wants to share a public prefix (for example, a common system prompt) across tenants creates a dedicated shared scope for it. Caches MUST NOT be shared across scopes otherwise.¶

4.3. KV Block Container

Blocks are exchanged in the KV Block Container. A container holds a contiguous range of layers of one block:¶

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Magic ("KVB1" = 0x4B564231)                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Version    |     Flags     |             Codec             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          First Layer                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Layer Count                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Token Count                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      Layer Count entries of { K Length (64), V Length (64) }  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Data: for each layer in ascending order, K octets, V octets  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version is 1. Flags are reserved and set to zero. Codec is a value from the "KVSP Codecs" registry (Section 11.2.2). Integers are in network byte order. The ascending layer order allows a receiver to start using layer l as soon as it has been received, overlapping computation with loading.¶

For codec 0x0001 ("raw"), the K and V sections of a layer each hold Token Count x kv_heads x head_dim elements of kv_dtype, in row-major order with the token index varying slowest and the dimension index fastest, each element in little-endian octet order; this is layout "kvsp-layout-1". Other codecs (for example, quantized or entropy-coded caches) define their own section encoding.¶

The layer digest of layer l is the SHA-256 of its K section followed by its V section. The digest of a replica is the SHA-256 of the concatenation of the layer digests of all layers, in ascending order. This construction lets a client that retrieves a range of layers verify each of them against the layer digests listed in the Replica Record, and verify that list against the replica digest.¶

4.4. Records

The following JSON objects are used in requests and responses. Unknown members MUST be ignored.¶

Replica Record:¶

{
  "block_key": "<hex32>",
  "compat_id": "<hex32>",
  "scope_id": "<hex16>",
  "holder": "https://h1.example/kvsp/",
  "codec": 1,
  "size": 2097152,
  "digest": "sha-256:<hex32>",
  "layer_digests": ["<hex32>", "<hex32>", "..."],
  "residency": [
    { "tier": "device", "layers": [0, 15] },
    { "tier": "host",   "layers": [16, 31],
      "read_mbit_per_s": 400000 }
  ],
  "ttl_ms": 600000
}

"layer_digests" lists the layer digests (Section 4.3) in layer order; it is REQUIRED for replicas that are served by layer range. The residency array states which layers reside in which tier. Layer ranges are inclusive and MUST NOT overlap. The optional "read_mbit_per_s" of a residency entry states the rate at which the holder can read that tier. A holder that keeps some layers of a block in accelerator memory and the others in host memory, to overlap layer loading with computation, reports this split so that placement can account for it.¶

A replica can also be served through Media over QUIC Transport [I-D.li-kvcache-efficient-transmission]. Its record then has a "holder" that is a "moqt" URI of the publishing endpoint or relay and a member "moqt_namespace" holding the base64url encoding (without padding) of the five Track Namespace Fields, each preceded by its length as one octet. The publisher of that namespace is the holder for the purposes of authorization, and the digests have the meaning defined in this section, which the MOQT object digests reproduce for codec "raw".¶

Instance Status Record:¶

{
  "instance": "https://ii7.example/kvsp/",
  "epoch": 12,
  "state": "active",
  "running": 18, "queued": 3, "batch_size": 32,
  "kv_utilization": 0.71,
  "prefill_tokens_per_s": 42000,
  "decode_tokens_per_s": 3100,
  "links": [
    { "holder": "https://h1.example/kvsp/",
      "mbit_per_s": 200000, "rtt_us": 12 }
  ],
  "requested_state": null,
  "ttl_ms": 3000
}

Session Checkpoint:¶

{
  "session": "6f1d0a9e-2c55-4d7e-9a0e-5b7f2f9f6a11",
  "epoch": 1,
  "compat_id": "<hex32>",
  "scope_id": "<hex16>",
  "prompt_blocks": ["<hex32>", "<hex32>"],
  "prompt_tail": [374, 264],
  "generated": [1296, 315, 279],
  "output_offset": 3,
  "sampler": { "method": "top-p", "params": {"p": 0.9},
               "seed": 7, "step": 3, "deterministic": false }
}

The session identifier is a UUID [RFC9562]. output_offset is the number of output tokens covered by the checkpoint. prompt_tail holds the prompt tokens after the last complete prompt block. "sampler.deterministic" is true only if every instance eligible to resume the session produces bit-identical output tokens from the same state, for example greedy decoding with batch-invariant kernels on identical software and hardware.¶

6.1. Publishing and Withdrawing Replicas

A holder publishes each replica it is willing to serve with PUT, carrying a Replica Record. The Index Service MUST verify that the authenticated client is the holder named in the record or is authorized to publish on its behalf, and that the client is authorized for the record's scope. A replica record expires after ttl_ms; the IS caps ttl_ms at a configured maximum. Holders refresh records before expiry with the same PUT, which is idempotent. A holder MUST withdraw a record with DELETE before or immediately after evicting the replica, and MUST NOT evict a replica covered by an unexpired lease (Section 6.6).¶

The index is advisory: a holder can evict an unleased replica before the withdrawal reaches the IS. Clients therefore treat a 404 from a holder as a cache miss and continue with the next replica or with recomputation.¶

6.2. Lookup

A client (normally the PC) computes the Block Keys of the prompt and sends them, in prefix order, to the IS:¶

POST {is-base}lookup
{
  "scope_id": "<hex16>",
  "compat_id": "<hex32>",
  "block_keys": ["<hex32>", "<hex32>", "<hex32>"],
  "targets": ["https://ii7.example/kvsp/",
              "https://ii9.example/kvsp/"]
}

The IS returns "matched", the number of leading keys for which at least one unexpired replica exists, and for each matched key the replica records. Because Block Keys are chained, the IS MUST stop at the first key without a replica. When "targets" is present and the IS has the needed status and link information, it also returns, for each target instance, "fetch_us" (the estimated time to make the matched blocks resident at that instance, Section 6.4) and "recompute_us" (the estimated time to prefill the same tokens on that instance). The IS MUST NOT return replicas of a scope for which the client is not authorized.¶

6.3. Instance Status and Lifecycle

Each inference instance sends its Instance Status Record to the PC at an interval no longer than one third of its ttl_ms. The PC considers an instance failed when its record expires. The "epoch" of an instance MUST increase every time it restarts; the start time of the instance in milliseconds since the Unix epoch satisfies this without persistent state, provided that the instance's clock does not move backward across restarts; otherwise the instance persists a counter. The PC MUST discard records with an epoch lower than the highest it has seen for that instance.¶

Instances move between the states active, draining, sleeping, and failed. An instance whose load has stayed below a configured threshold for a configured time MAY ask to sleep by setting "requested_state" to "sleeping". The PC answers the status PUT with 200 and a body {"state": "draining"} to accept, or {"state": "active"} to refuse. The PC can also change the state of an instance with PUT state on the instance.¶

• The PC MUST NOT assign new requests or send prefetch directives to an instance that is not active.¶
• A draining instance MUST complete its in-flight sessions and MUST NOT accept new ones; when it has none left it enters sleeping and reports it.¶
• A sleeping instance becomes active only on a state change from the PC.¶

6.4. Placement Inputs

The PC chooses an instance for each request. The policy is local, but it is expected to compare, for each candidate, the cost of loading cached blocks with the cost of recomputing them. The following estimates SHOULD be used, by the IS when it answers a lookup with targets and by the PC otherwise:¶

fetch_us(i)     = max over sources s of
                    ( rtt_us(i,s)
                      + 8 * bytes_from(s) / mbit_per_s(i,s) )
                  for blocks not already resident at i
recompute_us(i) = 1e6 * tokens / prefill_tokens_per_s(i)
wait_us(i)      = queued(i) * mean service time at i
cost(i)         = wait_us(i)
                  + min( fetch_us(i) + recompute_us_of_unmatched(i),
                         recompute_us_of_all(i) )

where bytes_from(s) is the volume the instance would load from source s, and mbit_per_s(i,s) is the link rate reported by instance i for source s, reduced, for layers that the source holds in a storage tier, to the "read_mbit_per_s" of that tier in the Replica Record. The PC SHOULD assign the request to an active instance with the lowest cost. When no active instance has acceptable cost or capacity, the PC MAY start a new instance and SHOULD send it a prefetch directive at once, so that cache loading overlaps the instance start.¶

6.5. Prefetch Directives

To load caches into an instance before a request reaches it, the PC sends a prefetch directive:¶

POST {ii-base}prefetch
{
  "directive": "a2b7c9e0-1f3d-4c1a-8f5b-6d2e9a7c3b10",
  "request_ref": "opaque-value-from-PC",
  "scope_id": "<hex16>",
  "compat_id": "<hex32>",
  "blocks": [
    { "block_key": "<hex32>",
      "sources": ["https://h1.example/kvsp/"] }
  ],
  "layer_order": "ascending",
  "deadline_ms": 50,
  "lease_ms": 2000
}

The instance answers 202 (Accepted) with a Location field naming the directive's status resource, and processes the directive while it continues to execute current work; prefetch MUST NOT block execution of requests already admitted. For each block it does not already hold, the instance acquires a lease of lease_ms at one of the listed sources (Section 6.6), so that the source cannot evict the block while it is being loaded, retrieves the block (Section 6.7), verifies the digest, places it in its tiers, and publishes its new replica (Section 6.1). The state of the directive ("pending", "partial", "complete", or "failed", with the list of loaded keys) can be read with GET. If the deadline expires, the instance stops loading and reports "partial"; the request is then served with the loaded prefix and the remaining tokens are recomputed.¶

"request_ref" is an opaque value that lets the PC associate the directive with the inference request it will route; how the request carries the value is outside the scope of this document.¶

6.6. Leases

POST leases on a holder, with a body listing block keys and "ttl_ms", creates a lease and returns its identifier and the granted TTL. PUT on the lease renews it; DELETE releases it. While a lease is valid the holder MUST NOT evict the leased replicas. A holder MUST enforce a per-client quota on leased octets and lease TTL and returns the problem type "kvsp-lease-quota" when a request exceeds it. A holder that must evict leased data due to a fault MUST first withdraw the affected replica records.¶

6.7. Block Retrieval and Storage

Block resources are named blocks/{compat}/{scope}/{block_key}, where {compat} is the Compatibility ID (hex32), {scope} the Scope ID (hex16), and {block_key} the Block Key (hex32), so that retrieval and storage address the same resource. GET on it returns the container (Section 4.3) with media type "application/kvsp-block". The query parameter "layers=a-b" requests the inclusive layer range a..b; a holder that does not hold those layers returns 404 with problem type "kvsp-layers-unavailable". The query parameter "codec=n" requests a codec; a holder MAY transcode. Holders MUST include a "Repr-Digest" field [RFC9530] with the SHA-256 of the returned container. Block representations are immutable but confidential; holders SHOULD send "Cache-Control: private, immutable" with a max-age no longer than the remaining TTL of the replica.¶

Clients MUST verify Repr-Digest. When the returned codec equals the replica's codec, clients MUST also verify the layer digests of the returned layers against the Replica Record, and, when all layers were retrieved, the replica digest. Transcoded representations are protected only by Repr-Digest, so clients that need producer-level integrity request the replica's codec.¶

PUT on the block resource with "If-None-Match: *" stores a block at a holder. The holder MUST reject the request if the client is not authorized for the scope. The key identifies the token prefix, not the stored octets, so a holder that already has a replica for the key returns 412 and keeps its copy.¶

6.8. Session Checkpoints and Migration

An instance that serves a session SHOULD publish a Session Checkpoint to the PC with PUT sessions/{session}/checkpoint whenever a block of generated tokens completes, and at least every 64 output tokens. It also publishes replicas for the generated blocks, so that their KV cache survives the instance. The PC records the checkpoint with the highest output_offset for the current session epoch and MUST reject a checkpoint with a lower epoch with problem type "kvsp-stale-epoch".¶

Output continuity depends on the sampler. If the checkpoint states that the sampler is deterministic, a resumed instance regenerates exactly the tokens the failed instance produced after the last checkpoint, and the front end discards the duplicates by index. Otherwise the instance MUST NOT release an output token to the front end before the PC has acknowledged a checkpoint that covers it; it can checkpoint several tokens at a time to bound the added latency. Every output token carries its index and the session epoch, and front ends MUST discard tokens that carry a lower epoch than one they have already seen for the session.¶

When the instance fails, the PC selects a new instance as in Section 6.4, increments the session epoch, and sends POST sessions/{session}/resume to it with the latest checkpoint and the new epoch. The new instance:¶

1. loads the blocks listed in the checkpoint and the generated blocks published by the failed instance;¶
2. recomputes the KV cache of prompt_tail and of generated tokens not covered by loaded blocks;¶
3. restores the sampler with the given method, parameters, seed, and step; and¶
4. continues generation and labels each output token with its index, starting at output_offset, so that the front end delivers every index exactly once.¶

Any message from the failed instance carrying the old epoch MUST be rejected. Under these rules the output already delivered is never repeated or altered, and the client receives a single consistent sample.¶

6.9. Sequence-Sharded Caches and Resharding

For long contexts, a parallel group can split one context by token range across several instances. The PC describes the split in a Shard Map:¶

{
  "map": "c3f8...e1", "version": 4,
  "shards": [
    { "tokens": [0, 32768],
      "instance": "https://ii1.example/kvsp/" },
    { "tokens": [32768, 65536],
      "instance": "https://ii2.example/kvsp/" },
    { "tokens": [65536, 98304],
      "instance": "https://ii3.example/kvsp/" }
  ]
}

Token ranges are half-open, contiguous, and non-overlapping. The computing demand of a context changes between phases: prefill is compute-bound and benefits from many instances, while early decoding steps need fewer instances and later ones need more memory. The PC can therefore change the group between iterations. To move from version v to v+1, it sends each instance in either version a reshard plan with POST reshard:¶

{
  "map": "c3f8...e1", "from": 4, "to": 5,
  "deadline_ms": 200,
  "retain":  [[0, 32768]],
  "fetch":   [{ "tokens": [32768, 49152],
                "from": "https://ii2.example/kvsp/" }],
  "release": []
}

The following rules apply:¶

• A token range assigned to the same instance in both versions MUST appear in "retain" for that instance and MUST NOT be transferred. Retained ranges keep their memory in place, so a change of parallelism costs no transfer for them.¶
• An instance acknowledges the plan with 200 after it has loaded all ranges listed in "fetch".¶
• Version v remains authoritative until all instances have acknowledged; the PC then sends POST reshard with {"map": ..., "commit": v+1} to all members, after which instances release the ranges listed in "release".¶
• If any instance fails to acknowledge within deadline_ms, the PC sends POST reshard with {"map": ..., "abort": v+1}, and the members discard the ranges they fetched for version v+1.¶

11.1. Media Types

IANA is requested to register the following media types in the "Media Types" registry [RFC6838].¶

Type name: application; Subtype name: kvsp+json; Required parameters: N/A; Optional parameters: N/A; Encoding considerations: binary (UTF-8 JSON); Security considerations: see Section 9 of RFC XXXX; Interoperability considerations: none; Published specification: RFC XXXX; Applications that use this media type: KV cache storage and distributed inference systems; Fragment identifier considerations: none; Additional information: Deprecated alias names for this type: N/A, Magic number(s): N/A, File extension(s): N/A, Macintosh file type code(s): N/A; Person and email address to contact: IETF <iesg@ietf.org>; Intended usage: COMMON; Restrictions on usage: none; Author: IETF; Change controller: IETF.¶

Type name: application; Subtype name: kvsp-block; Required parameters: N/A; Optional parameters: N/A; Encoding considerations: binary; Security considerations: see Section 9 of RFC XXXX; Interoperability considerations: none; Published specification: Section 4.3 of RFC XXXX; Applications that use this media type: KV cache storage and distributed inference systems; Fragment identifier considerations: none; Additional information: Deprecated alias names for this type: N/A, Magic number(s): 0x4B564231 at offset 0, File extension(s): N/A, Macintosh file type code(s): N/A; Person and email address to contact: IETF <iesg@ietf.org>; Intended usage: COMMON; Restrictions on usage: none; Author: IETF; Change controller: IETF.¶

11.2. KVSP Registries

IANA is requested to create a registry group named "KV Cache Storage Protocol (KVSP)" at "https://www.iana.org/assignments/kvsp" with the following registries. New assignments use the Specification Required policy [RFC8126]. The designated experts should check that a registration is specified precisely enough for independent implementations to interoperate, and that names are lowercase ASCII and do not duplicate existing entries.¶