Why Prefix Caching Misses Identical Requests: Concurrent Reuse and Single-Flight Coordination in Practice

In the self-built Rust LLM inference engine mini-vllm-rs, after enabling prefix caching, two completely identical requests arrived at a cold cache at the same time, yet not a single token was reused—both performed a full prefill. The problem lay in the visibility timing of cache pages: reusable pages were only published when a request completed, and both requests arrived before the other had published.

This cold-start failure gave rise to three progressively refined design decisions: when cache pages become visible, whether other requests need to wait, and when waiting ends.

The cold cache problem and the first benchmark

The author tested a 4-bit quantized Qwen2.5 0.5B model on the Metal GPU of a Mac mini, with a cache page size of 16 tokens, running each test 3 times. The initial reuse benchmark compared two scenarios:

Workload	Result
Reusing a pre-warmed document prefix	Recovered 880 of 904 input tokens, reducing time-to-first-token (TTFT) by 96.2%
4 identical requests arriving at a cold cache simultaneously	Recovered 0 tokens total, performed full prefill

These numbers show that the advantage of prefix caching is already very clear on the hot path, but it fails completely in the cold-start concurrent scenario. The crux of the problem is clear: there is a race between the cache's publication strategy and the execution order of concurrently arriving requests, and the original "publish only on request completion" strategy cannot cover this scenario.

Prefix caching is a class of techniques in LLM inference for reusing the attention key-value cache (KV cache). In autoregressive decoding, the attention of each token requires the Key and Value vectors of all preceding tokens, and these vectors are deterministic and reusable for identical prefixes. Prefix caching splits the prompt into fixed-size (16 tokens in this article) cache pages, each page corresponding to a segment of KV, and builds a hash index for it. When a new request arrives, the engine compares input tokens page by page; on a hit, it can directly reference these already-computed KV pages and skip the corresponding prefill computation. This yields enormous benefits for multi-turn conversations, repeated long documents in RAG, and batches of similar prompts (e.g., evaluation, classification), because prefill often dominates time-to-first-token (TTFT). The key constraint is: a cache page can only be seen by other requests after computation is complete and it has been correctly published; the visibility timing directly determines whether hits occur in concurrent scenarios.

Incremental publication: share while generating

The author introduced incremental publication: after each batched forward pass completes, the engine immediately publishes the newly completed cache pages, making them reusable while the current request is still generating.

The test method was to first start one request, wait for it to return the first output token, and then, while it continued generating the remaining 128 output tokens, submit more requests with the same prompt and observe whether they could reuse the already-cached prefix. The result was that each following request recovered 480 of the 493 prompt tokens.

In groups of 2, 4, and 8 concurrent requests, compared with "publish on completion," incremental publication reduced average TTFT by 48–93%. However, incremental publication did not eliminate duplicate computation for cold simultaneous arrivals: a request might find only part of the prefix, or even nothing at all, and still had to compute the remainder itself. Whether reuse occurs depends on execution order and publication timing.

To eliminate this race, one must decide "who computes the prefix."

Single-flight coordination: one request computes the prefix, how long do others wait?

Exact-input single flight works like this: one request becomes the leader, and other requests with exactly the same input tokens become followers and wait. What is coordinated is prompt computation, not the answer—each follower still generates its output independently according to its own generation settings (e.g., temperature).

The first implementation made followers wait for the leader's entire request to complete. Cache reuse became predictable, but the wait spanned the entire decode phase.

With 8 concurrent requests each generating 128 output tokens, this strategy reduced both average TTFT and the completion latency of the slowest request compared with independent execution. But with only 2 requests, average TTFT was actually worse than independent execution, although completion latency improved.

Since the prompt cache is already ready, why wait through the decode phase? The author added a second release strategy: once the leader's prefill completes, immediately publish its completed cache pages and make followers eligible for admission.

sequenceDiagram
    participant S as Scheduler
    participant C as Prefix cache
    participant L as Leader
    participant F as Followers
    S->>L: Admit leader
    S->>S: Block identical followers
    L->>L: Finish prompt prefill
    L->>C: Publish completed prefix pages
    L->>S: Report successful publication
    S->>S: Unblock followers
    S->>F: Admit as capacity allows
    F->>C: Look up matching prefix
    C-->>F: Return shared KV page references
    par Independent generation
        L->>L: Continue decode
    and Follower generation
        F->>F: Generate their own outputs
    end

The table below compares the two release strategies (identical requests concurrently generating 128 output tokens):

Concurrent requests	Release on request completion	Release after prefill	TTFT reduction
2	1,357.5 ms	584.7 ms	56.9%
4	1,757.9 ms	617.1 ms	64.9%
8	1,984.4 ms	646.7 ms	67.4%

In an 8-request burst compared with independent execution (each with a 532-token prompt and 128-token output):

Strategy	Tokens recovered per follower	Average TTFT change	Slowest request completion time change
Independent execution, publish on completion	0	baseline	baseline
Single flight, release on request completion	528	reduced 47.5%	reduced 25.8%
Single flight, release after prefill publication	528	reduced 82.9%	reduced 32.4%

But earlier release is not better on every metric. In a separate test, the second request arrived after the original request had entered the decode phase. Compared with release on request completion, early release reduced average TTFT by 72%, but increased the slowest request's completion latency by 14%. The reason is that the original flight had already closed, the second request opened a new flight and reused the hot prefix, and the two requests decoded concurrently rather than sequentially, changing the active batch.

The early-release strategy itself publishes the necessary checkpoints, and additional incremental publication yields little benefit in these exact-input coordination scenarios. But in uncoordinated scenarios, such as requests that share only part of the prefix, incremental publication remains useful.

Put simply: publication determines when data is reusable; coordination determines who waits and for how long.

Single flight is a classic pattern in concurrent programming: only one executor is allowed to actually run a given piece of work, and other identical requests are merged to wait for its result, avoiding duplicate computation. Go's golang.org/x/sync/singleflight is a common implementation. When introduced into LLM inference, there is one difference: the "identical work" here is only prompt prefill, not the entire request. Because each request still decodes independently according to its own sampling settings (temperature, top-p, etc.), the outputs are inherently different, so coordination covers only the shared cost of prefix computation. The leader computes and publishes cache pages, and followers wait for completion and then directly reference these pages to continue their own decoding. The endpoint of waiting is the core trade-off: waiting until the leader's entire request finishes gives a longer wait but deterministic ordering; releasing as soon as the leader's prefill finishes shortens the wait, but the leader and followers decode concurrently, changing the composition of the active batch and potentially increasing the slowest request's completion time.

State machine simplification: from Draining to separation of responsibilities

During this implementation, AI assisted in writing code, but reviewing its design was the key.

Initially, AI deleted the flight record directly when releasing followers, which seemed reasonable at the time—the wait was over. But the first single-flight benchmark exposed a problem: when followers later completed and notified the coordinator, the coordinator no longer recognized their IDs. AI proposed removing the unknown-request check, but the author rejected it, because that would also mask termination notifications carrying genuinely invalid request IDs.

The original design had no FlightState. To preserve validation, the team added Active and Draining states and tracked released followers until their termination:

enum FlightState {
    Active { leader_request_id: u64 },
    Draining,
}

struct Flight {
    input_token_ids: Arc<[u32]>,
    state: FlightState,
    follower_request_ids: VecDeque<u64>,
}

But the early-release strategy made this representation more complex: the leader might still be decoding after followers are released. AI kept the same fields and only changed the enum:

enum FlightState {
    Active { leader_request_id: u64 },
    Draining { leader_request_id: Option<u64> },
}

The optional leader made the author pause and think: different release strategies require different combinations. If a strategy should not retain the leader, but the state has one, do we need another check?

Step back: is the Draining state really needed? It was added to recognize released requests when they eventually terminate, which requires remembering their IDs, but not retaining their former flight relationship. Why not collect these IDs separately across flights?

So the team removed FlightState and tracked released request IDs separately:

pub(super) struct PrefixCacheFlightCoordinator {
    flights: HashMap<FlightId, Flight>,
    released_request_ids: HashSet<u64>,
    // Other fields omitted.
}

On release, remove the flight and its index, keeping only the request IDs that have not yet terminated. This preserves termination validation without retaining leader/follower relationships that no longer affect execution. Unknown request IDs still raise errors, and new requests with the same prompt open a new flight.

Human review means both protecting invariants and re-examining the structure used to protect them. Benchmarks show when a request can stop waiting; code review shows when a flight can stop existing.

Rust's enum ability to carry data (algebraic data types, ADT) allows a state machine to express states directly in the type: FlightState::Active { leader_request_id: u64 } indicates a flight in progress bound to a leader, while Draining indicates the wait phase has ended. The benefit is that certain fields exist only in specific states, and the compiler can force a match before use, avoiding illegal states. But when different release strategies require different field combinations (such as Draining { leader_request_id: Option<u64> }), the enum starts to bloat—raising questions like "should there be a leader in this state?" that require extra checks. A common refactoring approach is to split orthogonal responsibilities into different structures: the state machine describes only the execution phase, while "which requests have been released but not yet terminated" belongs to lifecycle tracking and can be maintained with an independent collection (such as HashSet<u64>). This avoids the branching introduced by Option and makes each structure carry only a single semantic, aligning with Rust's design philosophy of "making illegal states unrepresentable."

Open questions left by this small implementation

The above are all results from synthetic workloads, a single backend, and a small model. Exact-input coordination showed no meaningful completion-time regression for independent inputs in the control, but benchmarks cannot establish behavior under production traffic. Several directions are worth further exploration:

1. Partial prefix coordination: Requests may share a long document but differ at the tail question—how much overlap is worth waiting for?
2. Wait or recompute: The follower's latency target and the leader's remaining prefill workload change the choice.
3. Different attention states: Sliding window and hybrid models change retention and reuse strategies; vLLM's hybrid KV cache manager explores these constraints.
4. Reuse across backends and memory tiers: Routing must trade off prefix locality against speed and load; SGLang HiCache extends caching to GPU, host, and external storage.

These open questions remind us that coordination strategies for prefix caching in concurrent scenarios are far from settled, and this small Rust-based engine provides an observable, iterable experimental platform.