The Missing Memory Hierarchy: Demand Paging for LLM Context Windows

Die Arbeit stellt Pichay vor, ein Demand-Paging-System für LLM-Kontextfenster, das durch transparente Interposition und Auslagerung veralteter Inhalte die Kontextnutzung um bis zu 93 % reduziert und damit etablierte Konzepte der virtuellen Speicherverwaltung auf die Skalierung von Sprachmodellen anwendet.

Das Wesentliche

Stell dir vor, du bist ein genialer Architekt (das ist die Künstliche Intelligenz, der LLM), der einen riesigen Bauplan entwirft. Damit du arbeiten kannst, brauchst du einen Tisch (das ist das "Context Window" oder der Kontext-Fenster).

Das Problem ist: Dieser Tisch ist winzig. Aber die Bauherren (die Entwickler der KI-Tools) haben eine seltsame Regel aufgestellt: Alles, was jemals auf den Tisch gelegt wurde, darf nie weggeräumt werden.

Das Problem: Der überfüllte Tisch

Stell dir vor, du hast vor 10 Minuten einen Zettel mit einer Telefonnummer auf den Tisch gelegt. Du hast die Nummer benutzt, aber den Zettel nicht weggenommen. Jetzt liegt er noch da.
Dann hast du vor 20 Minuten einen ganzen Stapel Akten (Dateien) gelesen. Du hast sie benutzt, aber sie liegen immer noch da.
Dann hast du vor einer Stunde eine Liste mit 50 Werkzeugen bekommen, von denen du nur drei benutzt hast. Die Liste liegt immer noch da.

Nach 100 Arbeitsschritten ist dein Tisch so voll mit alten Zetteln, Akten und Werkzeuglisten, dass:

1. Kein Platz mehr für neue Ideen ist: Du musst neue Pläne auf den Boden legen, weil der Tisch voll ist.
2. Du verwirrt wirst: Du musst durch den ganzen Haufen alten Papierkrams wühlen, um das zu finden, was du gerade brauchst.
3. Es extrem teuer wird: Jedes Mal, wenn du einen neuen Satz schreibst, musst du den gesamten Inhalt des Tisches (auch den alten Müll) noch einmal lesen und verarbeiten. Das kostet Zeit und Geld.

Die aktuelle Lösung der Branche ist: "Machen wir den Tisch einfach riesig!" (1 Million Token, 10 Millionen Token). Das ist, als würde man versuchen, ein kleines Zimmer zu retten, indem man den ganzen Block abreißt und ein Stadion baut. Es funktioniert kurzfristig, aber es ist ineffizient und teuer.

Die Lösung: Pichay (Der clevere Diener)

Der Autor dieses Papiers, Tony Mason, hat eine Idee entwickelt, die er Pichay nennt. Stell dir Pichay als einen super-intelligenten Diener vor, der zwischen dir (dem Architekten) und dem Tisch steht.

Pichay kennt die Regeln des Betriebssystems (wie bei einem Computer vor 60 Jahren), die wir hier vergessen haben: Demand Paging (Bedarfsladung).

So funktioniert Pichay im Alltag:

1. Der Diener räumt auf (Eviction):
   Wenn du einen Zettel mit einer Telefonnummer benutzt hast und er liegt seit 4 Schritten nur noch herum, sagt Pichay: "Das hier ist alt. Ich nehme es weg."
   Aber: Er wirft es nicht in den Müll! Er legt einen kleinen Zettel darauf: "Telefonnummer war hier. Wenn du sie brauchst, sag Bescheid, und ich hole sie dir sofort."

2. Der Diener holt es zurück (Page Fault):
   Wenn du plötzlich sagst: "Moment, ich brauche die Telefonnummer!", merkt Pichay: "Aha! Du hast auf den alten Zettel reagiert."
   Er holt die echte Telefonnummer aus dem Archiv (dem Speicher auf der Festplatte) und legt sie sofort wieder auf den Tisch. Das nennt man einen "Page Fault" (Seitenfehler), aber bei Pichay ist das kein Fehler, sondern ein geplanter Vorgang.

3. Der Diener lernt (Pinning):
   Wenn Pichay merkt, dass du die Telefonnummer immer wieder brauchst, sagt er: "Okay, die Nummer ist wichtig. Ich klebe sie fest (pinning), damit sie nie wieder weggeräumt wird."

4. Die Zusammenarbeit (Cooperative Management):
   Das Geniale an Pichay ist: Der Diener fragt dich manchmal: "Hey, ich sehe, du hast diesen Plan schon lange nicht mehr benutzt. Soll ich ihn wegräumen, damit Platz für Neues entsteht?" Und du (die KI) kannst antworten: "Ja, mach das!" Das ist etwas, das bei echten Computern früher nicht ging – der Diener durfte nicht fragen, er musste einfach entscheiden.

Was bringt das?

Das Papier zeigt mit echten Zahlen, dass unsere aktuellen KI-Systeme 21,8 % ihres Platzes mit Müll verschwenden. Das sind alte Akten, die niemand mehr liest, und doppelte Listen.

Mit Pichay passiert Folgendes:

• Platzgewinn: Der Tisch bleibt fast immer leer genug für neue Ideen. In Tests wurde der freie Platz von 7 % auf 43 % erhöht.
• Geschwindigkeit: Da weniger Müll gelesen werden muss, arbeitet die KI schneller und günstiger.
• Intelligenz: Die KI wird nicht dumm, weil sie den Müll verliert. Sie weiß genau, wo der Müll liegt, und holt ihn sich, wenn er wirklich gebraucht wird.

Die große Erkenntnis

Die wichtigste Botschaft des Papiers ist: Wir behandeln den Kontext einer KI wie einen riesigen, unendlichen Speicher, aber er ist eigentlich nur ein winziger, schneller Cache (wie der Arbeitsspeicher eines Computers).

Wir brauchen nicht nur einen noch größeren Tisch. Wir brauchen ein Regalsystem:

• L1 (Der Tisch): Nur das, was du gerade brauchst.
• L2 (Das Regal daneben): Dinge, die du oft brauchst, aber nicht jeden Moment.
• L3 (Der Keller): Alte Gespräche, die zusammengefasst wurden.
• L4 (Das Archiv): Alles, was du jemals geschrieben hast, aber nur auf Abruf.

Pichay ist der erste Schritt, um dieses Regalsystem für KI zu bauen. Es ist, als würden wir endlich die "Betriebssysteme" für künstliche Intelligenz erfinden, die es für normale Computer schon seit den 1960er Jahren gibt.

Zusammengefasst: Pichay ist der clevere Hausmeister, der den überfüllten Schreibtisch der KI aufräumt, den alten Papierkram in den Keller schafft und ihn sofort wieder holt, wenn er gebraucht wird. Das macht die KI schneller, billiger und effizienter, ohne dass sie ihre Fähigkeiten verliert.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „The Missing Memory Hierarchy: Demand Paging for LLM Context Windows" von Tony Mason auf Deutsch.

1. Problemstellung

Das Paper identifiziert ein fundamentales Architekturproblem bei Large Language Models (LLMs), insbesondere bei agentic AI-Systemen (wie Claude Code, Cursor, GitHub Copilot).

• Fehlende Speicherebenen: Der Kontextfenster eines LLM wird derzeit fälschlicherweise als das gesamte Speichersystem behandelt. Es entspricht eher einem L1-Cache (klein, schnell, teuer), dem jedoch eine Hierarchie (L2, L3, virtuelles Speichersystem) fehlt. Es gibt keine Mechanismen für Demand Paging (bedarfsgesteuertes Laden), keine Seitenersetzungspolitiken und keine Working-Set-Schätzung.
• Strukturelle Verschwendung: Da der Kontext bei jedem API-Aufruf vollständig neu zusammengesetzt wird, bleiben alle Tool-Definitionen, System-Prompts und veralteten Tool-Ergebnisse für die gesamte Sitzung im Kontext.
• Messbare Ineffizienz: Eine Analyse von 857 Produktionssitzungen (4,45 Milliarden effektive Eingabetokens) ergab, dass 21,8 % der Tokens struktureller Abfall sind. Dieser setzt sich zusammen aus:
  • Ungenutzten Tool-Schemas (11,0 %)
  • Verdoppelten Inhalten (2,2 %)
  • Veralteten Tool-Ergebnissen (8,7 %), die mit einem medianen Verstärkungsfaktor von 84,4-fach (jeder Token wird 84-mal neu verarbeitet) re-verarbeitet werden.
• Kostenexplosion: Die Aufmerksamkeitsskosten (Attention Cost) skalieren quadratisch ($O(n^2)$) mit der Kontextlänge. Das bloße Vergrößern des Kontextfensters (z. B. auf 1M Tokens) ist keine skalierbare Lösung, da sie die quadratischen Kosten nur auf einen größeren Bereich verschiebt, ohne die Verwaltung des Working Sets zu lösen.

2. Methodik und Systemdesign (Pichay)

Die Autoren stellen Pichay vor, ein Demand-Paging-System, das als transparenter Proxy zwischen Client und Inference-API fungiert. Es interponiert den Nachrichtenstrom, ohne Änderungen an Client, Modell oder API zu erfordern.

Kernkomponenten:

• Trennung von Garbage Collection und Paging:
  • Garbage Collection: Entfernt flüchtige Tool-Ausgaben (z. B. Bash-Ergebnisse), die nicht wieder abgerufen werden können.
  • Paging: Entfernt adressierbare Inhalte (z. B. Dateilesevorgänge), die bei Bedarf (Page Fault) wieder geladen werden können.
• Eviction Policy (Austauschstrategie):
  • Basierend auf FIFO (First-In-First-Out) nach dem Alter der User-Turns.
  • Inhalte, die älter als $\tau$ Turns (z. B. 4) sind und größer als $s_{min}$ Bytes sind, werden eviziert.
  • Evizierte Inhalte werden durch Retrieval Handles ersetzt (z. B. [Paged out: Read file.py (8KB). Re-read if needed.]), die als Platzhalter dienen und dem Modell signalisieren, wie es den Inhalt wiederherstellen kann.
• Page Fault Detection:
  • Das System erkennt Page Faults, wenn das Modell ein eviziertes Tool (z. B. Read einer Datei) erneut aufruft.
  • Der Proxy lädt den Inhalt aus dem Backing Store (dem Client-Historie-Buffer) nach und injiziert ihn in den Kontext.
• Fault-Driven Pinning:
  • Eine adaptive Strategie: Wenn ein evizierter Inhalt einen Page Fault auslöst, wird er für den Rest der Sitzung „gepinnt" (nicht mehr eviziert). Dies reduziert wiederholte Fehler in stabilen Arbeitslasten.
• Kooperatives Speichermanagement:
  • Im Gegensatz zu klassischen OS, wo Anwendungen passiv sind, nutzt Pichay die Fähigkeit des LLM zur Kooperation.
  • Phantom Tools: Das Modell kann memory_release() (freigeben) oder memory_fault() (anfordern) aufrufen.
  • Cleanup Tags: Das Modell kann im Text Tags wie collapse: turns N-M senden, um Dialogabschnitte in Zusammenfassungen zu komprimieren (L3-Ebene).
• Druckzonen (Pressure Zones):
  • Das System reagiert gestuft auf Kontextdruck: Von reinem Beobachten über „Advisory"-Hinweise an das Modell bis hin zu erzwungener Eviction bei kritischer Füllung.

Die vorgeschlagene Hierarchie:

• L1: Generierungsfenster (aktiver Kontext).
• L2: Working Set (bedarfsgesteuert, gepinnt).
• L3: Sitzungshistorie (komprimiert durch Zusammenfassungen).
• L4: Sitzungsübergreifender persistenter Speicher.

3. Schlüsselbeiträge

1. Empirische Charakterisierung: Nachweis, dass 21,8 % der Tokens in agentic Workloads struktureller Abfall sind, mit einer detaillierten Taxonomie der Verschwendung.
2. Pichay-System: Implementierung eines Demand-Paging-Systems mit einer gemessenen Page-Fault-Rate von 0,0254 % (offline Replay) und erfolgreicher Produktionseinsatz.
3. Fault-Driven Pinning: Eine Ersetzungsstrategie, die aus Fehlern lernt und Working-Set-Seiten automatisch sperrt.
4. Kooperative Primitive: Einführung von Mechanismen (Phantom Tools, Cleanup Tags), die dem Modell erlauben, aktiv Speicher freizugeben oder anzufordern – ein neues Design-Paradigma gegenüber hardwarebasierten Hierarchien.
5. Architektonische Erkenntnis: Die strukturelle Abbildung von LLM-Kontextmanagement auf virtuelle Speicherverwaltung (Working Set, Demand Paging, Thrashing).
6. Vier-Ebenen-Hierarchie: Design und teilweise Implementierung einer vollständigen Speicherhierarchie für LLM-Systeme.

4. Ergebnisse

• Reduktion des Kontextverbrauchs: In einer Produktionssitzung (681 Turns) reduzierte das System den Kontextverbrauch um bis zu 93 % (von 5.038 KB auf 339 KB).
• Freier Kontext: Die Nutzung von Pichay erhöhte den freien Kontext von 7 % auf 43 %, was den Unterschied zwischen „unmittelbarem Kontext-Ende" und „substanzieller Kapazität" ausmacht.
• Fault-Rate: Im Offline-Test (1,4 Millionen simulierte Evictions) lag die Page-Fault-Rate bei nur 0,0254 %.
• Thrashing-Phänomen: Unter extremem Druck (Sitzung B) trat ein klassisches „Thrashing" auf (97 % Fault-Rate), bei dem das System mehr Zeit mit dem Laden/Entladen verbrachte als mit nützlicher Arbeit. Dies bestätigt die Notwendigkeit von Working-Set-Schätzungen.
• Qualitätserhalt: In einer Evaluierung (18 Sitzungen, 54 Urteile durch LLM-Judges) zeigte sich, dass die Behandlung (Eviction) die Ausgabequalität nicht verschlechterte; in einigen Fällen wurde die Qualität sogar als leicht verbessert eingestuft (Attention-Konzentrationseffekt).
• Kostenersparnis: Durch die Reduktion der zu verarbeitenden Tokens sinken die Attention-Kosten quadratisch. Bei einer 88-Turn-Sitzung wurde eine kumulative Reduktion der Token-Kosten um 45 % erreicht.

5. Bedeutung und Fazit

Das Paper argumentiert, dass die aktuelle Praxis, einfach nur größere Kontextfenster zu bauen, ein ineffizientes „Hardware-Upgrade" ist, das das eigentliche Problem der Speicherverwaltung ignoriert.

• Paradigmenwechsel: LLM-Kontextmanagement ist ein Speichermanagement-Problem, das die gleichen Lösungen wie Betriebssysteme der 1960er Jahre (Atlas, Multics) benötigt: Demand Paging, Working-Set-Theorie und eine Hierarchie aus schnellen/teuren und langsamen/günstigen Speicherebenen.
• Invertiertes Kostenmodell: Im Gegensatz zu klassischem RAM, wo das Halten einer Seite kostenlos ist, kostet jeder Token im Kontext bei jedem Schritt Geld. Daher ist aggressives Evizieren (Löschen) oft kosteneffizienter als das Halten, solange die Page-Fault-Kosten (das Nachladen) gering bleiben.
• Praktische Anwendbarkeit: Da Pichay als transparenter Proxy funktioniert, ist es sofort einsetzbar, ohne Modelle neu zu trainieren oder APIs zu ändern.
• Zukunft: Die Arbeit legt den Grundstein für eine vollständige Speicherhierarchie für KI-Agenten, einschließlich sitzungsübergreifenden Speichers (L4) und kostensensitiver Eviction-Strategien.

Zusammenfassend zeigt das Paper, dass durch die Anwendung etablierter Betriebssystem-Konzepte auf LLM-Kontextfenster massive Effizienzgewinne, Kostensenkungen und eine Skalierbarkeit erreicht werden können, die mit reinem Kontextwachstum nicht möglich wären.