Josh Klint said:
I can see how the performance here would be extremely fast, since it's not actually doing any math during the traversal:

That's maybe not what you want.
You have to factor in the latency from (usually incoherent) memory access. Better spend the waiting time on doing shitloads of math, than doing nothing while waiting. : )
(But just saying in general, not referring the paper at all.)

Josh Klint said:
Crytek claims their voxel lighting is faster for direct lighting than shadow maps, but I'm not sure these numbers make much sense.

I think that's true for scenes with many lights. Then it's ‘generate X SMs each frame’ vs. ‘reuse one acceleration structure for all frames’.
Even if a trace is much slower than a SM lookup, at some point X becomes the dominant factor even in practice.
If that X is in practical range for actual games on affordable HW is another question.