A cache hierarchy and a method of operating the cache hierarchy are disclosed. The cache hierarchy comprises a first cache level comprising an instruction cache, and predecoding circuitry to perform a predecoding operation on instructions having a first encoding format retrieved from memory to generate predecoded instructions having a second encoding format for storage in the instruction cache. The cache hierarchy further comprises a second cache level comprising a cache and the first cache level instruction cache comprises cache control circuitry to control an eviction procedure for the instruction cache in which a predecoded instruction having the second encoding format which is evicted from the instruction cache is stored at the second cache level in the second encoding format. This enables the latency and power cost of the predecoding operation to be avoided when the predecoded instruction is then retrieved from the second cache level for storage in the first level instruction cache again.