acceptodds
Under review as a conference paper at ICLR 2027

CandiKV: Preserving Candidate KV State Across Selection and Continuation in LLM Workflows

Abstract

Branching LLM workflows score several candidate histories before continuing from a selected subset. Scoring has already materialized the KV state of every candidate, yet request-scoped serving separates that state from the continuation that may consume it. When selection resolves, the chosen histories return as new requests, and the engine must recover work it has just performed before their first continuation tokens. We introduce CandiKV, which treats selection as a handoff of candidate state and keeps the candidate group live until the choice is known. While selection is pending, incoming scores guide computation and KV residency toward likely continuations. After the choice, selected histories enter generation with their state and progress intact. On six reasoning and retrieval workloads, CandiKV reduces continuation TTFT by up to 90.7%. It also cuts the GPU KV byte-seconds wasted on unselected candidates by 23.7–30.5% compared with keeping every candidate resident, while regular-request TTFT changes by at most 0.33%.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
LLM serving, KV cache, branching workflows, inference scheduling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NwGmOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2(+1)
Presentation
2
Soundness
1
Read review
Paper summary

This paper targets branching LLM workflows, where multiple candidate histories are scored. CandiKV preserves candidate KV states across the selection, uses intermediate scores to prioritize KV retention and pre-selection execution. Experiments on reasoning and retrieval workloads report up to 90.7% reduction in continuation TTFT and 23.7–30.5% reduction in wasted GPU KV residency.

Critical strengths
  1. The paper is easy to follow.
  2. The evaluation demonstrates latency improvements over vLLM.
Critical weaknesses
  1. Completely missing related work discussion with closely related KV management systems. Existing systems such as KVFlow [1], Continuum [2], and TokenCake [3] already preserve and manage KV state across agent workflow rather than treating it as the request. These works are not discussed nor evaluated. This makes the contribution unclear, the paper should clarify what is fundamentally new.

[1] KVFlow: Efficient prefix caching for accelerating LLM-based multi-agent workflows

[2] Continuum: Efficient and robust multi-turn llm agent scheduling with kv cache time-to-live

[3] Tokencake: A KV-Cache-centric Serving Framework for LLM-based Multi-Agent Applications

  1. The missing related work thus results in inconvincing baseline selection. PrefillOnly appears to be a weak baseline, as it is designed for prefill-only workloads. Also, how can PrefillOnly execute decoding involved tasks? Also, it is unclear how PrefillOnly executes tasks involving decoding. Given that the vLLM baseline uses automatic prefix caching, why does the continuation still need to recompute the branch-specific context? SGLang also provides Radix Attention and is not evaluated. Related workflow-aware KV management systems [1-3] for multi-agent systems should be quantitatively evaluated.

  2. Insufficient details and end-to-end evaluation. The construction of the branching workflows is under-specified. For GSM8K and MATH-500, it is unclear whether the PRM can meaningfully distinguish the candidate solutions or how selection affects the task accuracy. For MS MARCO, important details such as the concrete workload used and candidate passage construction are missing. Moreover, the evaluation mainly reports TTFT. The paper should report end-to-end JCT across all workloads, which, as partly shown in Figure 6(c), appears to mariginal.

  3. CandiKV's effectiveness depends on score arrival order. If early candidates receive high scores but are later displaced, their retained KV and speculative computation are wasted. If the final winner is scored late, the benefit may largely disappear. The paper does not evaluate winner arrival order or resources wasted in such cases. This brings another concern that should be evaluated: multiple candidates consumes additional KV memory, which may impact end-to-end perfformance under high QPS. Will the system be robust to such cases? I suggest evaluating these effects across different score arrival patterns and serving workload configurations.

Questions for authors

See Weaknesses. I do not expect that the concerns above can be fundamentally addressed through a rebuttal, but I believe the paper could be improved by addressing them in a future revision.

4 comments

We thank the reviewer for the careful reading and the suggestions on related KV management systems and baseline comparisons. And we have revised the paper in light of this feedback.

W1.

  • CandiKV manages candidate histories jointly before the selected subset is known. KVFlow, Continuum, and TokenCake use workflow information to improve KV management. CandiKV focuses on candidates governed by the same selection decision. For example, eight partial solutions to one problem occupy the same position in the workflow, but only two continue. Their execution distance can be identical even as incoming scores change the value of retaining each history. KVFlow primarily uses execution distance to manage fixed prefixes, Continuum sets retention time based on tool-call duration, and TokenCake allocates capacity using agent criticality and tool events. These signals are useful, but do not directly express the changing trade-off among candidates as scores arrive. We have added these works to the related-work discussion and clarified this distinction.

  • Candidate groups carry retained KV and completed work into the selected continuations. Retention reduces recomputation, pre-selection execution prepares the first token, and handoff gives prepared branches prompt access to generation. CandiKV keeps the continuation boundary, KV state, and execution progress in the same branch record, then transfers that record when selection resolves. These decisions act on the same branch record.

W2.

  • APC can reuse branch-specific context, while CandiKV also preserves the continuation boundary and execution progress. Automatic prefix caching (APC) identifies reusable histories through token matching. A cache hit can still be followed by residual computation at the boundary and a wait for engine scheduling. In the strict control with pre-selection execution disabled, retaining the boundary KV reduces post-selection prefill by about 88.2% on both workloads. Handoff alone reduces TTFT by 32.1% on GSM8K and 49.1% on NQ-Open. Cache coverage, boundary reuse, and continuation admission therefore account for different costs.

  • The gains persist at low load and against workflow-aware baselines. The table normalizes continuation TTFT p95 to vLLM with APC enabled on the same workload at the same load. Lower is better. Parentheses indicate the load multiplier.

    MethodGSM8K (0.25)GSM8K (0.90)NQ-Open (0.25)NQ-Open (0.90)
    vLLM1.0001.0001.0001.000
    SGLang1.6991.7821.0411.085
    KVFlow1.6702.4411.6461.507
    Continuum0.9780.7410.7020.583
    TokenCake1.5102.0471.4071.320
    CandiKV0.0520.0510.0290.019

    The improvements at low load show that high-load queueing does not fully explain the gap. Existing policies improve state availability, but the selected history still enters generation through the request path. CandiKV carries both its state and preparation progress across selection. This comparison evaluates KVFlow's GPU eviction policy, Continuum's publicly available retention and scheduling policy, and TokenCake's spatial management policy on a common vLLM backend. SGLang uses RadixAttention.

  • The PrefillOnly baseline uses terminal scoring followed by a new generation request. Scoring runs as a terminal one-token request, and the generation engine then decodes from the selected history. This control measures the cost of rebuilding state and starting decoding after scoring ends. The comparisons with APC, SGLang, LMCache, and the workflow-aware policies also support CandiKV's performance gains.

W3.

  • CandiKV preserves the application's selection policy and optimizes its serving cost. On the math workloads, Qwen2.5-Math generates partial solutions that end at natural reasoning-step boundaries. Skywork PRM ranks them, and the top two continue. All systems use the same candidates and selected set. Quality is evaluated on the highest-ranked selected branch, while group JCT covers all selected continuations. A partial solution's score assesses an intermediate stage of reasoning, while the final answer also depends on the subsequent continuation. PRM and random selection achieve similar final accuracy under the original setting with short partial solutions. We therefore evaluate selector quality and serving performance separately.

  • The PRM achieves higher accuracy on the harder math benchmarks using the same candidate sets. The random baseline below is the exact expected accuracy of uniformly selecting one candidate from each set.

    DatasetPRM Top1 accuracyExpected random Top1 accuracy
    AIME 202616.67%8.75%
    AMC 202554.76%42.86%

    These comparisons test selection quality and application behavior separately. In those comparisons, both systems achieve 94.6% accuracy on GSM8K 7B. With the MATH-500 continuation limit increased to 1,024 tokens, APC and CandiKV achieve 75.6% and 75.0%, respectively. These results support the serving improvements at comparable task quality.

  • The MS MARCO workload scores query–passage histories and continues from the selected history. The original serving trace takes eight passages per query from the public top1000.dev.tsv pool in their released file order. Each candidate history combines the query with one passage, and a one-token relevance score selects one history for continuation. Relevance judgments (qrels) are used only for evaluation. In a separate quality check with BM25 top-8 candidates, APC and CandiKV both achieve MRR@8 of 0.1842 and Recall@1 of 13.2%. We report the two candidate-pool protocols separately, covering both the construction of the serving trace and ranking quality with retrieved candidates. We have added these workload and candidate passage construction details to the revised paper.

  • The effect on group JCT depends on how much of the workflow is affected by continuation TTFT. CandiKV reduces recomputation and waiting after selection, while the same model performs the subsequent decoding. A large reduction in the initial wait can therefore account for a small fraction of a long task. We now report group JCT with natural EOS termination for every workload, measured from candidate-group submission until all selected continuations finish.

    Workload1.5B JCT p95 (s), APC / CandiKV7B JCT p95 (s), APC / CandiKV
    GSM8K2.905 / 2.9157.302 / 7.268
    MATH-5003.184 / 3.23210.400 / 10.422
    ARC-Challenge1.620 / 1.5935.316 / 5.342
    CommonsenseQA1.444 / 1.3444.434 / 4.385
    NQ-Open0.724 / 0.7091.896 / 1.917
    MS MARCO0.687 / 0.7061.414 / 1.403

    JCT changes range from −6.95% to +2.73%, and measured throughput changes by at most 0.31%. We also run online workflows that include actual candidate construction and scoring. End-to-end JCT falls by 4.28% on NQ-Open and changes by +0.60% on GSM8K, whose candidate generation takes much longer. The reduction in continuation TTFT remains, while its effect on end-to-end JCT depends on the share of time spent at this stage.

W4.

  • CandiKV retains its gains when the final winner is scored late. The engine takes ownership of candidate state when candidate processing finishes, before the final selected set is known. Unscored candidates remain eligible, while incoming scores allow service to stop earlier for branches that can no longer be selected. We hold the final scores and selected set fixed and vary score arrival order: winner early, winner late, random order, displacement of early leaders, and simultaneous arrival. TTFT reductions range from 94.4% to 95.0% on GSM8K and from 97.5% to 98.4% on NQ-Open. With the winner scored late, the reductions remain 95.0% and 98.0%, respectively. Early scores make preparation more selective, while state continuity provides benefits across these arrival patterns.

  • A bounded preparation budget and prompt reclamation control the resources spent on unselected candidates. Preparation before the winner is known can include work that is eventually discarded, so we measure both unselected state residency and group JCT. By default, preparation stops after one boundary output token per branch. Once scores rule a branch out, further service stops and its state is reclaimed. Across 500 groups, unselected branches account for 3,000 boundary output tokens on GSM8K and 3,500 on NQ-Open. These are counts of actual boundary outputs, with the overall compute impact assessed through JCT and mixed traffic. Compared with keeping all scoring requests open, CandiKV reduces the residency of unselected branch-specific tails by 23.3% on NQ-Open.

  • We examine continuation latency and group JCT together as candidate width and KV pressure increase. Larger WW adds scoring work for all methods and increases the amount of potentially unused state, so TTFT alone is insufficient to assess the capacity cost. The following conditions also place the final winner late in the score arrival order.

    ConfigurationGSM8K TTFT reduction / JCT changeNQ-Open TTFT reduction / JCT change
    W=8W=8, load 0.9, KV budget 25%95.75% / −4.21%97.98% / +0.92%
    W=16W=16, load 1.1, KV budget 25%94.54% / −3.43%97.98% / +0.58%
    W=32W=32, load 0.9, KV budget 100%93.32% / +1.28%97.88% / +0.69%

    These are fixed-trace pressure measurements over 500 groups. We do not use the wide-group points to claim steady-state capacity. Under mixed traffic, handoff admits only a bounded burst of selected continuations before returning to regular requests. In the added experiments, regular-request TTFT increases by at most 0.80% and TPOT by at most 1.86%, while group JCT changes by −0.25% and −0.84% on the two workloads.

Thank you for the detailed rebuttal and additional experiments. I appreciate the authors' efforts to address my concerns.

The new comparisons with related KV management systems and the additional experiments on score arrival order and KV pressure have addressed several of my original concerns. The clarification of the technical distinctions from prior work is also helpful.

However, my main concern remains the limited end-to-end benefits. Despite the significant reduction in continuation TTFT, the improvements in overall JCT and throughput remain marginal. This weakens the practical significance of the proposed system.

Another factor limiting my rating is the narrow applicability of the proposed workflow. I am not convinced that building dedicated serving infrastructure for such a specific branching pattern is reasonable. I would encourage the authors to evaluate more diverse and realistic agentic workloads to demonstrate broader applicability.

Overall, I acknowledge the improvements in the evaluation. I will raise my rating from 1 to 2. For future revisions, I would encourage deeper comparisons with closely related work and more comprehensive experiments to show end-to-end system-level improvements.

Reviewer_QoUSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CandiKV preserves candidate KV states across scoring and selection, allowing selected branches to continue without rebuilding their histories. It uses incoming scores to guide retention, speculative execution, and continuation admission.

Critical strengths
  • The candidate-group abstraction addresses a concrete waste: scoring computes KV states that selected continuations would otherwise rebuild.
  • The retention policy reduces wasted GPU KV byte-seconds by 23.7–30.5% while keeping latency close to retaining every candidate.
Critical weaknesses
  • The headline TTFT starts after selection, while CandiKV can compute the first token before selection. This measures faster delivery after the choice, but not necessarily faster workflows: group JCT changes by at most 0.95% in the mixed-traffic experiment (§5.6).
  • The retention policy depends on selection probabilities and placement costs, but their implementation remains underspecified. Appendix A.3 lists rank, margin, memory pressure, and queue slack without giving the actual probability mapping or cost coefficients.
  • Baseline behavior needs explanation. On 1.5B ARC, LMCache takes 11.3 seconds versus vLLM’s 77.1 milliseconds (Table 1). A breakdown of restoration and queueing is needed to establish that this comparison reflects a competitive host-cache configuration.
Questions for authors

Please see the weaknesses.

2 comments

We appreciate the reviewer's analysis of the latency gains, especially the relationship between post-selection TTFT and end-to-end workflow performance. And we have revised the paper in light of this feedback.

W1.

  • Post-selection TTFT and group JCT measure complementary serving objectives. After selection, KV recomputation, restoration, and rescheduling can delay the selected branch's output. CandiKV overlaps preparation with scoring and exposes output only after the branch is selected. Group JCT accounts for the full cost of that preparation. Faster delivery after selection is therefore a response-latency improvement, with its effect on workflow completion measured separately.

  • The end-to-end effect depends on the time spent constructing candidates and decoding their continuations. We measure actual candidate construction, scoring, and natural continuation together.

    WorkloadPost-selection TTFT changeChange in first-token latency from workflow startEnd-to-end JCT change
    GSM8K 7B−97.94%+0.48%+0.60%
    NQ-Open 7B−97.73%−3.80%−4.28%

    Candidate generation alone takes about 16.8 seconds on GSM8K, so the tens of milliseconds saved after selection account for a small part of the workflow. Candidate construction takes less time on NQ-Open, and the improvement is visible in both first-token latency from workflow start and end-to-end JCT. Across the natural-output comparisons, group JCT changes range from −6.95% to +2.73% and throughput changes by at most 0.31%. The results support faster delivery after selection while maintaining comparable overall serving performance.

  • Retention and continuation admission still help when speculative execution is disabled. In a strict zero-window control, we discard the scoring output and compute the first continuation token only after selection. Retaining boundary KV reduces post-selection prefill by about 88.2%, while handoff reduces TTFT by 32.1% on GSM8K and 49.1% on NQ-Open. The larger full-system reductions include the benefit of speculative execution, with state continuity and admission providing independent gains. The mixed-traffic result, where regular-request TTFT increases by at most 0.80%, also checks the impact on other requests.

W2.

  • The utility distinguishes selection probability from the value of occupying KV capacity. A high-scoring branch may be short and cheap to recompute. A long branch may be expensive to recompute but unlikely to be selected. Score-only or length-only retention can therefore waste capacity on different workloads. Their relative ordering reverses between GSM8K and NQ-Open in Figure 5 of the submission. CandiKV ranks state by expected work saved, then discounts occupancy and restoration costs.

  • Selection probabilities use a normalized rank prior, and placement costs use fixed default coefficients. Over the WW ranks, the prior is pr=min⁡(1,c/r)p_r=\min(1,c/r), with cc chosen so that the probabilities sum to KK. For tail length nin_i and APC coverage hih_i, the estimated recomputation time is F^i=ni(1−hi)τ^\widehat F_i=n_i(1-h_i)\widehat\tau. The score margin adjusts the expected benefit by the bounded factor 1+0.1tanh⁡(mi)1+0.1\tanh(m_i). The placement cost is Ci=10−9bi+L^i+5ρi+max⁡(F^i+L^i−slacki,0)C_i=10^{-9}b_i+\widehat L_i+5\rho_i+\max(\widehat F_i+\widehat L_i-\mathrm{slack}_i,0), accounting for state bytes, restoration time, memory pressure, and queue slack. Here ρi=max⁡(ei,0.75ui+0.25min⁡(qi/64,1))\rho_i=\max(e_i,0.75u_i+0.25\min(q_i/64,1)), where ei,ui,qie_i,u_i,q_i denote eviction pressure, GPU occupancy, and the number of running and waiting requests. The per-token time estimate uses weights of 0.9 for the previous estimate and 0.1 for the new observation. Restoration time is zero in the GPU-resident configuration evaluated here. We have included this mapping and these coefficients in the revised paper.

  • The gains persist under the tested estimation errors, while application selection remains unchanged. These estimates allocate memory and model service. The application scores still determine the selected set, so estimation errors affect the efficiency of retention and preparation without changing candidate histories or selection rules. We perturb the active cost terms, the prefill estimate, and the rank prior:

    PerturbationValues testedGSM8K TTFT reduction vs. APCNQ-Open TTFT reduction vs. APC
    Multiplier on all cost terms0.5, 2.094.60%–95.22%98.13%–98.16%
    Prefill-time estimate multiplier0.7, 1.394.86%–94.89%98.00%–98.08%
    Rank exponent0.5, 2.094.84%–95.45%98.00%–98.10%

    The execution-budget experiment also explains the default of preparing one boundary token. Deeper speculative execution consumes more model service once first-token preparation is nearly complete. Increasing the budget to 2 or 4 tokens raises JCT by up to 2.46% on GSM8K and 6.62% on NQ-Open. The default limits this cost while retaining the post-selection response benefit.

W3.

  • LMCache's continuation latency includes queueing beyond restoration. Its host tier improves state availability, while a continuation with restored KV still passes through submission, admission, and scheduling. The seconds-long ARC TTFT in the original table coincided with queue buildup and should not be read as the time for a single host-cache restoration. We sweep chunk sizes of 64, 128, and 256 tokens and measure restoration and queueing separately.

    ARC 1.5B configurationAPC TTFT (ms)Best tested LMCache TTFT (ms)CandiKV TTFT (ms)Retrieve p95 (ms)Engine queueing p95 (ms)
    Load 0.25, chunk 25629.8152.544.021.130.012
    Load 0.90, chunk 12849.3995.117.910.8632.23

    Restoration is already fast at low load, with additional overhead in the connector, submission, and execution path. Queueing, measured from entry into the engine queue to the first scheduling event, grows at the higher load. Each component reports its own p95, so the component percentiles are not additive.

  • CandiKV retains its advantage over both APC and the best tested LMCache configurations. Most selected-tail tokens already hit the GPU cache in these comparisons, and host restoration covers only a small fraction. Further reductions in transfer time therefore have limited room to help. CandiKV also preserves execution progress and hands the selected branch directly to generation, reducing submission and queueing costs before execution resumes. We have added the configuration details and latency breakdown to the revised paper, together with the load conditions for the original table.

Reviewer_jDFROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

Branching workflows score several candidates and then continue from a subset. Scoring has already produced their KV states, but the engine may release them before selection, forcing the selected branches to rebuild their tail KV. CandiKV keeps candidate groups alive across that interval: retain by score, do leftover prefill / first-token work while waiting, and hand selected branches into generation without the usual queue.

Impl on vLLM; one 4090D; Qwen2.5 1.5B/7B; GSM8K, MATH-500, ARC, CommonsenseQA, NQ-Open, MS MARCO; baselines PrefillOnly, vLLM prefix cache, LMCache. Authors report up to ~91% lower continuation TTFT than vLLM (from selection), less wasted GPU KV residency than retain-all, and little effect on regular traffic.

Critical strengths

1. The useful idea is that a candidate group needs to outlive the scoring request—the engine holds branch state before it knows who continues. Prefix caching and host KV mostly assume the consumer is already known. I have not seen that gap treated as a first-class serving object, and that is why I am positive on the paper.

2. Table 2 did more work for me than Table 1. Drop retention → post-selection prefill comes back; drop handoff → TTFT still hurts even when prefill is small. So retention and handoff are not the same knob.

Critical weaknesses

1. I cannot tell how much of the gain is “keep the right KV” versus “do work during the wait.” Long dd (slow verifier) favors pre-selection execution; d≈0d \approx 0 should leave mostly retention/handoff. Without gain vs dd in the main story, it is unclear what contribution I am endorsing.

2. LMCache in Table 1 often looks far worse than vLLM (e.g. GSM8K 1.5B: 7.53k vs 112 ms). Until that is explained, I discount the “strong baseline” framing. Setup is also one 4090D, ≤7B, narrow WW/KK—fine for a prototype, thin for the production tone in the intro.

After rebuttal

Thank you for the rebuttal and the additional experiments. The zero-window and tuned LMCache results give me more confidence in the paper’s soundness. In the zero-window experiment, handoff accounts for most of the latency improvement, while retaining KV mainly reduces recomputation. With a nonzero window, preparing the first token early provides an additional benefit. My remaining concerns are that end-to-end job completion time changes little and that the main evaluation uses one 4090D and models up to 7B. I am raising Soundness from 2 to 3 and keeping my overall rating at 3.

Questions for authors
  1. Please report continuation-TTFT (and, if possible, an ablation of retention / pre-selection exec / handoff) against selection-window length dd, including d≈0d \approx 0. When scores arrive together, what is left?
  2. For the LMCache rows in Table 1: host↔GPU restore time, hit rate on the selected tail, and whether LMCache got the same early group identity/hint as CandiKV or only post-selection token match. Without this I cannot trust that comparison.
  3. How are pi(t)p_i(t), Δi(a)\Delta_i(a), Ci(a,t)C_i(a,t) computed in code (formula or constants)? One sensitivity check if CiC_i is wrong would help.
  4. Under incremental scoring, can a branch with rank >K>K re-enter top-KK after a later score update? If yes, how is eligibility defined?

(Optional, not required for accept: if the app simply keeps the scoring request open until selection, which pieces of CandiKV are still necessary inside the engine?)

3 comments

We thank the reviewer for the careful reading and the specific suggestions on selection-window length, component contributions, and the LMCache comparison. And we have revised the paper in light of this feedback.

W1 / Q1.

  • At d=0d=0, retention reduces recomputation and handoff reduces queueing. With a nonzero selection window, pre-selection execution further reduces unfinished first-token work. To isolate these effects, the strict d=0d=0 control discards the scoring output and computes the first continuation token only after selection.

    ConfigurationGSM8K TTFT p95 (ms)NQ-Open TTFT p95 (ms)Post-selection prefill tokens, GSM8K / NQ-Open
    APC + FCFS163.72215.518,447 / 4,210
    APC + handoff111.18109.668,447 / 4,210
    Retained boundary KV + FCFS168.17215.291,000 / 500
    Retained boundary KV + handoff112.62109.511,000 / 500

    Retaining boundary KV reduces post-selection prefill by about 88.2%. Since APC already covers most of the history in this configuration, eliminating that residual computation has little effect on p95 under FCFS. Handoff directly reduces waiting and lowers TTFT by 32.1% and 49.1% on GSM8K and NQ-Open, respectively. Thus, the main zero-window latency gain comes from admission, while retention's independent effect is to reduce recomputation. Latency and executed work distinguish the two contributions.

  • Pre-selection execution overlaps first-token preparation with scoring, and its benefit saturates once preparation finishes. The window lengths below are set to the p25, p50, and p95 of the measured scoring durations.

    WorkloadSelection window dd (ms)APC TTFT p95 (ms)Full CandiKV TTFT p95 (ms)w/o pre-selection execution TTFT p95 (ms)
    GSM8K83.61142.577.85192.02
    GSM8K85.05142.957.01193.64
    GSM8K138.01146.477.39191.23
    NQ-Open217.51213.453.74162.37
    NQ-Open248.66191.423.24140.47
    NQ-Open354.33191.093.36143.55

    Full CandiKV can finish preparation before selection, leaving delivery and resumption on the post-selection path. Increasing dd further cannot reduce this time indefinitely. Without pre-selection execution, the remaining computation follows selection. For branches with a buffered first token, handoff also affects subsequent execution: at the p50 window, it reduces the time from selection until the engine observes the second output token by 18.2% on GSM8K and 45.6% on NQ-Open. First-token delivery alone can understate the scheduling benefit once that token is already prepared.

  • Simultaneous score arrival and a zero selection window are different conditions. Simultaneous arrival removes early rank information but leaves time during scoring to retain state and perform bounded preparation. The strict zero-window control also removes that preparation opportunity. With simultaneous scores, TTFT falls by 94.4% on GSM8K and 97.5% on NQ-Open. State continuity therefore remains useful without asynchronous score arrivals. Incremental scores additionally allow the engine to stop losing branches earlier and reduce unused residency during the wait.

W2 / Q2.

  • LMCache has a high selected-tail hit rate, but scheduling still adds substantial delay after the state is available. We sweep chunk sizes and record selected-tail hit sources and connector restore time. The table uses the lowest-TTFT configuration tested at load 0.9.

    WorkloadLMCache TTFT (ms)GPU / Host / Miss fractionsRetrieve p95 (ms)Engine queueing p95 (ms)
    ARC 1.5B95.1189.74% / 7.13% / 3.13%0.8632.23
    GSM8K 1.5B125.5092.72% / 4.00% / 3.28%0.7675.17
    NQ-Open 7B245.2395.22% / 3.88% / 0.90%1.42132.62

    Fractions are counted over selected-tail tokens. Retrieve is the restore operation recorded by the connector, and queueing is measured from entry into the engine queue to the first scheduling event. Each timing component reports its own p95. Low recomputation and fast restore still leave continuation admission on the path. CandiKV achieves TTFTs of 7.91, 8.16, and 3.40 ms, respectively, retaining its gains in these tuned comparisons.

  • Early candidate-group information is part of CandiKV's interface, while LMCache uses post-selection token matching. APC and LMCache do not receive the same early group identity or score hints. They identify reusable histories when continuations are submitted. CandiKV receives candidate-group identity and scores as they arrive, but does not know the final winner before selection is complete. The KVFlow, Continuum, and TokenCake comparisons also receive group/candidate metadata and have no access to future selected IDs.

  • The width and KV-budget sweeps test whether the gains are confined to small candidate groups. Increasing WW from 8 to 32 adds candidates and potentially unused state while only KK branches continue. A smaller KV budget further increases the opportunity cost of retention. At the W=32W=32 pressure points with late-scored winners, TTFT still falls by 93.3% on GSM8K and 97.9% on NQ-Open, with JCT changes of +1.28% and +0.69%, respectively. These are fixed-trace pressure results.

Q3.

  • These estimates guide resource allocation, while application scores determine the selected set. The runtime estimates pi(t)p_i(t) from the rank prior pr=min⁡(1,c/r)p_r=\min(1,c/r), normalized over the WW ranks to sum to KK. To estimate Δi(a)\Delta_i(a), it uses the recomputation time F^i=ni(1−hi)τ^\widehat F_i=n_i(1-h_i)\widehat\tau and adjusts the expected benefit by the margin factor 1+0.1tanh⁡(mi)1+0.1\tanh(m_i). The cost is Ci(a,t)=10−9bi+L^i+5ρi+max⁡(F^i+L^i−slacki,0)C_i(a,t)=10^{-9}b_i+\widehat L_i+5\rho_i+\max(\widehat F_i+\widehat L_i-\mathrm{slack}_i,0), accounting for occupancy, restore time, resource pressure, and SLO slack. Restore time is zero in the GPU-resident experiments. We have added the signal definitions, default coefficients, and online update rules to the appendix.

  • The gains persist under the tested cost and prior errors. Halving or doubling the cost terms still reduces TTFT relative to APC by 94.6%–95.2% on GSM8K and 98.1%–98.2% on NQ-Open. Changing the prefill estimate by ±30% or the rank exponent to 0.5 and 2 also preserves similar gains. Estimation errors affect which states receive resources first, while history matching and final selection follow the same rules. Correct workflow execution therefore does not require perfectly calibrated selection probabilities.

Q4.

  • A scored branch outside top-KK cannot re-enter under the selector used here. Each candidate's score is fixed once emitted. Incremental scoring reveals scores for more candidates. Once a branch's observed rank exceeds KK, at least KK candidates with fixed scores already precede it. Later score arrivals cannot change that fact. This is a deterministic elimination rule and does not predict future scores.

  • Unscored branches remain eligible, while retention determines where their KV state resides. The eligible set contains all unscored branches and the current top-KK among scored branches. A candidate is therefore not ruled out simply because its score has not arrived. Resource pressure can still affect its placement, with standard restore or recomputation available if needed. Section 4.2 and Appendix A.2 already state this property.

Optional.

  • Keeping scoring requests open provides state continuity, while candidate-group policies determine how that lifetime uses resources. With enough capacity, keeping requests open avoids some state reconstruction and should be a competitive control. The NQ-Open experiment supports this: keep-open and CandiKV achieve post-selection TTFTs of 3.29 and 3.56 ms. CandiKV maintains nearly the same residency for selected branch-specific tails while reducing residency for unselected tails by 23.3%. The reduction is 23.4% at a 25% KV budget.

  • Keeping requests open still leaves resource allocation among candidates and post-selection scheduling to be decided. The application must determine which states continue to occupy capacity, which branches can stop, and how selected continuations share service with regular traffic. Candidate-group records associate these decisions with the same selection event, allowing state continuity to work under shared capacity and mixed traffic. Residency integrates branch-specific tail bytes over the interval from pause until resume or release. Physical KV occupancy is reported separately.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the discussion and the revision

Dear Area Chair,

Thank you for handling our submission. We also thank the reviewers for their careful reading and constructive suggestions, which helped us strengthen the evaluation and clarify CandiKV’s contribution and scope. As the discussion period draws to a close, we would like to summarize the main concerns raised and the evidence we added in response.

The main concerns fell into four groups.

  1. Related work and baseline comparisons (NwGm, QoUS, jDFR). The reviewers requested distinctions from workflow-aware KV systems, additional baselines, and an explanation of LMCache’s latency.
  2. Practical significance and task quality (NwGm, QoUS). The reviewers requested full-workflow JCT, workload details, and evidence of selection quality.
  3. Attribution of the gains (QoUS, jDFR). The reviewers requested experiments separating retention, pre-selection execution, and handoff across selection-window lengths, including a strict zero-window setting.
  4. Policy implementation and resource behavior (NwGm, QoUS, jDFR). The reviewers asked for policy definitions, sensitivity checks, and tests of score arrival order, candidate width, and KV pressure.

We addressed the reviewers’ main concerns through additional experiments, measurements and clarifications.

  1. Added baseline comparisons and clarified the additional contribution. We added SGLang and comparisons with the KV-management policies of KVFlow, Continuum, and TokenCake. CandiKV jointly manages histories governed by the same selection decision and carries their KV state, continuation boundary, and preparation progress into generation. On GSM8K and NQ-Open, CandiKV reduces continuation TTFT p95 by approximately 93–97% relative to Continuum across low and higher loads. The gains reflect continuity of both KV state and execution progress across selection. We also added LMCache chunk-size sweeps, selected-tail hit measurements, and restoration and queueing breakdowns. Even with fast restoration, admission and scheduling still add substantial delay.

  2. Added evidence on full-workflow performance and task quality. We reported natural-completion JCT for all workloads and online runs covering candidate construction, scoring, and continuation. The online NQ-Open workflow completes 4.28% faster. On GSM8K, candidate generation dominates completion time, and JCT changes by +0.60%. CandiKV reduces the delay before a selected history resumes. Its effect on JCT depends on this delay’s share of total runtime. Measured throughput changes by at most 0.31% across the natural-completion comparisons. Both systems achieve 94.6% accuracy on GSM8K 7B, with comparable accuracy on MATH-500. Additional AIME and AMC experiments show that the PRM selects more accurate candidates than random selection. We also clarified candidate construction and the MS MARCO passage-pool protocol.

  3. Separated the effects of retention, pre-selection execution, and handoff. In the strict zero-window control, pre-selection execution is disabled and the first continuation token is computed only after selection. Retaining boundary KV reduces post-selection prefill by approximately 88.2%, while handoff reduces TTFT by 32.1% on GSM8K and 49.1% on NQ-Open relative to vLLM with automatic prefix caching. These experiments identify independent benefits without speculative execution. Selection-window sweeps further show how preparation overlaps scoring and saturates once first-token preparation is complete. Second-token measurements show that handoff also accelerates subsequent execution.

  4. Specified the policy and extended the resource evaluation. We added the probability mapping, cost coefficients, online update rules, eligibility definitions, and sensitivity experiments. Unscored candidates remain eligible, and fixed scores permit prompt reclamation once a branch can no longer enter the selected set. The gains persist with late winners, displacement of early leaders, and simultaneous score arrival. With 32 candidates and a late-scored winner, continuation TTFT falls by 93.3% on GSM8K and 97.9% on NQ-Open relative to vLLM. Separate KV-budget experiments examine tighter capacity. In the added mixed-traffic experiments, regular-request TTFT increases by at most 0.80% and TPOT by at most 1.86%. A keep-open control also shows similar continuation latency while CandiKV reduces unselected-tail residency by 23.3%.

CandiKV extends an existing serving engine with a candidate-group interface shared by reasoning and retrieval workflows, while preserving each application’s selection policy. We believe these clarifications and experiments on latency, full-workflow performance, task quality, and resource use strengthen the case for accepting CandiKV. We thank the reviewers and the Area Chair again for their time and careful consideration.

Best regards,

Authors of Submission 23577

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.