[Paper Review] Marconi: Prefix Caching for the Era of Hybrid LLMs

Paper Link

Marconi: Rethinking Prefix Caching for the Hybrid LLM Era

TL;DR

Marconi introduces a prefix-caching framework for hybrid LLM inference (Attention + SSM).
It selectively admits only highly-reusable prefixes and applies FLOP-per-byte–aware eviction, yielding up to 34.4× higher token-hit rate and 71.1 % lower P95 TTFT (−617 ms) compared with enhanced baselines (vLLM+, SGLang+).
(Evidence: Abstract, Fig. 7–9, § 5.2)

Core Idea

• Underlying Problem — “Exact-Match Only” Limitation:
  In hybrid LLMs, the SSM states are updated in place, so partial prefix reuse is impossible.
  Only exact matches can hit the cache, causing state explosion and poor reuse rates (§ 1).

• Solution Strategy:

  1. Admission Policy: Classify prefix reuse scenarios into
     (a) Purely Input and (b) Input + Output,
     checkpointing only prefixes with high reuse potential (§ 4.1).
  2. Eviction Policy: Score each entry by FLOP efficiency (saved FLOPs / state memory),
     then combine with recency to form S = recency + α · FLOP efficiency,
     determining which entries to evict (§ 4.2, Eq. 1–2).

Background — What Problem Does It Solve?

Transformers suffer severe serving inefficiency for long contexts due to
prefill cost O(L²) and KV memory O(L).
Hybrid models that interleave State Space Models (SSMs)—typically with ratios around Attn:SSM ≈ 1 : 6–10—mitigate this,
but because SSM states are fixed-size and must exactly match,
traditional prefix caching schemes (mostly LRU and KV-centric) lose their effectiveness (Fig. 1, § 2.1–2.2).

Example of the problem: In a 7 B hybrid model, a single 10 K-token input already occupies 17.4 GB of state memory,
3.3× larger than a Transformer baseline, causing cache thrashing and low hit rates (§ 3).

A New Approach — Marconi

Marconi is the first prefix-caching system designed for hybrid LLMs, combining
(i) reuse-potential–based admission and (ii) FLOP-efficiency–based eviction.
All states (KV and SSM) are managed within a single radix tree, ensuring precise and consistent state reuse (§ 4, Fig. 4).

• Admission Policy

  • Classification: Distinguish between
    Purely-Input prefixes (e.g., system prompts or examples) and
    Input + Output prefixes (e.g., dialog histories) (§ 4.1).
  • Rule: Checkpoint only the SSM state at the final token of each edge—the minimal coverage for maximal reuse—and, for interactive sessions, preserve the state after the last decoded token (Fig. 4, § 4.1).

• Eviction Policy

  • FLOP Efficiency Definition: \[ \text{FLOP-eff} = \frac{\text{Saved FLOPs (across all layers)}}% {\text{State Memory (SSM + KV)}} \] (Eq. 1)
  • Utility Score: \[ S(n) = \text{recency}(n) + \alpha · \text{FLOP-eff}(n) \] When α = 0, Marconi reduces to LRU.
    The authors replay workload snapshots and use grid search to select α automatically (Eq. 2, § 4.2).

How It Works — A Step-by-Step Example

Let’s illustrate the mechanism using a simple example.
Assume we have two sentences: NYC is a busy city → followed by NYC is very huge.
(Tokens are segmented by spaces.) (Ref: Fig. 4)

1. Request 1 — Prefill & Decode

   • The radix tree creates a path for NYC is a busy city.
     Only the SSM state at the final token of each edge is checkpointed. (§ 4 / Fig. 4)

2. Request 2 — Speculative Insertion

   • The new sequence NYC is very huge is virtually inserted into the tree.
     If a branch point appears, that node’s SSM state is checkpointed (Fig. 4 (b)).

3. Exact-Match Hit & Cache Reuse

   • Because hybrid models permit only exact-match reuse (due to in-place SSM updates),
     if the prefix up to the branch point matches, the node’s (SSM, KV) pair is reused,
     skipping the redundant prefill (§ 1, Fig. 2).

4. Eviction Example

   • When the cache fills, compute each node’s utility \(S(n)\).
     Nodes with low recency but high FLOP efficiency (typically long sequences) are retained,
     while short, low-value entries are evicted (§ 4.2, Fig. 5).

Performance Verification — Key Results

Experimental Setup (Summary)
Hybrid 7 B model with layers {Attn = 4, SSM = 24, MLP = 28}, FP16 precision,
running on AWS p4d.24xlarge (A100-40 GB × 8).
For TTFT analysis, they also used Jamba-1.5-Mini (12 B active / 52 B total, state dim = 128, A100-40 GB × 4) (§ 5.1).

A. Headline Numbers

• Token Hit Rate: Compared with vLLM+, Marconi achieves 4.5× / 7.3× / 34.4× higher rates on LMSys / ShareGPT / SWEBench (Fig. 7).
• P95 TTFT Reduction (vs vLLM+): 36.1 % / 71.1 % / 46.8 %, corresponding to −275.4 ms / −103.3 ms / −617.0 ms (Fig. 9).
• P95 Hit Gain (vs SGLang+): +45.6 % / +19.0 % / +219.7 % (Fig. 8).

B. Summary Table — Equal Settings Comparison

C. Detailed Observations

• Length-Dependent Gains:
  For short requests (< 7 K tokens), the hit rate drops slightly (up to −3.0 pp) while P5 TTFT rises only +2.1 ms.
  For long requests (≥ 7 K), the hit rate improves by +25.5 pp and FLOP savings reach +90.3 % (Fig. 10).

• Cache Contention (60 → 140 GB):
  Marconi’s advantage peaks under moderate contention, with improvements of 24.3 / 51.5 / 68.3 / 30.0 / 10.0 % across settings (Fig. 11).

• Architecture Scaling:
  As the Attn:SSM ratio grows from 1:2 to 1:8, Marconi’s gain over vLLM+ / SGLang+ increases from 13.5 % / 5.8 % to 2.6× / 59.7 %.
  In pure Transformer models, all systems perform identically (Fig. 12a).

Our View — Strengths, Limitations, and Why It Matters

Strengths

1. Accurate Problem Formulation — Marconi quantifies how the “exact-match restriction” and fixed-size SSM states break the assumptions behind LRU and size-based policies, formalizing it via Eq. (1),(2) and micro-benchmarks (§ 3–4, Fig. 5).

2. Empirically Validated Policy Design — Combining Admission and Eviction policies boosts hit rate by up to 34.4× and reduces P95 TTFT by 617 ms on long-sequence workloads (Fig. 7–9).

3. Trend Alignment — The higher the SSM ratio and state dimension, the larger the gain — well aligned with the direction of next-gen hybrid architectures (Fig. 12).

Limitations (Recognized and Observed)

• Short Requests (< 7 K): Hit rate drops by up to −3 pp and P5 TTFT rises by +2.1 ms, though P50/P95 still improve (Fig. 10).
• Contention Extremes: At high (60 GB) or low (140 GB) cache sizes, Marconi’s advantage shrinks since either useful prefixes cannot fit or eviction decisions rarely matter (Fig. 11).
• Pure Transformers: All methods perform identically (Fig. 12a).
• System Dependency: Chunked prefill for hybrid models still requires specialized kernels under development in most frameworks, and KV attention still depends on paging management (§ 6).

Why It Matters

Hybrid architectures are a practical path to supporting long contexts (Attention + SSM).
At its core, the problem is “which prefixes should be kept?”
By introducing FLOP-per-byte as a first-principles metric, Marconi normalizes cache decisions in terms of the model’s physical workload properties.
This provides a bridge to future stack-level optimizations such as KV paging and prefix-driven attention acceleration (e.g., Hydragen) (§ 4–6).

What Comes Next? — The Road Ahead

• KV Paging × FLOP-aware Integration
  Currently, SSM states are non-paged, while KV attention still requires paging.
  By extending Marconi’s FLOP-efficiency scoring to page replacement,
  both can share a unified global utility function for consistent optimization (§ 6).

• Dissemination of Chunked-Prefill Kernels
  To eliminate the overhead of 2-pass or approximate checkpointing,
  the authors call for widespread adoption of specialized kernels in mainstream frameworks (§ 6).

• Load-Adaptive Policy Tuning
  Because Marconi’s benefit peaks under medium contention,
  an online adaptation of α(t) based on session arrival rate could maximize hit-rate efficiency (Fig. 11 & 13).

• Synergy with Attention Accelerators
  Prefix-sharing systems like Hydragen already sustain throughput losses below 15 %
  even for 16 K-token prefixes—suggesting a natural synergy:
  Marconi decides what to keep; Hydragen decides how to use it fast (Hydragen Abstract & § 4).

Appendix — Experimental Notes (for Reproducibility)

• Datasets / Traces: LMSys, ShareGPT, SWEBench — each comprising multi-turn sessions with variable request intervals to mimic real-world latency (§ 5.1).
• Models / Hardware: 7 B Hybrid {Attn 4 | SSM 24 | MLP 28}, Jamba-1.5-Mini (12 B active / 52 B total, state dim = 128), FP16 on A100-40 GB (§ 5.1).
• Baselines: vLLM and SGLang lack native hybrid support,
  so the authors built hybrid-compatible versions (vLLM+, SGLang+) for fair comparison (§ 5.1).

In one sentence:
By redefining the twin axes of Admission (reuse probability) and Eviction (FLOPs per byte),
Marconi consistently achieves higher hit-rates (×) and lower TTFT ↓
in realistic hybrid serving environments dominated by long-context SSM workloads (Fig. 7–9, § 5.4).

Click to Expand — Detailed LLM Q&A Analysis