Feature request: Per-head KV-cache and eviction based on attention scores

[axeber01]

KV-cache compression techniques can be used for removing unimportant keys and values from the cache, which enables longer context lengths without increasing memory usage. Some popular methods for this include H2O and SnapKV. Both methods use the attention scores to rank which KV-entries are important for decoding the next token. This is different from sliding window attention, which just keeps recent tokens in memory.

Implementing this in llama.cpp could be done by evicting one token when the KV-cache is full, in order to enable a "streaming" KV-cache. Roughly speaking, the following would need to be done at each decoding step:

1. If the KV-cache is full, return lists of attention scores (one list per attention head) from last few queries w.r.t. all previous token and average over the queries.
2. For each attention head, find the KV-cache entries corresponding to the smallest score.
3. For each attention head, evict the KV-cache entry from memory in order to free a slot for the next token.
4. Decode the next token and store its KV-cache in the free slots.

One problem with the current KV-cache implementation is that there is only one global list of occupied KV-cache entries, which is assumed to be the same for all attention heads. Hence, functions like llama_kv_cache_unified::seq_rm operates on all attention heads. In order to support advanced KV-cache compression methods, it would be better to have a separate KV-cache for each head.