Technische Samenvatting: SAECache – Semantisch Bewuste Verwijdering voor LLM Prefix Caches

Probleemstelling

Prefix caching in Large Language Models (LLM's) heeft tot doel de inferentielatentie (specifiek Time-to-First-Token, of TTFT) te verlagen door Key-Value (KV) toestanden opnieuw te gebruiken van verzoeken die invoer-prefixen delen. De effectiviteit van prefix caching wordt echter ernstig beperkt door het beperkte GPU-geheugen, wat een verwijderingsbeleid noodzakelijk maakt om minder waardevolle blokken te verwijderen wanneer de capaciteit is bereikt.

Bestaande verwijderingsbeleid, zoals Least Recently Used (LRU) en Least Frequently Used (LFU), vertrouwen voornamelijk op toegangstijd- of frequentiestatistieken. Deze token-onafhankelijke benaderingen behandelen alle gecachete blokken uniform, waarbij ze twee kritieke dimensies van LLM-werklasten negeren:

1. Semantische Heterogeniteit: Verschillende tokentypen (bijvoorbeeld systeemprompt versus redenering in een chain-of-thought) vertonen sterk verschillende intrinsieke hergebruikstijden.
2. Werklastvariabiliteit: Hergebruikspatronen verschillen aanzienlijk tussen single-turn getemplateerde verzoeken (structureel hergebruik) en multi-turn gesprekken (sessielokaal temporair hergebruik), waarbij de intervallen tussen opeenvolgende beurten verschillende verdelingen volgen voor verschillende applicatietypen (bijvoorbeeld chat versus agentische workflows).

De auteurs observeren dat het behandelen van een hoogwaardig systeemprompt-blok en een laagwaardig chain-of-thought-blok als equivalent wanneer hun recentie overeenkomt, leidt tot suboptimale geheugentoewijzing. Bovendien falen beleid met vaste parameters wanneer de samenstelling van de werklast verschuift, wat resulteert in een prestatiedegradatie van tot wel 2,7× bij een mismatch in werklast.

Methodologie: SAECache

Om deze beperkingen aan te pakken, stellen de auteurs SAECache (Semantic-Adaptive Eviction for prefix caches) voor, een beleid dat token-semantische structuur integreert met online aanpassing van de werklast. Het systeem werkt via drie kernmechanismen:

1. Multi-Queue Architectuur met Regelgebaseerde Routing

SAECache routeert KV-blokken naar vier verschillende wachtrijen op basis van hun dominante hergebruikspatronen, in plaats van één enkele globale wachtrij:

• Evict-First Queue: Bewaart laagwaardige blokken, waaronder decode-fase tokens en niet-getemplateerde prefill-blokken met weinig hergebruikspotentieel. Deze worden eerst geleegd.
• Structural Queue: Bewaart KV-blokken van single-turn sessies die vertrouwen op gedeelde promptstructuren (bijvoorbeeld tool-gebruik templates, programmeerinstructies).
• Chat Queue: Bewaart multi-turn blokken van conversatiesessies, waarbij sessielokaal temporair hergebruik wordt gemodelleerd.
• Agentic Queue: Bewaart multi-turn blokken van agent/tool-gebruik sessies, die verschillend zijn in tokeninhoud en verdelingen van verzoekintervallen in vergelijking met standaard chat.

Een lichtgewicht multi-turn sessiepredictor (een 3-laags MLP dat de laatste verborgen toestanden van het dienende model hergebruikt) lost ambiguïteit op voor het eerste verzoek van een sessie, en routeert dit naar de juiste multi-turn wachtrij als voortzetting wordt voorspeld, of anderszins naar de structurele/evict-first wachtrijen.

2. Lokale Prioriteitscore

Binnen elke wachtrij worden blokken gescoord op verwijdering op basis van een samengestelde metriek $P(b)$:
$$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$$

• $\alpha_q$ (Wachtrijgewicht): Een dynamisch gewicht dat de recente hit-efficiëntie van de specifieke wachtrij weerspiegelt.
• $w_{\tau(b)}$ (Tokentype-gewicht): Een geleerd gewicht specifiek voor het tokentype (bijvoorbeeld systeemprompt, gebruikersvraag, chain-of-thought) van het blok.
• $p_q(b)$ (Lokale Overlevingskans):
  • Voor Chat/Agentic wachtrijen: Berekend als de overlevingskans $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ onder een log-normale verdeling die is aangepast aan de intervallen tussen opeenvolgende beurten van dat sessietype.
  • Voor de Structural queue: Berekend als $1 - (o_b / o_{max})^\gamma$, waarbij $o_b$ de blokkoffset is en $\gamma$ een geleerde vervalkracht, waarbij eerdere blokken in een prompt prioriteit krijgen.
• $\Delta t_b$: De verstreken tijd sinds de laatste toegang tot het blok.

3. Volledig Adaptief Online Leren

SAECache elimineert handmatige afstemming door alle parameters online bij te werken via een unified feedbacklus gebaseerd op cache-hit/miss-statistieken:

• Tokentype-gewichten: Bijgewerkt via Exponentiële Moving Average (EMA) gebaseerd op "miss-na-verwijdering"-percentages en algehele hitpercentages.
• Log-Normale Parameters ($\mu, \sigma$): Online geschat met Maximum Likelihood Estimation (MLE) op waargenomen toegangstijden voor chat- en agentische wachtrijen.
• Positie Vervalkracht ($\gamma$): Geleerd uit correlaties tussen blokkpositie en hitpercentages in de structurele wachtrij.
• Wachtrijgewichten ($\alpha_q$): Bijgewerkt op basis van de verhouding van hit-tokens tot toegewezen capaciteit voor elke wachtrij, geschaald met een temperatuurparameter.

Belangrijkste Bijdragen

1. Empirische Karakterisering: Een systematische studie die aantoont dat tokenhergebruik varieert met tot 756× tussen tokentypen (92,3% voor systeemprompts versus 2,2% voor chain-of-thought) en dat intervallen tussen opeenvolgende beurten sessiespecifieke log-normale verdelingen volgen in plaats van eenvoudige exponentiële vervallingen.
2. SAECache Beleid: Een semantisch bewust, multi-queue verwijderingsbeleid dat heterogene hergebruikmechanismen (structureel versus temporair) ontkoppelt en verschillende prioriteiten toekent aan tokentypen.
3. Online Aanpassing: Een leerframework dat automatisch timingverdelingen, positieafname en wegingsparameters afstemt zonder handmatige ingreep, en zich aanpast aan verschuivende werklastsamenstellingen.
4. Uitgebreide Evaluatie: Uitgebreide experimenten op real-world datasets (ShareGPT, LMSys, Chatbot-Arena) die robuustheid aantonen over heterogene werklasten.

Experimentele Resultaten

Geëvalueerd op een vLLM-implementatie met Qwen2.5-1.5B-Instruct op een NVIDIA A40 GPU, werd SAECache vergeleken met LRU (productie-baseline) en Learned Prefix Caching (LPC).

• TTFT Verbetering: SAECache behaalde een 1,4× tot 2,7× verbetering in TTFT ten opzichte van productiestijl baselines over heterogene werklasten.
• Cache Hit Ratio: SAECache behaalde consistent de hoogste cache-hitpercentages, met een verbetering van 4,8–5,9 procentpunten ten opzichte van de sterkste baseline (LRU of LPC) over alle geteste configuraties.
• Resilientie bij Werklastmismatch: Alternatieven met vaste parameters leden tot een 2,7× degradatie in TTFT wanneer de werklastsamenstelling afweek van de trainingstrace. SAECache behield stabiele prestaties door zijn parameters online aan te passen.
• Ablatie Studies:
  • Tokentype-bewuste weging droeg bij aan een extra 23% verbetering.
  • Adaptieve wachtrijweging droeg bij aan de grootste winst van 39%.
  • Log-normale timing en positie-afname-lering leverden extra winsten van respectievelijk 14% en 12%.
• Overhead: De multi-turn sessiepredictor is zeer efficiënt, vereist slechts ~1M parameters (tegenover 118M voor het embedding-model van LPC) en behaalt een inferentie-throughput die 8,8× hoger is.

Betekenis en Claims

Het artikel stelt dat prefix cache-verwijdering niet alle gecachete blokken uniform moet behandelen, zelfs niet wanneer ze vergelijkbare recentie- of frequentiestatistieken delen. De auteurs stellen dat tokensemantiek, promptstructuur en sessietype fundamentele drijfveren zijn van hergebruik die bestaande beleid niet kunnen vangen.

De betekenis van SAECache ligt in het vermogen om:

1. De kloof te overbruggen tussen statische heuristische beleidslijnen en de dynamische, semantische realiteit van LLM-diensten.
2. Handmatige afstemming te elimineren, waardoor het systeem robuust is tegen werklastverschuivingen (bijvoorbeeld van chat-zwaar naar tool-gebruik-zwaar verkeer) zonder opnieuw te trainen of parameters aan te passen.
3. Aan te tonen dat fijnmazige, semantisch bewuste verwijdering een kritieke ontwerpkeuze is voor efficiënte LLM-diensten, met name in omgevingen met hoge cache-druk en heterogene verzoekpatronen.

De auteurs merken op dat SAECache, hoewel het uitblinkt in multi-turn en gemengde werklasten, zijn overhead de prestaties iets kan verminderen in regimes die worden gedomineerd door single-turn verzoeken (bijvoorbeeld Chatbot-Arena), waar de voordelen van hogere hitpercentages de beheerkosten niet volledig compenseren. Dit benadrukt de noodzaak van adaptieve strategieën die kunnen schalen met werklastkarakteristieken.