The alternative to storing tokens is to use an AEAD encryption scheme like AES-GCM to protect tokens from forgery or tampering. You will still have to worry about reuse, so you will probably want to restrict use of this token to the user it was generated for and to a lifetime (say, 24 hours). That is a very high level description, there are details (like nonce generation) that must be done correctly for the system to be secure.