An apparatus includes a data array and control logic. The control logic is coupled to the data array and adapted to store at least one trace segment of instructions into the data array. The control logic allows the instructions of the trace segment to be sequentially retrieved beginning with a selected instruction. The selected instruction is offset from the first instruction of the trace segment. A method for caching instructions includes storing a first plurality of instructions in a first trace segment. A selected instruction of the first plurality of instructions is identified within the first trace segment. The selected instruction is offset from the first instruction of the first trace segment. The offset information related to the position of the selected instruction within the first trace segment is stored. A method for retrieving cached instructions, wherein the cached instructions are stored in a trace segment and the trace segment has a head instruction, includes determining a linear address related to a selected instruction to be retrieved. An entry point into the trace segment corresponding to the linear address is identified. The entry point is offset from the head instruction. The selected instruction is retrieved from the entry point within the identified trace segment.