解决大模型查询大小不一的缓存问题，降低推理成本12%。
LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference
- 将缓存选择建模为背包问题，用累积策略平衡开销与更新。
- 理论证明算法后悔界为O(√MNT)，优于此前方法的O(MN√T)。
- 适用于大规模部署中需降低成本的LLM推理场景。
本文重新审视大模型缓存强化学习问题，重点关注查询大小异构带来的挑战。以往研究常假设查询尺寸一致，而实际中查询大小差异会引入复杂的组合结构，使缓存替换在计算和统计上更困难。本文将最优缓存选择视为一个背包问题，采用基于累积的策略，有效平衡计算开销与缓存更新频率。理论分析表明，所提算法的后悔界为O(√MNT)，相比伯克利工作中的O(MN√T)在√MN项系数上得到改进，且首次提供了依赖问题的后悔界。实验基于真实数据集，结果表明该方法可降低总推理成本约12%。
原文摘要 · Abstract (English)
This paper revisits the LLM cache bandit problem, with a special focus on addressing the query heterogeneity for cost-effective LLM inference. Previous works often assume uniform query sizes. Heterogeneous query sizes introduce a combinatorial structure for cache selection, making the cache replacement process more computationally and statistically challenging. We treat optimal cache selection as a knapsack problem and employ an accumulation-based strategy to effectively balance computational overhead and cache updates. In theoretical analysis, we prove that the regret of our algorithm achieves an $O(\sqrt{MNT})$ bound, improving the coefficient of $\sqrt{MN}$ compared to the $O(MN\sqrt{T})$ result in Berkeley, where $N$ is the total number of queries and $M$ is the cache size. Additionally, we also provide a problem-dependent bound, which was absent in previous works. The experiment rely on real-world data show that our algorithm reduces the total cost by approximately 12\%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。