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 stores a subset of tags stored by the tag storage. Where 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. In another embodiment, 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. A replacement table is maintained for use in evicting or replacing cached tags based on an indicated level of activity for a set of the cache of cache tags.