So I thought if I just deleted old Messages threads which contained lots of graphics that storage would become available again for other purposes. Wrong. Apparently, graphics remain saved on your device even when you delete the thread. You need to delete the graphics separately.
Settings > General > iPhone Storage > Messages > Review Large Attachments
I’m not sure what retaining those attachments there is supposed to do for me. If I deleted the thread I’m either not interested in its contents, or I’ll have already saved them to some other location (camera roll, Dropbox, etc.).
Anyway, if you’re running low on memory this could be low hanging fruit. And for those who don’t want to go over it by hand, there’s an auto delete option. I would have thought that this is the same as in Settings > Messages > Keep Messages, but apparently not. A moment ago the latter for me was set to forever, but the under iPhone Storage it was showing on.