Many areas of computer performance analysis require detailed traces of events that occur during a program's execution. Collecting traces is expensive. The additional code required to record events greatly slows a program's execution. In addition, the resulting trace files can grow unmanageably large. This paper describes a technique called abstract execution that alleviates both problems. Abstract execution records a small set of events during the traced program's execution. These events serve as input to an abstract version of the program that generates a full trace by re-executing selected portions of the original program. This process greatly reduces both the cost of tracing the original program and the size of the trace files. The cost of regenerating a trace is insignificant in comparison to the cost of applications that use it. This paper also describes a system called AE that implements Abstract Execution. The paper contains measurements that demonstrate that AE can efficiently trace large programs.