Как работает stateless token authentication?
очень легко мыслить токенами, как сессией, но токен это не сессия, не стоит путать. 
Токены используют как раз для того чтоб отойти от классической схемы с сессиями/паролями.
по порядку:
1) смотрите у вас есть сервис, состоит например из 10 серверов, которые отвечают за разные части функционала, поскольку функционал коммерческий вам нужно проверять каждый запрос от пользователя есть ли у него права для этого запроса.
вы вынуждены сделать единый сервер валидации, и с каждого своего сервера, для каждого запроса, запрашивать на сервере валидации проверку пользователя и его прав.
в такой ситуации сервер валидации для вашего сервиса становиться бутылочным горлышком, и мешает горизонтальной масштабируемости.
и абсолютно без разницы валидируете вы пользователя по паролю, айпи, или токену, сессии, схема одна и таже, производительность тоже одна и таже (именно поэтому нет никакого смысла менять сверку пользователя вместо пароля на сверку по айпи, или токену, или сессию, тем более понятно почему использования айпи в этой схеме просто глупая идея).
поэтому есть задача отойти от этой схемы, для возможности простого горизонтального масштабирования, для этого вы берёте информацию о пользователе (например его айди,  права, и тд) и зашифровываете эти данные, и передаёте пользователю в виде токена. 
2) На каждом вашем сервере есть алгоритм быстрой расшифровки, который на лету проверяет токены, и из него получает нужную информацию, о правах и айди пользователя (валидирует пользователя, без бутылочного горлышка), сами токены временные, в них также вшивают информацию о времени его действия, обычно в районе пары часов/суток, после чего вы перегенерируете токен заново (ключ для перегенерации и получения нового токена также вшиваете в токен, осуществляя непрерывность процесса перегенерации токенов).
3. Что делать если пользователь поменял пароль?
ничего - токен даёт пользователю право на вход, и не имеет значения какой у пользователя пароль.
1. Нужно, как правило хранят в отдельной табличке что-то типа user_id | token | дополнительные поля.
2. Как вариант можно сохранять/проверять ip адрес или какие-то другие параметры. Если посмотреть api соцсетей - там у токен выдается на довольно короткое время с возможностью обновления времени.
3. Удалить все токены связанные с этим пользователем, выдать новый.
4. Считывать с бд, сильной нагрузки эта операция не создаст.