🚀 The feature, motivation and pitch

Key Idea:

For a prefix cache of size size, and access frequency freq, define:

Retention Benefit of a prefix (over time T): T * freq * compute_cost.

where compute_cost = cost_factor * cost_func(size)

cost_func = size^alpha

alpha is 2 and may be smaller with implementations such as FlashAttention.

We should evict a prefix if its retention benefit is smallest, that is to say it has the minimum freq * compute_cost. In practice, T and cost_factor take no effect because we just use the benefit for comparing, so we can ignore it.

Instead of evicting the Least Recently Used prefix, with this policy, the compute cost we save is freq * compute_cost - another_freq * another_compute_cost. Where another_freq and another_compute_cost is the access frequency and compute cost of prefix cache selected by LRU.

To compute the retention benefit, we need the fisrt generate time and total access count for each prefix cache. We can maintain these information for each prefix cache.

If this is valuable, I am happy to write further design and implement this feature.

If I am missing anything, please fell free to tell me. Hope to get your feedback and having further discussion~

Alternatives

No response

Additional context

There is a feature request and where share some background and motivations: #23083 (pin prefix cache). I think these two feature is not conflict, and users could choose which policy to use upon their own situation.

Before submitting a new issue...

• Make sure you already searched for relevant issues, and asked the chatbot living at the bottom right corner of the documentation page, which can answer lots of frequently asked questions.