A method, comprising: storing, by a processor of a client device, previously received search queries associated with a user of the client device; receiving, by a processor of the client device and from the user, one or more characters of a search query, wherein the one or more characters of the search query being fewer than all of a plurality of characters of the search query; identifying, by a processor of the client device, a plurality of the previously received search queries that include the one or more characters; presenting, by a processor of the client device and to the user, query refinement options that include the plurality of the previously received search queries; spell-checking the one or more characters of the search query, wherein spell-checking the one or more characters of the search, query includes: determining an amount of time that has passed since a last character, of the one or more characters of the search query, was received, and spell-checking the one or more characters of the search query when the amount of time satisfies a time threshold, wherein the spell-checking is performed asynchronously and remotely using a server; identifying, based on spell-checking the one or more characters of the search query, possible corrections to the one or more characters of the search query; presenting, in the query refinement options and separately from the plurality of the previously received search queries, the possible corrections; receiving, by a processor of the client device, at least one additional character of the search query; identifying, by a processor of the client device, a particular query, of the plurality of the previously received search queries, that does not include the at least one additional character of the search query; and removing, by a processor of the client device, the particular query from the presented query refinement options. storing, by a processor of a client device, previously received search queries associated with a user of the client device; receiving, by a processor of the client device and from the user, one or more characters of a search query, wherein the one or more characters of the search query being fewer than all of a plurality of characters of the search query; identifying, by a processor of the client device, a plurality of the previously received search queries that include the one or more characters; presenting, by a processor of the client device and to the user, query refinement options that include the plurality of the previously received search queries; spell-checking the one or more characters of the search query, wherein spell-checking the one or more characters of the search, query includes: determining an amount of time that has passed since a last character, of the one or more characters of the search query, was received, and spell-checking the one or more characters of the search query when the amount of time satisfies a time threshold, wherein the spell-checking is performed asynchronously and remotely using a server; identifying, based on spell-checking the one or more characters of the search query, possible corrections to the one or more characters of the search query; presenting, in the query refinement options and separately from the plurality of the previously received search queries, the possible corrections; receiving, by a processor of the client device, at least one additional character of the search query; identifying, by a processor of the client device, a particular query, of the plurality of the previously received search queries, that does not include the at least one additional character of the search query; and removing, by a processor of the client device, the particular query from the presented query refinement options.