A method for updating replacement policy data for a cache that stores translations from a first address space to a second address space, where the translations are associated with at least two different page sizes and least-recently-used data is associated with each page size, the cache including a plurality of sets, each set including a plurality of ways divided into a plurality of groups of ways, where each group of ways includes least-recently-used data for at least two different page sizes, the method comprising: detecting an update to a first cache entry of the cache, the first cache entry of the cache being associated with a first set of the plurality of sets and with a first group of ways (316) of the plurality of groups of ways; responsive to the update to the first cache entry, modifying a first replacement policy data entry corresponding to the first cache entry and the first group of ways (316), the first replacement policy data entry being associated with a first level of generality, the modifying causing the first replacement policy data entry to indicate that the first cache entry of the cache is not least recently used for the first level of generality; responsive to the modifying the first replacement policy data entry, identifying a second replacement policy data entry associated with a second level of generality that is more specific than the first level of generality, the second replacement policy data entry also being associated with the first cache entry and with the first group of ways (316); and modifying the second replacement policy data entry to also indicate that the first cache entry of the cache is not least recently used for the second level of generality, wherein the level of generality refers to the portion of an address space covered by a cache entry, wherein the first level of generality corresponds to translations for a larger page size and the second level of generality corresponds to translations for a smaller page size. detecting an update to a first cache entry of the cache, the first cache entry of the cache being associated with a first set of the plurality of sets and with a first group of ways (316) of the plurality of groups of ways; responsive to the update to the first cache entry, modifying a first replacement policy data entry corresponding to the first cache entry and the first group of ways (316), the first replacement policy data entry being associated with a first level of generality, the modifying causing the first replacement policy data entry to indicate that the first cache entry of the cache is not least recently used for the first level of generality; responsive to the modifying the first replacement policy data entry, identifying a second replacement policy data entry associated with a second level of generality that is more specific than the first level of generality, the second replacement policy data entry also being associated with the first cache entry and with the first group of ways (316); and modifying the second replacement policy data entry to also indicate that the first cache entry of the cache is not least recently used for the second level of generality, wherein the level of generality refers to the portion of an address space covered by a cache entry, wherein the first level of generality corresponds to translations for a larger page size and the second level of generality corresponds to translations for a smaller page size.