# The CAP Principle for LLM Serving: A Survey of Long-Context Large Language
Model Serving

Pai Zeng
Huawei Cloud & SJTU
Zhenyu Ning
SJTU
Jieru Zhao
SJTU
Weihao Cui
SJTU
Mengwei Xu
BUPT
Liwei Guo
UESTC
Xusheng Chen
Huawei Cloud
Yizhou Shan
Huawei Cloud

###### Abstract

We survey the large language model (LLM) serving area to understand the
intricate dynamics between cost-efficiency and accuracy, which is magnified by
the growing need for longer contextual understanding when deploying models at
a massive scale. Our findings reveal that works in this space optimize along
three distinct but conflicting goals: improving serving context length (C),
improving serving accuracy (A), and improving serving performance (P). Drawing
inspiration from the CAP theorem in databases, we propose a CAP principle for
LLM serving, which suggests that any optimization can improve at most two of
these three goals simultaneously. Our survey categorizes existing works within
this framework. We find the definition and continuity of user-perceived
measurement metrics are crucial in determining whether a goal has been met,
akin to prior CAP databases in the wild. We recognize the CAP principle for
LLM serving as a guiding principle, rather than a formal theorem, to inform
designers of the inherent and dynamic trade-offs in serving models. As serving
accuracy and performance have been extensively studied, this survey focuses on
works that extend serving context length and address the resulting challenges.

##  1 Introduction

Large language models (LLMs) and their underlying transformer architecture
have revolutionized AI and have become the bedrock of many emerging
applications. The ecosystem around LLM is on an upward spiral towards
artificial general intelligence (AGI): the number of new LLMs and their
applications skyrocketed, and as of 2024, LLM-based applications already
outperform humans across many tasks such as image classification and visual
reasoning [1, 2]. High-quality models are essential for any realization of
AGI, but it’s equally important to deploy and serve models at a massive scale
with a reasonably low cost without compromising their accuracy. The conflict
between serving accuracy and serving performance (e.g., tokens per second.) is
a hard one, prompting extensive research in this area [3, 4]. Generally, there
is no one-size-fits-all solution in production settings. Optimizations to
improve performance can lead to reduced accuracy and vice versa. For example,
sparsity and quantization are two common techniques that trade accuracy for
better performance.

Unfortunately, this conflict between accuracy and performance has been
exacerbated recently by the growing demand for longer contextual understanding
when deploying models in practice [5]. This introduces new complexities as the
transformer’s attention mechanism exhibits a quadratic increase in resource
consumption with longer contexts [6]. Furthermore, LLMs struggle to utilize
information from longer contexts effectively [7]. Essentially, the need for
long-context serving breaks the fragile balance between serving accuracy and
performance, and calls for novel system designs.

To explore the complex relationship between accuracy and performance in large-
scale model deployments, particularly for handling long contexts, we conducted
an extensive survey of the LLM serving area. We highlight three key
observations after reviewing related literature.

  1. 1.

First, we find the scope of a serving system has expanded. It comprises two
system layers: a model serving layer and an agent serving layer. The model-
layer system runs a given LLM model, typically exposing model inference as its
northbound APIs [8, 9]. Works at this layer commonly optimize the model
structure [10, 11], cache [8, 12], scheduling [13, 14], etc. The agent-layer
system sits atop the model-layer system and results from emerging LLM-based
system applications that leverage LLM-driven workflow to improve a raw LLM
model’s accuracy and efficiency while handling complex real-world tasks [15].

  2. 2.

Second, we find works in this space optimize along three distinct goals:
improving serving context length (Context), improving serving accuracy
(Accuracy), and improving serving performance (Performance). Specifically,
context means the number of tokens in the context window; accuracy means
evaluation metrics on certain tasks (e.g., MMLU), and performance means time-
to-first-token, tokens per second, price per million tokens, etc.

  3. 3.

Finally, we find a trilemma among the above three goals regardless of which
layer they are applied to. We find that any serving optimization can only
improve at most two distinct goals. We also observe progress in one direction
does not lead to progress in others. For example, using positional embedding
to extend a model’s range does not improve the model’s accuracy beyond the
context length [16], and using quantization [11], pruning [17], and sparsity
[12] enable one to serve a model with faster speed but at the cost of
potentially lower accuracy.

Based on the above observations and inspired by the classical CAP theorem in
databases [18], we propose the CAP principle for LLM serving, which states
that any given LLM serving optimization, regardless of which system layer it
is applied to, can improve at most two of the following goals:

  * •

Context: The length of context effectively processed and perceived by end
users.

  * •

Accuracy: The precision of outputs as evaluated by end users, based on
specific task metrics.

  * •

Performance: The efficiency of token processing and generation perceived by
end users.

Figure 1: The CAP principle for LLM Serving. C is improving context length, A
is improving accuracy, and P is improving serving performance or cost-
efficiency in general. It states that any serving optimization can improve at
most two of the above three goals.

The perspective of the proposed CAP principle emphasizes what end users
perceive from applying a specific optimization to a remote LLM serving system
rather than focusing on a specific component within the LLM serving system.
This is crucial because we care whether an LLM serving system as a whole can
serve AGI rather than a singular improvement in one direction. In general,
this principle leads to six types of optimizations: C, A, P, CA, CP, and AP,
depending on which goals are prioritized.

The LLM’s CAP principle is similar to the database’s CAP theorem in many ways.

  * •

Both state that you must forfeit at least one goal to achieve the others.
Since our focus is on long-context serving, maintaining a lengthy context (C)
is essential. This leaves us with two options: improving accuracy (A) or
improving performance (P). Improving accuracy relies on devising new
algorithms to better leverage the feature of lengthy context. However, these
algorithms could hurt model execution cost-efficiency due to increased FLOPs,
hardware-unfriendly operations, etc. On the other hand, enhancing performance
on specific hardware through techniques like quantization and sparsity usually
comes at the cost of reduced accuracy. Although there are methods to increase
performance without losing accuracy, they generally require additional
hardware resources.

  * •

Their goals are measured continuously rather than in binary. The definition
and continuity of user-perceived measurement metrics are crucial in
determining whether a goal has been met. Some recent studies have examined
this aspect for accuracy [19, 20]. The availability of the database’s CAP and
the accuracy of the LLM’s CAP both range from 0 to 100. The accuracy of LLM’s
CAP principle, like the availability of the database’s CAP theorem, does not
have to be 100%. It just has to be high enough that end users deem it useful.
Thus, from a system’s perspective, an optimization categorized as CP might
still be perceived as achieving all three CAP goals if it fulfils the user’s
accuracy requirements, similar to how CAP is observed in practical databases
[21].

  * •

Both are originally proposed to keep system designers aware of the hard design
trade-offs while deploying large-scale systems.

We foresee the possibility of a true CAP in the future, in which there is no
inherent conflict among these goals. The proposed CAP principle primarily
arises from the use of transformer-based LLMs on existing AI chips, reflecting
both the constraints and capabilities of today’s hardware and software. As we
progress towards AGI, both models and hardware are expected to evolve
significantly. Emerging technologies are likely to be developed in tandem,
with new models specifically designed to optimize performance on the next
generation of hardware. This synergy between evolving models and hardware is
crucial for overcoming current barriers and achieving a true CAP in LLM
serving.

Our survey is organized based on the propose CAP principle. Compared to prior
surveys [4, 3, 22, 23, 24, 25, 26], we makes two unique contributions. First,
we propose the CAP principle for LLM serving and map existing works onto the
CAP landscape to highlight the tension among them. Second, we approach the
large-scale LLM serving system as a whole rather than focusing on a specific
technique (e.g., RAG [26], long-context [23]), or a layer (e.g., model [3],
agent [25]). In the rest of the paper, we will discuss works as listed in
Table 1 and Figure 2. We focus on works that extend serving context length and
address the resulting accuracy and performance issues. Specifically, we will
cover model memory (Table 2), positional embedding (Table 3), found-in-the-
middle, distributed acceleration for long context, prompt compression,
sparsity (Table 5), and agent memory (Table 7).

##  2 CAP for LLM Serving

Table 1: The CAP theorem for LLM serving results in six types. Type | Optimizations
---|---
C | Model Memory, Positional Embedding
A | Found-in-the-middle
P |  Sparse Attention, Linear Attention, Distributed Accl., Quantization, Model Pruning
CP | Prompt Pruning
CA | Agent Memory
AP | N/A
Figure 2: A modern-day LLM serving system commonly has two layers: a model
layer, which runs a given LLM model, and an agent layer, which runs LLM-based
system applications. PE means Positional Embedding. Quant is short for
quantization.

###  2.1 Overview

We survey the area and map them onto Table 1 across the agent and model layers
as depicted in Figure 2. Remarkably, we can map all existing LLM serving
optimization works onto six types resulting from CAP, highlighting that our
proposed CAP principle reflects the inherent and long-standing design trade-
offs in this area.

An overview of Table 1:

  * •

There are six types: C, A, P, CA, CP, and AP, depending on which goals are
prioritized.

  * •

C: works in this area only improve the context length of an LLM serving
system. Our research identifies two approaches to improve C. We dub the first
as Model Memory, a line of work that augments the transformer with recurrence
and dynamic external memory. The other is Positional Embedding, which extends
the context window of the model to a longer context and more tokens.

  * •

A: works in this area address the accuracy issues that arise from long-context
serving. A few initial works exist, such as found-in-the-middle, but some
forfeit P for a better A.

  * •

P: works in this area improve serving performance or cost-efficiency in
general. We focus on two lines of work specifically proposed for improving
long-context serving. The first is distributed acceleration, which explores
sequence parallelism for faster processing. The second is sparsity, which
reduces the computation and memory usage for better performance

  * •

CP: this type of work improves both at the same time. We have identified
prompt compression as this category’s only line of work.

  * •

CA: this type of work improves both at the same time. We have identified agent
memory as this category’s only line of work.

###  2.2 Improve Context (C)

This section surveys work that extends serving systems’ context length to
address the increasing demand for long-context reasoning. We will discuss two
approaches. We dub the first as Model Memory, a line of work that augments the
transformer architecture with recurrence and dynamic external memory. The
other is Positional Embedding, which extends the context window of LLMs to
deal with more tokens.

####  2.2.1 Model Memory

Table 2: Comparing model memory works. Work |  Memory Aggregation |  Memory Org. |  Memory Retrieval |  Memory Update |  Memory Eviction
---|---|---|---|---|---
Transformer-XL [10] | dot-attention | FIFO | all | None | Discard
Compressive Transformer [27] | dot-attention | FIFO | all | None | Discard
Memorizing Transformer [28] | learned-gate | FIFO | kNN | None | Discard
Memformer [29] | dot-attention | random | all | Yes | Yes
Memory Transformer [30] | soft prompt | random | all | Yes | Yes
RMT [31] | soft prompt | FIFO | all | None | Discard
AutoCompressor [32] | soft prompt | FIFO | all | None | Discard
Infini-Attention [33] | learned gate | random | linear | Yes | Yes

One way to extend the context length of transformers is by adding memory to
hold long-range information. Model memory is a term we dubbed for such a line
of work, which augments the transformer architecture with recurrence and
dynamic external memory. At its core, model memory builds a memory system for
the transformer, enabling it to examine past long-range information.

##### Taxonomy from the systems perspective

We realize that managing the transformer model’s augmented memory is similar
to the classical virtual memory management in OS [34], which centers around
organizing memory, what to read, update, and what and when to evict. To this
end, we propose to compare model memory works by mapping them into the
following five dimensions.

  * •

Memory Aggregation: dictates how to aggregate local memory with global memory
(retrieved from the augmented memory). It can be attention, learned gate, or
soft prompt.

  * •

Memory Organization: dictates how the external augmented memory is organized.
It can be a FIFO buffer or random-access buffer, with fixed memory size. It
appears there is no dynamic-sized memory due to capacity concerns.

  * •

Memory Retrieval: dictates how and what to retrieve from the augmented memory.
Most works will retrieve the full memory, while others retrieve a portion
using certain algorithms.

  * •

Memory Update: dictates how to update the augmented memory when there is a new
memory. If it is FIFO memory, the update means enqueue. If it is random
memory, the update will use certain algorithms to update all or parts of the
memory.

  * •

Memory Eviction: dictates what to evict when the augmented memory is full. If
it is FIFO memory, the eviction discards the tail memory. If it is random
memory, no eviction will occur as memory is updated in place.

We now delve into works listed in Table 2.

  * •

Transformer-XL [10] adds recurrence to the transformer architecture. It
captures long-term dependency using a per-layer memory buffer and segments
long sequences into fixed-size segments to capture segment-level recurrence
between adjacent layers. Its memory organization is FIFO, and there are no
update rules. Old memories are discarded as new segments come in. During
inference, it aggregates the hidden states read from memory and local states
from the current segment using dot-product-attention. Compressive Transformer
[27] adds a second-level compressed memory to Transformer-XL. It extends the
context further without changing the core mechanisms. Memorizing Transformer
[28] takes a slightly different approach. Instead of reading the whole memory,
it uses a kNN algorithm to retrieve from the external memory and aggregates
via a learned gate. The above three works discard information from the distant
past.

  * •

Memformer [29] adds a fixed-size dynamic external memory to the transformer
architecture. It uses random-access memory rather than the FIFO memory used by
the former two works. It segregates the memory into many slots and devises an
attention-based algorithm to update the memory slots independently.
Additionally, it uses a forgetting mechanism to evict memory slots that are
not updated for many timestamps. By doing so, it attends to more important
information and claims a theoretically infinite temporal range of
memorization.

  * •

Memory Transformer [30] differs from Memformer [29] in that the former uses
soft prompt [35] to aggregate information from external memory with the
current prompt. It prepends memory tokens to tokenized user prompts and uses
an unmodified attention module to enable memory tokens to attend to long
sequences.

  * •

RMT [31] and AutoCompressor [32] use soft prompting to add memory tokens to
the beginning of the prompts, which is similar to Memory Transformer [30] and
segment-level recurrence as in Transformer-XL [10]. Both are built based on
Transformer-XL’s code base.

  * •

Infin-Attention [33] is the latest work in this category. It closely
integrates compressive and dynamic memory with the vanilla dot-product
attention layer to enable models to attend to infinite context length. It
adopts an associative matrix as its memory, allowing random access. It
retrieves memory using linear attention and updates memory using a delta
update rule. It aggregates retrieved memory with a local attention state using
a learned gate. This approach uses less compute and memory compared to the
vanilla Transformer-XL.

In summary, the model memory line of work augments the original transformer
architecture with dynamic and compressive memory, enabling the model to
process long or even infinite contexts. They differ in how they access the
memory, how memory is updated, etc. Since most of them either discard or
compress memory, they inevitably hurt A. They are neutral in P as they do not
address the quadratic complexity in the attention mechanism.

####  2.2.2 Positional Embedding

Table 3: Comparing positional embedding works. Work | Location |  Require Training | Adaptive | Integration
---|---|---|---|---
ALiBi [36] | After QK multiply | ✓ | ✗ | Add
XPOS [37] | Before QK multiply | ✓ | ✗ | Multiply
CLEX [38] | Before QK multiply | ✓ | ✓ | Multiply
Linear Interpolation [39] | Before QK multiply | ✗ | ✗ | Multiply
NTK Interpolation [40] | Before QK multiply | ✗ | ✗ | Multiply
YaRN [41] | Before QK multiply | ✓ | ✓ | Multiply
FIRE [42] | After QK multiply | ✓ | ✓ | Add
LongRoPE [43] | Before QK multiply | ✓ | ✓ | Multiply

This line of work focuses on positional embedding (PE), enabling LLM to handle
long context sequences (hence improving C). In Table 3, we compare them across
four dimensions.

  * •

Location: where is position information being encoded into token
representation.

  * •

Require training: whether it can plug-and-play without re-training.

  * •

Adaptive: whether it can adapt and adjust based on the input.

  * •

Integration: how are position representations integrated with token
representations.

Our discussion below is categorized as extrapolation and interpolation.

  * •

Position Extrapolation. This strategy extends the position embedding beyond
the max context length used in training. For example, ALiBi [36] introduces
relative positional embedding and a learnable linear bias on attention, which
allows the model to dynamically adjust the attention distribution according to
the actual length of the sequence. XPOS [37] introduces an additional
exponential decay term based on ROPE, which allows attention to decay with
increasing relative distance. CLEX [38] models the continuous dynamics as an
ordinary differential equation with length scaling factors by generalizing the
position-embedding scaling.

  * •

Position Interpolation: This strategy scales the input position encoding index
range to the context window of a model. For example, Linear Interpolation [39]
introduces a position interpolation technique that directly reduces the
position index. In this way, the maximum position index matches the previous
context window constraints of the pre-training phase and hence extends the
context window. Inspired by Neural Tangent Kernel (NTK) theory, the model
using only positional interpolation would have difficulty recognizing the
order and position of neighboring tokens. NTK Interpolation [40] devised a
nonlinear method that changes the base in RoPE to adjust the scaling factor
dynamically. YaRN [41] combines NTK Interpolation and Linear Interpolation and
introduces an attention distribution correction strategy to offset the
distributional bias in the attention matrix caused by long inputs. FIRE [42]
uses a learnable continuous function to map position information to biases and
proposes progressive interpolation to address generalization issues when input
lengths are outside the training domain. LongRoPE [43] improves the position
interpolation method by recognizing and exploiting non-uniformity in the RoPE
dimensions and non-uniformity in the token positions. PoSE [44] introduces a
training approach called Positional Skip-wise Method, which emulates extended
inputs within a fixed context window by applying tailored skipping bias terms
to adjust the position indices for each segment.

In summary, the research on positional embeddings enhances the model’s ability
to generalize positional information that was not present during the training
phase through both extrapolation and interpolation. These methods vary
depending on whether the input position index range is scaled to fit within
the model’s context window. They are neutral in C and P. and we believe they
are crucial for achieving long-context serving.

###  2.3 Improve Accuracy (A)

A longer C challenges A. This section focuses on works that address the
accuracy issues that arise from long-context LLM serving. Lost-in-the-middle
[7] is a pioneer work in analyzing how LLMs utilize long context. They found
that existing LLMs cannot robustly utilize information in a lengthy context,
and the position of the documents will affect the final serving accuracy. This
drawback will limit long-context LLM’s usage in practical applications,
leading to biases in outputs.

We find three works to address this issue.

  * •

Attention Sorting [45] addresses this issue by placing critical information at
the end of the input prompt. They achieve this by performing one step of
decoding, sorting documents by the attention they receive (highest attention
going last), repeating the process, generate the answer with the newly sorted
contexts. Though it could improve A, this approach’s limitations are clear:
not all tasks map to a set of documents, and the extra sorting adds non-
trivial overhead, hurting P.

  * •

Attention Bucket [46] uses multiple model replicas, each with a distinct based
angle for the rotary position embedding. This creates a unique attention
waveform to enhance LLM’s awareness of various contextual positions. This
solution works across the model-layer and agent-layer. They improve A but
forfeit P because they require multiple replicas to process the input prompt.

  * •

Found-in-the-middle [47] takes a much lighter approach. They found that the
lost-in-the-middle phenomenon likely arises from two factors: casual attention
in which LLMs disproportionately favor initial tokens [12] and long-term decay
effect of RoPE [16] that diminishes the attention score of distantly
positioned yet semantically meaningful tokens. Their answer is Multi-scale
Positional Encoding (Ms-PoE), which assigns different scaling ratios to
different attention heads to preserve information learned from the pre-
training step while using the position indices rescaling to mitigate the long-
term decay effect. This work belongs to the model layer and improves A without
adding extra overhead.

In summary, improving A under a long C is an area that still needs close
examination. There are some initial works that aim to improve long-context
reasoning and understanding, but some of them forfeit P for a better A. We
believe more research is needed to improve A and P simultaneously.

###  2.4 Improve Performance (P)

This section covers works that improve P. Long-context serving demands
significantly more resources in terms of computational flops and memory usage.
From a system’s perspective, using principles such as parallelism or
approximation to battle these issues is not uncommon. We focus on three lines
of work specifically proposed for improving long-context serving: sparse
attention, linear attention, and distributed acceleration.

Sparse attention reduces resource usage by selectively focusing on only a
subset of the inputs at each attention step. Linear attention reduces resource
usage by approximating the attention calculation through a kernel function
that maps the input features into a lower-dimensional space before computing
the attention scores. Both techniques aim to reduce the quadratic complexity
of the traditional attention mechanism. Linear attention does so through
dimensionality reduction, while sparse attention uses selective focusing.
Sparse attention is particularly useful when the importance of different parts
of the data is non-uniform or when the sequence has a natural locality (like
in images or structured text). Linear attention is more suited for tasks where
the entire data needs to be compressed and processed efficiently. Distributed
acceleration explores sequence parallelism for faster processing. We refer
readers to [4, 3] for general optimizations that improve P, for example, paged
attention [8], flash attention [48], KV caching [49], etc.

####  2.4.1 Sparse Attention

This section explores sparsity, a method that enhances computational
efficiency by minimizing redundant $QK$ multiplication operations and reducing
memory usage. We categorize sparsity techniques into four main types, based on
two fundamental aspects. The first aspect relates to the transformer
architecture. For the Encoder-Decoder architecture, sparsity is applied to
selectively ignore less significant interactions between queries and keys in
the attention computation. This helps focus computational resources on more
crucial elements. For the Decoder-only architecture, sparsity is used to purge
less important data from the key and value cache. The second aspect focuses on
the strategy of identifying which connections between queries and keys are
less important. These strategies are divided into two categories including
dynamic and static sparsity [50]. Dynamic sparsity adapts to the incoming
sequence by continually recognizing less important connections between queries
and keys and filtering out corresponding tokens at runtime. Static sparsity,
on the other hand, uses pre-determined sparse patterns to decide which
connections to disregard, simplifying the implementation but potentially
sacrificing adaptiveness.

We compare representative sparsity works in Table 5 across four dimensions.

  * •

Sparsity Strategy: whether the sparse pattern of the attention matrix is pre-
defined (static) or determined dynamically during inference (dynamic,
sometimes also called learned).

  * •

Pattern Strategy: composition of retained connections (corresponding to static
methods) and technique of obtaining the pattern (corresponding to dynamic
methods).

  * •

Compensate: whether the system compensates for discarded elements.

  * •

Require training: whether a sparsity work plug and play without training.

The following discussion is organized based on Table 4.

Table 4: The matrix for discussion. | Encoder-Decoder | Decoder-only
---|---|---
Dynamic Sparsity | (1) | (4)
Static Sparsity | (2) | (3)

(1) Dynamic Sparsity + Encoder-Decoder. In the pre-LLM period, encoder-decoder
models dynamically adjust attention patterns at runtime based on input queries
and keys, including algorithmic works such as Adaptively Sparse Transformer
[51], Sinkhorn Attention [52], Routing transformer [53], Reformer [54],
Landmark attention [55], and hardware accelerator works such as $A^{3}$ [56],
Spatten [57], Sanger [58], Dota [59], Salo2 [50], Acceltran [60], Fact [61],
Energon [62] and Dtqatten [63], etc. These methods filters out irrelevant
tokens and generates sparse patterns for crucial attention computation based
on input or internal states. They adopt various techniques to determine the
sparse pattern at runtime, such as pruning the attention matrix based on a
threshold, identifying important keys for queries through clustering, or
employing Top-k pruning, among others. For example, Routing Transformer
utilizes clustering to measure the similarity between keys and queries and
identifies the Top-k most relevant keys for each query. Sanger, Acceltran, and
Dtqatten derive sparse patterns by masking out elements below a predefined
threshold in the approximated score matrix.

(2) Static Sparsity + Encoder-Decoder. The quadratic complexity of the
attention mechanism incurs heavy computational and memory burdens, especially
when the content length is very long. In scenarios with long input sequences,
dynamic sparsity brings about efficieny issues due to the additional overhead
of filtering or clustering queries and keys. This gives rise to static
sparsity. Models like Block-Bert [64], Sparse transformer [65], Longformer
[66], BigBird [67], Star-transformer [68], LongT5 [69], LongNet [70], Zebra
[71] and certain hardware accelerators such as Vitcod [72] and Salo [73] adopt
static sparsity strategies. These works achieve sparsity by constraining
attention connections to predefined sparse patterns such as block attention,
sliding window attention, global attention, random attention, and dilated
attention. For example, Longformer combines sliding window attention and
global attention to capture local and long dependencies, respectively.

(3) Static Sparsity + Decoder-Only. Now in the LLM period, the model of the
decoder-only architecture is becoming mainstream. In the decoding process of
the decoder-only transformers, historical keys and values are cached to
improve computational efficiency, so sparsity now favors evicting unimportant
keys and values in the KV cache. Static sparsity is still applicable on models
with decoder-only architecture. For example, LM-Infinite [74] and StreamingLLM
[12] caches the keys and values of the start token and the last $L$ tokens,
and only the keys and values in the cache will be used for attention with the
current query.

(4) Dynamic Sparsity + Decoder-Only. Dynamic sparsity is active again due to
the linear complexity of the single-step decoding of the decoder-only
architecture. For example, FastGen [75] chooses the appropriate compression
strategy for each attention head in the prefill phase and chooses whether to
cache the KV vectors of newly generated tokens according to the compression
strategy in the decoding phase. H2O [76] and Keyformer [77] caches the key and
value vectors of the last $L$ tokens and the important tokens dynamically
selected by attention score at runtime. SparQ Attention [78] eliminates
unimportant key and value vectors based on the approximated attention scores.
To compensate for the eliminated value vectors, SparQ Attention additionally
maintains the mean value vector of all eliminated value vectors to compute the
attention output. EasyKV [79] evicts unimportant key and value vectors by a
Robust Cache omission policy based on local attention scores and robustness
measures. LESS [80] uses a low-rank approach based on KV Cache eviction to
learn the residual difference between the original attention output and the
sparse policy approximation of the attention output, which is accomplished by
accumulating the information discarded according to the eviction policy into a
constant-sized low-rank cache or state, allowing queries to recover the lost
information. InfLLM [81] caches keys and values of the start token and the
last $L$ tokens and reloads some relevant evicted key and value vectors stored
at an external memory by a lookup table.

Table 5: Comparing sparsity works. Work |  Sparsity Strategy |  Pattern Strategy | Compensate |  Require Training
---|---|---|---|---
Sparse Transformers [65] | Static | Local + dilated | ✗ | ✓
Adaptively Transformers [51] | Dynamic | Topk | ✗ | ✓
Block Attention [64] | Static | Block | ✗ | ✓
ETC [82] | Static | Local + Global | ✗ | ✓
BigBird [67] | Static | Local + Global + Random | ✗ | ✓
Longformer [66] | Static | Local + Global | ✗ | ✓
Reformer [54] | Dynamic | LSH | ✗ | ✓
Sinkhorn Attention [52] | Dynamic | Block + Sort | ✗ | ✓
Routing Transformer [53] | Dynamic | Clustering | ✗ | ✓
Star Transformer [68] | Static | Local + Global | ✗ | ✓
LongT5 [69] | Static | Local + Global | ✓ | ✓
LongNet [70] | Static | Dilated | ✗ | ✓
Zebra [71] | Static | Local or Global | ✗ | ✓
Lankmark Attention [55] | Dynamic | Block + Topk | ✗ | ✓
LM-Infinite [74] | Static | Local + Global | ✗ | ✓
StreamingLLM [12] | Static | Local + Global | ✗ | ✗
H2O [76] | Dynamic | Local + Topk | ✗ | ✗
Keyformer [77] | Dynamic | Local + Topk | ✗ | ✗
SparQ Attention [78] | Dynamic | Topk | ✓ | ✗
EasyKV [79] | Dynamic | Topk | ✗ | ✗
LESS [80] | Dynamic | Topk | ✓ | ✓
InfLLM [81] | Dynamic | Local + Topk | ✗ | ✗

In summary, sparsity improves P by minimizing redundant computation and memory
usage. Most works in this area only improve P but at the cost of lower
potentially degraded accuracy. StreamingLLM [12] is an exception as it
achieves both CP by enabling an infinite context window and utilizing
efficient attention. We believe it’d be interesting to explore a combination
of model memory, positional embedding, and sparsity optimizations.

####  2.4.2 Linear Attention

Linear attention reduces the complexity of the attention mechanism from
quadratic to linear with respect to the sequence length. It does this by
approximating the attention calculation through a kernel function that maps
the input features into a lower-dimensional space before computing the
attention scores. Specifically, it replaces the softmax operation with other
function, e.g., $sim(Q,K)=\phi(Q)\phi(K)^{T}$, and computing
$\phi(Q)(\phi(K)^{T}V)$ instead of $sim(Q,K)V$, linear attention reduces
quadratic complexity $O(n^{2}d)$ to linear $O(nrd)$, where $r$ means $\phi()$
maps $\mathbb{R}^{d}$ to $\mathbb{R}^{r}$. Works in this space like Linear
Transformer [83], Performer [84], and Efficient Attention [85] define
different $\phi()$ to approximate the softmax operation, while Scatterbrain
[86] and ViTALiTy [87] further compensate the low rank function with sparse
attentions from Reformer [54] and Sanger [58] separately. For example,
Performer uses positive orthogonal random features (PORF) as a low rank
function $\phi()$, while Scatterbrain shows that combining both low-rank
linear attention (via function $\phi()$ in Performer) and sparse attention
(via locality-sensitive hashing in Reformer) leads to efficient approximation
with better performance than individual ones.

Both linear attention and sparse attention reduce the quadratic complexity of
the traditional attention mechanism. Linear attention does so through
dimensionality reduction, while sparse attention uses selective focusing. Both
trade A for a better P.

####  2.4.3 Distributed Acceleration

Online Normalizer [88]Memory Efficient Attention [89]Flash Attention
[48]Blockwise Parallel Transformer [90]Ring Attention [91]Burst Attention
[92]Striped Attention [93]Dist Attention [94]

Figure 3: Works using sequence parallelism. Gray boxes are not tailored for
long-context serving.

(a) The workflow for computing a single decoder layer in Ring Attention [91].
It efficiently implements SP through block-wise computation and overlapping of
computation and data transfer.

(b) The workflow for computing a single decoder layer in Striped Attention
[93]. It optimizes Ring Attention by token permutation, which reduces load-
imbalance among SP nodes caused by causal masking.

Figure 4: Efficient SP-attention mechanisms used in the prefilling phase of
LLM serving. Figure 5: Dist Attention [94, 95], SP-attention mechanism
optimized for the auto-regressive decode phase of LLM serving. In the decode
phase, Q length is one and KV is already distributed.

We discuss works that explore the Sequence Parallelism (SP) dimension in a
distributed fashion. Here, a long-context inference request is segmented into
sub-sequences and distributed across nodes for parallel processing. While
traditional distributed strategies like tensor parallelism (TP) or pipeline
parallelism (PP) can also enhance inference performance, we omit them in this
survey because, they are not specifically designed for long-context handling
and generally serve as orthogonal or complementary to SP optimizations.

Our analysis unfolds in two steps. First, we investigate methods to accelerate
a single long-context request using SP. Second, we investigate methods to
accelerate a cluster serving long-context requests.

Accelerate a Single Request.

  * •

Figure 3 shows the relation among this line of research work. This line of
research can be traced back to the online normalizer work [88], a
mathematically equivalent method for block-wise softmax calculation that
avoids materializing the full attention matrix softmax$(QK^{T})$. This method
is a foundation for memory-efficient attention [89] and their CUDA
implementations [48, 96].

  * •

SP was first introduced by Li et al.[97] and has been widely used in
distributed LLM training frameworks such as Megatron[98] and Deepspeed [99].
In the context of LLM serving systems, new challenges emerge: (1) LLM serving
is usually latency-sensitive and thus requires much smaller batch sizes than
LLM training; (2) LLM serving has an auto-regressive decode phase, where the
sequence length is only one, but it requires large memory for KV cache
storage; (3) LLM serving usually relies on large fused kernels for improving
performance. While the feed-forward network (FFN) computations for each token
in a sequence are linearly independent, the computations for attention are
not. Consequently, substantial data exchange is involved when computing
distributed attention using SP, thereby opening significant space for
performance optimization.

  * •

Blockwise Parallel Transfomer (BPT) [90] extends this block-wise parallel
computation idea from self-attention to a fusion of self-attention and FFN.
BPT computes FFN directly with each block of Q’s attention result without
materializing the full attention matrix at all, thus reducing memory demands
for handling requests with extended contexts.

  * •

Ring Attention [91] is a follow-up work of BPT and adapt it for distributed
settings. As shown in Figure 4(a), it distributes blockwise attention and FFN
computations across devices, enabling the concurrent communication of key-
value blocks in a circular pattern among hosts. This setup overlaps
communication with the computation of query-key-value blocks and FFN,
enhancing efficiency. Striped Attention [93] refines Ring Attention by
addressing the load imbalance among distributed nodes that arises after causal
masking, as shown in Figure 4(b). Burst Attention [92] enhances Ring Attention
by integrating FlashAttention’s tiling optimizations into per-node
computations and incorporating a global optimizer for distributed
coordination. Dist Attention [94] optimizes Ring Attention specifically for
the auto-regressive decode phase, as shown in Figure 5 where the query length
is just one. In the decode phase, Q length is one and KV is already
distributed among sequence parallel nodes.

Accelerate a Cluster.

  * •

When deploying long-context serving, the system encounters requests of varying
context lengths. This diversity poses significant challenges to the LLM
serving system, the computational and memory requirements for different
requests can vary by order of magnitude. Two concurrent works, Infinite-LLM
[94] and LoongServe [95], address this challenge using similar ideas: they
employ SP to segment requests of different context lengths into smaller,
manageable pieces and distribute these pieces across the entire cluster for
scheduling.

  * •

Infinite-LLM [94] introduces Dist Attention, an SP attention mechanism
optimized for the auto-regressive decode phase. Additionally, Infinite-LLM
incorporates a global memory manager that coordinates the cluster’s memory
allocation among request pieces, taking into account of coherency constraints
and fragmentation.

  * •

LoongServe [95], on the other hand, proposes Elastic Sequence Parallelism
(ESP) to dynamically adjust the degree of parallelism for an inference request
with minimal overhead. ESP facilitates two optimization strategies: (1)
reducing the degree of sequence parallelism after the prefill phase and
maintaining a lower degree of parallelism during the decode phase, as this
phase requires less computation (per auto-regressive step); (2) increasing the
degree of sequence parallelism during the auto-regressive phase as the
sequence length grows, which is particularly promising when the LLM is
expected to generate long output sequences.

In summary, existing works have greatly improved long-context serving’s P,
either from a single request’s perspective or the cluster’s perspective. We
also find potential future directions worth exploring. First, although these
system works are general to long-context models, their optimization approaches
have no synergy with, or may even contradict the upper-layer model-level
optimization. For instance, attention mechanisms optimized for load balance
among SP nodes may perform poorly with context sparsity. Second, as far as we
are concerned, no effort has been made to the co-design between the agent-
layer techniques and the distributed acceleration systems. For instance, after
the distributed inference of a request, its “memory” is scattered among
multiple nodes, posing challenges for the agent system to collect and filter
them. Finally, likewise, no effort examines whether we should and how to
accelerate model memory line of work (see §2.2) with SP.

###  2.5 Improve Context and Performance (CP)

This section discusses works that can improve C and P at the same time. It is
challenging to hit two birds with one stone and we have identified one line of
work: prompt compression.

####  2.5.1 Prompt Compression

Table 6: Comparing prompt compression works. Type |  Work
---|---
Block-Box |  Selective Context [100], LLMLingua [101], LongLLMLingua [102], LLMLingua2 [103]
White-Box |  Gist-Token [104], PCCC [105], ICAE [106], AutoCompressor [32]

Prompt compression reduces the length of a given prompt while preserving the
essential information such that the serving system can process longer context.
Recall that we determine whether C and P have been met based on user-perceived
measurement metrics. We classify this approach as CP because it can shorten
the user-provided prompt before being fed into the model, thereby improving
user-perceived context length and performance. We classify works based on
whether the LLM model is used as a black box or a while box.

  * •

Block-box Compression. LLMLingua [101] observes significant redundancy in
natural languages and proposes a set of methods for compressing prompts by
removing tokens. It uses a token-level iterative algorithm to compress
prompts. Doing so can preserve the key information within the prompt by
considering the conditional dependencies between tokens. LongLLMLingua [102]
is built based on LLMLingua, adding question-awareness compression by adding
contrastive perplexity which captures the distribution shift of tokens w.r.t.
questions. LLMLingua2 [103] takes a step further, it targets task-agnostic
prompt compression. It uses GPT-4 to generate compressed texts from original
prompts and a bi-class classifier to drop unneeded tokens.

  * •

White-box Compression. This line of work will modify the model architecture in
certain ways to achieve compression. And they feed the compressed prompts via
soft prompting [35]. Gist tokens [104] modifies the transformer attention
masks to enable an LLM to compress prompts into smaller sets of “gist” tokens
which can be cached and reused for compute efficiency, improving both C and P.
Another work, PCCC [105], adds a trainable soft prompt weight to an LLM. Their
insight is that prompts used to condition a LLM can be approximately
represented by a much smaller set of carefully chosen weights. Their goal is
to train the soft prompt weights to mimic a fixed hard prompt as closely as
possible. ICAE [106] takes a different approach. It consists of 2 modules: a
learnable encoder adapted from the LLM with LoRA for encoding a long context
into a small number of memory slots, and a fixed decoder, which is the LLM
itself where the memory slots representing the original context are
conditioned on to interact with prompts to accomplish various goals. Finally,
AutoCompressor [32], a work based on the RMT architecture [31], builds a
segment-level summary token to compress prompts.

In summary, there are various ways to compress prompts. One can either treat
the LLM as a black-box and use a set of methods to compress prompts before
being sent to the black-box LLM. Alternatively, one can also modify the model
architecture to achieve effective compression. Prompt compression improves
user-perceived C and P.

###  2.6 Improve Context and Accuracy (CA)

This section discusses works that can improve C and A at the same time. We
have identified one line of work: agent memory, which manages memory at the
agent layer.

####  2.6.1 Agent Memory

One way to extend a serving system’s context length and performance is by
implicitly managing the memory and prompt within the agent layer. We dub this
approach as agent memory. It belongs to CA because it can create the illusion
of infinite context over fixed-context models and reflect on past memory for
higher accuracy in future tasks, thereby improving user-perceived C and A.
Agent memory differs from model memory (covered earlier) in that agent memory
manipulates memory and prompts within agents, while model memory manipulates
memory within models. They are not conflicting solutions, they complement each
other. For example, one can run an agent memory work such as MemGPT [107] atop
a model memory work such as Infini-Attention [33].

Table 7: Comparing agent memory works. Work |  Online Memory Management |  Offline Memory Reflection
---|---|---
MemWalker [108] | ✓ | /
WebGPT [109] | ✓ | /
MemGPT [107] | ✓ | /
TheSim [110] | ✓ | ✓
ChatDev [111] | ✓ | ✓
MetaGPT [112] | ✓ | ✓
Self-Refine [113] | ✓ | ✓
Reflexion [114] | ✓ | ✓
MLCopilot [115] | ✓ | ✓

We discuss agent memory work across two dimensions.

  * •

Online Memory Management: it indicates whether a solution can dynamically
construct a prompt being fed to the model in real-time based on the agent’s
past memory, external knowledge, and current user prompt. It requires
mechanisms to fetch relevant information from past memory and mechanisms to
construct prompts. MemWalker [108], WebGPT [109], and MemGPT [107] are seminal
works in this space. In particular, MemGPT provides the illusion of an
infinite context atop a fixed-context model. It builds a multi-level hierarchy
and a set of mechanisms to swap memory between the current constructed prompt
and external past memory. Hence, it implicitly improves C.

  * •

Offline Memory Reflection: it indicates whether a solution can reflect on an
agent’s past memory to learn experiences, distill knowledge, remove
unnecessary sentences, etc. It requires mechanisms to read and write past
memory. Many agent-based applications adopt this mechanism offline to improve
serving accuracy for future tasks [114, 113]. For example, agents in ChatDev
[111], Generative Agents [110], and MLCopilot [115] regularly reflect, which
synthesizes past memories into higher-level knowledge to improve future task
accuracy. Combined, agent memory with feature improves C and A.

In summary, agent memory has three key features: online memory management and
offline memory reflection. The former meets C, and the latter meets A. Agent
memory comes close to CAP if one adds prompt compression to it.

##  3 Conclusion

We believe it’s equally important to deploy and serve models at a massive
scale with a reasonably low cost without compromising its accuracy, in
addition to having a high-quality model. we survey the LLM serving area to
understand the intricate dynamics between cost-efficiency and accuracy with
the growing need for long-context serving. Our findings reveal that works in
this space optimize along three distinct but conflicting goals: improving
serving context length (C), improving serving accuracy (A), and improving
serving performance (P). We propose the CAP principle, which states that any
given LLM serving optimization can only improve at most two of the above three
goals. We closely examine the related literature and find existing works can
fall into this category. Looking forward, we hope this principle is used to
inform designers of the inherent and dynamic trade-offs when building large-
scale serving systems.

## References

  * [1] Meredith Ringel Morris, Jascha Sohl-dickstein, Noah Fiedel, Tris Warkentin, Allan Dafoe, Aleksandra Faust, Clement Farabet, and Shane Legg.  Levels of agi: Operationalizing progress on the path to agi.  arXiv preprint arXiv:2311.02462, 2023.
  * [2] THE AI INDEX REPORT.  https://aiindex.stanford.edu/report/.
  * [3] Mengwei Xu, Wangsong Yin, Dongqi Cai, Rongjie Yi, Daliang Xu, Qipeng Wang, Bingyang Wu, Yihao Zhao, Chen Yang, Shihe Wang, et al.  A survey of resource-efficient llm and multimodal foundation models.  arXiv preprint arXiv:2401.08092, 2024.
  * [4] Zixuan Zhou, Xuefei Ning, Ke Hong, Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang, Zhihang Yuan, Xiuhong Li, et al.  A survey on efficient inference for large language models.  arXiv preprint arXiv:2404.14294, 2024.
  * [5] Khaled Saab, Tao Tu, Wei-Hung Weng, Ryutaro Tanno, David Stutz, Ellery Wulczyn, Fan Zhang, Tim Strother, Chunjong Park, Elahe Vedadi, et al.  Capabilities of gemini models in medicine.  arXiv preprint arXiv:2404.18416, 2024.
  * [6] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean.  Efficiently scaling transformer inference.  Proceedings of Machine Learning and Systems, 5, 2023.
  * [7] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang.  Lost in the middle: How language models use long contexts.  Transactions of the Association for Computational Linguistics, 12:157–173, 2024.
  * [8] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica.  Efficient memory management for large language model serving with pagedattention.  In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611–626, 2023.
  * [9] TensorRT LLM.  https://github.com/NVIDIA/TensorRT-LLM.
  * [10] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov.  Transformer-xl: Attentive language models beyond a fixed-length context.  arXiv preprint arXiv:1901.02860, 2019.
  * [11] Yilong Zhao, Chien-Yu Lin, Kan Zhu, Zihao Ye, Lequn Chen, Size Zheng, Luis Ceze, Arvind Krishnamurthy, Tianqi Chen, and Baris Kasikci.  Atom: Low-bit quantization for efficient and accurate llm serving.  arXiv preprint arXiv:2310.19102, 2023.
  * [12] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis.  Efficient streaming language models with attention sinks, 2023.
  * [13] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun.  Orca: A distributed serving system for $\\{$Transformer-Based$\\}$ generative models.  In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, 2022.
  * [14] Cunchen Hu, Heyang Huang, Liangliang Xu, Xusheng Chen, Jiang Xu, Shuang Chen, Hao Feng, Chenxi Wang, Sa Wang, Yungang Bao, et al.  Inference without interference: Disaggregate llm inference for mixed downstream workloads.  arXiv preprint arXiv:2401.11181, 2024.
  * [15] Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi.  The shift from models to compound ai systems.  https://bair.berkeley.edu/blog/2024/02/18/compound-ai-systems/, 2024.
  * [16] Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu.  Roformer: Enhanced transformer with rotary position embedding.  CoRR, abs/2104.09864, 2021.
  * [17] Xunyu Zhu, Jian Li, Yong Liu, Can Ma, and Weiping Wang.  A survey on model compression for large language models.  arXiv preprint arXiv:2308.07633, 2023.
  * [18] Wikipedia.  The cap theorem.  https://en.wikipedia.org/wiki/CAP_theorem, 2024.
  * [19] Zhengxiao Du, Aohan Zeng, Yuxiao Dong, and Jie Tang.  Understanding emergent abilities of language models from the loss perspective.  arXiv preprint arXiv:2403.15796, 2024.
  * [20] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo.  Are emergent abilities of large language models a mirage?  Advances in Neural Information Processing Systems, 36, 2024.
  * [21] Google.  Spanner, truetime & the cap theorem.  https://storage.googleapis.com/gweb-research2023-media/pubtools/pdf/45855.pdf, 2017.
  * [22] Saurav Pawar, SM Tonmoy, SM Zaman, Vinija Jain, Aman Chadha, and Amitava Das.  The what, why, and how of context length extension techniques in large language models–a detailed survey.  arXiv preprint arXiv:2401.07872, 2024.
  * [23] Zican Dong, Tianyi Tang, Lunyi Li, and Wayne Xin Zhao.  A survey on long text modeling with transformers.  arXiv preprint arXiv:2302.14502, 2023.
  * [24] Xindi Wang, Mahsa Salmani, Parsa Omidi, Xiangyu Ren, Mehdi Rezagholizadeh, and Armaghan Eshaghi.  Beyond the limits: A survey of techniques to extend the context length in large language models.  arXiv preprint arXiv:2402.02244, 2024.
  * [25] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al.  The rise and potential of large language model based agents: A survey.  arXiv preprint arXiv:2309.07864, 2023.
  * [26] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang.  Retrieval-augmented generation for large language models: A survey.  arXiv preprint arXiv:2312.10997, 2023.
  * [27] Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap.  Compressive transformers for long-range sequence modelling.  arXiv preprint arXiv:1911.05507, 2019.
  * [28] Yuhuai Wu, Markus N Rabe, DeLesley Hutchins, and Christian Szegedy.  Memorizing transformers.  arXiv preprint arXiv:2203.08913, 2022.
  * [29] Qingyang Wu, Zhenzhong Lan, Kun Qian, Jing Gu, Alborz Geramifard, and Zhou Yu.  Memformer: A memory-augmented transformer for sequence modeling.  arXiv preprint arXiv:2010.06891, 2020.
  * [30] Mikhail S Burtsev, Yuri Kuratov, Anton Peganov, and Grigory V Sapunov.  Memory transformer.  arXiv preprint arXiv:2006.11527, 2020.
  * [31] Aydar Bulatov, Yury Kuratov, and Mikhail Burtsev.  Recurrent memory transformer.  Advances in Neural Information Processing Systems, 35:11079–11091, 2022.
  * [32] Alexis Chevalier, Alexander Wettig, Anirudh Ajith, and Danqi Chen.  Adapting language models to compress contexts.  arXiv preprint arXiv:2305.14788, 2023.
  * [33] Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal.  Leave no context behind: Efficient infinite context transformers with infini-attention.  arXiv preprint arXiv:2404.07143, 2024.
  * [34] Yizhou Shan, Yutong Huang, Yilun Chen, and Yiying Zhang.  LegoOS: A disseminated, distributed OS for hardware resource disaggregation.  In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 69–87, Carlsbad, CA, October 2018. USENIX Association.
  * [35] Brian Lester, Rami Al-Rfou, and Noah Constant.  The power of scale for parameter-efficient prompt tuning.  arXiv preprint arXiv:2104.08691, 2021.
  * [36] Ofir Press, Noah A. Smith, and Mike Lewis.  Train short, test long: Attention with linear biases enables input length extrapolation, 2022.
  * [37] Yutao Sun, Li Dong, Barun Patra, Shuming Ma, Shaohan Huang, Alon Benhaim, Vishrav Chaudhary, Xia Song, and Furu Wei.  A length-extrapolatable transformer, 2022.
  * [38] Guanzheng Chen, Xin Li, Zaiqiao Meng, Shangsong Liang, and Lidong Bing.  Clex: Continuous length extrapolation for large language models, 2024.
  * [39] Shouyuan Chen, Sherman Wong, Liangjian Chen, and Yuandong Tian.  Extending context window of large language models via positional interpolation, 2023.
  * [40] bloc97.  Ntk-aware scaled rope allows llama models to have extended (8k+) context size without any fine-tuning and minimal perplexity degradation, 2023.  https://www.reddit.com/r/LocalLLaMA/comments/14lz7j5/ntkaware_scaled_rope_allows_llama_models_to_have/,D, Last accessed on 2023-12-19.
  * [41] Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole.  Yarn: Efficient context window extension of large language models, 2023.
  * [42] Shanda Li, Chong You, Guru Guruganesh, Joshua Ainslie, Santiago Ontanon, Manzil Zaheer, Sumit Sanghai, Yiming Yang, Sanjiv Kumar, and Srinadh Bhojanapalli.  Functional interpolation for relative positions improves long context transformers, 2024.
  * [43] Yiran Ding, Li Lyna Zhang, Chengruidong Zhang, Yuanyuan Xu, Ning Shang, Jiahang Xu, Fan Yang, and Mao Yang.  Longrope: Extending llm context window beyond 2 million tokens, 2024.
  * [44] Dawei Zhu, Nan Yang, Liang Wang, Yifan Song, Wenhao Wu, Furu Wei, and Sujian Li.  Pose: Efficient context window extension of llms via positional skip-wise training, 2024.
  * [45] Alexander Peysakhovich and Adam Lerer.  Attention sorting combats recency bias in long context language models.  arXiv preprint arXiv:2310.01427, 2023.
  * [46] Yuhan Chen, Ang Lv, Ting-En Lin, Changyu Chen, Yuchuan Wu, Fei Huang, Yongbin Li, and Rui Yan.  Fortify the shortest stave in attention: Enhancing context awareness of large language models for effective tool use.  arXiv preprint arXiv:2312.04455, 2023.
  * [47] Zhenyu Zhang, Runjin Chen, Shiwei Liu, Zhewei Yao, Olatunji Ruwase, Beidi Chen, Xiaoxia Wu, and Zhangyang Wang.  Found in the middle: How language models use long contexts better via plug-and-play positional encoding.  arXiv preprint arXiv:2403.04797, 2024.
  * [48] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  Advances in Neural Information Processing Systems, 35:16344–16359, 2022.
  * [49] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al.  Efficiently programming large language models using sglang.  arXiv preprint arXiv:2312.07104, 2023.
  * [50] Jieru Zhao, Pai Zeng, Guan Shen, Quan Chen, and Minyi Guo.  Hardware-software co-design enabling static and dynamic sparse attention mechanisms.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 1–1, 2024.
  * [51] Gonçalo M. Correia, Vlad Niculae, and André F. T. Martins.  Adaptively sparse transformers, 2019.
  * [52] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan.  Sparse sinkhorn attention, 2020.
  * [53] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier.  Efficient content-based sparse attention with routing transformers.  Transactions of the Association for Computational Linguistics, 9:53–68, 2021.
  * [54] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer, 2020.
  * [55] Amirkeivan Mohtashami and Martin Jaggi.  Landmark attention: Random-access infinite context length for transformers, 2023.
  * [56] Tae Jun Ham, Sung Jun Jung, Seonghak Kim, Young H. Oh, Yeonhong Park, Yoonho Song, Jung-Hun Park, Sanghee Lee, Kyoung Park, Jae W. Lee, and Deog-Kyoon Jeong.  A3: Accelerating attention mechanisms in neural networks with approximation, 2020.
  * [57] Hanrui Wang, Zhekai Zhang, and Song Han.  Spatten: Efficient sparse attention architecture with cascade token and head pruning, 2021.
  * [58] Liqiang Lu, Yicheng Jin, Hangrui Bi, Zizhang Luo, Peng Li, Tao Wang, and Yun Liang.  Sanger: A co-design framework for enabling sparse attention using reconfigurable architecture.  MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, 2021.
  * [59] Zheng Qu, L. Liu, Fengbin Tu, Zhaodong Chen, Yufei Ding, and Yuan Xie.  Dota: detect and omit weak attentions for scalable transformer acceleration.  Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 2022.
  * [60] Shikhar Tuli and Niraj K. Jha.  Acceltran: A sparsity-aware accelerator for dynamic inference with transformers, 2023.
  * [61] Yubin Qin, Yang Wang, Dazheng Deng, Zhiren Zhao, Xiaolong Yang, Leibo Liu, Shaojun Wei, Yang Hu, and Shouyi Yin.  Fact: Ffn-attention co-optimized transformer architecture with eager correlation prediction.  Proceedings of the 50th Annual International Symposium on Computer Architecture, 2023.
  * [62] Zhe Zhou, Junlin Liu, Zhenyu Gu, and Guangyu Sun.  Energon: Toward efficient acceleration of transformers using dynamic sparse attention.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(1):136–149, 2023.
  * [63] Tao Yang, Dongyue Li, Zhuoran Song, Yilong Zhao, Fangxin Liu, Zongwu Wang, Zhezhi He, and Li Jiang.  Dtqatten: Leveraging dynamic token-based quantization for efficient attention architecture.  In 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 700–705, 2022.
  * [64] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Yih, Sinong Wang, and Jie Tang.  Blockwise self-attention for long document understanding.  ArXiv, abs/1911.02972, 2019.
  * [65] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever.  Generating long sequences with sparse transformers, 2019.
  * [66] Iz Beltagy, Matthew E. Peters, and Arman Cohan.  Longformer: The long-document transformer, 2020.
  * [67] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed.  Big bird: Transformers for longer sequences.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17283–17297. Curran Associates, Inc., 2020.
  * [68] Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, and Zheng Zhang.  Star-transformer, 2022.
  * [69] Mandy Guo, Joshua Ainslie, David Uthus, Santiago Ontanon, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang.  LongT5: Efficient text-to-text transformer for long sequences.  In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz, editors, Findings of the Association for Computational Linguistics: NAACL 2022, pages 724–736, Seattle, United States, July 2022. Association for Computational Linguistics.
  * [70] Jiayu Ding, Shuming Ma, Li Dong, Xingxing Zhang, Shaohan Huang, Wenhui Wang, Nanning Zheng, and Furu Wei.  Longnet: Scaling transformers to 1,000,000,000 tokens, 2023.
  * [71] Kaiqiang Song, Xiaoyang Wang, Sangwoo Cho, Xiaoman Pan, and Dong Yu.  Zebra: Extending context window with layerwise grouped local-global attention, 2023.
  * [72] Haoran You, Zhanyi Sun, Huihong Shi, Zhongzhi Yu, Yang Zhao, Yongan Zhang, Chaojian Li, Baopu Li, and Yingyan Lin.  Vitcod: Vision transformer acceleration via dedicated algorithm and accelerator co-design, 2022.
  * [73] Guan Shen, Jieru Zhao, Quan Chen, Jingwen Leng, Chao Li, and Minyi Guo.  Salo: An efficient spatial accelerator enabling hybrid sparse attention mechanisms for long sequences, 2022.
  * [74] Chi Han, Qifan Wang, Hao Peng, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang.  Lm-infinite: Zero-shot extreme length generalization for large language models, 2023.
  * [75] Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao.  Model tells you what to discard: Adaptive kv cache compression for llms, 2024.
  * [76] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen.  H2o: Heavy-hitter oracle for efficient generative inference of large language models, 2023.
  * [77] Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J. Nair, Ilya Soloveychik, and Purushotham Kamath.  Keyformer: Kv cache reduction through key tokens selection for efficient generative inference, 2024.
  * [78] Luka Ribar, Ivan Chelombiev, Luke Hudlass-Galley, Charlie Blake, Carlo Luschi, and Douglas Orr.  Sparq attention: Bandwidth-efficient llm inference, 2024.
  * [79] Siyu Ren and Kenny Q. Zhu.  On the efficacy of eviction policy for key-value constrained generative language model inference, 2024.
  * [80] Harry Dong, Xinyu Yang, Zhenyu Zhang, Zhangyang Wang, Yuejie Chi, and Beidi Chen.  Get more with less: Synthesizing recurrence with kv cache compression for efficient llm inference, 2024.
  * [81] Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, Song Han, and Maosong Sun.  Infllm: Unveiling the intrinsic capacity of llms for understanding extremely long sequences with training-free memory, 2024.
  * [82] Joshua Ainslie, Santiago Ontañón, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang.  ETC: encoding long and structured inputs in transformers.  In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 268–284. Association for Computational Linguistics, 2020.
  * [83] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret.  Transformers are rnns: Fast autoregressive transformers with linear attention.  In International conference on machine learning, pages 5156–5165. PMLR, 2020.
  * [84] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  arXiv preprint arXiv:2009.14794, 2020.
  * [85] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Efficient attention: Attention with linear complexities.  In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 3531–3539, 2021.
  * [86] Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré.  Scatterbrain: Unifying sparse and low-rank attention.  Advances in Neural Information Processing Systems, 34:17413–17426, 2021.
  * [87] Jyotikrishna Dass, Shang Wu, Huihong Shi, Chaojian Li, Zhifan Ye, Zhongfeng Wang, and Yingyan Lin.  Vitality: Unifying low-rank and sparse approximation for vision transformer acceleration with a linear taylor attention.  In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 415–428. IEEE, 2023.
  * [88] Maxim Milakov and Natalia Gimelshein.  Online normalizer calculation for softmax.  arXiv preprint arXiv:1805.02867, 2018.
  * [89] Markus N Rabe and Charles Staats.  Self-attention does not need $O(n^{2})$ memory.  arXiv preprint arXiv:2112.05682, 2021.
  * [90] Hao Liu and Pieter Abbeel.  Blockwise parallel transformers for large context models.  Advances in Neural Information Processing Systems, 36, 2024.
  * [91] Hao Liu, Matei Zaharia, and Pieter Abbeel.  Ring attention with blockwise transformers for near-infinite context.  arXiv preprint arXiv:2310.01889, 2023.
  * [92] Sun Ao, Weilin Zhao, Xu Han, Cheng Yang, Zhiyuan Liu, Chuan Shi, Maosong Sun, Shengnan Wang, and Teng Su.  Burstattention: An efficient distributed attention framework for extremely long sequences.  arXiv preprint arXiv:2403.09347, 2024.
  * [93] William Brandon, Aniruddha Nrusimha, Kevin Qian, Zachary Ankner, Tian Jin, Zhiye Song, and Jonathan Ragan-Kelley.  Striped attention: Faster ring attention for causal transformers.  arXiv preprint arXiv:2311.09431, 2023.
  * [94] Bin Lin, Tao Peng, Chen Zhang, Minmin Sun, Lanbo Li, Hanyu Zhao, Wencong Xiao, Qi Xu, Xiafei Qiu, Shen Li, et al.  Infinite-llm: Efficient llm service for long context with distattention and distributed kvcache.  arXiv preprint arXiv:2401.02669, 2024.
  * [95] Bingyang Wu, Shengyu Liu, Yinmin Zhong, Peng Sun, Xuanzhe Liu, and Xin Jin.  Loongserve: Efficiently serving long-context large language models with elastic sequence parallelism.  arXiv preprint arXiv:2404.09526, 2024.
  * [96] Tri Dao.  Flashattention-2: Faster attention with better parallelism and work partitioning.  arXiv preprint arXiv:2307.08691, 2023.
  * [97] Shenggui Li, Fuzhao Xue, Chaitanya Baranwal, Yongbin Li, and Yang You.  Sequence parallelism: Long sequence training from system perspective.  arXiv preprint arXiv:2105.13120, 2021.
  * [98] Vijay Anand Korthikanti, Jared Casper, Sangkug Lym, Lawrence McAfee, Michael Andersch, Mohammad Shoeybi, and Bryan Catanzaro.  Reducing activation recomputation in large transformer models.  Proceedings of Machine Learning and Systems, 5, 2023.
  * [99] Sam Ade Jacobs, Masahiro Tanaka, Chengming Zhang, Minjia Zhang, Leon Song, Samyam Rajbhandari, and Yuxiong He.  Deepspeed ulysses: System optimizations for enabling training of extreme long sequence transformer models.  arXiv preprint arXiv:2309.14509, 2023.
  * [100] Yucheng Li.  Unlocking context constraints of llms: Enhancing context efficiency of llms with self-information-based content filtering.  CoRR, abs/2304.12102, 2023.
  * [101] Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu.  Llmlingua: Compressing prompts for accelerated inference of large language models.  arXiv preprint arXiv:2310.05736, 2023.
  * [102] Huiqiang Jiang, Qianhui Wu, Xufang Luo, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, and Lili Qiu.  Longllmlingua: Accelerating and enhancing llms in long context scenarios via prompt compression.  arXiv preprint arXiv:2310.06839, 2023.
  * [103] Zhuoshi Pan, Qianhui Wu, Huiqiang Jiang, Menglin Xia, Xufang Luo, Jue Zhang, Qingwei Lin, Victor Rühle, Yuqing Yang, Chin-Yew Lin, et al.  Llmlingua-2: Data distillation for efficient and faithful task-agnostic prompt compression.  arXiv preprint arXiv:2403.12968, 2024.
  * [104] Jesse Mu, Xiang Li, and Noah Goodman.  Learning to compress prompts with gist tokens.  Advances in Neural Information Processing Systems, 36, 2024.
  * [105] David Wingate, Mohammad Shoeybi, and Taylor Sorensen.  Prompt Compression and Contrastive Conditioning for Controllability and Toxicity Reduction in Language Models.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Findings of the Association for Computational Linguistics: EMNLP 2022, pages 5621–5634, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
  * [106] Tao Ge, Jing Hu, Xun Wang, Si-Qing Chen, and Furu Wei.  In-context autoencoder for context compression in a large language model.  CoRR, abs/2307.06945, 2023.
  * [107] Charles Packer, Vivian Fang, Shishir G Patil, Kevin Lin, Sarah Wooders, and Joseph E Gonzalez.  Memgpt: Towards llms as operating systems.  arXiv preprint arXiv:2310.08560, 2023.
  * [108] Howard Chen, Ramakanth Pasunuru, Jason Weston, and Asli Celikyilmaz.  Walking down the memory maze: Beyond context limit through interactive reading.  arXiv preprint arXiv:2310.05029, 2023.
  * [109] Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al.  Webgpt: Browser-assisted question-answering with human feedback.  arXiv preprint arXiv:2112.09332, 2021.
  * [110] Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein.  Generative agents: Interactive simulacra of human behavior.  In Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, pages 1–22, 2023.
  * [111] Chen Qian, Xin Cong, Cheng Yang, Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun.  Communicative agents for software development.  arXiv preprint arXiv:2307.07924, 2023.
  * [112] Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, et al.  Metagpt: Meta programming for multi-agent collaborative framework.  arXiv preprint arXiv:2308.00352, 2023.
  * [113] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al.  Self-refine: Iterative refinement with self-feedback.  Advances in Neural Information Processing Systems, 36, 2024.
  * [114] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.  Reflexion: Language agents with verbal reinforcement learning.  Advances in Neural Information Processing Systems, 36, 2024.
  * [115] Lei Zhang, Yuge Zhang, Kan Ren, Dongsheng Li, and Yuqing Yang.  Mlcopilot: Unleashing the power of large language models in solving machine learning tasks.  arXiv preprint arXiv:2304.14979, 2023.