Preprocessing audio data to generate parameters associated with time scaling reduces the processing power required for real-time time scaling of the audio data. An augmented audio data structure includes the audio data and the parameters. The parameters for a frame of the audio data can identify best match blocks for time scaling or represent a plot of offset versus time scale that can be interpolated to determine an offset. The real-time time scaling uses the blocks that the parameters identify instead of performing a search for the best matching blocks. The parameters can also indicate which of the frames represent silence and can be scaled differently from frames that do not represent silence.