An audio identification system accounts for an audio signal's complexity when generating a test audio fingerprint for identification of the audio signal. In particular, the audio identification system determines a complexity of an audio signal to be fingerprinted. For example, the audio signal's complexity may be determined by performance of an autocorrelation on the audio signal. Based on the determined complexity, the audio identification system determines a length of a sample of the audio signal used to generate a test audio fingerprint. A sample having the length is then obtained and used to generate a test audio fingerprint for the audio signal. The test audio fingerprint may be compared to a set of reference audio fingerprints to identify the audio signal.