System Settings > General > Storage. Click the ⓘ next to Messages. Sort by size and delete large attachments.

Appreciate the suggestion but that's similar to fixes like "Have you tried re-installing your OS, maybe that fixes the issue?".

I don't want to babysit my attachments or delete old conversations just because Apple doesn't put effort into that app. Probably my fault for still using it, but Telegram, WhatApp and Signal all manage to do it better.