Hacker News Reader

Wouldn't they only need to store the outputs that they themselves signed, in order to prevent themselves from signing the same one twice?

Yes but that's two-thirds of the total number of transactions, since no transaction is final until two-thirds of validators have signed it.