Presumably you can keep counters like these on the server edges, and just push new values out to servers whenever things change, as opposed to query a DB every time. This wouldn't invalidate individual tokens however, but all tokens that have that counter value. It'd also mean there's a window where tokens can still be used while servers are being updated with the new value(s).

These are just some random and half-baked thoughts, I have no idea what OP does, but there are options to limit hitting backing DBs anyway.