Why My Prefix Cache Missed Identical Requests

I enabled prefix caching in mini-vllm-rs, my Rust LLM inference engine for macOS, and submitted two identical requests concurrently to a cold cache.

Neither reused a single token. Both computed the same prompt.

Why? My cache published reusable pages only when a request finished. Both requests arrived before either had published anything, so neither found a prefix to reuse. Later requests reused completed prefixes correctly.

Supporting concurrent reuse required more decisions: when should cached pages become visible, should another request wait for them, and when should that wait end?

Benchmarks led me to add incremental publication and single-flight coordination. Deciding when to release waiting requests then exposed another problem: an increasingly complicated AI-generated state machine.

I tested a 4-bit quantized Qwen2.5 0.5B model on my Mac mini's Metal GPU, with 16-token cache pages and 3 repeated runs. My first reuse benchmark compared warm reuse with simultaneous cold arrivals:

That cold-cache result was the problem I encountered at the start of this article.

I added incremental publication. After each successful batched model forward, the engine immediately publishes any newly completed pages containing committed tokens, so they become available for reuse before this request finishes.

To test this change, I started one request and waited until it returned its first output token. While it continued generating the rest of its 128-token output, I submitted more requests with the same prompt to see whether they could reuse the cached prefix.

Incremental publication let each follower restore 480 of its 493 prompt tokens. Across groups of 2, 4, and 8 concurrent requests, mean TTFT fell by 48–93% compared with completion-only publication. That average includes every request's wait from submission to first streamed output. For detailed measurements, see the follow-up benchmark report.

However, incremental publication did not eliminate duplicate work for simultaneous cold arrivals. A request can reuse complete prefix pages already published when it starts execution, even if the other request is still prefilling. But it may find only part of the prompt, or nothing yet, and compute the rest itself. Reuse therefore depends on execution order and publication timing.

Avoiding that race required deciding who should compute the prefix.

I added exact-input single flight. One request becomes the leader, while other requests with identical input tokens wait as followers. This coordinates prompt computation, not answers. Every follower still generates its own output, as expected: identical prompts can use different generation settings, such as temperature.

My initial implementation made followers wait until the leader's entire request finished. The cache reuse became predictable, but the policy also made them wait through decode.

With 8 simultaneous requests each generating a 128-token output, this policy reduced both mean TTFT and the slowest request's completion latency compared with independent execution. But with only 2 such requests, mean TTFT became worse than independent execution, even though completion latency improved. Avoiding duplicate computation had introduced a new waiting cost.

Why wait through decode when the prompt cache was already ready? I added a second release policy. Once the leader finishes prefill, the engine publishes its completed prefix pages, then makes 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

For simultaneous identical requests generating 128 output tokens each, both policies restored the same number of cached tokens, while releasing followers after prefill reduced mean TTFT:

To compare both policies with independent execution, the table below focuses on the 8-request burst. Each request had a 532-token prompt and a 128-token output:

Regular incremental publication is disabled in all rows. The early-release policy explicitly publishes the prompt prefix when prefill finishes.

However, earlier release did not improve every metric. In a separate test, a second request arrived right after the original request entered decode phase. Compared with release-at-completion single flight, early release reduced mean TTFT by 72%, but increased the slowest request's completion latency by 14%.

Why? The original flight had already closed, so the second request started a new flight and reused the warm prefix. The two requests then decoded concurrently rather than sequentially, changing the active batch. That may have contributed to the longer completion time.

The earlier-release policy publishes the required checkpoint itself. Extra incremental publications added little for these coordinated exact-input workloads. They remain useful without coordination, including requests that share only part of a prefix.

Publication decides when data becomes reusable. Coordination decides who waits, and for how long.

These are synthetic workloads on one backend with a small model. Exact-input coordination showed no meaningful completion-time regression for distinct inputs in this control, but the benchmark does not establish behavior under production traffic. Some future directions are:

The release change also exposed a design problem in the coordinator itself.

AI helped implement these features. As in my first article, reviewing its designs was part of building a system I could understand and maintain.

Initially, AI deleted a flight when it released the followers, which seemed reasonable because the waiting had ended.

But the first single-flight benchmark exposed a problem: followers later completed and notified the coordinator that no longer recognized their IDs. AI proposed removing the unknown-request check.

I rejected that fix because it would also hide termination notifications carrying genuinely invalid request IDs. The original design had no FlightState. To preserve validation, we added Active and Draining states and tracked released followers until they terminated. Here is that first revision, with methods omitted:

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

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

The leader had already finished, so Draining tracked only the released followers.

Earlier release made that representation more complicated. The leader could now still be decoding after followers were released. AI retained the same Flight fields but changed the enum:

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

The optional leader made me . Different release policies required different combinations. If a policy should not retain a leader but the state contained one, would we need another check?

I took a step back: did we really need a Draining state? We had added it to recognize released requests when they eventually terminated. That required remembering their IDs, but not preserving their former flight membership. Why not collect those IDs separately across flights?

I asked AI to separate those responsibilities. We 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, we remove the flight and its indexes, keeping only the IDs of requests that have not yet terminated. This preserves termination validation without retaining leader/follower relationships that no longer affect execution. Unknown request IDs still produce errors, and a new request with the same prompt starts a new flight.

AI preserved validation once I challenged the deletion. Later, it kept extending that solution until I questioned the abstraction itself.

Human review meant both preserving an invariant and reconsidering the structure used to enforce it. The benchmark showed when requests could stop waiting. Reviewing the code showed when the flight could stop existing.