Embodiments are directed to efficiently determining which cache entries are to be evicted from memory and to incorporating a probability of reuse estimation in a cache entry eviction determination. A computer system with multiple different caches accesses a cache entry. The computer system determines an entry cost value for the accessed cache entry. The entry cost value indicates an amount of time the computer system is slowed down by to load the cache entry into cache memory. The computer system determines an opportunity cost value for the computing system caches. The opportunity cost value indicates an amount of time by which the computer system is slowed down while performing other operations that could have used the cache entry's cache memory space. Upon determining that the entry cost value is lower than the opportunity cost value, the computer system probabilistically evicts the cache entry from cache memory.