1. A method for managing a variable caching structure for managing storage for a processor, comprising: using a multi-way tag array to store a plurality of pointers for a corresponding plurality of different size groups of physical storage of a storage stack, wherein the pointers indicate guest addresses that have corresponding converted native addresses stored within the storage stack; allocating a group of storage blocks of the storage stack, wherein the size of the allocation is in accordance with a corresponding size of one of the plurality of different size groups; storing a plurality of blocks of converted native instructions onto the storage stack in accordance with the allocating of group of storage blocks; receiving a subsequent request for a guest address at the multi-way tag array; indexing the multi-way tag array to determine whether there exists a pointer in the multi-way tag array that corresponds to the index; upon a hit on the tag, accessing a corresponding entry to retrieve a pointer that indicates where in the storage stack a corresponding group of storage blocks of converted native instructions reside; and fetching the converted native instructions from the storage stack for execution.