Disclosed herein are exemplary techniques for generating trace information streams to facilitate the reconstruction of the instruction execution history of a processing device for a given time period. The linear instruction pointers or other representations of the instructions executed by a processing device are output as a trace information stream. When one or more translation lookaside buffers (TLBs) used by the processing device are modified by the addition of a new linear-to-physical translation and/or the eviction of an old linear-to-physical translation, a representation of the newly added translation entry, or, alternatively the evicted translation entry, is inserted into the trace information stream. In this manner, the context for the address mapping of the instruction pointers of the trace information stream is provided and, consequently, the execution instruction history of the processing device may be more fully reconstructed.