Typo-tolerant autocomplete

Design typo-tolerant autocomplete that still returns good suggestions when the user mistypes the prefix, 'restaraunt', 'bluetooth', 'iphine', within a 50ms p99 budget at 500k QPS. Exact-prefix trie matching returns nothing for a typo. You can't run full edit-distance against millions of terms per keystroke. How do you make fuzzy matching fast enough to stay on the autocomplete hot path?