A set-associative cache memory includes a plurality of congruence classes each including multiple entries for storing cache lines of data. A respective one of a plurality of counters is maintained for each cache line stored in the multiple entries. In response to a memory access request, the cache memory selects a victim cache line stored in a particular entry of a particular congruence class for eviction from the cache memory by reference to at least a counter value of the victim cache line. The cache memory also receives a new cache line of data for insertion into the particular entry and an indication of a distance from the cache memory to a data source from which the cache memory received the new cache line. The cache memory installs the new cache line in the particular entry and sets an initial counter value of the counter for the new cache line based on the received indication of the distance.