Marconi: Prefix Caching for the Era of Hybrid LLMs

Marconi: Prefix Caching for the Era of Hybrid LLMs

Speakers: Rui Pan, PhD Student, Princeton; Zhuang Wang, Zhen Jia, Can Karakus, Tri Dao, Ravi Netravali

Conference: MLSys 2025

YouTube: https://www.youtube.com/watch?v=None

Overview

In the rapidly evolving landscape of large language models (LLMs), a critical challenge persists: achieving efficiency under increasingly long context lengths. Traditional transformer-based LLMs, while powerful, grapple with the attention mechanism's quadratic computational complexity and the KV cache's linear memory scaling, both of which become bottlenecks as sequence lengths grow. This talk introduces Marconi, a pioneering prefix caching system specifically engineered to address these inefficiencies within the context of hybrid LLMs, which integrate both transformer attention layers and more efficient State Space Models (SSMs) like Mamba.

Presented by Rui Pan from Princeton, this work, a collaboration with researchers from AWS, tackles the fundamental problem that existing LLM serving systems and their optimizations, such as prefix caching, are built on assumptions tailored exclusively for transformers. SSMs, while offering superior efficiency at the modeling level by compressing context into fixed-size states, complicate system-level optimizations because their states are updated in place and cannot be easily "rolled back" to represent prefixes. Marconi's significance lies in its innovative approach to cache management, moving beyond conventional recency-centric strategies to judiciously admit and evict cache entries based on predicted reuse likelihoods and a novel flop efficiency metric. This enables hybrid models to leverage the benefits of prefix caching, ultimately improving throughput and reducing the time to first token (TDFT) latency.

Background

▶ Watch: Introduction and problem of LLM efficiency (0:00)

The journey of LLMs has been marked by an exponential increase in context lengths, pushing the boundaries of what these models can process and understand. At the core of most modern LLMs lies the transformer architecture, renowned for its ability to capture long-range dependencies through the attention mechanism. However, this power comes at a significant cost: the computational complexity of attention scales quadratically with the sequence length (O(N²)), making it prohibitively expensive for very long contexts. Furthermore, the KV cache, which stores key and value representations for previously processed tokens to avoid recomputing them, grows linearly with the sequence length (O(N)), quickly becoming a major memory bottleneck, especially for batch inference scenarios.

To circumvent these fundamental limitations, researchers have explored alternative architectures. State Space Models (SSMs), exemplified by models like Mamba, and other linear RNNs or linear attention variants such as sliding window attention, have emerged as promising solutions. These models diverge from the attention mechanism by compressing prior context into a recurrent, compact, and fixed-sized representation, referred to as SSM states. This design choice drastically alters the scaling properties: computational complexity becomes linear (O(N)), and memory consumption for the states becomes constant (O(1)), regardless of the sequence length. While these SSM states are fixed-sized, they are orders of magnitude larger than the KV pairs of a single token, as they aim to encapsulate similar information as a full sequence's KV cache.

Recognizing the strengths of both paradigms, the industry has moved towards hybrid models. These architectures strategically mix SSM layers with a few attention layers, aiming to strike an optimal balance between the efficiency offered by SSMs and the robust language modeling capabilities of transformers. Such hybrid models are increasingly being productionized by companies, with larger iterations continually under development.

Beneath the modeling layer, a sophisticated ecosystem of serving systems has evolved to deploy these LLMs at scale. These systems incorporate numerous optimizations, one of the most crucial being prefix caching. Prefix caching works by reusing the model states (specifically, the KV cache for transformers) of shared prefixes across multiple requests. For instance, if several users interact with a chatbot that starts with a common system prompt, the states corresponding to that prompt can be cached and reused, significantly reducing the time to first token (TDFT) by allowing subsequent requests to skip the "prefill" phase for the shared prefix.

However, applying prefix caching effectively to SSMs introduces a significant challenge. For transformer layers, reusing a prefix's state is straightforward: one can simply perform tensor slicing on the KV cache to extract the relevant portion. In contrast, SSM states are updated in place. This means that the state at the end of a sequence encapsulates the entire history up to that point and cannot be "rolled back" or sliced to represent an arbitrary prefix of the sequence. A naive approach might involve checkpointing—saving the SSM state every X tokens. But as the talk highlights, this strategy is highly inefficient. Each SSM state is considerably large, and these checkpointed states are often sparsely hit, meaning only a small fraction are actually reused by future requests. The speaker illustrated this with an experiment showing that with a checkpoint frequency of every 32 tokens, while 25% of KVs might be reused, less than 1% of SSM states are reused—a 65-fold difference. This leads to a bloated cache, frequent cache thrashing, and ultimately, low hit rates, undermining the very purpose of prefix caching. This fundamental incompatibility between SSM state management and traditional prefix caching forms the core problem that Marconi sets out to solve.

Key Findings

▶ Watch: Why prefix caching is tricky for SSMs (4:00)

Marconi represents a significant advancement in LLM serving infrastructure, specifically designed to bridge the gap between efficient hybrid model architectures and system-level optimizations like prefix caching. Its core contributions and findings are:

• First Prefix Caching System for Hybrid LLMs: Marconi is the pioneering system engineered to accommodate models with arbitrary layer compositions, encompassing pure transformers, pure SSMs, and critically, hybrid models that combine both. This addresses a critical unmet need as LLM architectures diversify.
• Judicious Cache Management Philosophy: The system's fundamental principle is to move away from the traditional recency-centric approach in caching. Instead, Marconi employs a more judicious strategy for both admission (deciding what to cache) and eviction (deciding what to remove from the cache).
• Reuse Likelihood-Based Admission: Marconi innovates in cache admission by estimating the reuse likelihood of prefixes. It categorizes potential prefix reusing scenarios into a taxonomy:
• Purely Input: Prefixes that are part of the input sequence of a prior request (e.g., system prompts, few-shot examples). Marconi observes and compares previous requests to identify these "hot" common prefixes.
• Input and Output: Prefixes that represent a continuation from a previous interaction (e.g., chatbots appending to the last decoded token).
• A radix tree is used to bookkeep requests and forecast these reuse likelihoods, with intermediate nodes representing high-utility branch-off points and leaf nodes marking sequence ends for potential appending.
• Flop-Aware Eviction Policy: To manage the heterogeneous nature of states in hybrid models (attention KVs vs. fixed-size SSM states), Marconi introduces a novel flop-aware eviction policy. This policy evaluates cache entries not just on recency, but also on their flop efficiency, defined as the compute saved per unit of memory. This allows for a more holistic cache management strategy that prioritizes entries providing the most computational savings for their memory footprint.
• Significant Performance Improvements:
• Token Hit Rate: Marconi achieves dramatically higher token hit rates, up to 34 times greater compared to baseline systems like VLM+ (which uses blocks of tokens for bookkeeping), by avoiding wasteful caching decisions and improving cache utilization.
• Time to First Token (TDFT) Reduction: While there's a minor, absolute hit (around 2 milliseconds) in TDFT for very short sequences (which hybrid models already prefill quickly), Marconi significantly reduces tail latencies. It lowers the P50 and P95 TDFT by approximately 20%, translating to hundreds of milliseconds of latency reduction for longer, more complex requests.
• Open-Source Availability: The Marconi codebase is open-source on GitHub, facilitating adoption and further research within the community.

These findings demonstrate that Marconi successfully overcomes the inherent challenges of prefix caching for SSMs and hybrid models, delivering substantial efficiency gains that are critical for deploying these advanced LLM architectures at scale.

Technical Deep Dive

▶ Watch: Introducing Marconi: first prefix caching for hybrid LLMs (6:00)

The core technical challenge Marconi addresses is the fundamental incompatibility between the in-place update mechanism of State Space Model (SSM) states and the requirements of traditional prefix caching. Unlike transformer KV caches, which can be easily sliced to represent a prefix, SSM states at the end of a sequence cannot be "rolled back." A naive approach of checkpointing SSM states at fixed intervals (e.g., every 32 tokens) leads to an explosion of large, sparsely hit cache entries, resulting in severe cache thrashing and extremely low reuse rates (less than 1% for SSM states compared to 25% for KVs in one experiment). Marconi circumvents this by adopting a "judicious" approach to both cache admission and eviction, moving beyond simple recency.

Judicious Admission: Forecasting Reuse Likelihoods

Marconi's admission strategy is built on the insight that while future prefix reuse patterns are not perfectly predictable, they can be sufficiently estimated by classifying common reuse scenarios. The system categorizes the token composition of all reused prefixes into two types:

1. Purely Input: This category includes prefixes that originate entirely from the input sequence of a prior request. Common examples are system prompts, which are often shared across many user interactions, or few-shot examples used for in-context learning. For these scenarios, Marconi actively observes and compares previous requests to identify frequently occurring, "hot" common prefixes. The assumption here is that if a prefix has been part of many previous inputs, it's likely to be reused again.
2. Input and Output: This case refers to scenarios where a new request continues from a previous interaction, typical in chatbots or agentic workloads. Here, the prefix often consists of the previous conversation's input and the model's generated output. Marconi specifically values and caches SSM states that represent the last decoded token between conversation rounds, as future turns typically append to this point.

To implement this, Marconi leverages a radix tree (also known as a prefix tree). This data structure is ideal for bookkeeping requests and forecasting reuse likelihoods because its nodes naturally correspond to the identified reuse scenarios:

• Intermediate nodes in the radix tree represent common branch-off points in sequences. These nodes naturally correspond to "purely input" prefixes that are shared across multiple requests, making them high-utility states for caching.
• Leaf nodes in the tree mark the end of a sequence. These nodes are significant for the "input and output" case, as future sequences (e.g., subsequent turns in a conversation) are likely to append to these specific endpoints.

By using the radix tree, Marconi can efficiently identify and prioritize states associated with these high-utility prefixes for admission into the cache, ensuring that valuable memory is not wasted on unlikely-to-be-reused states.

Judicious Eviction: Flop-Aware Cache Management

The challenge of eviction in hybrid models is compounded by the heterogeneous nature of the states involved: attention KVs and SSM states. These two types of states exhibit fundamentally different tradeoffs between memory consumption and the computational savings they deliver:

• Attention KVs scale linearly with sequence length, meaning longer sequences consume proportionally more memory in the KV cache but also save more compute (due to the quadratic nature of attention).
• SSM states are fixed-sized, regardless of the sequence length they represent. While they are larger than single-token KVs, their memory footprint does not grow with the sequence. However, they still save significant compute by avoiding re-computation of the recurrent updates.

To quantify and compare these disparate tradeoffs, Marconi introduces a novel metric: flop efficiency. This metric is defined as the compute saved per unit of memory for a cached state. Mathematically, it's calculated as the sum of skipped floating-point operations (flops) divided by the total memory used by the states across all stateful layers (both attention and SSM layers).

The talk illustrates the importance of flop efficiency with an example comparing three model types: a pure Mamba (SSM), a hybrid model, and a pure transformer. As sequence length scales, models with a higher proportion of SSM layers exhibit more flop-efficient states. This is because SSM states offer constant memory for linear compute savings, making them increasingly efficient compared to the linearly scaling memory of transformer KVs for quadratically scaling compute savings.

Traditional prefix caching systems, designed for transformers, typically rely on Least Recently Used (LRU) policies for eviction, valuing only recency. Marconi's flop-aware eviction policy extends this by evaluating cache entries based on a utility score that is a weighted sum of two components:

1. Recency Score: Reflects how recently the state was accessed.
2. Flop Efficiency Score: Reflects the compute savings per memory unit, as defined above.

The utility score for each node in the radix tree is computed as α (Flop Efficiency Score) + (1 - α) (Recency Score). The parameter α (alpha) provides a tunable mechanism to control the system's preference for flop efficiency over recency. When α is set to zero, the policy gracefully degrades to a pure LRU eviction. This flexible, flop-aware approach allows Marconi to make more informed eviction decisions, retaining states that offer the most significant computational benefits relative to their memory cost, rather than simply discarding the least recently used entries.

By combining the intelligent admission strategy based on a radix tree and reuse likelihoods with a nuanced, flop-aware eviction policy, Marconi provides a robust and efficient prefix caching solution for the complex and diverse landscape of hybrid LLMs.

Experimental Setup & Results

▶ Watch: Marconi's admission: categorizing prefix reuse likelihoods (8:00)

To validate Marconi's effectiveness, the researchers conducted a series of evaluations using a representative hybrid model. This model was configured with a composition of one attention layer for every six SSM layers, reflecting common hybrid architectures designed to balance performance and efficiency. The evaluations were performed across three distinct workloads, carefully chosen to cover both chatbot and agentic workloads, which typically involve shared prefixes and conversational continuations—scenarios where prefix caching is most beneficial.

The primary metrics used to assess performance were:

• Token Hit Rate: This metric quantifies the percentage of tokens that were successfully served from the cache, thereby allowing the model to skip the computationally expensive prefill phase. A higher token hit rate directly indicates better cache utilization and efficiency.
• Time to First Token (TDFT): TDFT measures the latency from when a request is received until the first output token is generated. Reducing TDFT is crucial for improving user experience and perceived responsiveness.

Marconi was benchmarked against two key baselines:

1. VLM+: An existing prefix caching system that uses blocks of tokens as its bookkeeping granularity. This baseline represents a more traditional approach to prefix caching.
2. S3LM+: A more sophisticated baseline that also employs a radix tree for judicious admission of states, similar to Marconi's approach. However, S3LM+ uses a standard LRU (Least Recently Used) policy for eviction, without considering the flop efficiency of different state types.

Headline Results

The experimental results demonstrated Marconi's superior performance across the board:

• Token Hit Rate: Compared to VLM+, Marconi achieved a significantly higher token hit rate, showing an improvement of up to 34 times. This dramatic increase highlights Marconi's effectiveness in avoiding wasteful caching decisions and optimizing cache utilization, directly attributable to its judicious admission and eviction policies.
• TDFT Reduction (P50 and P95): For the critical Time to First Token (TDFT) metric, Marconi delivered substantial improvements, particularly for tail latencies. It reduced the P50 (median) and P95 (95th percentile) TDFT by approximately 20%. This translates to a reduction of hundreds of milliseconds for users, significantly enhancing the perceived responsiveness of LLM applications.

Insights from Flop-Aware Eviction

A closer examination of Marconi's flop-aware eviction policy revealed an interesting trade-off and its benefits:

• Comparison with S3LM+: When comparing Marconi with S3LM+, which uses a radix tree for admission but LRU for eviction, Marconi exhibited a higher token hit rate for longer sequences or sequences identified as having higher flop efficiency. Conversely, S3LM+ sometimes showed a slightly higher hit rate for shorter sequences.
• Prioritizing Longer Sequences: Marconi's design explicitly prioritizes caching entries that offer higher flop efficiency. Since longer sequences generally consume more computational resources (flops), Marconi intelligently favors caching their states over shorter ones, even if they were accessed less recently.
• TDFT Trade-off: This prioritization strategy resulted in a slight hit in TDFT for shorter sequences, estimated at approximately two milliseconds. However, this is considered a "neat tradeoff" because hybrid models are inherently efficient at prefilling short sequences, meaning their absolute latency is already low. The minimal increase of 2ms for short sequences is a small price to pay for the significant gains achieved for longer, more expensive requests.
• Overall Impact: By optimizing for flop efficiency, Marconi ensures that the cache space is allocated to states that yield the greatest overall computational savings, leading to a substantial reduction in tail latencies (P50 and P95 TDFT) for the workloads that benefit most from efficient caching.

In summary, the experimental results unequivocally demonstrate that Marconi's judicious, flop-aware approach to prefix caching provides a robust and highly effective solution for improving the efficiency and responsiveness of hybrid LLMs, particularly under demanding, long-context workloads.

Practical Implications

▶ Watch: Marconi's eviction: flop efficiency for state types (12:00)

Marconi's innovations in prefix caching for hybrid LLMs carry significant practical implications for various stakeholders involved in the deployment and operation of large language models.

For practitioners and infra teams responsible for serving LLMs at scale, Marconi offers a crucial enabling technology. As model architectures diversify beyond pure transformers to incorporate State Space Models (SSMs) like Mamba and other linear attention variants, traditional serving optimizations become less effective or even counterproductive. Marconi provides the first robust and efficient solution for prefix caching in this heterogeneous environment, allowing these teams to leverage the performance benefits of hybrid models without sacrificing the efficiency gains from caching common prefixes. This means better resource utilization, higher throughput, and ultimately, lower operational costs for LLM inference.

Model builders and deployers gain more flexibility in choosing model architectures. With Marconi, the decision to use a hybrid model (e.g., one attention layer for every six SSM layers) no longer implies a compromise on prefix caching capabilities. They can confidently design and deploy models that balance efficiency and language modeling capabilities, knowing that system-level optimizations will work effectively. This allows for a wider exploration of model architectures tailored for specific use cases, where the benefits of SSMs (linear scaling, constant memory for states) can be fully realized.

The core contribution of Marconi—moving away from a purely recency-centric caching approach—is a paradigm shift that will likely influence future LLM serving system designs. The introduction of flop efficiency as a metric for cache management provides a generalized framework for evaluating the utility of diverse state types, which is particularly relevant as LLM architectures continue to evolve rapidly. This metric allows infrastructure teams to make more informed decisions about what to cache, ensuring that valuable memory resources are allocated to states that deliver the greatest computational savings, rather than simply the most recently used.

Tradeoffs and Limitations: While Marconi offers significant advantages, it also highlights inherent tradeoffs. The slight increase in TDFT (approximately 2 milliseconds) for very short sequences is a minor limitation. However, this is a pragmatic design choice, as hybrid models are already quite efficient at processing short inputs. The benefit of substantially reducing P50 and P95 TDFT (by 20% or hundreds of milliseconds) for longer, more complex, and thus more expensive requests far outweighs this minor latency increase for simpler queries. This trade-off prioritizes the user experience for computationally intensive tasks, where latency is often most critical. Furthermore, the alpha parameter in the flop-aware eviction policy, which weights recency versus flop efficiency, needs careful tuning based on specific workload characteristics and desired performance profiles. While this offers flexibility, it also implies an additional configuration step for optimal deployment.

In essence, Marconi future-proofs LLM serving infrastructure for the era of diverse and hybrid model architectures. By enabling efficient prefix caching for these models, it helps unlock their full potential, leading to more responsive, cost-effective, and scalable LLM deployments across a wide range of applications. Its open-source availability further lowers the barrier to adoption and encourages community-driven improvements.

Key Takeaways

• Hybrid LLMs Present Caching Challenges: While hybrid models (mixing SSM and attention layers) offer efficiency benefits over pure transformers, their in-place state updates complicate traditional prefix caching mechanisms.
• Marconi Solves a Critical Gap: Marconi is the first prefix caching system specifically designed for LLMs with arbitrary layer compositions, including pure transformers, pure SSMs, and crucial hybrid models.
• Judicious Cache Admission: The system employs a novel admission strategy based on a taxonomy of reuse likelihoods (purely input and input and output prefixes), efficiently managed by a radix tree for forecasting.
• Flop-Aware Eviction Policy: Marconi introduces a groundbreaking flop-aware eviction policy that considers both recency and flop efficiency (compute saved per unit memory), allowing for intelligent cache management of heterogeneous state types.
• Significant Performance Gains: Marconi achieves up to 34 times higher token hit rate and reduces P50 and P95 TDFT by approximately 20% (hundreds of milliseconds) compared to baselines.
• Pragmatic Trade-offs: It makes a strategic trade-off, accepting a minimal 2ms TDFT increase for very short sequences to achieve substantial tail latency improvements for longer, more computationally intensive requests.

About the Speaker(s)

The primary speaker for this presentation was Rui Pan, a third-year PhD student at Princeton University. The work presented on Marconi is a collaborative effort, involving contributions from numerous individuals. The team includes Zhuang Wang, Zhen Jia, Can Karakus, and Yida from AWS, indicating a strong industry-academic partnership. Additionally, Tri Dao and Ravi Netravali from Princeton were key collaborators on this project, bringing expertise from both research institutions.