In a cache which writes new data over less recently used data, methods and apparatus which dispense with the convention of marking new cache data as most recently used. Instead, non-referenced data is marked as less recently used when it is written into a cache, and referenced data is marked as more recently used when it is written into a cache. Referenced data may correspond to fetch data, and non-referenced data may correspond to prefetch data. Upon fetch of a data value from the cache, its use status may be updated to more recently used. The methods and apparatus have the affect of preserving (n-1)/n of a cache's entries for the storage of fetch data, while limiting the storage of prefetch data to 1/n of a cache's entries. Pollution which results from unneeded prefetch data is therefore limited to 1/n of the cache. In reality, however, pollution from unneeded prefetch data will be significantly less, as many prefetch data values will ultimately be fetched prior to their overwrite with new data, and upon their fetch, their use status can be upgraded to most recently used, thus ensuring their continued maintenance in the cache.