Those guarantees are also what makes the algorithm exploitable and inflexible to handle unknown or adversary workloads. Your LRU example suffers in scan / loop / zigzag patterns, which the author's policies do poorly at as well. They target CDNs workloads where that can be ignored there due to its scale, but that is not a generalizable assumption for other workloads where it more common like databases, search, and analytics.

If the algorithm is known and accepts user facing requests then it becomes a target. A client can use the network speed of a dialup modem to bring down a modern server simply by crafting a request pattern to exploit hash flooding. This is why you generally want some injected noise, adaptivity, and use an algorithm that offers robustly good hit rates. A specialized policy that is superior in a narrow set of workload is still very useful when targeted at an expensive problem, but that's a design assumption that few can reasonably make.

Hash attacks work because hash tables are pseudo random algorithms, whose worst case performance is linear, and whose average case constant time performance depends on keys being distributed evenly, which depends on luck. A different kind of container, like something with a worst case that is logarithmic and doesn't depend on luck is immune to that kind of attack.

It is only these kinds of pseudo-randomized algorithms that have hidden degenerate cases that need to be randomized for protection.

More generally, software that has some hidden severe problems for certain inputs, such that the degenerate choice of inputs depends on incidental factors, benefits from having those incidental factors perturbed randomly (like a form of seeding) so that attackers cannot identify those inputs or use the same ones consistently.

ASLR is like this. A bug-free program (or at least one free of memory errors) does not benefit from address space layout randomization, only one that has bugs. The successful exploitation of those bugs for gaining unauthorized access depends on incidental pseudo-random factors like in what layout the misused objects are allocated.

I believe there's no need for a cache to have a behavior whereby a sequence of accesses that shows good locality its able to get a frequently accessed item to be given poor cache residency, while another item that is just as frequently accessed is given good residency. On the other hand kind of inputs that trigger poor hit rates in a cache are hardly random. To trigger a poor hit rate in almost any cache algorithm whatsoever, all you have to do is access a sequence of items in which nothing appears twice. Only an algorithm with prefetch that happens to predict that sequence will do well or at least somewhat well.