Auditing Prompt Caching in Language Model APIs

Thank you for the detailed and thoughtful review! We address the main points below.

1. Request routing strategies

We can show that our experimental results are valid regardless of routing strategies. Under the null hypothesis $H_0$ of no caching, request-routing will be independent of whether the prompt was recently sent. Therefore, since the distribution of prompts $\mathcal{P}$ is the same in the cache hit and cache miss procedures (these procedures differ only in whether the attacker’s prompt was previously sent), a non-caching request-routing strategy will perform the same on the distributions of the cache hit and cache miss procedures. Therefore, $\mathcal{D}\_\text{hit} = \mathcal{D}\_\text{miss}$ still holds under the null hypothesis $H_0$, so the statistical audit is valid.

If the API provider is performing caching, then different routing strategies may make it easier or harder to detect caching, but the audit still outputs valid p-values with respect to the null hypothesis. For example, if prompts are intentionally routed to a server where the prompt is already cached, it will be easy to produce and detect cache hits using NumVictimRequests = 1. On the other hand, if prompts are randomly routed, more victim requests may be needed to detect caching. Multiple victim requests may be needed to cache the prompt in enough servers for the attacker’s prompt to have a sufficient probability of producing a cache hit.

2. Bonferroni correction

While the Bonferroni correction is indeed conservative, it is simple and straightforward, and we only use a maximum correction factor of 6. We are confident that performing Bonferroni correction did not cause our audits to miss any real caching because the p-values for the APIs in which we did not detect caching were orders of magnitude larger than the significance level of $\alpha = 10^{-8}$. As shown in Table 3 in the appendix (page 14), in the first level of audits, all non-significant p-values were larger than 0.1, and most significant p-values were many orders of magnitude smaller than $10^{-8}$.

3. Other factors that could cause similar caching phenomena

For the purposes of our audit, the specific caching mechanism is unimportant, as long as it follows the simple properties we describe (page 2, line 70, right column). The potential privacy leakage does not depend on what specific mechanisms cause timing differences between cached and non-cached prompts; the leakage occurs simply because there are timing differences. Even if the caching phenomena has strange causes—e.g., the server intentionally delays responses for new prompts but immediately returns responses for previously seen prompts—our audits can detect it, and the timing differences lead to potential privacy leakage.

Thank you for the detailed and thoughtful review! We address the main points below.

Practical exploitability

We agree that practical exploitations of prompt cache sharing are challenging. The attacker needs to guess a long prompt prefix to check if it is cached, as you described. As we discussed in Section 4.4: Difficulty of Prompt Extraction Attacks (page 7, line 350, left column), a natural idea is to use breadth-first search to try to extract cached prompts token-by-token. However, we were unable to execute practical prompt extraction attacks due to several challenges, such as the difficulty of making repeated measurements. Accordingly, we emphasized that the privacy leakage is only potential throughout the paper.

However, we believe that even potential privacy leakage due to global cache sharing is a cause for concern, especially as LLM APIs are being used by increasingly many users and companies for increasingly many tasks, which may include sensitive data. In addition, future work may overcome or eliminate the practical challenges we discussed.

Following our responsible disclosure, several API providers made changes to mitigate the potential privacy leakage. OpenAI, Microsoft Azure, and Fireworks AI worked quickly to mitigate vulnerabilities by stopping global cache sharing. (Note that this is not an exhaustive list of all companies that implemented fixes.) Fireworks AI also added detailed documentation about prompt caching and data privacy, as well as an option to opt-out of caching for a particular prompt. The mitigations implemented by these companies illustrate the real-world impact of our findings.

Also, we found that prompt caching can leak information about model architecture, which is of practical importance given the competitiveness and secrecy of the modern LLM landscape. Namely, we found evidence that OpenAI’s text-embedding-3-small model has a decoder-only Transformer architecture, which was previously not publicly known.

Thank you for the detailed and thoughtful review! We address the questions below.

Speculative decoding

This is an interesting point. We have thought about this, and we believe that speculative decoding should not impact the TTFT when we set the max response tokens to 1. First, we note that speculative decoding is not beneficial when only 1 response token is generated. Speculative decoding is only beneficial when the smaller draft model can generate multiple tokens, and the larger target model can “check” these tokens in parallel. Since the larger target model has to make a forward pass regardless, when generating only 1 token, it is faster to skip the smaller draft model.

If speculative decoding is nevertheless enabled when generating only 1 token, we believe that it would not cause a noticeable variation in TTFT across different prompts (of the same length). In this scenario, the smaller draft model would generate 1 token, then the larger target model would make a forward pass and either accept or reject the draft token. The only timing difference between accepting and rejecting would come from resampling a token from the target distribution, which is negligible compared to the time for the forward pass.

Note that when the LLM generates full responses (number of tokens $\gg 1$), speculative decoding causes data-dependent timing variations that may be exploited. As mentioned in the related works (page 8, line 404, right column), Carlini & Nasr (2024) and Wei et al. (2024) exploit speculative decoding to extract encrypted and streamed LLM responses by measuring delays between packets.

Intentionally delaying responses

Yes, we believe that intentionally delaying the response times for cache hits so that they look like cache misses is a viable mitigation for providers. We briefly touch upon this in the paper (page 8, line 410, left column). This eliminates the benefits of prompt caching for users, but API providers could still benefit, as cached prompts require less GPU processing time.

Providers would need to be somewhat careful about implementing this, as simply waiting a random amount of time may not adequately disguise cache hits. One better strategy is to first compute distributions of the server-side TTFT for cache misses for various prompt lengths. Then, when a cache hit occurs, the server would sample a TTFT from the cache miss distribution corresponding to the given prompt length, and delay the response until that TTFT has elapsed (if the actual TTFT has already exceeded the sampled TTFT, then send the response immediately). This way, the distribution of times for cache hits and cache misses should approximately match each other.

Thank you for the detailed and thoughtful review! We address the main points below.

Random prompts produce cache misses

We assume that random prompts produce cache misses because it is exceedingly unlikely that a random prompt shares a prefix of noticeable length with any cached prompts. In the worst case, assume that all other users are sending random prompts with the same structure as in the paper, i.e., random letters separated by spaces. (In reality, very few, if any, other users will be sending such prompts.) As mentioned in the paper (page 4, line 196, left column), the probability that two of these random prompts share a prefix of 15 tokens or longer is less than $10^{-25}$. Assume that the server can store 1 billion prompts in its cache (in reality, the true cache capacity is likely much smaller). Then, using a union bound, the probability that a random prompt shares a prefix of 15 tokens or longer with any cached prompt is less than $10^{-25} \times 10^{9} = 10^{-16}$. We send 250 random prompts for cache miss timings in each audit, so using another union bound, the probability that any of these prompts produce cache hits is less than $10^{-12}$.

We are also able to empirically confirm that random prompts produce cache misses. Some API providers have officially released prompt caching features, such as OpenAI and Anthropic. As part of these features, each API response returns the number of cached prompt tokens. Using this information, we ran some simple tests that empirically confirm that the random prompts used in our experiments consistently produce cache misses in real-world API usage scenarios.

Random prompts versus natural language

We used random alphabetic prompts instead of natural language prompts for a few reasons. We can assume that random prompts reliably produce cache misses, as discussed above. However, there is a greater chance that prefixes of realistic natural language prompts have already been sent by other users, making it harder to reliably measure cache misses. In addition, it is more difficult to construct a clean, well-defined distribution of natural language prompts containing exactly PromptLength tokens, compared to using random prompts. This distribution is important for our rigorous statistical hypothesis testing framework.

As mentioned in the paper (page 6, line 302, right column), our audits detected the exact level of cache sharing stated by OpenAI and Anthropic for their chat models (per-organization sharing, but not global sharing). This demonstrates the efficacy of our audits on real-world APIs, even if the random prompts do not necessarily reflect realistic workflows.

Real-world exploitation and mitigations

As discussed in Section 4.4: Difficulty of Prompt Extraction Attacks (line 350, page 7, left column), we believe that real-world exploitation of these vulnerabilities is challenging. However, we believe that even potential privacy leakage due to global cache sharing is a cause for concern, especially as LLM APIs are being used by increasingly many users and companies for increasingly many tasks, which may include sensitive data. In addition, future work may overcome or eliminate the practical challenges we discussed.

To mitigate these vulnerabilities, we believe that API providers should disable global cache sharing and disclose the level of cache sharing. Following our responsible disclosure, several API providers followed this approach. OpenAI, Microsoft Azure, and Fireworks AI worked quickly to mitigate vulnerabilities by stopping global cache sharing. (Note that this is not an exhaustive list of all companies that implemented fixes.) Fireworks AI also added detailed documentation about prompt caching and data privacy, as well as an option to opt-out of caching for a particular prompt. The mitigations implemented by these companies illustrate the real-world impact of our findings.

Also, we found that prompt caching can leak information about model architecture, which is of practical importance given the competitiveness and secrecy of the modern LLM landscape. Namely, we found evidence that OpenAI’s text-embedding-3-small model has a decoder-only Transformer architecture, which was previously not publicly known.

Ethics review

As discussed in the Impact Statement (page 9, line 440, left column), to mitigate real-world harms arising from our research, we followed standard responsible disclosure practices for security vulnerabilities. In October 2024, we disclosed our audit results with each API provider in which we detected prompt caching. We gave providers 60 days to address the vulnerabilities before publicly releasing or submitting our findings, and the actual time elapsed ended up being longer.