In various exemplary embodiments, a system and associated method predict auto-complete recommendations for a partial search request. A search engine receives a partial search request with one or more characters from a client device. A first set of auto-complete recommendations corresponding to the one or more characters of the partial search request are identified. A second partial search request is predicted that comprises a set of characters with one or more additional characters added to the one or more characters from the partial search request. A second set of auto-complete recommendations corresponding to the second partial search request is identified. The first set of auto-complete recommendations and the second set of auto-complete recommendations are returned to the client device as a response to the partial search request.