# LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference

arXiv: https://arxiv.org/abs/2509.15515 · HTML: https://mlsanity.com/paper/2509.15515/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 19 Sep 2025.

## Builds on (most cited first, 6 of 6)

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)

## Built on by (most cited first, 1 of 1)

- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)

## Abstract (arXiv)

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(√MNT) bound, improving the coefficient of √MN compared to the O(MN√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%.