Techniques and mechanism to provide a cache of cache tags in determining an access to cached data. In an embodiment, a tag storage stores a first set including tags associated with respective data locations of a cache memory. A cache of cache tags store a subset of tags stored by the tag storage. In response to any determination that a tag of the first set is to be stored to the cache of cache tags, all tags of the first set are stored to the first portion. Any storage of tags of the first set to the cache of cache tags includes storage of the tags of the first set to only a first portion of the cache of cache tags. In another embodiment, a replacement table is maintained for use in determining, based on an indicated level of activity for a set of the cache of cache tags, whether the set is to be selected for eviction and replacement of cached tags.