https://9vx.org/post/on-window-tinylfu/
The core trick is to use some kind of Bloom-filter-style structure to keep approximate counts of accesses. Caffeine uses a count-min sketch, but you could also use a counting Bloom filter, and these are really just two members of a family of very similar things. The counts are occasionally halved, so they are really a sort of decaying average, allowing for changes in access pattern over time.
There's a minor trick of using a simple Bloom filter (the post says "single-bit minimum-increment counting Bloom filter", but that is just a Bloom filter, isn't it?) as a 'doorkeeper', so you don't bother tracking frequency for objects until they are accessed for a second time. This helps if you have a long tail of objects which are only accessed once, because it means the main frequency counter can focus on a small subset of objects, and so be more accurate.
The actual cache is split into two parts. New objects are added to the first part, which is managed by simple LRU. When objects are evicted from the LRU queue, their access frequency is examined, and if it is high enough, the object is added to the second part. The use of frequency like this is called a cache admission policy.
There are a lot of details I don't understand. Mostly to do with how a cache admission policy is used in a two-part cache, rather than anything to do with Window-TinyLFU.
How is the second part of the cache managed? LRU? Or do you evict the object with the lowest frequency?
What is the frequency threshold for adding something to the second part?
Are objects added to the first part if they have only just been added to the doorkeeper? Or only if they were already known to the doorkeeper? Does the doorkeeper also get reset occasionally?
What are the relative sizes of the first and second parts? Do they change?
Is an object ever added directly to the second part? You might have an object with high historical frequency, but which has been evicted because it wasn't used recently.
I couldn't find a good general overview of cache admission policies.