You can use a bloom filter to check if a token has been revoked, and then do the query for false positives.