Rather than a time to live you probably want a number of requests to live. Decrement a counter associated with the token at every request until it expires.

An obvious followup is to decrement it by a larger amount if requests are made at a higher frequency.