Thanks! I think the answer is that it would fall down pretty hard if the tempo started varying, the reason being that the algorithm seeks out interval modes instead of averages, with only a little wiggle room.
In the testing section, the songs that we fail to identify correctly are usually those we couldn't get a "handle" on in the form of identifying common intervals. A varying tempo would exacerbate that problem.
Additionally, the question becomes: what is the tempo of a song that has an inconsistent tempo?
I wonder if the algorithm can adapt to recordings where the tempo isn't quite constant.
Amusingly, I first read "beat" as a verb in your title, and was expecting something cloak-and-dagger.