This should be doable. On each access append the key to a list of recent keys which would also not be terrible expensive if the keys are much smaller than the values. Ever so often you can then look through the list of recent keys and analyze the access patterns and maybe change the eviction algorithm.

But I think this might also not be too helpful overall. I think in many cases there is an obvious choice depending on how and for what the cache is used. And then there are caches that have more unpredictable access patterns, a file system cache might be a good candidate, experiencing the access patterns of all the different applications.

In that case there is probably no best choice as several applications with different access patterns concurrently hit the cache. Or if there is a best choice, it might change very quickly as different applications or components of applications execute. In such a scenario it seems more promising to me to try to categorize the access patterns on a per source basis and treating them accordingly instead of trying to find one best policy for all sources combined.

On the other hand something like this might quickly become prohibitively expensive.