It's incredible that there's actually this much room to improve. How does this compare to GPU implementations?

Also it looks like the optimization is related to running operations on a compressed representation, for the 10x vs 100x speedup, is there a tradeoff between speed and accuracy, or is that extra degree of magnitude just from bringing SIMD into the picture?

From what I can tell, this is a machine learning based approximation to matrix multiplication by a particular matrix (which it was trained on). It trades accuracy for speed. If you need to multiply many (many!) vectors by a static matrix and you have loose enough error tolerance, this can provide up to 100x speedup.

There's definitely a tradeoff between speed and accuracy. We characterize this for various problems in the paper (https://arxiv.org/pdf/2106.10860.pdf), but tl;dr is that it speeds things up more at a given level of error when there's more redundancy in your matrices.

Back-of-the-envelope calculation suggests that this won't beat tensor cores on NVIDIA GPUs. This is basically because ~half the die is an ASIC for dense (and 2:4 sparse) matmuls, with no support for the sparsity structure we induce. If 1:16 sparsity were supported or there were a batched warp_shuffle instruction, we'd get similar speedups for GPUs as we do on CPUs.