A core executes memory instructions. A memory management unit (MMU) coupled to the core includes a first cache that stores a plurality of final mappings of a hierarchical page table, a page table walker that traverses levels of the page table to provide intermediate results associated with respective levels for determining the final mappings, and a second cache that stores a limited number of intermediate results provided by the page table walker. The MMU compares a portion of the first virtual address to portions of entries in the second cache, in response to a request from the core to invalidate a first virtual address, based on a match criterion that depends on the level associated with each intermediate result stored in an entry in the second cache, and removes any entries in the second cache that satisfy the match criterion.