1. A method performed by one or more computers, the method comprising: receiving a search string from a user device; selecting a plurality of candidate query suggestions based on the search string; determining, for each candidate query suggestion, a probability for the candidate query suggestion based on a count in a query log of the number of times that the plurality of candidate query suggestions were submitted as search queries and a count in the query log of the number of times that the candidate query was submitted as a search query; determining a measure of query completeness for the search string based on an aggregation of the determined probabilities, including determining a probability of receiving the N most probable query suggestions for the search string, wherein N is an integer greater than zero; comparing the measure of query completeness to a threshold measure of query completeness; and providing one or more specific query suggestions to the user device, selected from a plurality of specific query suggestions for the search string, when the measure of query completeness exceeds the threshold measure of query completeness; or providing one or more general query suggestions to the user device, selected from a plurality of general query suggestions for the search string, when the measure of query completeness does not exceed the threshold measure of query completeness.