Authorization cache with revocation

Design caching for an authorization/permissions service that answers 'can user U do action A on resource R?' It's called on nearly every API request (read-heavy, 50k qps), permissions change rarely but a revocation must take effect within ~5s, and a cache miss is expensive (a graph traversal). Also, lots of queries are for principals that don't exist or have no grant. Design the cache, including how you handle negative results and revocations.