Web of Trust & Proof of Work are both incredibly effective, especially if combined.

This note has a ~10 ms proof of work attached to it. I could even bump that up to 1 second if I wanted without any real problem to usability.... but for a Bot to have any reach, it has to spam millions of notes, and that computation becomes expensive (at some point).