🤖 machine learning

Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

Dieses Papier stellt sparse prefix caching für hybrides und rekurrentes LLM-Serving vor, eine Methode, die die Latenz optimiert, indem sie exakte rekurrente Zustände an spärlichen Checkpoint-Positionen strategisch speichert, um die Berechnung vom tiefsten Übereinstimmungspunkt fortzusetzen, wodurch sie bestehende dichte Caching-Heuristiken übertrifft, während sie exakte Ausgaben bewahrt und keine Kernel-Änderungen erfordert.

Ursprüngliche Autoren: Mikhail Shirokikh, Sergey Nikolenko

Veröffentlicht 2026-05-08

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Mikhail Shirokikh, Sergey Nikolenko

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 sind ein Koch, der ein komplexes, mehrgängiges Menü für eine Reihe von Gästen zubereitet. In der Welt der Large Language Models (LLMs) ist das „Menü" das Generieren einer Antwort, und die „Zutaten" sind die Wörter (Tokens), die das Modell bereits verarbeitet hat.

Der alte Weg: Die „Alles-oder-Nichts"-Küche

Traditionell prüft der Koch, wenn ein neuer Gast (eine neue Anfrage) eintrifft, ob er etwas Ähnliches wie der letzte Gast bestellt hat.

Wenn er exakt denselben Vorspeisenteller bestellt hat: Der Koch verwendet den gesamten Teller erneut.
Wenn er etwas leicht Unterschiedliches bestellt hat: Der Koch wirft den gesamten Vorspeisenteller weg und fängt von vorne an zu kochen, selbst wenn die ersten 90 % der Zutaten identisch waren.

In technischen Begriffen wird dies als dichtes Caching bezeichnet. Das System speichert eine Kopie jedes einzelnen Schritts (jedes Tokens) ab, um sie später wiederzuverwenden. Dies funktioniert hervorragend für Standardmodelle, aber für eine neue Art von Modell, genannt Hybrid- oder Rekurrentes Modell, ist dieser Ansatz wie der Versuch, eine Bibliothek voller Bücher zu tragen, nur um einen Satz zu lesen. Es ist zu schwer und nimmt zu viel Speicherplatz in Anspruch.

Die neue Idee: Die „Checkpoint"-Strategie

Dieser Artikel schlägt einen intelligenteren Umgang mit diesen spezifischen Modellen vor. Betrachten Sie den Speicher des Modells nicht als Bibliothek jedes einzelnen Wortes, sondern als einen Zustand des Geistes.

Stellen Sie sich vor, Sie lesen einen sehr langen Roman.

Der alte Weg: Sie kleben ein Lesezeichen auf jede einzelne Seite, damit Sie sofort zurückspringen können. (Zu viele Lesezeichen!).
Der neue Weg (Sparse Prefix Caching): Sie kleben Lesezeichen nur auf Seite 1, Seite 100, Seite 200 usw.

Wenn ein neuer Leser die Geschichte ab Seite 150 fortsetzen möchte:

Sie werfen das ganze Buch nicht weg.
Sie finden das letzte Lesezeichen (Seite 100).
Sie lesen die Geschichte schnell von Seite 101 bis 149 nach, um wieder in den aktuellen Zustand zu gelangen.
Dann fahren Sie ab Seite 150 fort.

Da das Modell „rekurrent" ist (es entwickelt seinen Zustand schrittweise weiter), benötigt es nicht die gesamte Historie, sondern nur den Zustand an einem bestimmten Punkt. Dieser Artikel nennt diese Lesezeichen Checkpoints.

Das Problem: Wo platziert man die Lesezeichen?

Jetzt kommt der knifflige Teil. Sie haben ein begrenztes Budget für Lesezeichen (Speicher). Wo sollten Sie sie platzieren, um die meiste Zeit zu sparen?

Die „ausgewogene" Strategie: Platzieren Sie die Notizen gleichmäßig (alle 100 Seiten). Das ist sicher, aber vielleicht nicht die schnellste Methode.
Die „intelligente" Strategie (Was dieser Artikel tut): Betrachten Sie die Gewohnheiten Ihrer Leser.
- Wenn die meisten Leute um Seite 50 aufhören zu lesen, platzieren Sie dort ein Lesezeichen.
- Wenn die Leute normalerweise bis zum Ende lesen, platzieren Sie Lesezeichen nahe dem Ende.
- Wenn die Leute oft bei Seite 200 aufhören, platzieren Sie dort ein Lesezeichen.

Die Autoren haben eine mathematische Formel (ein „Dynamisches Programm") entwickelt, die wie ein superintelligenter Bibliothekar funktioniert. Sie analysiert vergangene Anfragen, um vorherzusagen, wo zukünftige Leser wahrscheinlich aufhören werden. Anschließend platziert sie die Lesezeichen genau dort, wo sie am nützlichsten sein werden, anstatt sie gleichmäßig zu verteilen.

Die Ergebnisse: Zeit- und Speichereinsparung

Der Artikel testete dies in realen Szenarien, wie zum Beispiel:

QuALITY: Ein langes Dokument, bei dem Menschen verschiedene Fragen zum selben Text stellen.
System-Prompts: Eine lange Reihe von Anweisungen, gefolgt von vielen verschiedenen Benutzerfragen.

Was sie herausfanden:

Weniger Speicher, gleiche Geschwindigkeit: Durch das „intelligente" Platzieren von Checkpoints basierend darauf, wo Menschen tatsächlich aufhören, konnten sie weniger Lesezeichen (Checkpoints) verwenden als die Standardmethode mit „gleichmäßigem Abstand", während sie dennoch die gleiche Menge an Kochzeit sparten.
Große Gewinne bei knappen Budgets: Die größten Verbesserungen traten auf, wenn nur sehr wenige Lesezeichen zur Verfügung standen. In diesen engen Situationen war die „intelligente" Platzierung viel besser als bloßes Raten oder gleichmäßiges Verteilen.
Exakte Ergebnisse: Im Gegensatz zu einigen Abkürzungen, die die Antwort erraten, garantiert diese Methode, dass die Ausgabe zu 100 % identisch ist mit dem Ergebnis, das man durch die Arbeit von vorne erhalten würde. Sie erledigt es einfach schneller, indem sie die Teile überspringt, die sie bereits kennt.

Das Fazit

Dieser Artikel stellt eine Methode vor, um KI-Modelle, die „rekurrenten" Speicher verwenden, effizienter zu machen. Anstatt jeden einzelnen Schritt zu speichern oder gar nichts zu speichern, speichert es ein paar strategische „Schnappschüsse" des Gehirns des Modells. Indem es Mathematik nutzt, um genau herauszufinden, wo diese Schnappschüsse basierend darauf, wie Menschen die KI tatsächlich nutzen, gespeichert werden sollen, kann das System schneller laufen und weniger Speicher verbrauchen, insbesondere wenn viele Benutzer ähnliche Fragen zu demselben langen Dokument stellen.

Es ist wie ein GPS, das Ihnen nicht nur die gesamte Karte zeigt, sondern genau weiß, welche Abfahrten Sie am wahrscheinlichsten nehmen werden, sodass es nur die Wegbeschreibungen für diese spezifischen Abfahrten speichert.

Technische Zusammenfassung: Sparse Prefix Caching für hybrides und rekurrentes LLM-Serving

1. Problemstellung

Bestehende Serving-Systeme für Large Language Models (LLM) stützen sich stark auf denses Prefix-Caching, bei dem die Key/Value (KV)-Zustände für jedes Token in einem gemeinsamen Prefix gespeichert werden, um redundante Prefill-Berechnungen zu vermeiden. Dieser Ansatz ist für Transformer-Architekturen Standard. Allerdings weisen State-Space-Modelle (SSMs) und hybride Architekturen (die Attention mit rekurrenten Schichten kombinieren) eine strukturelle Asymmetrie auf: Eine rekurrente Schicht entwickelt ihren Zustand als $h_t = F(h_{t-1}, x_t)$ weiter, was bedeutet, dass sie die Berechnung von einem einzelnen gespeicherten Zustand $h_c$ aus fortsetzen kann, anstatt die gesamte Historie der Zwischenzustände zu benötigen.

Eine dichte pro-Token-Caching der rekurrenten Zustände ist oft unnötig und prohibitiv teuer. Für Modelle wie Qwen-3.5 skaliert der rekurrente Zustand pro Kopf als $d_{head}^2$ , während die KV-Speicherung für Attention linear skaliert. Folglich verbraucht die Speicherung des rekurrenten Zustands jedes Tokens deutlich mehr Speicher als Attention-KV-Caches, bietet jedoch keinen zusätzlichen Nutzen gegenüber der Speicherung eines spärlichen Satzes von Checkpoints.

Das adressierte Kernproblem lautet: Gegeben ein Speicherbudget von $M$ Checkpoint-Slots für ein Prefix der Länge $N$ , wo sollten Checkpoints platziert werden, um die erwarteten Neuberechnungskosten unter einer spezifischen Verteilung zukünftiger Überlappungstiefen zu minimieren? Diese Optimierung unterscheidet sich von Cache-Zulassungs- oder Eviktionsrichtlinien; sie konzentriert sich darauf, welche Tokens innerhalb eines einzelnen beibehaltenen Eintrags zu checkpointen sind, um den Nutzen für partielle Prefix-Überlappungen zu maximieren.

2. Methodik

Theoretische Formulierung

Die Autoren formalisieren das Problem als einseitiges gewichtetes k-Median-Problem auf einer Linie.

Sei $C = \{c_1, \dots, c_M\}$ die Menge der Checkpoint-Positionen.
Für eine Anfrage, die das Prefix bis zur Tiefe $t$ überlappt, ist der tiefste wiederverwendbare Checkpoint $\ell(t; C) = \max(\{0\} \cup \{c \in C : c \le t\})$ .
Die Kosten entsprechen der Anzahl der neu zu berechnenden Tokens: $r(t; C) = t - \ell(t; C)$ .
Das Ziel ist es, die erwarteten Neuberechnungskosten $E[r(T; C)]$ unter einer Überlappungstiefenverteilung $T$ mit Wahrscheinlichkeiten $p_t$ zu minimieren.

Algorithmischer Ansatz

Optimale balancierte Platzierung (Uniform/Worst-Case): Die Autoren beweisen, dass unter einer uniformen Überlappungsverteilung oder im Worst-Case-Szenario eine balancierte Abstandssetzung (gleichmäßig verteilte Checkpoints) optimal ist.
Verteilungsabhängige Dynamische Programmierung (DP): Für nicht-uniforme, reale Überlappungsverteilungen leiten die Autoren einen exakten $O(NM)$-Dynamische-Programmierung-Algorithmus her.
- Die Rekursionsbeziehung lautet: $dp[m, j] = \min_{1 \le s \le j} (dp[m-1, s-1] + w(s, j))$ , wobei $w(s, j)$ die Kosten darstellt, $s$ als tiefsten Checkpoint für die Tiefen $s \dots j$ zu verwenden.
- Dies wird effizient unter Verwendung der monotonen konvexen Hüllkurven-Methode (monotone convex hull trick) gelöst, die die Monotonie der Präfixsummen ausnutzt.
Umgang mit Verteilungsdrift: Da die wahre Überlappungsverteilung unbekannt ist und aus historischen Daten geschätzt werden muss, liefert das Papier theoretische Garantien (via Lemma 1 und Theorem 3), dass die Wertfunktion bezüglich der Überlappungsverteilung Lipschitz-stetig ist. Dies stellt sicher, dass die Verwendung eines empirischen Histogramms (oder eines exponentiell gewichteten Histogramms für driftende Verteilungen) einen nahezu optimalen Zeitplan mit begrenzter Suboptimalität liefert.

Implementierungsstrategie

Checkpointing: Das System speichert exakte rekurrente Zustände an spärlichen Positionen. Bei einem Cache-Hit setzt das System vom tiefsten gespeicherten Checkpoint fort und berechnet das Suffix exakt neu.
Exaktheit: Da die rekurrente Aktualisierung deterministisch ist, erzeugt das Fortsetzen von einem Checkpoint und das Abspielen des Suffixes bit-identische Ausgaben im Vergleich zu einem vollständigen Prefill.
Hybride Integration: Für hybride Modelle speichert die Methode den vollständigen Attention-KV-Cache (dicht), wendet jedoch spärliches Checkpointing nur auf die rekurrenten Schichten an.

3. Hauptbeiträge

Theoretische Optimalität: Beweis, dass balancierte Abstandssetzung unter uniformer Überlappung und Worst-Case-Bedingungen optimal ist (Theorem 1).
Exakter Algorithmus: Formulierung von sparse Prefix Caching als gewichtetes k-Median-Problem und Bereitstellung einer exakten $O(NM)$-Dynamische-Programmierungslösung (Theorem 2).
Robustheitsgarantien: Nachweis, dass der optimale Zeitplan bei Fehlspezifikation der Verteilung stabil ist. Die Suboptimalität ist durch den Total-Variations-Abstand zwischen empirischer und wahrer Überlappungsverteilung begrenzt (Theorem 3) und wird auf Szenarien mit Verteilungsdrift unter Verwendung exponentieller Neugewichtung erweitert (Theorem 4).
Empirische Validierung: Validierung der Methode auf realen Datensätzen (QuALITY, NarrativeQA, System Prompts), die konsistente Verbesserungen gegenüber Baselines mit festem Budget zeigen.

4. Experimentelle Ergebnisse

Datensätze und Setup

Datensätze:
- QuALITY: Ein einzelnes Dokument mit mehreren Fragen (hohe Überlappung nahe der vollen Länge).
- NarrativeQA: Ähnliche Struktur mit breiter multimodaler Überlappung.
- System Prompts: Reale System-Prompts kombiniert mit Benutzerabfragen (Überlappung konzentriert auf kurze Längen).
Baselines: Vergleich mit „No Cache", „KV Only", „Balanced" (gleichmäßige Abstandssetzung), „Block" (feste Blockgröße), „Logarithmic" und „ $\sqrt{L}$ -spaced"-Strategien.
Hardware: Prototyp-Läufe auf NVIDIA RTX 2080 Super mit dem Modell Qwen-3.5-0.8B.

Erkenntnisse

Token-Einsparungen: Der DP-optimale Zeitplan dominiert deterministische Baselines (Balanced, Block, Logarithmic) konsistent in Bezug auf Reduktionsfaktoren für rekurrente Arbeit.
Vorteil bei niedrigem Budget: Die Leistungslücke ist bei niedrigen Checkpoint-Budgets am größten, wo die Überlappungsverteilung am stärksten nicht-uniform ist. Beispielsweise platziert die DP-Methode bei System Prompts (wo Überlappungen kurz sind) Checkpoints dicht nahe dem Divergenz-Peak und erreicht die gleiche Laufzeit wie Block-Caching mit weniger Checkpoints.
Wandzeit: Bei QuALITY und System Prompts liefert der DP-abgeleitete Zeitplan messbare Wandzeit-Verbeschleunigungen für repräsentative Schichtengruppen. Die Laufzeitreduktion korreliert linear mit der Anzahl der eingesparten Tokens.
Overhead: Der Overhead beim Laden von Checkpoints von der CPU auf die GPU ist gering im Vergleich zu den Einsparungen durch reduzierte Neuberechnung, was zu einer Netto-Laufzeitverbesserung führt.

5. Bedeutung und Behauptungen

Das Papier behauptet, dass sparse Prefix Caching einen neuen Designpunkt für hybrides und rekurrentes LLM-Serving erschließt, der zuvor nicht verfügbar war.

Memory/Compute-Trade-off: Es bietet einen Trade-off zwischen Speichernutzung und Neuberechnung, den dichtes KV-Caching nicht bieten kann, speziell für Architekturen, bei denen Zustände exakt extrahiert und wiederhergestellt werden können.
Exaktheit: Im Gegensatz zu approximativen KV-Komprimierungstechniken bewahrt diese Methode exakte Ausgaben, ohne die rekurrenten Berechnungskerne zu verändern.
Anwendbarkeit: Sie ist am vorteilhaftesten für Workloads, bei denen Anfragen einen substanziellen, aber nicht identischen Prefix teilen (z. B. RAG mit verschiedenen Fragen, variierende System-Prompts). Sie bietet keine zusätzlichen Vorteile für strikt append-only Chat-Workloads (wo der letzte Zustand ausreicht), verursacht aber in solchen Fällen keinen Overhead.
Zukünftige Arbeit: Die Autoren erkennen Engineering-Herausforderungen an, insbesondere die Notwendigkeit effizienter APIs zur Zustandsentnahme/-wiederherstellung in Produktions-Laufzeiten und die Integration dieser Platzierungsstrategie mit Zulassungs-/Eviktionsrichtlinien (z. B. Marconi et al.). Sie weisen zudem darauf hin, dass die aktuelle Theorie für einzelne Prefixes auf allgemeine Prefix-Bäume erweitert werden könnte.