One embodiment of the present invention sets forth a system and method for supporting high-throughput virtual to physical address translation using compressed TLB cache lines with variable address range coverage. The amount of memory covered by a TLB cache line depends on the page size and page table entry (PTE) compression level. When a TLB miss occurs, a cache line is allocated with an assumed address range that may be larger or smaller than the address range of the PTE data actually returned. Subsequent requests that hit a cache line with a fill pending are queued until the fill completes. When the fill completes, the cache line's address range is set to the address range of the PTE data returned. Queued requests are replayed and any that fall outside the actual address range are reissued, potentially generating additional misses and fills.