StepCache: Step-Level Reuse with Lightweight Verification and Selective Patching for LLM Serving

1. Het Probleem

Large Language Models (LLM's) worden steeds vaker ingezet in interactieve systemen waar latentie en kosten cruciale beperkingen zijn. Bestaande caching-mechanismen voor LLM-diensten werken echter vaak op een te grof niveau:

• Semantische caching: Hergebruikt een volledige respons als de prompt vergelijkbaar is. Dit is kwetsbaar; zelfs kleine, lokale wijzigingen in de constraints (bijv. een andere variabele in een wiskundeprobleem of een extra vereiste sleutel in JSON) maken de volledige cache-response onbruikbaar.
• Prefix/KV-caching: Hergebruikt interne modelstaten (KV-cache) voor identieke prompt-voorvoegsels. Dit is echter sterk gekoppeld aan specifieke backends, tokenizers en modellen, en hergebruikt zelden delen van een antwoord.

In veel real-world scenario's delen verzoeken een stabiele oplossingsstructuur, maar verschillen ze in lokale constraints. Bestaande methoden dwingen het systeem om ofwel een onjuist antwoord te geven (door volledige hergebruik) ofwel een groot deel van een herbruikbare oplossing opnieuw te berekenen (door volledige regeneratie). Er is een behoefte aan een fijnmaziger hergebruikseenheid die correctheid behoudt bij lokale wijzigingen.

2. Methodologie: StepCache

StepCache is een backend-agnostische laag die bovenop bestaande LLM-diensten werkt. In plaats van het hele antwoord of interne modelstaten te hergebruiken, behandelt StepCache een antwoord als een geordende reeks stappen.

De werkstroom van StepCache omvat de volgende fasen:

1. Segmentatie: Het gegenereerde antwoord wordt opgesplitst in een lijst van stappen (bijv. op alinea-grenzen, expliciete "Stap 1"-labels, of voor JSON als één enkel object).
2. Retrieval: Bij een nieuw verzoek wordt de prompt ge-embed en wordt de beste match uit de cache opgehaald op basis van prompt-similariteit.
3. Per-stap verificatie: De opgehaalde stappen worden één voor één gecontroleerd met lichtgewicht, taakbewuste verificatie (bijv. controleren of een wiskundige tussenstap klopt met de nieuwe constanten, of of een JSON-object de vereiste sleutels bevat).
4. Selectieve patching:
   • Als een stap slaagt, wordt deze hergebruikt.
   • Als een stap faalt, wordt niet het hele antwoord opnieuw gegenereerd. In plaats daarvan wordt een contigu blok (van de eerste falende stap tot het einde) opnieuw gegenereerd ("patching"). Dit respecteert afhankelijkheden tussen stappen.
   • Voor JSON wordt een strikte herstel-prompt gebruikt om alleen het JSON-object te repareren.
5. Fallback-strategieën:
   • Skip-reuse: Als de inconsistentie te groot is (bijv. de kern van de wiskundige vergelijking is veranderd), wordt hergebruik vermeden en wordt het verzoek volledig opnieuw gegenereerd om inefficiëntie te voorkomen.
   • Deterministische fallback: Voor wiskundige taken die kunnen worden geverifieerd, garandeert StepCache correctheid door bij falende checks een minimale, deterministische oplossing te retourneren (bijv. v = v* berekend uit de vergelijking).

3. Belangrijkste Bijdragen

• Stap-level hergebruik: Een nieuwe abstractie voor LLM-serving die hergebruik toestaat op het niveau van individuele stappen in plaats van het hele antwoord.
• Selectieve patching met veilige fallbacks: Een mechanisme om alleen de falende regio's te regenereren, gecombineerd met een adaptieve beleid om hergebruik te skippen wanneer dit onproductief zou zijn.
• Taakbewuste verificatie en herstel: Implementatie van specifieke, goedkope verifiers voor twee representatieve families: gestructureerde JSON-output (vereiste sleutels, syntactische validatie) en lineaire vergelijkingen (wiskundige consistentie).
• Instrumentatie en evaluatie: Een volledig werkend prototype dat gedetailleerde accounting biedt (aantal calls, tokens, latentie) en een zware micro-benchmark biedt om robuustheid te testen.

4. Resultaten

De evaluatie vond plaats in een CPU-only micro-benchmark met zware perturbaties (paraphrasing en constraint-wijzigingen) op wiskundige en JSON-taken. De resultaten (gemiddeld over drie seeds) tonen aanzienlijke verbeteringen:

• Latentie: De gemiddelde latentie daalde van 2,13s naar 0,67s (een verbetering van ~3,2x). De mediaan daalde zelfs van 2,42s naar 0,01s, omdat het merendeel van de verzoeken de snelle "hergebruik"-pad volgt.
• Token-gebruik: Het totale token-verbruik daalde met 24% (van 36.1k naar 27.3k tokens), wat neerkomt op een daling van 162,7 naar 123 tokens per verzoek.
• Correctheid: De eindcorrectheid steeg van 72,5% naar 100% onder zowel taak-specifieke checks als integriteitschecks van de samengestelde output.
• Verdeling van uitkomsten:
  • 79,7% van de verzoeken volgde het snelle pad (alleen hergebruik).
  • 5,4% vereiste patching (hergeneratie van een blok).
  • 14,9% triggerde "skip-reuse" (volledige regeneratie) vanwege semantische veranderingen.

5. Betekenis en Toekomstperspectief

StepCache vult een belangrijke lacune in de LLM-serving-architectuur. Waar bestaande systemen kiezen tussen "alles of niets", biedt StepCache een granulaire, correcte en efficiënte tussenoplossing.

• Backend-agnostisch: Omdat het boven de model-runtime werkt en geen toegang vereist tot interne KV-gegevens, kan het als "drop-in" oplossing worden gebruikt met elke backend (zoals vLLM of lokale endpoints).
• Kostenefficiëntie: Door het vermijden van volledige regeneratie voor gedeeltelijk herbruikbare taken, worden rekenkosten en token-gebruik drastisch verlaagd.
• Toekomstige werk: De auteurs wijzen op de noodzaak om verifiers uit te breiden naar open-ended tekst (code, agent-workflows) en om de integriteit van de cache te versterken tegen adversariale aanvallen. Verdere evaluatie op GPU-systemen en met realistische werklasten (zoals BurstGPT-traces) staat gepland.

Kortom, StepCache demonstreert dat door slimme segmentatie en verificatie, LLM-diensten aanzienlijk sneller en goedkoper kunnen worden zonder in te leveren op de kwaliteit van het antwoord.