<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="yang-etal-2026-llm-cache">
    <titleInfo>
        <title>LLM Cache Bandits with Query Heterogeneity for Cost-Efficient Inference</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Hantao</namePart>
        <namePart type="family">Yang</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Hong</namePart>
        <namePart type="family">Xie</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Xutong</namePart>
        <namePart type="family">Liu</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Defu</namePart>
        <namePart type="family">Lian</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2026-10</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Hung-Yi</namePart>
            <namePart type="family">Lee</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Sunipa</namePart>
            <namePart type="family">Dev</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Jessy</namePart>
            <namePart type="family">Li</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Desmond</namePart>
            <namePart type="family">Elliott</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Budapest, Hungary</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
        <identifier type="isbn">979-8-89176-459-0</identifier>
    </relatedItem>
    <abstract>This paper revisits the LLM cache bandit problem, with a special focus on addressing query heterogeneity for cost-effective LLM inference. Previous works often assume uniform query sizes. Heterogeneous query sizes introduce a combinatorial structure into 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 our theoretical analysis, we prove that the regret of our algorithm achieves an O(\sqrtMNT) bound, improving the coefficient of \sqrtMN compared to the O(MN\sqrtT) result in Zhu et al. (2023), 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. Experiments on real-world data show that our algorithm reduces the total cost by approximately 12%.</abstract>
    <identifier type="citekey">yang-etal-2026-llm-cache</identifier>
    <location>
        <url>https://aclanthology.org/2026.emnlp-main.1849/</url>
    </location>
    <part>
        <date>2026-10</date>
        <extent unit="page">
            <start>42054</start>
            <end>42087</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T LLM Cache Bandits with Query Heterogeneity for Cost-Efficient Inference
%A Yang, Hantao
%A Xie, Hong
%A Liu, Xutong
%A Lian, Defu
%Y Lee, Hung-Yi
%Y Dev, Sunipa
%Y Li, Jessy
%Y Elliott, Desmond
%S Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-459-0
%F yang-etal-2026-llm-cache
%X This paper revisits the LLM cache bandit problem, with a special focus on addressing query heterogeneity for cost-effective LLM inference. Previous works often assume uniform query sizes. Heterogeneous query sizes introduce a combinatorial structure into 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 our theoretical analysis, we prove that the regret of our algorithm achieves an O(\sqrtMNT) bound, improving the coefficient of \sqrtMN compared to the O(MN\sqrtT) result in Zhu et al. (2023), 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. Experiments on real-world data show that our algorithm reduces the total cost by approximately 12%.
%U https://aclanthology.org/2026.emnlp-main.1849/
%P 42054-42087

Markdown (Informal)

[LLM Cache Bandits with Query Heterogeneity for Cost-Efficient Inference](https://aclanthology.org/2026.emnlp-main.1849/) (Yang et al., EMNLP 2026)

• LLM Cache Bandits with Query Heterogeneity for Cost-Efficient Inference (Yang et al., EMNLP 2026)

ACL

• Hantao Yang, Hong Xie, Xutong Liu, and Defu Lian. 2026. LLM Cache Bandits with Query Heterogeneity for Cost-Efficient Inference. In Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing, pages 42054–42087, Budapest, Hungary. Association for Computational Linguistics.