No, you don't look up the token. You check a zero-knowledge proof.
The way this works is, there's a function with both public and private inputs, and an output. You can send me public inputs, and I can pass those plus my private inputs into the function, and give you the function output, along with a proof that the output is correct given your inputs.
So in this case, the government has a public key, which it uses to sign your credentials, consisting of your birthdate and a unique identifier.
The website sends you a large random number.
The public inputs are the government public key, the random number, today's date, and maybe a revocation list of identifiers.
The private data is my unique identifier and birth date.
The function returns true if my calculated age > 18, the government's signature of my data is valid, my private identifier is not on the public revocation list, and (to avoid replays) that the hash of your random number is not zero.
I send you back the generated proof, which is just a 256-bit number. You can check that the proof is correct without looking anything up. The proof does not give you any way to reconstruct my private data. It is only associated with the random number you gave me, and the public data everyone knows.
To keep the revocation list from growing forever, we could also make credentials expire after some period of time. Add an issue date to the private data, and we can add an expiration check to the function. Client software can automatically get a new credential if the old one is valid, expiration is just to allow us to delete old identifiers from the revocation list.
A hole in the above scheme is that government could try redoing proofs for a given random number, using all the current identifiers. To prevent this, the user passes in another random number as private data, and the function checks that that doesn't hash to zero either. User can change that random number every time, its only function is to change the generated proof to something the government can't replicate.