🤖 machine learning

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches

Dieser Artikel stellt SAECache vor, eine semantisch adaptive Prefix-Cache-Eviction-Richtlinie, die durch eine Multi-Queue-Architektur und Online-Learning die unterschiedlichen Wiederverwendungswerte verschiedener Token-Typen nutzt, um die Effizienz des LLM-Servings erheblich zu steigern und gleichzeitig die Notwendigkeit manueller Parameteranpassungen zu eliminieren.

Ursprüngliche Autoren: Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

Veröffentlicht 2026-05-20

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie betreiben einen sehr belebten, gehobenen Coffee-Shop (das Large Language Model oder LLM), der täglich Millionen von Kunden bedient. Um Kaffee schnell zuzubereiten, haben Sie ein spezielles „Gedächtnisregal" (GPU-Speicher), auf dem Sie die vorgefertigten Zutaten und Anweisungen für Bestellungen lagern, die Sie bereits begonnen haben. Dies wird als Prefix Caching bezeichnet.

Wenn ein neuer Kunde einen Latte bestellt, der zu 90 % mit einer vorherigen Bestellung übereinstimmt, müssen Sie keine neuen Bohnen mahlen oder keine neue Milch aufschäumen; Sie greifen einfach auf die vorgefertigte Basis vom Regal zu. Dies lässt den ersten Schluck (den ersten Token) fast augenblicklich erscheinen.

Ihr Regal ist jedoch winzig. Sie können nicht jede einzelne vorgefertigte Basis für immer aufbewahren. Irgendwann müssen Sie einige Dinge wegwerfen, um Platz für neue Bestellungen zu schaffen. Dies ist die Eviction Policy (Entfernungsrichtlinie).

Das Problem: Der „Einheitsgröße"-Irrtum

Lange Zeit verwendeten Coffee-Shop-Manager eine einfache Regel: „Werfen Sie den ältesten Gegenstand zuerst weg." (Dies ist die LRU-Richtlinie).

Die Arbeit argumentiert, dass dies eine schlechte Idee ist, da nicht alle Gegenstände auf dem Regal gleich wertvoll sind.

Der System-Prompt: Stellen Sie sich ein „Standardmenü" vor, das jeder Kunde sieht. Es ändert sich nie. Es ist unglaublich wertvoll, weil jeder es bestellt.
Die Chain-of-Thought: Stellen Sie sich das chaotische, innere Monolog eines Kunden darüber vor, warum er einen Latte möchte. Dies ist einzigartig für diese eine Person und diesen einen Moment. Es ist fast nie für den nächsten Kunden nützlich.

Die alte Regel behandelte das „Standardmenü" und das „chaotische Monolog" exakt gleich. Wenn das Monolog etwas neuer war als das Menü, würde die alte Regel das Menü wegwerfen, um Platz für das Monolog zu schaffen. Dies ist eine Katastrophe, da der nächste Kunde das Menü sofort benötigt, das Monolog für ihn jedoch nutzlos ist.

Die Lösung: SAECache (Der intelligente Manager)

Die Autoren haben ein neues System namens SAECache entwickelt. Stellen Sie sich dies als einen intelligenten Manager vor, der nicht nur schaut, wann ein Gegenstand zuletzt berührt wurde, sondern was der Gegenstand tatsächlich ist.

So funktioniert es, unter Verwendung einfacher Analogien:

1. Die vier spezialisierten Behälter (Multi-Queue-Architektur)

Anstatt eines großen Regals organisiert SAECache das Regal in vier distincte Behälter, jeder mit eigenen Regeln:

Der „Müll"-Behälter: Enthält Gegenstände, die fast nie wiederverwendet werden (wie das chaotische Monolog oder die letzten Schritte eines Getränks). Diese werden zuerst weggeworfen.
Der „Vorlage"-Behälter: Enthält Standardanweisungen und System-Prompts (wie das Menü). Diese werden sehr sorgfältig aufbewahrt, da sie ständig wiederverwendet werden.
Der „Chat"-Behälter: Enthält Gespräche, bei denen Menschen hin und her sprechen.
Der „Agent"-Behälter: Enthält komplexe Aufgaben, bei denen die AI arbeitet (wie Programmieren oder das Verwenden von Werkzeugen).

2. Der „Wert-Score" (Semantisch bewusste Gewichtung)

Der Manager rät nicht nur, welcher Behälter wichtig ist. Er lernt!

Wenn der Manager einen „System-Prompt" wegwirft und dann sofort wieder danach gefragt wird, lernt das System: „Ups! Ich habe etwas Wertvolles weggeworfen. Ich sollte System-Prompts beim nächsten Mal einen höheren Score geben."
Wenn er ein „Chain-of-Thought" wegwirft und niemand danach fragt, lernt es: „Gute Arbeit! Das war Schrott. Ich werde ihm weiterhin einen niedrigen Score geben."

Dies geschieht automatisch, wie ein Manager, der die Regale basierend darauf anpasst, was die Kunden tatsächlich kaufen, ohne dass ein Mensch ihm sagen muss, was zu tun ist.

3. Die „Zeitmaschine" (Adaptive Timing)

Das System lernt auch, wann die Leute zurückkommen.

Chat-Sitzungen können lange Pausen haben (wie ein Kunde, der eine Kaffeepause macht).
Agent-Sitzungen können sehr schnell und hektisch sein.
Das System lernt den spezifischen „Herzschlag" jeder Sitzungsart. Es weiß, dass, wenn eine Chat-Sitzung seit 10 Minuten nicht zurückgekehrt ist, sie wahrscheinlich für immer weg ist. Aber wenn eine Agent-Sitzung seit 10 Sekunden nicht zurückgekehrt ist, denkt sie vielleicht nur. Es passt seine Entfernungsregeln in Echtzeit an, um dem Rhythmus des Verkehrs zu entsprechen.

Die Ergebnisse: Schnellerer Kaffee, weniger Verschwendung

Die Arbeit testete diesen neuen Manager gegen die alte „älteste-zuerst"-Regel und andere intelligente, aber starre Systeme.

Geschwindigkeit: Das neue System ließ den ersten Schluck Kaffee in belebten, gemischten Umgebungen 1,4- bis 2,7-mal schneller erscheinen.
Anpassungsfähigkeit: Die alten Systeme brachen, wenn sich die Art der Kunden änderte (z. B. wenn der Shop plötzlich mehr Kunden mit Einzelbestellungen statt Chattern bekam). Das neue System passte sich sofort an.
Effizienz: Es sparte eine massive Menge an „verschwendetem" Speicher, indem es keinen Schrott (wie die chaotischen Monologe) horte und die wertvollen Dinge (wie das Menü) sicher aufbewahrte.

Zusammenfassung

Kurz gesagt sagt die Arbeit: Behandeln Sie nicht alle Speicherblöcke gleich. Nur weil zwei Dinge zur gleichen Zeit berührt wurden, bedeutet das nicht, dass sie gleich nützlich sind. Indem wir dem Computer beibringen, die Bedeutung der Daten zu verstehen (ist dies ein Menü? ist dies ein Witz? ist dies ein Werkzeug?) und ihn aus seinen eigenen Fehlern in Echtzeit lernen lassen, können wir KI viel schneller und effizienter machen.

Technische Zusammenfassung: SAECache – Semantikbewusste Auslagerung für LLM-Präfixcaches

Problemstellung

Präfixcaching bei Large Language Models (LLMs) zielt darauf ab, die Inferenzlatenz (insbesondere Time-to-First-Token, TTFT) zu reduzieren, indem Key-Value (KV)-Zustände von Anfragen wiederverwendet werden, die Eingabepräfixe teilen. Die Wirksamkeit des Präfixcaching wird jedoch durch den begrenzten GPU-Speicher stark eingeschränkt, was eine Auslagerungsstrategie (Eviction Policy) erforderlich macht, um weniger wertvolle Blöcke bei Erreichen der Kapazitätsgrenze zu verwerfen.

Bestehende Auslagerungsstrategien wie Least Recently Used (LRU) und Least Frequently Used (LFU) stützen sich primär auf Zugriffszeiten oder Häufigkeitsstatistiken. Diese tokenagnostischen Ansätze behandeln alle gecachten Blöcke einheitlich und ignorieren zwei kritische Dimensionen von LLM-Workloads:

Semantische Heterogenität: Unterschiedliche Tokentypen (z. B. Systemprompts vs. Chain-of-Thought-Reasoning) weisen stark unterschiedliche intrinsische Wiederverwendungsraten auf.
Workload-Variabilität: Wiederverwendungsmuster unterscheiden sich erheblich zwischen Single-Turn-templatierten Anfragen (strukturelle Wiederverwendung) und Multi-Turn-Konversationen (session-lokale zeitliche Wiederverwendung), wobei die Intervalle zwischen den Turns unterschiedlichen Verteilungen bei verschiedenen Anwendungstypen folgen (z. B. Chat vs. agentische Workflows).

Die Autoren stellen fest, dass die Behandlung eines hochwertigen Systemprompt-Blocks und eines minderwertigen Chain-of-Thought-Blocks als gleichwertig, wenn ihre Aktualität übereinstimmt, zu einer suboptimalen Speicherallokation führt. Darüber hinaus versagen fest parametrisierte Strategien, wenn sich die Workload-Zusammensetzung ändert, was zu einer Leistungsverschlechterung von bis zu 2,7-fach bei Workload-Mismatch führt.

Methodik: SAECache

Um diese Einschränkungen zu adressieren, schlagen die Autoren SAECache (Semantic-Adaptive Eviction for prefix caches) vor, eine Strategie, die die token-semantische Struktur mit einer Online-Workload-Anpassung integriert. Das System arbeitet durch drei Kernmechanismen:

1. Multi-Queue-Architektur mit regelbasierter Routing

SAECache leitet KV-Blöcke basierend auf ihren dominanten Wiederverwendungsmustern in vier verschiedene Warteschlangen weiter, anstatt eine einzige globale Warteschlange zu nutzen:

Evict-First-Warteschlange: Speichert minderwertige Blöcke, einschließlich Decode-Phasen-Token und untemplatierter Prefill-Blöcke mit geringem Wiederverwendungspotenzial. Diese werden zuerst geleert.
Strukturelle Warteschlange: Speichert KV-Blöcke aus Single-Turn-Sitzungen, die auf gemeinsame Prompt-Strukturen angewiesen sind (z. B. Tool-Use-Templates, Programmieranweisungen).
Chat-Warteschlange: Speichert Multi-Turn-Blöcke aus konversationellen Sitzungen und modelliert die session-lokale zeitliche Wiederverwendung.
Agentische Warteschlange: Speichert Multi-Turn-Blöcke aus Agent-/Tool-Use-Sitzungen, die sich im Vergleich zum Standard-Chat durch unterschiedlichen Token-Inhalt und Verteilungen der Anfrageintervalle auszeichnen.

Ein leichter Multi-Turn-Sitzungsvorhersager (ein 3-Schichten-MLP, das die finalen versteckten Zustände des Serving-Modells wiederverwendet) löst Unklarheiten für die erste Anfrage einer Sitzung auf und leitet sie in die entsprechende Multi-Turn-Warteschlange weiter, wenn eine Fortsetzung vorhergesagt wird, oder andernfalls in die strukturelle oder Evict-First-Warteschlangen.

2. Lokale Prioritätsbewertung

Innerhalb jeder Warteschlange werden Blöcke basierend auf einer zusammengesetzten Metrik $P(b)$ für die Auslagerung bewertet:
$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$

$\alpha_q$ (Warteschlangengewicht): Ein dynamisches Gewicht, das die aktuelle Treffer-Effizienz der spezifischen Warteschlange widerspiegelt.
$w_{\tau(b)}$ (Tokentyp-Gewicht): Ein gelerntes Gewicht, das spezifisch für den Tokentyp (z. B. Systemprompt, Benutzeranfrage, Chain-of-Thought) des Blocks ist.
$p_q(b)$ (Lokale Überlebenswahrscheinlichkeit):
- Für Chat-/Agentische Warteschlangen: Berechnet als Überlebenswahrscheinlichkeit $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ unter einer Log-Normal-Verteilung, die an die Intervalle zwischen den Turns dieses Sitzungstyps angepasst ist.
- Für die Strukturelle Warteschlange: Berechnet als $1 - (o_b / o_{max})^\gamma$ , wobei $o_b$ der Block-Offset und $\gamma$ eine gelernte Abklingkraft ist, die frühere Blöcke in einem Prompt priorisiert.
$\Delta t_b$ : Die vergangene Zeit seit dem letzten Zugriff auf den Block.

3. Vollständig adaptive Online-Lernverfahren

SAECache eliminiert manuelle Abstimmung, indem es alle Parameter online über einen einheitlichen Feedback-Loop aktualisiert, der auf Cache-Treffer-/Fehlschlag-Statistiken basiert:

Tokentyp-Gewichte: Aktualisiert mittels Exponentieller Gleitender Durchschnitt (EMA) basierend auf Raten von „Fehlschlag nach Auslagerung" und allgemeinen Trefferquoten.
Log-Normal-Parameter ( $\mu, \sigma$ ): Online geschätzt mittels Maximum-Likelihood-Schätzung (MLE) an beobachteten Zugriffsintervallen für Chat- und agentische Warteschlangen.
Positions-Abklingkraft ( $\gamma$ ): Gelernt aus Korrelationen zwischen Blockposition und Trefferquoten in der strukturellen Warteschlange.
Warteschlangengewichte ( $\alpha_q$ ): Aktualisiert basierend auf dem Verhältnis von Treffer-Token zur zugewiesenen Kapazität für jede Warteschlange, skaliert durch einen Temperaturparameter.

Hauptbeiträge

Empirische Charakterisierung: Eine systematische Studie, die zeigt, dass die Token-Wiederverwendung je nach Tokentyp um bis zu 756-fach variiert (92,3 % für Systemprompts vs. 2,2 % für Chain-of-Thought) und dass Intervalle zwischen den Turns sitzungsspezifischen Log-Normal-Verteilungen folgen und nicht einfachen exponentiellen Abklingkurven.
SAECache-Strategie: Eine semantikbewusste, Multi-Queue-Auslagerungsstrategie, die heterogene Wiederverwendungsmechanismen (strukturell vs. zeitlich) entkoppelt und unterschiedliche Prioritäten für Tokentypen zuweist.
Online-Anpassung: Ein Lernframework, das Zeitverteilungen, Positionsabklingen und Gewichtsparameter automatisch ohne manuelle Eingriffe justiert und sich an sich ändernde Workload-Zusammensetzungen anpasst.
Umfassende Evaluierung: Umfangreiche Experimente mit realen Datensätzen (ShareGPT, LMSys, Chatbot-Arena), die Robustheit über heterogene Workloads hinweg demonstrieren.

Experimentelle Ergebnisse

Evaluiert auf einer vLLM-Implementierung mit Qwen2.5-1.5B-Instruct auf einer NVIDIA A40-GPU wurde SAECache mit LRU (Produktions-Baseline) und Learned Prefix Caching (LPC) verglichen.

TTFT-Verbesserung: SAECache erzielte über heterogene Workloads hinweg eine 1,4- bis 2,7-fache Verbesserung des TTFT gegenüber produktionsähnlichen Baselines.
Cache-Trefferquote: SAECache erzielte konsistent die höchsten Cache-Trefferquoten und verbesserte sich um 4,8–5,9 Prozentpunkte gegenüber der stärksten Baseline (LRU oder LPC) über alle getesteten Konfigurationen hinweg.
Resilienz bei Workload-Mismatch: Fest parametrisierte Alternativen litten bei Abweichung der Workload-Zusammensetzung vom Trainingsverlauf unter einer 2,7-fachen Verschlechterung des TTFT. SAECache behielt durch Online-Anpassung seiner Parameter eine stabile Leistung bei.
Ablationsstudien:
- Tokentyp-bewusste Gewichtung trug eine zusätzliche 23 %-Verbesserung bei.
- Adaptive Warteschlangengewichtung trug den größten Gewinn mit 39 % bei.
- Log-Normal-Zeitplanung und Positions-Abkling-Lernverfahren lieferten zusätzliche Gewinne von 14 % bzw. 12 %.
Overhead: Der Multi-Turn-Sitzungsvorhersager ist hocheffizient, erfordert nur ~1M Parameter (im Vergleich zu 118M für das Embedding-Modell von LPC) und erreicht eine 8,8-fach höhere Inferenz-Durchsatzrate.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass die Auslagerung von Präfixcaches nicht alle gecachten Blöcke einheitlich behandeln sollte, selbst wenn sie ähnliche Aktualitäts- oder Häufigkeitsstatistiken aufweisen. Die Autoren betonen, dass Token-Semantik, Prompt-Struktur und Sitzungstyp fundamentale Treiber der Wiederverwendung sind, die bestehende Strategien nicht erfassen.

Die Bedeutung von SAECache liegt in seiner Fähigkeit:

Die Lücke zu schließen zwischen statischen heuristischen Strategien und der dynamischen, semantischen Realität des LLM-Servings.
Manuelle Abstimmung zu eliminieren, wodurch das System robust gegenüber Workload-Verschiebungen (z. B. von chat-lastig zu tool-use-lastig) wird, ohne Neustraining oder Parameteranpassung.
Nachzuweisen, dass feingranulare, semantikbewusste Auslagerung eine kritische Designentscheidung für effizientes LLM-Serving ist, insbesondere in Umgebungen mit hohem Cache-Druck und heterogenen Anfrage Mustern.

Die Autoren weisen darauf hin, dass SAECache zwar bei Multi-Turn- und gemischten Workloads hervorragend funktioniert, sein Overhead jedoch die Leistung in Single-Turn-dominierten Regimen (z. B. Chatbot-Arena) leicht reduzieren kann, wo die Vorteile höherer Trefferquoten die Verwaltungskosten nicht vollständig ausgleichen. Dies unterstreicht die Notwendigkeit adaptiver Strategien, die sich mit den Workload-Charakteristika skalieren können.