acceptodds
Under review as a conference paper at ICLR 2027

Quality-Aware Cross-Model Computation Reuse

Abstract

An intermediate result computed by one model can be reused by other models to perform their tasks. Existing work mainly focuses on practical execution, leaving a theoretical gap in optimizing reuse decisions. This optimization faces two challenges: quality uncertainty, because the effect of reuse on task quality is uncertain across models, and coupled scheduling, because tasks need to share the cost of preparing reusable results. These challenges compound each other: quality must be learned online, but the shared preparation structure makes scheduling NP-hard even with known quality, breaking the key assumption in existing methods. We formulate cross-model computation reuse as an online decision problem and develop the Quality-Aware Reuse Scheduling (QARS) algorithm to address it. For quality uncertainty, QARS learns task-dependent reuse quality from selected, possibly delayed feedback and uses optimistic estimates to guide decisions. For coupled scheduling, it jointly chooses which results to prepare and which tasks should use them, adapting scheduling accuracy to the remaining quality uncertainty. For the considered problem, our analysis separates learning and optimization error in regret and quantifies the tradeoff between scheduling accuracy and computation. Completing the quality-aware stopping rule yields regret while preserving feasibility. Experiments demonstrate the effectiveness of QARS in optimizing cross-model reuse, reducing the combined cost of computation and quality loss by up to 18.0%, and mean regret by 63.9% over the strongest scheduling baseline.

Primary area:
learning theory
Keywords:
Online Scheduling, Cross-Model Computation Reuse, Online Learning

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_J9AVOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper looks at quality-aware cross-model computation reuse in LLM serving, where the reuse quality is not known in advance and different tasks may share some preparation costs. The authors formulate it as an online optimization problem and propose QARS, which combines confidence-based quality estimation with joint preparation and assignment scheduling. One interesting part is the quality-aware stopping rule, which tries to balance the scheduling accuracy and the uncertainty from learning. The paper also provides regret analysis and experiments showing better quality-aware cost and scheduling efficiency compared to several baselines.

Critical strengths
  1. The problem is meaningful and quite practical. Considering uncertain reuse quality together with shared preparation costs makes sense, and it captures some important challenges in cross-model computation reuse that are often overlooked.

  2. I think the quality-aware stopping rule is an interesting part of the paper. It connects the optimization gap with the uncertainty in quality estimation, so the scheduler doesnt need to spend too much computation when the current solution is already good enough given what has been learned.

  3. The paper provides a fairly complete theoretical analysis, including hardness results, regret bounds and scheduling complexity. The experiments also shows consistent improvements over the baselines, which supports the usefulness of the proposed approach.

Critical weaknesses
  1. My main concern is about the experimental evaluation. Most of the regret results are based on a semi-synthetic simulator fitted using LLM outputs, and the linear quality assumption is basically satisfied by construction. This makes the results a bit less convincing, since its not clear how well QARS would work with real online LLM feedback, especially when the quality model is not exactly linear.

  2. Another concern is the regret benchmark. It compares against the per-epoch optimal decision under the same observed state, but doesnt really consider how current preparation decisions may change future reuse opportunities. In practical caching or computation reuse systems, these decisions can have longer-term effects. So I think the current regret guarantee might not fully reflect the actual long-term performance of the system.

Questions for authors
  1. What is the real performance of QARS in real-world LLM deployment?

  2. Please consider how current preparation decisions may change future reuse opportunities?

4 comments
AuthorsOpenReview ↗

Official Comment by Authors

We sincerely appreciate your constructive feedback. We hope the responses and revisions below address your concerns, and we welcome any further questions.


Q1: My main concern is about the experimental evaluation. Most of the regret results are based on a semi-synthetic simulator fitted using LLM outputs, and the linear quality assumption is basically satisfied by construction. This makes the results a bit less convincing, since it's not clear how well QARS would work with real online LLM feedback, especially when the quality model is not exactly linear.

A1: Thank you for this constructive feedback. We have added experiments with real LLM feedback on held-out documents (Appendix I, Table I.1). We explain our evaluation design, new results, and extensions to richer quality models below.

  1. Original semi-synthetic evaluation. Our original experiments use a semi-synthetic evaluation to enable exact regret calculation and controlled comparisons across resource capacities, workload sizes and scheduling deadlines. The quality models are fitted to real Qwen answer losses on four public QA datasets, and computation costs are calibrated from measured prefill and decode times (Appendix H).
  2. Real LLM feedback. We added experiments using measured LLM answer losses on held-out documents, keeping the learner unchanged and revealing only feedback from each method’s selected assignments. As shown in Table I.1, QARS achieves the lowest realized quality-aware cost on all four datasets, with reductions of 10.6–14.1% relative to UCB-LocalSearch. These results support its effectiveness beyond linearly generated feedback on the tested workloads.
  3. Linear modeling and extensions. We adopt route-specific linearity as a tractable starting point for efficient quality estimation and confidence bounds [1]. Related LLM-routing work, such as PILOT, also uses linear reward models [2]. As noted in Footnote 2, generalized linear [3] and neural [4] bandits offer richer quality models. These extensions would retain the joint scheduling formulation while replacing the learner and adapting the stopping tolerance to valid confidence bounds for conditional expected losses.
Table I.1. Objective per task under real LLM feedback (lower is better). Settings as in Section 6.
MethodQuALITYQASPERMultiRCRACE
QARS206.65105.3041.399.77
UCB-LocalSearch234.20121.8046.2811.38
Point Estimate250.63128.6047.8512.83
NU239.50149.3151.0414.81
QARS improvement over best baseline (%)11.813.510.614.1

References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.
[2] P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma. Adaptive LLM Routing under Budget Constraints. Findings of EMNLP 2025, pp. 23934–23949.
[3] B. Howson, C. Pike-Burke, and S. Filippi. Delayed Feedback in Generalised Linear Bandits Revisited. AISTATS 2023.
[4] M. Moghimi, S. T. Jose, and S. Moothedath. Neural Contextual Bandits Under Delayed Feedback Constraints. In 2025 IEEE 64th Conference on Decision and Control (CDC), 2026.

AuthorsOpenReview ↗

Official Comment by Authors

Q2: Another concern is the regret benchmark. It compares against the per-epoch optimal decision under the same observed state, but doesn't really consider how current preparation decisions may change future reuse opportunities. In practical caching or computation reuse systems, these decisions can have longer-term effects. So I think the current regret guarantee might not fully reflect the actual long-term performance of the system.

A2: Thank you for this constructive comment. We have further clarified the effects of current decisions on future reuse and the scope of the regret benchmark in Section 3.2. We explain these mechanisms and the planning extension below.

  1. Retained results support future reuse. Preparing result gg at epoch tt incurs Fg,tF_{g,t}. If retained, its preparation cost becomes Fg,t+1=0F_{g,t+1}=0, allowing later compatible requests to reuse it without another preparation charge. QARS uses these updated costs and available results to guide future decisions.
  2. Regret measures how well QARS learns and schedules. Under the stated conditions, sublinear regret means QARS’s average cost gap to the known-quality optimum under the same observed states tends to zero. This guarantee does not compare policies that create different future reuse opportunities.
  3. Preparation planning can account for future savings. QARS currently evaluates new preparations using the current epoch’s objective. A promising extension would anticipate future requests and result retention, and optimize cumulative quality-aware cost along the states created by each policy. We have expanded this discussion in Section 7.

Q3: What is the real performance of QARS in real-world LLM deployment?

A3: Thank you for highlighting this important point. For experimental validation, we have added experiments with measured LLM feedback, where QARS reduces quality-aware cost by 10.6–14.1% relative to UCB-LocalSearch across four QA datasets (Appendix I, Table I.1). For deployment, Section 3.1 (Figure 2) presents our design for using QARS as the reuse scheduler in LLM serving systems supported by engines such as vLLM or SGLang. For end-to-end performance, evaluating latency and throughput in large-scale deployments remains future work (Section 7).


Q4: Please consider how current preparation decisions may change future reuse opportunities?

A4: Thank you for this suggestion. Current preparation decisions affect future reuse opportunities: later compatible requests can reuse a prepared result without another preparation charge if it remains available. QARS uses these savings to guide future decisions, while evaluating new preparations for current tasks. Planning preparation for future savings is a promising extension that could explicitly model request arrivals and retention. We have clarified this distinction in Section 3.2 and expanded the discussion in Section 7.


We hope these clarifications and additional results address your concerns, and we would be happy to clarify any remaining points.

Reviewer_J9AVOpenReview ↗

I maintain the original score

The additional experiments with real LLM feedback are helpful and partially address my concerns, and the further discussion on future reuse is also useful. Overall, I'm happy to maintain my current score.

AuthorsOpenReview ↗

Thank you for your follow-up

Thank you for your thoughtful follow-up and continued support. We are glad that you found the experiments with real LLM feedback helpful and the discussion of future reuse useful. Your feedback has helped us strengthen the empirical evaluation and clarify the scope of our guarantees. We would be happy to provide any further clarification you may find helpful.

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

Motivated by computation reuse for efficiency in LLM systems, this paper develops a theoretical framework for cross-model reuse—the task of deciding what intermediate results to compute, and how they can be shared across different models and tasks. The authors formulate cross-model reuse as an online decision-making problem in which (1) reuse utility for different tasks is unknown and must be learned from delayed feedback, and (2) when utilities are known, myopic optimization determines the best reuse strategy. Their proposed algorithm, quality-aware reuse scheduling (QARS), achieves sublinear regret for this problem under a linear model of reuse quality. Moreover, QARS is efficiently computable when the underlying candidate result-sharing structure among tasks is sufficiently simple. Semi-synthetic experiments based on four question-answering datasets show that QARS improves the tradeoff between computation cost and answer quality relative to the baseline reuse strategies.

Critical strengths

The proposed theoretical framework captures two important features of cross-model reuse: intermediate results have different (initially unknown) utility across tasks, and the reuse decisions must be coordinated among tasks since the cost of producing an intermediate result is only incurred once. These two components alone are enough to make the problem non-trivial (e.g., the authors show via a reduction from set cover that shared costs make computing optimal reuse in a single time period NP-hard). Moreover, QARS jointly optimizes both components in an intuitive way, first estimating qualities from available delayed feedback, then directly optimizing reuse based on these quality estimates.

Critical weaknesses

One of the main motivations for reuse in LLM systems (e.g. prefix caching, etc.) is the idea that doing extra work now can lead to efficiency gains in the future. Although the proposed framework explicitly allows prepared results to persist across time steps, QARS’ optimization objective (and subsequent regret bound) accounts only for reuse savings in the current time step, rather than across future decisions. As a result, QARS achieving sub-linear regret does not necessarily imply effective reuse over time. Consider the following simple example: a single question arrives in each time step with a cost of 2 to answer from scratch. One intermediate result can serve each question at cost 1, but costs 3 to initially prepare. Under the proposed reuse model, a policy that answers each question from scratch achieves zero regret despite incurring an excess cost of T−3T-3 over a policy that computes the result once then reuses it across all TT time steps.

Questions for authors

• The theory relies on a strong assumption that reuse quality is a linear function of context and leaves weakening this assumption to future work. To what extent does this assumption hold in practice for LLM systems? Namely, how does QARS’ performance change in experiments if rather than constructing synthetic reuse qualities to exactly satisfy this theory assumption, reuse quality is measured directly from LLM performance on a held-out validation set? This would help to better understand if the reported gains are limited to a narrow setting, or generalize to the types of (potentially non-linear) reuse qualities encountered in practice.

• Can QARS account for the long-term value of preparation decisions when taking actions? If not, is it possible to modify the long-term scheduling problem P\mathbb{P} to capture this behavior, or could you clarify the types of real-world reuse problems you intend to model where myopic optimization is the appropriate choice?

5 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for your insightful feedback. Our responses are as follows, which we hope could well address your concerns. We also welcome any further questions.


Q1: One of the main motivations for reuse in LLM systems (e.g. prefix caching, etc.) is the idea that doing extra work now can lead to efficiency gains in the future. Although the proposed framework explicitly allows prepared results to persist across time steps, QARS' optimization objective (and subsequent regret bound) accounts only for reuse savings in the current time step, rather than across future decisions. As a result, QARS achieving sub-linear regret does not necessarily imply effective reuse over time. Consider the following simple example: a single question arrives in each time step with a cost of 2 to answer from scratch. One intermediate result can serve each question at cost 1, but costs 3 to initially prepare. Under the proposed reuse model, a policy that answers each question from scratch achieves zero regret despite incurring an excess cost of T−3T-3 over a policy that computes the result once then reuses it across all TT time steps.

A1: Thank you for this insightful comment. We would like to clarify how QARS uses updated costs and accumulated quality feedback from earlier decisions to guide future decisions. In this context, the example above highlights the value of planning new preparations for future savings, beyond what our current per-epoch objective optimizes. We have expanded Section 3.2 to clarify these mechanisms and the regret benchmark, and added a discussion of this extension in Section 7.

  1. Current decisions affect future costs. Preparing result gg at time step tt costs Fg,tF_{g,t}. If retained, Fg,t+1=0F_{g,t+1}=0, so later requests can reuse it without paying for preparation again. These costs are known before each decision from profiling and result availability. QARS uses these updated costs to benefit from earlier preparations. The example above highlights a further question: whether to prepare a result now for future savings. Our current per-epoch objective does not account for those future savings. We discuss extending QARS to anticipate future reuse in our response to Q3.
  2. Learning improves future decisions. In addition to benefiting from earlier preparations, QARS uses accumulated feedback to learn the unknown quality parameter θ⋆\theta^\star and guide future preparation and assignment decisions. It combines this learning with joint scheduling to address the NP-hard scheduling problem in each epoch. Under the stated conditions, our sublinear regret guarantee implies a vanishing average cost gap to the known-quality optimum under the same observed states [1, 2]. This guarantee does not compare policies that induce different future reuse states. The per-epoch objective also captures savings from joint preparation and assignment within a batch, as illustrated in Appendix B.3 and discussed in A3.

References
[1] W. Chen, Y. Wang, and Y. Yuan. Combinatorial Multi-Armed Bandit: General Framework and Applications. ICML 2013.
[2] K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K. Kawarabayashi. Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions. AAAI 2021.

AuthorsOpenReview ↗

Official Comment by Authors


Q2: The theory relies on a strong assumption that reuse quality is a linear function of context and leaves weakening this assumption to future work. To what extent does this assumption hold in practice for LLM systems? Namely, how does QARS' performance change in experiments if rather than constructing synthetic reuse qualities to exactly satisfy this theory assumption, reuse quality is measured directly from LLM performance on a held-out validation set? This would help to better understand if the reported gains are limited to a narrow setting, or generalize to the types of (potentially 'non-linear') reuse qualities encountered in practice.

A2: Thank you for this constructive suggestion. We have added an evaluation with real LLM feedback on held-out documents (Appendix I, Table I.1). We address each point below.

  1. Linearity provides a tractable starting point. We adopt the linear assumption for efficient quality estimation and tractable confidence bounds. Related LLM-routing work, such as PILOT, also uses linear reward models [3]. We use route-specific linearity as a starting point for our theory.
  2. QARS remains effective with real LLM feedback. We added an experiment with real LLM feedback, keeping the learner unchanged. As shown in Table I.1, QARS achieves the lowest realized quality-aware cost on all four datasets, including reductions of 11.8% on QuALITY and 13.5% on QASPER relative to UCB-LocalSearch.
  3. Gains persist beyond linearly generated feedback. The added results show that the gains persist with measured LLM feedback on the four tested datasets. For richer quality models, Footnote 2 discusses generalized linear [4] and neural [5] bandits as possible extensions. We can reuse the joint scheduling formulation, while replacing the quality learner and adapting the stopping tolerance to its valid confidence bounds for conditional expected losses.
Table I.1. Objective per task under real LLM feedback (lower is better). Settings as in Section 6.
MethodQuALITYQASPERMultiRCRACE
QARS206.65105.3041.399.77
UCB-LocalSearch234.20121.8046.2811.38
Point Estimate250.63128.6047.8512.83
NU239.50149.3151.0414.81
QARS improvement over best baseline (%)11.813.510.614.1

References
[3] P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma. Adaptive LLM Routing under Budget Constraints. Findings of EMNLP 2025, pp. 23934–23949.
[4] B. Howson, C. Pike-Burke, and S. Filippi. Delayed Feedback in Generalised Linear Bandits Revisited. AISTATS 2023.
[5] M. Moghimi, S. T. Jose, and S. Moothedath. Neural Contextual Bandits Under Delayed Feedback Constraints. In 2025 IEEE 64th Conference on Decision and Control (CDC), 2026.

AuthorsOpenReview ↗

Official Comment by Authors

Q3: Can QARS account for the long-term value of preparation decisions when taking actions? If not, is it possible to modify the long-term scheduling problem P\mathbb{P} to capture this behavior, or could you clarify the types of real-world reuse problems you intend to model where myopic optimization is the appropriate choice?

A3: Thank you for these insightful questions. We would like to clarify that QARS exploits retained results and accumulated quality feedback, while evaluating new preparations by their benefit to the current tasks. Explicitly planning new preparations for future savings is a promising extension. We explain these points below.

  1. Reuse and learning guide future decisions. As explained in A1, retained results have zero preparation cost in later epochs, and accumulated feedback informs subsequent quality estimates. QARS uses this information to guide decisions, while evaluating new preparations by their benefit to the current tasks.
  2. Planning preparation for future reuse. One possible extension adjusts the scheduling cost to F~g,t=max⁡({Fg,t−Sg,t,0)}\tilde F_{g,t}=\max(\{F_{g,t}-S_{g,t},0)\}, where Sg,tS_{g,t} is a nonnegative estimate of cumulative savings based on past requests and quality estimates available before scheduling. This is a possible heuristic extension whose performance under the original cumulative-cost objective would require separate analysis. A state-based formulation could also model request arrivals and result retention explicitly to guide future preparation [6].
  3. Applicable workloads. QARS targets cross-model computation reuse, including shared summaries and compatible cached intermediate results. It addresses cases where reuse quality is hard to predict, such as a shared summary serving questions with different information needs. In the two-task case of Appendix B.3, native execution costs 2. Preparing a shared result for only one task raises the total cost to 2.5, while assigning both tasks to it reduces the total cost to 1.5. These savings arise within the current batch, without relying on future reuse. The measured-feedback results support its effectiveness on the tested workloads (Table I.1).

References
[6] T. Jaksch, R. Ortner, and P. Auer. Near-optimal Regret Bounds for Reinforcement Learning. JMLR, 11:1563–1600, 2010.


We hope these clarifications and additional results address your concerns, and we would be happy to clarify any remaining points.

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

This paper explores LLM cross‑model computation reuse. It proposes QARS, which addresses quality uncertainty and NP‑hard coupled scheduling via bandit‑style learning and adaptive joint scheduling, achieving O(sqrt(T)) regret. Experiments yield substantial cost and regret reductions over baselines.

Critical strengths

Rigorous theoretical treatment for cross‑model computation reuse, formulating the practical scheduling task as an online decision problem and proving its NP‑hardness. QARS separates learning and optimization errors, achieving O(sqrt(T)) regret with a quality‑aware stopping rule that adapts scheduling precision to quality uncertainty. Empirically, it notably cuts combined computation‑quality cost and regret, outperforming strong scheduling baselines under delayed feedback and shared preparation costs.

Critical weaknesses

Quality‑modelling limitation. QARS builds upon a linear bandit assumption for quality loss, restricting how task‑reuse quality can be represented. The paper acknowledges that richer models such as generalized‑linear or neural bandits are left for future work. Real‑world LLM reuse quality may exhibit complex non‑linear patterns, so the linear setup could under‑fit practical workloads and degrade estimation accuracy in complex real‑world deployments.

Experimental scope. Evaluations rely on semi‑synthetic simulation built atop four public datasets with only two Qwen model variants. Large‑scale end‑to‑end serving tests, diverse model families, and real KV‑cache cross‑model reuse scenarios are not validated. This creates a gap between simulated results and production‑grade LLM serving environments, leaving real‑world latency and throughput benefits unproven.

The proposed algorithm has practical computational trade‑offs. Though the quality‑aware stopping rule reduces overhead, the underlying scheduling problem is NP‑hard. In highly complex instances with many components and results, even the approximate RLS/GLS solvers may still incur non‑trivial computation. Deployment would require careful parameter tuning, and the overhead of confidence‑bound computation could add non‑negligible latency for high‑throughput online serving systems.

Questions for authors

na

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

We sincerely thank you for your valuable feedback. We hope our responses and revisions below address your concerns, and we welcome any further questions.


Q1: Quality-modelling limitation. QARS builds upon a linear bandit assumption for quality loss, restricting how task-reuse quality can be represented. The paper acknowledges that richer models such as generalized-linear or neural bandits are left for future work. Real-world LLM reuse quality may exhibit complex non-linear patterns, so the linear setup could under-fit practical workloads and degrade estimation accuracy in complex real-world deployments.

A1: Thank you for this constructive comment. We have expanded the discussion of the linear model in Section 3.1 and added experiments with real LLM feedback (Appendix I, Table I.1). We explain our modeling approach and experimental results below.

  1. Linear modeling and extensions. We adopt route-specific linearity as a tractable starting point for efficient quality estimation and confidence bounds [1]. Related LLM-routing work, such as PILOT, also uses linear reward models [2]. Our paper also discusses extending the quality model to generalized linear [3] and neural [4] bandits (Footnote 2). These extensions would retain the joint scheduling formulation while replacing the learner and adapting the stopping tolerance to valid confidence bounds for conditional expected losses.
  2. QARS remains effective with real LLM feedback. We added experiments using measured LLM answer losses, keeping the learner unchanged. QARS achieves the lowest realized quality-aware cost on all four datasets, with reductions of 10.6–14.1% relative to UCB-LocalSearch (Table I.1). These results support the effectiveness of the original learner beyond linearly generated feedback on the tested workloads.

References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.
[2] P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma. Adaptive LLM Routing under Budget Constraints. Findings of EMNLP 2025, pp. 23934–23949.
[3] B. Howson, C. Pike-Burke, and S. Filippi. Delayed Feedback in Generalised Linear Bandits Revisited. AISTATS 2023.
[4] M. Moghimi, S. T. Jose, and S. Moothedath. Neural Contextual Bandits Under Delayed Feedback Constraints. In 2025 IEEE 64th Conference on Decision and Control (CDC), 2026.

AuthorsOpenReview ↗

Official Comment by Authors

Q2: Experimental scope. Evaluations rely on semi-synthetic simulation built atop four public datasets with only two Qwen model variants. Large-scale end-to-end serving tests, diverse model families, and real KV-cache cross-model reuse scenarios are not validated. This creates a gap between simulated results and production-grade LLM serving environments, leaving real-world latency and throughput benefits unproven.

A2: Thank you for emphasizing the need for practical evidence. We have added an evaluation with real LLM feedback (Appendix I, Table I.1) and clarified the experimental scope in Section 6.1. We explain our evaluation design, added experiments, and deployment plans below.

  1. Original semi-synthetic evaluation. Our original experiments use a semi-synthetic evaluation to enable exact regret calculation and controlled comparisons across resource capacities, workload sizes and scheduling deadlines. The quality models are fitted to real Qwen answer losses on four public QA datasets, and computation costs are calibrated from measured prefill and decode times (Appendix H).
  2. Added experiments with real LLM feedback. We added experiments using measured LLM answer losses on held-out documents, keeping the learner unchanged. As shown in Table I.1, QARS achieves the lowest realized quality-aware cost on all four datasets, with reductions of 10.6–14.1% relative to UCB-LocalSearch.
  3. Model coverage and deployment. Our evaluation uses Qwen3.5-4B and Qwen3.5-9B, a same-family setting also studied in cross-model KV-cache reuse [5, 6]. As described in Section 3.1 (Figure 2), QARS is designed to serve as the reuse scheduler in LLM serving systems supported by engines such as vLLM or SGLang. Evaluating end-to-end latency and throughput at scale, across more model families and real KV-cache reuse scenarios, is a direction for future work (Section 7).
Table I.1. Objective per task under real LLM feedback (lower is better). Settings as in Section 6.
MethodQuALITYQASPERMultiRCRACE
QARS206.65105.3041.399.77
UCB-LocalSearch234.20121.8046.2811.38
Point Estimate250.63128.6047.8512.83
NU239.50149.3151.0414.81
QARS improvement over best baseline (%)11.813.510.614.1

References
[5] Y. Liu et al. DroidSpeak: KV Cache Sharing across Fine-tuned Model Variants. NSDI 2026.
[6] T. Heo et al. Cross-Model KV Cache Transfer in LLM Families: A Closed-Form Linear Mapping for Prefill Reuse. arXiv:2608.03893, 2026.


Q3: The proposed algorithm has practical computational trade-offs. Though the quality-aware stopping rule reduces overhead, the underlying scheduling problem is NP-hard. In highly complex instances with many components and results, even the approximate RLS/GLS solvers may still incur non-trivial computation. Deployment would require careful parameter tuning, and the overhead of confidence-bound computation could add non-negligible latency for high-throughput online serving systems.

A3: Thank you for this constructive suggestion. We have further clarified the complexity analysis and scheduling measurements in Section 5.2 and Appendix H.2. We discuss the theoretical guarantees, existing experiments, and deployment design below.

  1. Theoretical analysis bounds scheduling complexity. Under Assumption 2, Theorem 2 gives an upper bound on RLS’s computation. For a fixed rounding resolution κ and fixed limits on the numbers of tasks and results in each component, this bound grows linearly with the number of components. If scheduling stops early, QARS keeps a feasible schedule. Theorem 1 accounts for the remaining optimization error.
  2. Existing experiments demonstrate scheduling efficiency. As shown in Table H.1, quality-aware stopping reduces mean scheduling time by 58.8% compared with zero tolerance (1.770 vs. 4.291 ms per epoch). Regret remains nearly unchanged (0.785 vs. 0.787). Across 24–64 components, RLS averages 2.72 ms versus 11.55 ms for Exact DP, while achieving the same mean objective (Figure 5). Appendix H.3 also examines sensitivity to the quality weight ω.
  3. QARS is designed for deployment in LLM serving systems. Section 3.1 (Figure 2) presents our design for using QARS as the reuse scheduler in systems supported by vLLM [7] or SGLang [8]. Real-world deployment and end-to-end evaluation are future work (Section 7), including the effects of confidence computation and parameter choices on latency and throughput.

References
[7] W. Kwon et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.
[8] L. Zheng et al. SGLang: Efficient Execution of Structured Language Model Programs. NeurIPS 2024.


We hope these clarifications and additional results address your concerns, and we would be happy to clarify any remaining points.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision Summary

We thank the reviewers and the Area Chair for their time and consideration. We appreciate the reviewers' constructive suggestions and positive comments on our formulation of quality-aware reuse with shared preparation costs. We summarize the main revisions below:

  1. Experiments with real LLM feedback (Appendix I). We added experiments using answer losses measured directly from LLM outputs as feedback. In these experiments, QARS achieves the lowest quality-aware cost on all four QA datasets, 10.6–14.1% below UCB-LocalSearch.

  2. Linear quality modeling (Section 3.1). We explain why we use a separate linear quality model for each reuse route. We also discuss how richer models could retain the joint scheduling formulation, with a different quality learner and a stopping tolerance based on valid confidence bounds.

  3. Regret benchmark and joint scheduling (Section 3.2, Appendix B.3). We clarify the known-quality benchmark under the same observed state at each epoch and explain how retained results and accumulated feedback guide later decisions. The example in Appendix B.3 illustrates how joint preparation and assignment can reduce a batch's cost even when reassigning one task would increase it.

  4. Preparing for future reuse (Section 7). We discuss planning new preparations for future requests as an extension of the current per-epoch objective. We consider adjusting preparation costs based on estimated reuse savings, or modeling request arrivals and result retention to guide these decisions.

Thank you again for considering our responses and revisions. We would be happy to provide any further clarification you may find helpful.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.