In one embodiment, a method includes receiving a search query including one or more n-grams, determining for each n-gram if a contextual speller model indicates the n-gram is misspelled, identifying for each misspelled n-gram one or more variant-tokens based at least on the search query and a contextual speller model, generating one or more unique combinations of the n-grams and variant-tokens, where each unique combination includes a variant-token corresponding to each misspelled n-gram, calculating a relevance-score for each unique combination based at least in part on the search query and the contextual speller model, generating one or more corrected queries, where each corrected query includes a unique combination having a relevance-score greater than a threshold relevance-score, and sending one or more of the corrected queries to a user for display.