missing

# Privacy-Aware Semantic Cache for Large Language Models

Waris Gill  Virginia TechBlacksburgUSA<EMAIL_ADDRESS>,  Mohamed Elidrisi
CiscoSeattleUSA<EMAIL_ADDRESS>,  Pallavi Kalapatapu  CiscoSan JoseUSA
<EMAIL_ADDRESS>,  Ali Anwar  University of MinnesotaMinneapolisUSA
<EMAIL_ADDRESS>and  Muhammad Ali Gulzar  Virginia TechBlacksburgUSA
<EMAIL_ADDRESS>
###### Abstract.

Large Language Models (LLMs) like ChatGPT and Llama2 have revolutionized
natural language processing and search engine dynamics. However, these models
incur exceptionally high computational costs. For instance, GPT-3 consists of
175 billion parameters where inference demands billions of floating-point
operations. Caching is a natural solution to reduce LLM inference costs on
repeated queries which constitute about 31% of the total queries. However,
existing caching methods are incapable of finding semantic similarities among
LLM queries, leading to unacceptable _false_ hit-and-miss rates.

This paper introduces MeanCache, a user-centric semantic cache for LLMs that
identifies semantically similar queries to determine cache hit or miss. Using
MeanCache, the response to a user’s semantically similar query can be
retrieved from a local cache rather than re-querying the LLM, thus reducing
costs, service provider load, and environmental impact. Existing caching
solutions for LLMs raise privacy and scalability concerns and perform wasteful
query requests. MeanCache leverages Federated Learning (FL) to collaboratively
train a query similarity model across LLM users without violating privacy. By
placing a local cache in each user’s device and using FL, MeanCache reduces
the latency and costs and enhances model performance, resulting in lower false
hit rates. MeanCache compresses the embedding dimensions to minimize cache
storage and also finds the optimal cosine similarity threshold. Our
experiments benchmarked against the state-of-the-art caching method, reveal
that MeanCache attains an approximately 17% higher F-score and a 20% increase
in precision during semantic cache hit-and-miss decisions. It also reduces the
storage requirement by 83% and accelerates semantic cache hit-and-miss
decisions by 11%.

Federated Learning, Cache, Hit, Miss, Rate, ChatGPT, Llama, Semantic, Search,
Large Language Models, LLMs, GPT, Machine Learning, Privacy, Embeddings,
Cosine Similarity, Client

##  1\. Introduction

Large Language Models (LLMs) like ChatGPT (cha, [n.d.]), Google Bard (bar,
[n.d.]), Claude (cla, [n.d.]), and Llama 2 (Touvron et al., 2023) have
demonstrated remarkable capabilities in understanding and generating human
language, leading to significant advancements in applications ranging from
search engines to conversational agents. LLMs are increasingly integrated into
platforms like the Perplexity AI search engine (per, [n.d.]b), Rabbit OS (rab,
[n.d.]), Arc browser (arc, [n.d.]), and Bing Chat (bin, [n.d.]). For instance,
in 2023, 1.9 billion queries were sent to Bing chat, reflecting the massive
use of such systems (bin, [n.d.]).

Motivation. Generating responses to user queries with LLMs, such as GPT-3,
requires substantial computations and poses environmental challenges (Frantar
et al., 2023; Wang et al., 2023; Tseng et al., 2024; Sachdeva et al., 2024; Ma
et al., 2024; Strubell et al., 2019). For example, GPT-3’s 175B parameters in
float16 format consume 326 GB memory, exceeding single GPU capacities and
necessitating multi-GPU deployments (Frantar et al., 2023). These requirements
lead to high operational costs.

Consequently, LLM-based services charge users and limit query rates (per,
[n.d.]a; ope, [n.d.]). Prior studies report that users frequently submit
similar queries to web services (Lempel and Moran, 2003; Xie and O’Hallaron,
2002)—approximately 33% of search engine queries being resubmitted (Markatos,
2001). We investigate if a similar pattern exists with queries to LLMs. Our
analysis of a large corpus of real-world user conversations with ChatGPT
reveals that approximately 31% of such queries have a high similarity with a
previously submitted query 2. Thus, there is a potential to reduce the query
inference cost of LLMs by up to one-third.

Caching serves as an effective technique in traditional web services to
address duplicate search queries, avoiding redundant computations,
significantly improving response time, reducing the load on query processors,
and enhancing network bandwidth utilization (Markatos, 2001; Saraiva et al.,
2001; Xie and O’Hallaron, 2002; Lempel and Moran, 2003; Brin and Page, 1998;
Podlipnig and Böszörmenyi, 2003; Baeza-Yates et al., 2007). If applicable to
LLMs-based web services, such caching can substantially impact billions of
floating point operations, thereby decreasing operational costs and
environmental impacts.

Figure 1. Analysis of real-world ChatGPT conversations reveals that, on
average, 31% of queries are similar to previously submitted queries.

Problem. Existing caching techniques (Saraiva et al., 2001; Markatos, 2001;
Xie and O’Hallaron, 2002; Lempel and Moran, 2003) use keyword matching, which
often struggles to capture the semantic similarity among similar queries to
LLM-based web services, resulting in a significantly low hit rate. For
instance, existing caches do not detect the semantic similarity between ”How
can I increase the battery life of my smartphone?” and ”Tips for extending the
duration of my phone’s power source.”, leading to a cache miss. Recently, Zhu
et al. (2023) and GPTCache(Bang, 2023) present server-side semantic caching
for the LLMs-based services to address the limitations of keyword-matching
caching techniques. If a new query is semantically similar to any query in the
cache, the server returns the response from the cache. Otherwise, a model
multiplexer selects the most suitable LLM for the query to generate the
response.

Existing semantic caches have several limitations. First, they demand a
significantly large central cache to store the queries and responses of all
users, which is unscalable and violates users’ privacy. Second, they incur the
network cost of sending a user query to the server even if there is a cache
hit. An end user will still be charged for the query even if the query is
served from the server cache. Third, they use a single server-side embedding
model to find the semantic similarity among queries, which does not generalize
to each user’s querying patterns For instance, Google Keyboard (gbo, [n.d.])
adapts to each user’s unique writing style and embeds such personalized
behaviors to enhance the accuracy of the next word prediction model. Fourth,
they employ Llama-2 to enhance the accuracy of semantic matching (Bang, 2023);
however, in practice, such models perform billions of operations to generate
embeddings, offsetting the benefits of the cache.

Key Insights and Contributions of MeanCache. This work introduces a novel
_user-centric_ semantic caching system called MeanCache. MeanCache provides a
privacy-preserving caching system that returns the response to similar queries
directly from the user’s local cache, bypassing the need to query the LLM-
based web service. MeanCache achieves these goals in the following ways.

To address privacy concerns associated with central server-side caching,
MeanCache introduces a user-side cache design ensuring that the user’s queries
and responses are never stored outside of the user’s device. While a
personalized per-user cache may not offer benefits for similar queries across
multiple users, our investigation with real-world conversations with ChatGPT
reveals that approximately 31% of the queries are still similar to at least
one of the previously submitted queries by the same user. Therefore, having a
user-centric cache offers the same, if not more, opportunities to eliminate
expensive LLM queries.

To find a semantic match between a new query and cached queries, prior work
(Bang, 2023) advocates for a larger model, such as Llama 2, to generate highly
accurate embeddings but requires billions of operations. Such models are not
suitable for resource-limited users’ devices. Previous work has shown that a
smaller model can achieve performance comparable to larger models on custom
tasks (Ouyang et al., 2022; Penedo et al., 2024; Du and Kaelbling, 2024).
MeanCache uses smaller embedding models such as MPNet (Song et al., 2020) to
generate embeddings for semantic matching locally.

Each user may not have sufficient queries to customize an embedding model that
can help find a semantic match between new queries and cached queries. To
address this, MeanCache utilizes federated learning, which exploits data silos
on user devices for private training for collaborative learning, thereby
personalizing an embedding model for each user. This privacy-preserving
training not only customizes the embedding model to the user’s querying
patterns but also enhances the performance (_i.e.,_ accuracy) of semantic
caching without compromising user privacy (_i.e.,_ without storing user data
on the web server).

The runtime performance of MeanCache is primarily influenced by the time taken
to match a new query embedding vector with existing ones in the cache to find
a semantically similar query. The search time is directly proportional to the
dimensions of the embedding vector. To optimize runtime performance, MeanCache
compresses the embedding vector by leveraging principal component analysis
(PCA) (Pearson, 1901; Hotelling, 1933; Jolliffe and Cadima, 2016), effectively
reducing the size of the embedding vector (_i.e.,_ projecting it to lower
dimensional space). MeanCache also offers an adaptive cosine similarity
threshold, which is also collaboratively computed using FL, to improve
accuracy in finding semantic matches between queries.

Study of Real-World Queries. To measure the prevalence of similar queries in
real-world conversation with LLM-based web service, We recruited 20
participants who regularly use ChatGPT and conducted a thorough analysis of
their queries in a privacy-preserving manner. Across 27K queries, we find that
31% of a user’s queries are similar to at least one previous query by the same
user, which could have been retrieved from a cache.

Evaluations. We compare MeanCache with GPTCache(Bang, 2023), a widely-used
open-source semantic cache for LLM-based web services. GPTCache (Bang, 2023)
is the most closely related work to MeanCache and has received over 6,000
stars on GitHub(zil, [n.d.]). We benchmark MeanCache’s performance against
GPTCache on the GPTCache’s dataset (dat, [n.d.]) to demonstrate its
effectiveness and highlight the improvements MeanCache offers over existing
solutions.

MeanCache surpasses GPTCache (Bang, 2023) by achieving a 17% higher F score
and approximately a 20% increase in precision in end-to-end deployment for
identifying duplicate queries to LLM-based web services. MeanCache’s embedding
compression utility approximately reduces storage and memory needs by 83% and
results in 11% faster semantic matching, while still outperforming the state-
of-the-art GPTCache.

##  2\. Similar User Queries in Practice

Prior study (Markatos, 2001) measured the prevalence of similar queries across
the entire user population. To understand the extent to which a single user
submits similar queries, we conducted the first empirical study to measure how
often a real-world ChatGPT user submits similar queries. Given the private
nature of conversations with the ChatGPT service, study participants are
naturally reluctant to share their query corpus. To address this problem, we
develop a script that runs locally on each participant’s computer and
identifies semantically similar queries, and calculates the percentage of
similar queries on the participant’s query corpus. We then ask the
participants to review the results and share, if comfortable, only three
metrics (% of similar queries, total queries, and days since the first query)
anonymously with the authors.

We recruited 20 participants, including male and female participants,
university professors, and graduate students who regularly use ChatGPT. Before
measuring the query statistics, our analysis script addresses false positives
by excluding large queries with lengths beyond 256 tokens. We examined over
27K queries across 20 participants who have been using ChatGPT for an average
of 332 days.

Figure 1 presents the results of this study. We find that, on average, 31% of
each participant’s queries are highly similar to at least one of the
previously submitted queries by the same participant, which necessitates a
user-centric cache for LLM-based web services.

##  3\. Background

###  3.1. Federated Learning

Federated Learning is a distributed, privacy-preserving training of a machine
learning (ML) model. An FL round starts when a central server shares a global
model with all the participating clients. Each client trains the model on its
local data and sends the updated model to the central server. The central
server aggregates the received models’ weights to form a new global model to
be used in the next round. Different aggregating algorithms have been
proposed, such as FedAvg (McMahan et al., 2017), FedProx (Li et al., 2020),
and FedMA (Wang et al., 2020b). The FedAvg algorithm is the most popular one,
and it aggregates the models with the following equation:

(1) $W_{global}^{t+1}=\sum_{k=1}^{K}\frac{n_{k}}{n}w_{k,t}$

$W_{global}^{t+1}$represents the new global model, $w_{k,t}$ denotes the model
of the $k^{th}$ client at the $t^{th}$ round, $n_{k}$ are the number of
samples available at $k^{th}$ client and $n$ is the total number of samples of
clients participating in the given round. This procedure is reiterated for
multiple rounds until the model reaches convergence.

###  3.2. Transformer Architecture

The transformer architecture is a deep learning model based on the attention
mechanism, which allows the model to focus on the important parts of the input
(Vaswani et al., 2017). The transformer architecture is primarily used for
sequence-to-sequence tasks in NLP, such as machine translation, text
summarization, and question-answering.

The attention mechanism calculates the importance of each input element by
considering its relationship with other elements in the sequence. This enables
the model to capture long-range dependencies and improve performance on tasks
that require an understanding of context. The feed-forward layer

helps the model capture complex patterns and relationships in the data. The
transformer architecture also incorporates positional encoding, which provides
information about the position of each element in the input sequence. This
helps the model understand the order of the elements, which is crucial for
tasks like machine translation.

####  3.2.1. Embeddings and Cosine Similarity

Transformer model can encode the given text into embeddings. Embeddings
represent words or phrases as dense vectors in a high-dimensional space and
capture the semantic meaning of words or phrases, and therefore, words or
sentences with similar meanings will have similar vector representations
(Reimers and Gurevych, 2019; Karpukhin et al., 2020; Ni et al., 2022). For
example, the words ”king” and ”queen” are semantically similar because they
both refer to royalty. Therefore, their embeddings will be close to each other
in the vector space. These embeddings encode the contextual information and
semantic meaning of the sentences. Cosine similarity is a measure of
similarity between two vectors. In the context of embeddings, cosine
similarity is often used to quantify the similarity between sentence
embeddings. It is calculated by taking the cosine of the angle between the two
vectors. The cosine similarity ranges from -1 to 1, where -1 indicates
completely opposite vectors, 0 indicates orthogonal (perpendicular) vectors,
and 1 indicates identical vectors. Cosine similarity ($\theta$) between
embeddings E1 and E2 is measured as:

(2)
$\theta=\frac{{\textbf{E1}}\cdot{\textbf{E2}}}{\|{\textbf{E1}}\|\|{\textbf{E2}}\|}$

Here, E1 and E2 represent the two word embeddings, ”dot” represents the dot
product of the vectors, and ”——E1——” and ”——E2——” represent the Euclidean
norms (magnitudes) of the vectors.

Figure 2. MeanCache’s Workflow

##  4\. MeanCache’s Design

MeanCache is a user-centric semantic caching system optimized for user-side
operation. Figure 2 illustrates the workflow of MeanCache for similar queries.
When a user submits a query to an LLM web service with MeanCache enabled,
MeanCache computes the query embeddings. These embeddings are then matched
with the embedding of the cached queries using cosine similarity. If MeanCache
locates a similar query within the cache, the response is retrieved from the
local cache and returned to the user. Otherwise, MeanCache forwards the query
to the LLM web service to obtain the response. The query and its response and
embeddings are then stored in the cache.

The key contribution of MeanCache comes from harnessing the collective
intelligence of multiple users to training a semantic similarity model and its
user-centric design that addresses both privacy and scalability issues. To
achieve these, MeanCache takes the following design decisions. It employs a
small embedding model with lower computational overhead than large Language
Learning Model (LLM) based embedding models, such as Llama 2. It uses
federated learning (FL) for collaborative training to fine-tune the embedding
model without ever storing user data on a central server. This approach
generates high-quality embeddings and improves the accuracy of embedding
matching for retrieving similar queries. To reduce storage and memory overhead
and expedite the search time for finding similar queries in the cache,
MeanCache compresses the embeddings using Principal Component Analysis (PCA).
MeanCache leverages user feedback (i.e., forcing LLM request instead of the
cache query) to adapt the threshold for cosine similarity. It then shares the
updated threshold via FL to determine the optimal threshold across multiple
users. It does this by varying the threshold and selecting the one that
optimizes the F-score of the cache on clients.

Figure 3. Privacy-Preserving Embedding Model FL Training in MeanCache.

###  4.1. FL Based Embedding Model Training

GPTCache(Bang, 2023) suggests using Llama 2 to generate superior embeddings,
thereby enhancing semantic matching accuracy. However, this approach has
several limitations. Large language models like Llama 2 are not only sizable,
being gigabytes in size, but they also require substantial computational
resources to generate embeddings. Deploying such models, especially at the
end-user level, is impractical due to their size and significant computational
overhead for semantic matching. MeanCache employs a compact embedding model,
which has a lower computational overhead compared to large embedding models.
The smaller model may not provide the same level of accuracy as an LLM.
However, a smaller model trained on customized tasks can match the performance
of an LLM (Ouyang et al., 2022; Penedo et al., 2024; Du and Kaelbling, 2024).
One challenge in using smaller embedding models is that each user may not have
sufficient data to train and customize the embedding model.

MeanCache utilizes federated learning to exploit the vast amount of
distributed data available on users’ devices to train and personalize the
smaller embedding model. Federated Learning allows the users to train the
embedding model locally and learn the optimal threshold for cosine similarity.
The updated weights and local threshold are shared with the server. The server
aggregates the updated weights and cosine similarity threshold from multiple
users to update the global model, which is redistributed back to the users.
This approach ensures that the user’s privacy is maintained, and the
collective intelligence of multiple users is leveraged to improve the
performance of the caching system. Figure 3 shows the overview of privacy-
preserving training of the embedding model with FL.

In the first step, the server sends the initial weights of the embedding model
($W_{global}^{t+1}$) and global threshold ($\tau$) to a subset of users as
shown in step 1 in Figure 3. The subset of users is usually randomly selected
or selected based on their battery level, network bandwidth, or performance
history. Additionally, the server also sends the hyperparameters (_e.g.,_
learning rate, batch size, epochs) necessary for FL training of the embedding
model.

####  4.1.1. Client Training.

Upon receiving the embedding model ($W_{global}^{t+1}$) from the server, each
client replaces its local embedding model weights with the newly received
weights. Subsequently, each client trains the embedding model locally on its
unique local dataset (step 2 in Figure 3).

To generate high-quality embeddings from unique and similar queries,
MeanCache’s clients’ training employs a multitask learning approach,
integrating two distinct loss functions: contrastive loss (Reimers and
Gurevych, 2019) and multiple-negatives ranking loss (Henderson et al., 2017;
Reimers and Gurevych, 2019). These loss functions update the weights of the
embedding model during the training process. The contrastive loss function
operates by distancing unique (non-duplicate) queries from each other within
the embedding space, thereby facilitating the differentiation between
duplicate and non-duplicate queries. Unlike contrastive loss, the multiple-
negatives ranking loss function minimizes the distance between positive pairs
(duplicate queries) amidst a large set of potential candidates _i.e.,_
multiple-negatives ranking loss does not concentrate on distancing unique
queries and its primary objective is to draw positive pairs (similar queries)
closer within the embedding space.

This multitasks learning approach enables MeanCache to adjust to diverse query
patterns exhibited by users. For instance, some users may generate more
repetitive queries compared to others, while certain users may not produce any
repetitive queries at all. Interestingly, MeanCache’s multitask learning
objective can benefit from learning even from a user with no repetitive
queries. This is because MeanCache’s global embedding model
($W_{global}^{t+1}$) will learn to widen the distance between unique queries,
thereby effectively learning the true misses of the non-duplicate queries and
minimizing the false hits during the search process. True miss happens when a
similar query is not present in the cache. A false hit is when a query is
found and returned from the cache, which is not actually similar.

####  4.1.2. Finding the Optimal Threshold for Cosine Similarity.

After generating query embeddings using an embedding model, a similarity
metric such as cosine similarity is used to determine if the new query
embeddings match the cached embeddings of past queries. This process involves
setting a threshold for cosine similarity, which is a delicate balance.

In addition to privacy-preserving training of the embedding model, MeanCache
also learns the optimal threshold ($\tau$) for cosine similarity. The range of
$\tau$ is between 0 and 1. This threshold ($\tau$) dictates the level of
similarity above which a cached query is considered relevant to the current
user query. Setting the threshold too low could result in numerous false hits,
leading to retrieving irrelevant queries from the cache. Conversely, a
threshold that is set too high might cause many false misses, where relevant
queries are not retrieved from the cache. Hence, finding the optimal threshold
($\tau$) for cosine similarity is vital.

During the client’s local training, MeanCache determines this optimal
threshold ($\tau$) from the client’s response to the cache query response.
Even after finding a cached response, a user requests a response from the LLM,
MeanCache considers it as a false positive and adjusts its threshold.
MeanCache varies the threshold $\tau$ to find the optimal threshold that
optimizes the F-score of the cache (Section 5.3). The user will use the
optimal threshold to find similar queries in the cache. By finding the optimal
threshold, MeanCache effectively balances between true hits and true misses,
therefore yielding improved accuracy in semantic similarity matching to return
the response from the cache on duplicate queries.

####  4.1.3. Aggregation.

After client local training and finding the optimal threshold, each client
sends updated weights of the global model ($W_{global}^{t+1}$) and optimal
threshold ($\tau$) to the server (step 3 in Figure 3). The server aggregates
the updated weights from multiple users to form a new embedding model
($W_{global}^{t+1}$) using FedAvg (McMahan et al., 2017) as shown in step 4 of
Figure 3. The server also computes the mean of the received optimal thresholds
from the clients for a global optimal threshold ($\tau_{global}$). The benefit
of finding $\tau_{global}$ is that when a new user joins the system, the user
will not have queries to find its own optimal threshold. In such cases, the
system can use $\tau_{global}$ as a starting point for semantic similarity.

After finding the global optimal threshold and the global embedding model, the
server then redistributes the updated embedding model to the users for the
next round of FL training. This process is repeated over several to improve
the semantic matching accuracy of the MeanCache (_i.e.,_ lower false hits and
false misses). This approach ensures that the user’s privacy is maintained
(_i.e.,_ clients queries are never stored at the central server), and the
collective intelligence of multiple users is leveraged to improve the
performance of the MeanCache. After the completion of the FL training, each
client will have access to a fine-tuned embedding model ($W_{global}^{t+1}$)
to generate high-quality embeddings which can capture the complex semantics of
a user query. For example, MeanCache’s embedding model can discern the
semantic similarity between ”Draw a line plot in Python” and ”Plot a linear
graph using Python”, and serve such queries locally, as depicted in Figure 2.

Figure 4. Embeddings Compression using PCA

####  4.1.4. Embeddings Compression using PCA

The substantial size of the embedding vector, for instance, the Llama 2
embeddings dimension being 4096, can lead to considerable overhead during the
matching process of a new user query embeddings with cached queries
embeddings. This is due to the search time being directly proportional to the
dimensions of the embedding vector. Furthermore, high-dimensional embeddings
demand more memory and storage. For example, the embeddings generated by Llama
2 for a single query require approximately 32.05 KB of memory storage.
Consequently, calculating the cosine similarity between two high-dimensional
embeddings, specifically new query embeddings and each embedding in the cache,
becomes computationally demanding and time-intensive. Therefore, to improve
the search time for identifying similar queries in the cache and to reduce the
client’s storage needs, it is essential to diminish the dimensionality of the
embeddings while ensuring minimal impact on the tool’s performance.

Principal Component Analysis (PCA) is a dimensionality reduction technique
that is widely used to compress high-dimensional data into a lower-dimensional
space (Pearson, 1901; Hotelling, 1933; Jolliffe and Cadima, 2016), while still
maintaining the most important information. First, MeanCache generates
embeddings for all the users’ queries using the embedding model. Next,
MeanCache applies PCA to learn the principal components of all the queries
embeddings generated in the previous step, as shown in Figure 4-a. MeanCache
integrates the learned principal components as an additional layer in the
embedding model. This new layer will project the original embeddings onto the
lower dimensional space, producing compressed embeddings (Figure 4-b).

When a non-duplicate query is received, MeanCache uses the updated embedding
model (with PCA layer) to generate the compressed embeddings (Figure 4-b) for
the new query and store the query, response, and the compressed embedding in
the cache. Storing the compressed embeddings in the cache will significantly
reduce the storage and memory overhead of the embeddings. Next, when a
duplicate query is received, MeanCache uses the same embedding model with PCA
components to generate the compressed embeddings for this duplicate query and
find similar queries in the cache. Since the embeddings are compressed, the
search time for finding similar queries in the cache will be significantly
reduced.

###  4.2. Cache Population and MeanCache Implementation

Once the embedding model is trained within MeanCache on each user, it is
deployed as depicted in Figure 2. Initially, when a new user starts using
MeanCache, the local cache is vacant. During these interactions, if a user
query’s response is not found in the cache, the request is forwarded to the
LLM web service to retrieve the response, which is then inserted in the cache.
If MeanCache finds a semantically similar query for any of the following
queries, it responds to the user’s similar queries by retrieving the response
from the local cache.

MeanCache is a python-based application that is built on the Flower FL
framework (Beutel et al., 2020). A user can submit LLM queries via this
application to take advantage of the local cache. The central server, which
orchestrates the FL training, may reside on the LLM web service. We employ the
Sbert (Reimers and Gurevych, 2019) library to train MPNet (Song et al., 2020)
and Albert (Lan et al., 2019) on each client and to generate query embeddings.
To efficiently execute a cosine similarity search between a query embedding
and cached embeddings, we utilize Sbert’s semantic search, which can handle up
to 1 million entries in the cache. MeanCache cache storage is persistent and
built using DiskCache (Dis, [n.d.]) library.

##  5\. Evaluation

Our evaluation answer the following research questions.

  * •

Is it possible to train an embedding model in a privacy-preserving manner
without the need for centralized data?

  * •

Besides preserving user query privacy, how does MeanCache perform in
comparison to baseline in terms of performance metrics?

  * •

What effect does the cosine similarity threshold have on the performance of
MeanCache?

  * •

What level of overhead does MeanCache impose on the user side? Is it possible
to reduce the embedding dimension to save storage space while still
outperforming the baseline?

  * •

GPTCache (Bang, 2023) suggests using Llama 2 to generate embeddings to improve
semantic matching. Is it feasible to use Llama 2 to compute embeddings at the
user side for semantic matching?

###  5.1. Evaluation Settings

We conduct evaluations of MeanCache against the baseline (Bang, 2023) to
demonstrate that MeanCache achieves optimal performance while preserving user-
privacy (_i.e.,_ without storing the user queries at the server). For a fair
comparison between MeanCache and baseline, we employ the optimal configuration
as described in the GPTCache study (Bang, 2023). This configuration utilizes
Albert (Lan et al., 2019) and sets the cosine similarity threshold at 0.7 to
determine the cache hit or miss.

####  5.1.1. Transformer Models and Datasets.

For extensive evaluations of MeanCache, we utilize the Llama 2 (Touvron et
al., 2023), MPNet (Song et al., 2020), and Albert (Lan et al., 2019)
transformer models to generate embeddings.

We evaluate MeanCache using the GPTCache dataset. The dataset is partitioned
into training, testing, and validation subsets. The training and validation
datasets are randomly distributed among the clients, with each client
receiving non-overlapping data points. During local training, each client
utilizes its training dataset to update its local embedding model and employs
the validation dataset to determine the optimal threshold for cosine
similarity (Section 5.3). The testing dataset, located at the central server,
facilitates a fair comparison between MeanCache and GPTCache (Bang, 2023).

####  5.1.2. Experimental Setup

The experiments are conducted on a high-performance computing cluster,
equipped with 128 cores, 504 GB of memory, and four A100 Nvidia GPUs, each
with 80 GB of memory. We utilize the Flower FL (Beutel et al., 2020) library
to simulate a federated learning setup. Additionally, the SBERT (Reimers and
Gurevych, 2019) library is employed to train the embedding model on each
client. The number of clients participating in FL training are 20. The number
of clients is restricted due to the limited size of the GPTCache dataset,
which is inadequate for distribution among hundreds of clients. However, we
believe MeanCache results are not influenced by the number of clients, and the
evaluation setup of MeanCache is consistent with the evaluation standard in FL
(Avdiukhin and Kasiviswanathan, 2021; Wang et al., 2020a).

####  5.1.3. Evaluation Metrics

In caching systems, the efficacy has traditionally been gauged by cache hit-
and-miss rates. A cache hit implies the data or query is retrieved from the
cache, whereas a cache miss indicates the opposite. Semantic caching
introduces a nuanced classification: true and false hits, alongside true and
false misses. A true hit signifies a correct match between a query and a
similar cached query, whereas a false hit is an incorrect match with a non-
similar cached query.

Thus, semantic caching complexity renders traditional hit/miss metrics
potentially misleading. For example, a query might incorrectly match with an
irrelevant cached query (deemed a hit traditionally) due to semantic matching.
This necessitates more sophisticated metrics to accurately assess a semantic
cache’s performance. We adopt precision, recall, F1 score, and accuracy, for a
comprehensive evaluation of MeanCache against GPTCache. These metrics are
defined as follows:

Precision. The ratio of true positive hits to all positive hits (including
both true positives and false positives). In semantic caching, this measures
how many of the queries matched to a cached query are correctly matched.
$\text{Precision}=\frac{TP}{TP+FP}$ where $TP$ represents true positives (true
hits) and $FP$ represents false positives (false hits).

Recall. The ratio of true positive hits to all relevant items (including both
true positives and false negatives). In semantic caching, this assesses the
proportion of correctly matched queries out of all queries that should have
been matched to a cached query. $\text{Recall}=\frac{TP}{TP+FN}$ where $FN$
represents false negatives (false misses).

Fβ Score. A weighted harmonic mean of precision and recall, balancing the two
based on the value of $\beta$. $\beta>1$ gives more weight to recall, while
$\beta<1$ emphasizes precision.

$F_{\beta}=(1+\beta^{2})\cdot\frac{\text{Precision}\times\text{Recall}}{(\beta^{2}\times\text{Precision})+\text{Recall}}$

Accuracy. The ratio of correctly identified queries (both true hits and true
misses) to all queries. $\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$ where $TN$
represents true negatives (true misses).

01020304050FL Training
Rounds0.750.800.850.900.95ScoreF1PrecisionRecallAccuracy

Figure 5. FL training enhances _MPNet’s_ ability to generate high-quality
embeddings by leveraging users’ private data, thereby improving MeanCache’s
query matching precision from 0.74 to 0.85, demonstrating its effectiveness.

01020304050FL Training
Rounds0.750.800.850.900.95ScoreF1PrecisionRecallAccuracy

Figure 6. FL training boosts MeanCache’s user query matching precision with
_Albert_ embedding model from 0.74 to 0.81, ensuring privacy.

###  5.2. Privacy Preserving Embeddings Model Training

Storing user or client queries on the server side presents a potential privacy
risk. To address this, each client can retain its local data on its own
device. The ensuing challenge is how to train an embedding model that can also
utilize the distributed data from all clients. Federated Learning is
recognized for training neural networks in a privacy-preserving manner. As
such, MeanCache employs FL to train and fine-tune an embedding model, thereby
preserving privacy and leveraging the dataset residing on the client’s side.
In this section, our objective is to evaluate whether FL training can
progressively enhance the embedding model to generate high-quality embeddings
for user queries. To simulate this scenario, we distribute the training
dataset among 20 clients. In each round, we sample 4 clients, conducting a
total of 50 FL training rounds. Each client trains its embedding model for 6
epochs, operating on a dedicated A100 GPU. We conduct two experiments with the
Albert and MPNet models. The batch size is set to 256 for the Albert model,
and for MPNet, it is set to 128 during the local training by participating
clients.

Figures 5 and 6 depict the performance of MeanCache as FL training progresses.
The X-axis represents the training round, while the Y-axis shows the
performance metrics such as F-score, precision, recall, and accuracy of the
global model ($W_{global}^{t+1}$). As illustrated in Figure 5, the F-score for
MPNet increases from 0.82 to 0.88, and for Albert, it rises from 0.83 to 0.86,
as shown in Figure 6. Similarly, precision for MPNet significantly increases
from 0.74 to 0.85, as depicted in Figure 5, and for Albert, it increases from
0.74 to 0.81, as demonstrated in Figure 6. Given that MPNet is a more robust
transformer architecture compared to Albert, it is also observed during our
training that MPNet outperforms Albert, exhibiting superior learning in FL
settings.

Summary. Overall, FL training increases 11% precision of MeanCache for MPNet
and a 7% increase for Albert. Therefore, it is evident that the performance of
the embedding model to generate high-quality embeddings can improve in a
privacy-preserving manner using FL training, that is, without storing user
queries at the central server.

0.00.20.40.60.81.0Threshold0.250.500.751.00ScoreF1PrecisionRecallAccuracy

Figure 7. Extremes in threshold harm semantic matching; MeanCache autonomously
optimizes MPNet’s threshold at 0.83 for an F score of 0.89.

0.00.20.40.60.81.0Threshold0.000.250.500.751.00ScoreF1PrecisionRecallAccuracy

Figure 8. For Albert embedding model, MeanCache identifies an optimal
threshold of 0.78, achieving a peak F-score of 0.88 on validation data.

###  5.3. Cosine Similarity Threshold Impact on Semantic Matching

The process of semantic matching for a new user query begins by generating the
embeddings of the user’s query ($E_{q}$) using the embedding model. Following
this, the cosine similarity ($\theta$) is computed with the cached embeddings.
If the cosine similarity $\theta$ exceeds the threshold $\tau$, the cache is
hit and the response to the user query is returned from the cache. Therefore,
the cosine similarity threshold $\tau$ plays a crucial role in determining the
similarity between a user query and cached entries. A low threshold value of
$\tau$ can lead to false hits (incorrect matches), while a high threshold
might overlook the appropriate matches (_i.e.,_ false cache misses or false
negatives). Hence, identifying an optimal threshold is essential.

To illustrate this, MeanCache varies the threshold $\tau$ from 0 to 9 and
evaluates the performance metrics F-Score, precision, recall, and accuracy
with an equal distribution of duplicate and non-duplicate queries from the
validation data to avoid bias.

Figures 7 and 8 show how the cosine similarity threshold ($\tau$) affects
MeanCache’s performance. The X-axis represents the threshold $\tau$ values,
and the Y-axis denotes the performance metrics. For instance, at a 0.3
threshold, MeanCache’s semantic matching accuracy using MPNet is 57%, with a
precision of 54% as shown in Figure 7. Similarly, with Albert at the same
threshold, the accuracy is 55%, and precision is 53% (Figure 8). Precision
typically improves with an increase in threshold. However, beyond a certain
point, increasing the threshold $\tau$ leads to a decline in F score,
accuracy, and recall, _i.e.,_ higher value of $\tau$ increases false cache
misses (false negatives). Therefore, setting an optimal threshold is
imperative.

For MPNet, the optimal threshold $\tau$ is identified at 0.83, achieving an F1
score of 0.89, precision of 0.92, and accuracy of 0.90 (Figure 7). For Albert,
the optimal threshold is 0.78, with an F1 score of 0.88, precision of 0.86,
and accuracy of 0.88. Note that in the rest of the evaluations, we use these
thresholds for MPNet and Albert with MeanCache.

Summary. Experimental evaluations indicate that GPTCache’s suggested threshold
of 0.7 will result in suboptimal performance during semantic matching.
Moreover, the optimal threshold $\tau$ values varies with the embedding model.
MeanCache optimally adjusts the threshold based on user data, outperforming
GPTCache’s suggested threshold by 16% in precision and 4% in F score for
MPNet, and by 10% in precision and 2% in F score for Albert. This highlights
the importance of fine-tuning the cosine similarity threshold to its optimal
value.

020406080100Query ID0.00.51.0Time (s)Llama 2Llama 2+GPTCacheLlama 2+MeanCache

Figure 9. Response times of 100 randomly sampled user queries to the Llama
2-based LLM service in three scenarios: without any semantic cache, with
GPTCache, and with MeanCache. The integration of a semantic cache does not add
significant overhead to non-duplicate queries, meaning it does not impede the
performance of the LLM-based service. Moreover, it significantly reduces the
average response times for duplicate queries (70-99) by serving them from the
local cache.

020406080100Query IDHitMissLabelReal LabelGPTCache Predicted LabelMeanCache
Predicted Label

Figure 10. Comparison of MeanCache and GPTCache on a set of 100 queries,
including 70 non-duplicate and 30 duplicate queries, sent to the Llama 2-based
LLM service. Queries 0 to 69 are non-duplicate (_i.e.,_ real label is miss),
and GPTCache produces significantly higher false hits on these unique queries
compared to MeanCache.

01Predicted Label01Real Label6118966234

(a) MeanCache

01Predicted Label01Real Label46723346254

(b) GPTCache

Figure 11. Confusion matrices for MeanCache and GPTCache on 1000 queries comprising 700 unique and 300 duplicate queries. Among the 700 unique queries, MeanCache produces only 89 false hits, while GPTCache generates a significantly larger number of false hits, 233 in total. False hits are undesirable as they require the user to resend the query to the LLM service to obtain the correct response. Metrics | GPTCache | MeanCache | MeanCache
---|---|---|---
|  | (MPNet) | (Albert)
F score | 0.56 | 0.73 | 0.68
Precision | 0.52 | 0.72 | 0.66
Recall | 0.85 | 0.78 | 0.77
Accuracy | 0.72 | 0.85 | 0.81
Table 1. MeanCache outperforms GPTCache (Baseline)

100020003000(a) Number of Cached Queries02000400060008000Storage Size
(KBs)100020003000(b) Number of Cached Queries0.010.020.03Avg. Search Time
(s)100020003000(c) Number of Cached Queries0.50.60.7F ScoreGPTCacheMeanCache
(MPNet)MeanCache (Albert)MeanCache-Compressed (MPNet)MeanCache-Compressed
(Albert)

Figure 12. (a)MeanCache’s embedding compression utility significantly reduces
storage space by 83% compared to GPTCache. (b) MeanCache’s semantic matching
speed is 11% faster with compression enabled, while still outperforming
GPTCache. (c) MeanCache’s F score is slightly lower with compression enabled,
but it still outperforms GPTCache.

###  5.4. MeanCache Comparison with Baseline (GPTCache)

Markatos (2001); Xie and O’Hallaron (2002) have shown that users often send
repeated queries to online services. While these repeated queries typically
make up a smaller volume than the total query count, identifying them at the
client-side can significantly reduce server load, decrease bandwidth
requirements, and improve response times. Therefore, detecting repeated
queries not only benefits LLM based services but also enhances the overall
user experience and conserves the permissible query quota. We evaluate
MeanCache against GPTCache, a baseline semantic cache, to assess improvements
in user experience, precision, recall, and F score. We select a sample of 1000
queries, 30% of which are repeated queries (_i.e.,_ 300 queries are repeated),
and load these 1000 queries as cached queries. Note that repeated queries are
usually fewer than non-repeated queries. Thus, we use 30% as repeated queries,
a similar percentage previously observed for web services (Markatos, 2001).

Initially, we send a new set of one thousand queries to Llama 2 (i.e., without
any semantic cache) to establish a baseline for response times. We limit
responses to 50 tokens to reflect practical response sizes, although actual
sizes can be much larger. Note that MeanCache’s performance is not dependent
on the response as it only matches the queries. Next, we send these queries to
Llama 2 based local LLM service with MeanCache and GPTCache to measure the
response times and performance metrics (e.g., precision, recall, F-score)
respectively. An analysis of a random subset of 100 queries (70 non-duplicate
and 30 duplicate) from the 1000 queries shows the impact of caching on
response times in Figure 9 and cache hit and miss rates in Figure 10. The
X-axis represents the query and the Y-axis represents each semantic cache hit
and miss alongside the real label in Figure 10. The Y-axis in Figure 9 shows
the response time of each query without any cache (Llama 2), with GPTCache
(Llama 2+ GPTCache), and with MeanCache (Llama 2+MeanCache). Figure 9
demonstrates that implementing a semantic cache does not impede the
performance (queries ranging from 0 to 69) and improves the user experience as
response times reduces on duplicate queries (queries 70 to 99).

However, Figure 10 shows that GPTCache produces significant false hits on non-
duplicate queries (queries 0 to 69) compared to MeanCache. Each false hit
means the user receives an incorrect query response from the cache and must
resend the same query to LLM service, resulting in a poor user experience. To
prioritize precision, we adjust the beta value in the F score to 0.5, valuing
precision twice as highly as recall to ensure user satisfaction by avoiding
false positives. This decision is driven by the need to minimize user
inconvenience caused by incorrect cache hits. A false miss (low recall) does
not require user intervention as the false miss query will be automatically
routed to the LLM. Thus, precision in semantic caching is more important than
recall.

Table 1 and the confusion matrices in Figure 11 highlight MeanCache’s superior
performance over GPTCache on the 1000 user queries. Notably, MeanCache with
MPNet achieves a precision of 0.72, significantly surpassing GPTCache’s 0.52.
This superiority is evident in the lower false positive rates (i.e., false
hits) shown in Figure 11(a). The number of false hits for MeanCache is 89
(Figure 11(a)), while GPTCache has 233 false hits, as depicted in Figure
11(b). In practical terms, this means that with GPTCache, the end user has to
manually resend 233 queries to the LLM service to get the correct responses,
compared to only 89 queries with MeanCache. While GPTCache’s recall is higher
than MeanCache’s, as we discussed earlier, precision is significantly more
important than recall, and MeanCache outperforms GPTCache in this regard.
Overall, the F-score of MeanCache with MPNet is 0.73 and 0.68 with the Albert
embedding model, both of which outperform GPTCache’s F-score of 0.56.

Summary. In an end-to-end deployment with Llama 2 as LLM service, MeanCache
significantly outperforms GPTCache. It demonstrates a 17% higher F score and a
20% increase in precision in optimal configuration. The substantial reduction
in false cache hits enhances the end-user experience.

###  5.5. MeanCache Embedding Compression utility and Impact on Storage Space

Clients or users often face storage limitations compared to web servers.
Storing embeddings in the local cache on the user side for semantic search
demands memory storage. Various models yield embeddings with differing vector
sizes; for example, the MPNet and Albert models produce an output embedding
vector of 768 dimensions, whereas the Llama 2 model’s embeddings dimension
size is 4096. The embedding vector size also affects semantic search speeds,
where smaller vectors could enhance speed and lower resource demands.

Figure 12 illustrates the effects of MeanCache dimension reduction utility on
the storage, semantic matching speed (overhead), and MeanCache’s performance
(F score). The x-axis indicates the number of queries stored in the cache,
while the y-axis shows storage size, average search time, and the F score in
respective graphs. MeanCache-Compressed (MPNet) and MeanCache-Compressed
(Albert) represent instances where MeanCache decreases the embedding
dimensions from 768 to 64 by employing the compression, as detailed in
MeanCache design (Section 4).

Figure 12 demonstrates that an increase in stored queries linearly raises
storage needs. Yet MeanCache with compression enabled drastically lowers
storage needs by 83% compared to GPTCache.

Figure 12 also indicates that compression decreases the average search time,
with MeanCache enabled compression being approximately 11% faster than
without. Moreover, despite a slight decrease in F score with compression
enabled, MeanCache still surpasses GPTCache. Furthermore, given the evidence
from Figures 5 and 6 that MPNet produces more precise embeddings, and it is
also clear from Figure 12 that MPNet’s embeddings are particularly resilient
to compression and excel in semantic matching.

Summary. The application of embedding compression optimization in MeanCache
offers substantial benefits, including an 83% savings in storage and an 11%
faster search process, while still outperforming the established baseline
(GPTCache).

Llama-2mpnetalbert0.000.020.04Computation Time
(s)0.0400.0050.009Llama-2mpnetalbert0102030Storage Size (KBs)3266

Figure 13. Llama 2 takes significantly longer to compute embeddings and
requires substantially more storage space than Albert and MPNet.

0.00.20.40.60.81.0Threshold0.000.250.500.751.00ScoreF1PrecisionRecallAccuracy

Figure 14. Llama 2 as an embedding model does not perform well in semantic
matching, even at optimal thresholds. The maximum F1 score is 0.75,
significantly lower than with the smaller embedding models (MPNet and Albert).

###  5.6. Infeasibility of Embedding Generation with Llama 2

GPTCache(Bang, 2023) recommend using Llama 2 for generating embeddings to
enhance GPTCache’s performance. However, Llama 2’s embedding computation is
expensive in terms of inference time, requires substantial storage, and incurs
considerable overhead during semantic searches. For example, Llama 2 with its
7 billion parameters, demands 30 GB of memory (Siz, [n.d.]), whereas Albert
and MPNet require only 43 MB and 420 MB, respectively.

To highlight the impracticality to generate query embeddings with Llama 2, we
compare the embedding computation time, embedding storage space requirement of
Llama 2, Albert and MPNet transformer models. Figure 13 shows the average time
to compute the embeddings of a single query and storage requirements for the
embeddings. Figure 13 shows that the average embedding computation time of
Llama 2 is 0.04 seconds, while for Albert and MPNet the average computation
time is 0.005 and 0.009 seconds respectively. Single query embeddings
generated from Llama 2 takes approximately 32 KBs of space and embeddings
generated by both MPNet and Albert only take 6 KBs, as shown in Figure 13.

Furthermore, we evaluate the performance of the Llama 2 on embedding
generation and semantic matching. Figure 14 shows that the performance of
Llama 2 with different cosine similarity threshold ($\tau$) and corresponding
performance metric. We can see that the performance of Llama 2 is not good
even with the optimal cosine similarity threshold, as also noted by
researchers (Use, [n.d.]). The maximum F1 score achieved by Llama 2 is 0.75
which is quite low when compared with the optimal thresholds scores from the
Figures 7 and Figure 8.

Smaller models tailored for specific tasks often surpass larger models in
efficiency (Ouyang et al., 2022; Penedo et al., 2024; Du and Kaelbling, 2024).
Thus, diverging from GPTCache’s approach, we advocate for adopting smaller,
more efficient embedding models for semantic caching. These models not only
ensure optimal performance but also minimize the semantic cache’s overhead on
users, featuring lower inference demands and reduced output embedding sizes,
thereby facilitating deployment on edge devices.

Summary. Llama 2 as an embedding model is not a viable option for generating
embeddings. Future enhancements might improve its performance to generate
high-quality embeddings, yet the computational demands, semantic search
duration, and storage requirements are likely to remain elevated, consequently
impacting the system’s overall efficacy.

##  6\. Related Work

Several caching systems are proposed to optimize the performance of search
engines, databases and operating systems. Saraiva et al. (2001) suggest a two-
tier dynamic caching architecture for web search engines to enhance response
times in hierarchical systems. Utilizing LRU eviction at both levels, they
demonstrate how the second-tier cache can significantly lower disk traffic and
boost throughput. Baeza-Yates and Saint-Jean (2003) propose a three-level
index organization and Long and Suel (2005) propose a three-tier caching. Xie
and O’Hallaron (2002) examined two real search engine datasets to explore
query locality, aiming to develop a caching strategy based on this concept.
Their analysis centered on query frequency and distribution, assessing the
feasibility of caching at various levels, such as server, proxy, and client
side. Lempel and Moran (2003) proposed a novel caching technique, called
Probability Driven Cache (PDC), to optimize the performance of search engines.
PDC uses the probability of a query to be repeated to decide whether to cache
the query or not. Fagni et al. (2006) proposes SDC (Static Dynamic Cache) that
exploit the temporal and spatial locality present in the query stream to avoid
processing the same query and thereby saving the computational resources.
Baeza-Yates et al. (2007) explore efficient caching design for web search
engines, comparing static and dynamic caching, and weighing caching query
results against posting lists. Zhang et al. (2008) examines challenges in
large search engines processing thousands of queries per second across vast
document collections. The study focuses on index compression and caching
optimizations, evaluating various inverted list compression algorithms,
including novel variants, and analyzing different caching policies (_e.g.,_
LRU, LFU). Marin et al. (2010) introduces an innovative cache hierarchy aimed
at boosting web search engines’ efficiency in processing user queries. By
implementing a hierarchical cache system, the study aims to store different
pieces of data useful for solving frequent queries, thereby enhancing overall
query throughput and reducing single-user query latency and power consumption.

In all of the above studies, the caching systems are designed for traditional
search engines that process keyword queries (_i.e.,_ key word matching) and
return a list of links to the user as a response. However, such caching
systems, when applied to LLMs-based web servers or APIs, do not provide a
single concise response and may return many false results. On top of that,
such caching techniques will fail to capture the semantic similarity among
repeated queries and will result in a significantly low hit rate. Zhu et al.
(2023) and (Bang, 2023) propose server-side caching for the services based on
LLMs to reduce the massive computational cost of LLMs. For instance, Zhu et
al. (2023) upon receiving a new query at the server checks if the query is
semantically similar to any query in the cache. If the query is similar to any
query in the cache then the server returns the response from the cache.
Otherwise, a model multiplexer is used to select the most suitable LLM for the
query.

Although these techniques can handle the semantic similarity among the queries
and can provide a single concise response, they raise privacy concerns as they
store user queries on an external server. These techniques are static and
unable to adapt to the behavior of each user. Furthermore, an end user will
still be charged for the query even if the query is served from the cache.
Thus, we need a user-centered semantic cache that can run on the user side,
which can benefit the user in terms of privacy, cost, and latency. Such a
cache should be able to detect the semantic similarity among the queries and
should be able to adapt to the behavior of each user in a privacy preserving
manner. MeanCache provides the aforementioned benefits without violating the
user’s privacy.

##  7\. Conclusion

MeanCache is the first user-centric semantic cache for Language Model (LLM)
based web services, such as ChatGPT. In MeanCache, clients train the global
embedding model using federated learning on their local data, while preserving
user privacy. The global model formed after the aggregation generates high-
quality embeddings for semantic matching. When a new user’s query is
duplicated, MeanCache semantically matches the new query with the user’s local
cache and returns the most relevant results. This process reduces the
computational cost of the LLM service, improves bandwidth and latency, and
conserves the user’s query quota for the LLM service. Despite compressing
embeddings and saving 83% of storage space, MeanCache outperforms the existing
baseline semantic cache (GPTCache). With its distribution cache design,
MeanCache offers pathways to reduce one-third of the LLM query inference costs
related to semantically similar queries.

## References

  * (1)
  * arc ([n.d.]) [n.d.].  Arc Max is the popular browser’s new suite of AI tools - The Verge.  https://www.theverge.com/2023/10/3/23898907/arc-max-ai-browser-mac-ios.  (Accessed on 01/19/2024).
  * Dis ([n.d.]) [n.d.].  DiskCache: Disk Backed Cache — DiskCache 5.6.1 documentation.  https://grantjenks.com/docs/diskcache/.  (Accessed on 04/01/2024).
  * gbo ([n.d.]) [n.d.].  Federated Learning: Collaborative Machine Learning without Centralized Training Data – Google Research Blog.  https://blog.research.google/2017/04/federated-learning-collaborative.html.  (Accessed on 04/01/2024).
  * bar ([n.d.]) [n.d.].  Google AI updates: Bard and new AI features in Search.  https://blog.google/technology/ai/bard-google-ai-search-updates/.  (Accessed on 01/18/2024).
  * dat ([n.d.]) [n.d.].  GPTCache/examples/benchmark at main · zilliztech/GPTCache.  https://github.com/zilliztech/GPTCache/tree/main/examples/benchmark.  (Accessed on 03/04/2024).
  * cha ([n.d.]) [n.d.].  Introducing ChatGPT.  https://openai.com/blog/chatgpt.  (Accessed on 01/18/2024).
  * cla ([n.d.]) [n.d.].  Introducing Claude 2.1 \ Anthropic.  https://www.anthropic.com/news/claude-2-1.  (Accessed on 01/18/2024).
  * rab ([n.d.]) [n.d.].  Learning human actions on computer applications.  https://www.rabbit.tech/research.  (Accessed on 01/19/2024).
  * bin ([n.d.]) [n.d.].  Microsoft Edge and Bing Users Engage in Over 1.9 Billion Copilot Chats in 2023.  https://www.msn.com/en-us/money/other/microsoft-edge-and-bing-users-engage-in-over-19-billion-copilot-chats-in-2023/ar-AA1mmrxZ.  (Accessed on 01/22/2024).
  * ope ([n.d.]) [n.d.].  OpenAI Pricing.  https://openai.com/pricing.  (Accessed on 01/19/2024).
  * per ([n.d.]a) [n.d.]a.  Perplexity Pro.  https://www.perplexity.ai/pro.  (Accessed on 03/01/2024).
  * Siz ([n.d.]) [n.d.].  Sizing Guide - NVIDIA Docs.  https://docs.nvidia.com/ai-enterprise/workflows-generative-ai/0.1.0/sizing-guide.html.  (Accessed on 01/25/2024).
  * Use ([n.d.]) [n.d.].  [User] Embedding doesn’t seem to work? · Issue #899 · ggerganov/llama.cpp.  https://github.com/ggerganov/llama.cpp/issues/899.  (Accessed on 01/18/2024).
  * per ([n.d.]b) [n.d.]b.  What is Perplexity?  https://blog.perplexity.ai/faq/what-is-perplexity.  (Accessed on 01/19/2024).
  * zil ([n.d.]) [n.d.].  zilliztech/GPTCache: Semantic cache for LLMs. Fully integrated with LangChain and llama_index.  https://github.com/zilliztech/gptcache.  (Accessed on 03/03/2024).
  * Avdiukhin and Kasiviswanathan (2021) Dmitrii Avdiukhin and Shiva Kasiviswanathan. 2021.  Federated learning under arbitrary communication patterns. In _International Conference on Machine Learning_. PMLR, 425–435.
  * Baeza-Yates et al. (2007) Ricardo Baeza-Yates, Aristides Gionis, Flavio Junqueira, Vanessa Murdock, Vassilis Plachouras, and Fabrizio Silvestri. 2007.  The impact of caching on search engines. In _Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval_. 183–190.
  * Baeza-Yates and Saint-Jean (2003) Ricardo Baeza-Yates and Felipe Saint-Jean. 2003.  A three level search engine index based in query log distribution. In _String Processing and Information Retrieval: 10th International Symposium, SPIRE 2003, Manaus, Brazil, October 8-10, 2003. Proceedings 10_. Springer, 56–65.
  * Bang (2023) Fu Bang. 2023.  GPTCache: An Open-Source Semantic Cache for LLM Applications Enabling Faster Answers and Cost Savings. In _Proceedings of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 2023)_. 212–218.
  * Beutel et al. (2020) Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marques, Yan Gao, Lorenzo Sani, Hei Li Kwing, Titouan Parcollet, Pedro PB de Gusmão, and Nicholas D Lane. 2020.  Flower: A Friendly Federated Learning Research Framework.  _arXiv preprint arXiv:2007.14390_ (2020).
  * Brin and Page (1998) Sergey Brin and Lawrence Page. 1998.  The anatomy of a large-scale hypertextual web search engine.  _Computer networks and ISDN systems_ 30, 1-7 (1998), 107–117.
  * Du and Kaelbling (2024) Yilun Du and Leslie Kaelbling. 2024.  Compositional Generative Modeling: A Single Model is Not All You Need.  _arXiv preprint arXiv:2402.01103_ (2024).
  * Fagni et al. (2006) Tiziano Fagni, Raffaele Perego, Fabrizio Silvestri, and Salvatore Orlando. 2006.  Boosting the performance of web search engines: Caching and prefetching query results by exploiting historical usage data.  _ACM Transactions on Information Systems (TOIS)_ 24, 1 (2006), 51–78.
  * Frantar et al. (2023) Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. 2023.  OPTQ: Accurate Quantization for Generative Pre-trained Transformers. In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.  https://openreview.net/pdf?id=tcbBPnfwxS
  * Henderson et al. (2017) Matthew Henderson, Rami Al-Rfou, Brian Strope, Yun-Hsuan Sung, László Lukács, Ruiqi Guo, Sanjiv Kumar, Balint Miklos, and Ray Kurzweil. 2017.  Efficient natural language response suggestion for smart reply.  _arXiv preprint arXiv:1705.00652_ (2017).
  * Hotelling (1933) Harold Hotelling. 1933.  Analysis of a complex of statistical variables into principal components.  _Journal of educational psychology_ 24, 6 (1933), 417.
  * Jolliffe and Cadima (2016) Ian T Jolliffe and Jorge Cadima. 2016.  Principal component analysis: a review and recent developments.  _Philosophical transactions of the royal society A: Mathematical, Physical and Engineering Sciences_ 374, 2065 (2016), 20150202.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense Passage Retrieval for Open-Domain Question Answering. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association for Computational Linguistics, Online, 6769–6781.  https://doi.org/10.18653/v1/2020.emnlp-main.550
  * Lan et al. (2019) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019.  ALBERT: A Lite BERT for Self-supervised Learning of Language Representations.  _CoRR_ abs/1909.11942 (2019).  arXiv:1909.11942 http://arxiv.org/abs/1909.11942
  * Lempel and Moran (2003) Ronny Lempel and Shlomo Moran. 2003.  Predictive caching and prefetching of query results in search engines. In _Proceedings of the 12th international conference on World Wide Web_. 19–28.
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. 2020.  Federated optimization in heterogeneous networks.  _Proceedings of Machine learning and systems_ 2 (2020), 429–450.
  * Long and Suel (2005) Xiaohui Long and Torsten Suel. 2005.  Three-level caching for efficient query processing in large web search engines. In _Proceedings of the 14th international conference on World Wide Web_. 257–266.
  * Ma et al. (2024) Shuming Ma, Hongyu Wang, Lingxiao Ma, Lei Wang, Wenhui Wang, Shaohan Huang, Li Dong, Ruiping Wang, Jilong Xue, and Furu Wei. 2024.  The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits.  _arXiv preprint arXiv:2402.17764_ (2024).
  * Marin et al. (2010) Mauricio Marin, Veronica Gil-Costa, and Carlos Gomez-Pantoja. 2010.  New caching techniques for web search engines. In _Proceedings of the 19th ACM international symposium on high performance distributed computing_. 215–226.
  * Markatos (2001) Evangelos P. Markatos. 2001.  On caching search engine query results.  _Computer Communications_ 24, 2 (2001), 137–143.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017.  Communication-efficient learning of deep networks from decentralized data. In _Artificial intelligence and statistics_. PMLR, 1273–1282.
  * Ni et al. (2022) Jianmo Ni, Gustavo Hernandez Abrego, Noah Constant, Ji Ma, Keith Hall, Daniel Cer, and Yinfei Yang. 2022.  Sentence-T5: Scalable Sentence Encoders from Pre-trained Text-to-Text Models. In _Findings of the Association for Computational Linguistics: ACL 2022_ , Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (Eds.). Association for Computational Linguistics, Dublin, Ireland, 1864–1874.  https://doi.org/10.18653/v1/2022.findings-acl.146
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ 35 (2022), 27730–27744.
  * Pearson (1901) Karl Pearson. 1901.  LIII. On lines and planes of closest fit to systems of points in space.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ 2, 11 (1901), 559–572.  https://doi.org/10.1080/14786440109462720 arXiv:https://doi.org/10.1080/14786440109462720
  * Penedo et al. (2024) Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Hamza Alobeidli, Alessandro Cappelli, Baptiste Pannier, Ebtesam Almazrouei, and Julien Launay. 2024.  The refinedweb dataset for falcon llm: Outperforming curated corpora with web data only.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Podlipnig and Böszörmenyi (2003) Stefan Podlipnig and Laszlo Böszörmenyi. 2003.  A survey of web cache replacement strategies.  _ACM Computing Surveys (CSUR)_ 35, 4 (2003), 374–398.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, Hong Kong, China, 3982–3992.  https://doi.org/10.18653/v1/D19-1410
  * Sachdeva et al. (2024) Noveen Sachdeva, Benjamin Coleman, Wang-Cheng Kang, Jianmo Ni, Lichan Hong, Ed H Chi, James Caverlee, Julian McAuley, and Derek Zhiyuan Cheng. 2024.  How to Train Data-Efficient LLMs.  _arXiv preprint arXiv:2402.09668_ (2024).
  * Saraiva et al. (2001) Patricia Correia Saraiva, Edleno Silva de Moura, Nivio Ziviani, Wagner Meira, Rodrigo Fonseca, and Berthier Ribeiro-Neto. 2001.  Rank-preserving two-level caching for scalable search engines. In _Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval_. 51–58.
  * Song et al. (2020) Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. 2020.  Mpnet: Masked and permuted pre-training for language understanding.  _Advances in Neural Information Processing Systems_ 33 (2020), 16857–16867.
  * Strubell et al. (2019) Emma Strubell, Ananya Ganesh, and Andrew McCallum. 2019.  Energy and Policy Considerations for Deep Learning in NLP. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. 3645–3650.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023\.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ (2023).
  * Tseng et al. (2024) Albert Tseng, Jerry Chee, Qingyao Sun, Volodymyr Kuleshov, and Christopher De Sa. 2024.  QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks.  _arXiv preprint arXiv:2402.04396_ (2024).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wang et al. (2023) Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Huaijie Wang, Lingxiao Ma, Fan Yang, Ruiping Wang, Yi Wu, and Furu Wei. 2023.  Bitnet: Scaling 1-bit transformers for large language models.  _arXiv preprint arXiv:2310.11453_ (2023).
  * Wang et al. (2020b) Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. 2020b.  Federated Learning with Matched Averaging. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=BkluqlSFDS
  * Wang et al. (2020a) Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. 2020a.  Tackling the objective inconsistency problem in heterogeneous federated optimization.  _Advances in neural information processing systems_ 33 (2020), 7611–7623.
  * Xie and O’Hallaron (2002) Yinglian Xie and David O’Hallaron. 2002.  Locality in search engine queries and its implications for caching. In _Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies_ , Vol. 3. IEEE, 1238–1247.
  * Zhang et al. (2008) Jiangong Zhang, Xiaohui Long, and Torsten Suel. 2008.  Performance of compressed inverted list caching in search engines. In _Proceedings of the 17th international conference on World Wide Web_. 387–396.
  * Zhu et al. (2023) Banghua Zhu, Ying Sheng, Lianmin Zheng, Clark Barrett, Michael Jordan, and Jiantao Jiao. 2023.  Towards Optimal Caching and Model Selection for Large Model Inference. In _Thirty-seventh Conference on Neural Information Processing Systems_.  https://openreview.net/forum?id=gd20oaZqqF