4 ms·

I think this sentence: > But matrix multiplication, to which our civilization is now devoting so many of its marginal resources, has all the elegance of a man

by sfpotter 11mo ago

I think this sentence: > But matrix multiplication, to which our civilization is now devoting so many of its marginal resources, has all the elegance of a man hammering a nail into a board. is the most interesting one. A man hammering a nail into a board can be both beautiful and elegant! If you've ever seen someone effortlessly hammer nail after nail into wood without having to think hardly at all about what they're doing, you've seen a master craftsman at work. Speaking as a numerical analyst, I'd say a well multiplied matrix is much the same. There is much that goes into how deftly a matrix might be multiplied. And just as someone can hammer a nail poorly, so too can a matrix be multiplied poorly. I would say the matrices being multiplied in service of training LLMs are not a particularly beautiful example of what matrix multiplication has to offer. The fast Fourier transform viewed as a sparse matrix factorization of the DFT and its concomitant properties of numerical stability might be a better candidate.

jamespropp 11mo ago
Yes!
- gsf_emergency_6 11mo ago
  >The fast Fourier transform viewed as a sparse matrix factorization of the DFT Riffing further on the Fourier connection: are you planning to explore the link between matmul and differentiation? Using the "Pauli-Z" matrix that you introduced without a straightforward motivation, eg. (I took it that you intended it to be a "backyard instance" of "dual numbers")
hobs 11mo ago
https://www.youtube.com/watch?v=Ruf-cLr2PZ8 https://www.youtube.com/watch?v=Ruf-cLr2PZ8 I always think of this when thinking about the gracefulness of a hammer.
- JanNash 11mo ago
  Wow, thank you for this gem!!!
- nialse 11mo ago
  Turns out it’s the skill of the person handling the hammer that matters most. Enlightening! Appreciate the link!
- mauvehaus 11mo ago
  Upholstery tacks are sold sterilized for people holding them in their mouths. Now I wonder the same about drywall nails! Thanks for the link; that is absolutely masterful work.
sdenton4 11mo ago
A somewhat more beautiful matmul for neural networks is given by the Monarch paper: https://arxiv.org/abs/2204.00595 https://arxiv.org/abs/2204.00595 Generally, low-rank and block-diagonal matrices are both great strategies for producing expressive matmuls with fewer parameters. We can view the FFT as a particularly deft example of factorizing one big matmul into a number of block-diagonal matmuls, greatly reducing the overall number of multiplications by minimizing the block size. However, on a G/TPU, we have a lot more parallelism available, so the sweet spot for size of the blocks may be larger than 2x2... We can also mix low-rank, block diagonal, and residual connections to get the best of both worlds: x' = (L@x + B@x + x) The block-diagonal matrix does 'local' work, and the low-rank matrix does 'broadcast' work. I find it pretty typical to be able to replace a single dense matmul with this kind of structure and save ~90% of the params with no quality cost... (and sometimes the regularization actually helps!)
- bee_rider 11mo ago
  Do low rank/block diagonal matrices come up in LLMs often? What about banded or block tridiagonal? Intuitively banded matrices seem like they ought to be good at encoding things about the world… everything is connected but not randomly so.
  - sdenton4 11mo ago
    Yep! Think of LORA for network fine tuning. Monarch (linked above) uses lots of block diagonality. These ideas also make flash attention flash. I haven't seen banded matrices as much, though (with weight sharing) they're just convolutions. One nice feature of block diagonality is that you can express it as batched matrix multiplication, reusing all the existing matmul kernels.
- btown 11mo ago
  https://hazyresearch.stanford.edu/blog/2023-12-11-truly-subquadratic https://hazyresearch.stanford.edu/blog/2023-12-11-truly-subq... is an approachable overview of the Monarch approach, for those interested! There's a lot of opportunity here. Just because matrix multiplication makes for a beautiful mathematical building block, and a very reasonable one to build high-level ML logic on, doesn't mean it needs to be computed the same way, and in the same order, that we learned in linear algebra courses. I'm quite curious if this is being used in practice at scale, or whether it's still in the lab at the moment!

jamespropp 11mo ago

Yes!

gsf_emergency_6 11mo ago
>The fast Fourier transform viewed as a sparse matrix factorization of the DFT Riffing further on the Fourier connection: are you planning to explore the link between matmul and differentiation? Using the "Pauli-Z" matrix that you introduced without a straightforward motivation, eg. (I took it that you intended it to be a "backyard instance" of "dual numbers")

hobs 11mo ago

https://www.youtube.com/watch?v=Ruf-cLr2PZ8 https://www.youtube.com/watch?v=Ruf-cLr2PZ8 I always think of this when thinking about the gracefulness of a hammer.

JanNash 11mo ago
Wow, thank you for this gem!!!
nialse 11mo ago
Turns out it’s the skill of the person handling the hammer that matters most. Enlightening! Appreciate the link!
mauvehaus 11mo ago
Upholstery tacks are sold sterilized for people holding them in their mouths. Now I wonder the same about drywall nails! Thanks for the link; that is absolutely masterful work.

sdenton4 11mo ago

A somewhat more beautiful matmul for neural networks is given by the Monarch paper: https://arxiv.org/abs/2204.00595 https://arxiv.org/abs/2204.00595 Generally, low-rank and block-diagonal matrices are both great strategies for producing expressive matmuls with fewer parameters. We can view the FFT as a particularly deft example of factorizing one big matmul into a number of block-diagonal matmuls, greatly reducing the overall number of multiplications by minimizing the block size. However, on a G/TPU, we have a lot more parallelism available, so the sweet spot for size of the blocks may be larger than 2x2... We can also mix low-rank, block diagonal, and residual connections to get the best of both worlds: x' = (L@x + B@x + x) The block-diagonal matrix does 'local' work, and the low-rank matrix does 'broadcast' work. I find it pretty typical to be able to replace a single dense matmul with this kind of structure and save ~90% of the params with no quality cost... (and sometimes the regularization actually helps!)

bee_rider 11mo ago
Do low rank/block diagonal matrices come up in LLMs often? What about banded or block tridiagonal? Intuitively banded matrices seem like they ought to be good at encoding things about the world… everything is connected but not randomly so.
- sdenton4 11mo ago
  Yep! Think of LORA for network fine tuning. Monarch (linked above) uses lots of block diagonality. These ideas also make flash attention flash. I haven't seen banded matrices as much, though (with weight sharing) they're just convolutions. One nice feature of block diagonality is that you can express it as batched matrix multiplication, reusing all the existing matmul kernels.
btown 11mo ago
https://hazyresearch.stanford.edu/blog/2023-12-11-truly-subquadratic https://hazyresearch.stanford.edu/blog/2023-12-11-truly-subq... is an approachable overview of the Monarch approach, for those interested! There's a lot of opportunity here. Just because matrix multiplication makes for a beautiful mathematical building block, and a very reasonable one to build high-level ML logic on, doesn't mean it needs to be computed the same way, and in the same order, that we learned in linear algebra courses. I'm quite curious if this is being used in practice at scale, or whether it's still in the lab at the moment!