Methods and apparatus for providing query suggestions to a user based on one or more past queries submitted by the user. Candidate query suggestions responsive to a current query may be identified. A candidate query similarity measure may be determined for a given candidate query suggestion based on matching entities related to the given candidate query suggestion and the one or more past queries. In some implementations, the similarity measure of the given candidate query suggestion may be based on a comparison of current entities of the given candidate query suggestion that match entities of one or more past queries, to a group of the current entities that includes entities that do not match the entities of one or more past queries. In some implementations a ranking of the candidate query suggestions may be determined based on the similarity measure.