1. A computer-implemented method comprising: generating, at a mobile computing device, a model that, for each of multiple entities that are other than the user of the mobile computing device, stores one or more facts that are associated with the entity and that are derived from local data stored on the mobile computing device; storing the model on the mobile computing device; after the model is stored on the mobile computing device, receiving, at the mobile computing device, a search query; identifying, by the mobile computing device and based on the search query, (i) a reference to a particular entity that is other than a user of the mobile computing device, and (ii) a reference to a category; selecting, by the mobile computing device, a proper subset of facts from among all of the facts in the model that is stored for the particular entity on the mobile computing device and that are derived from local data stored on the mobile computing device that are pre-associated in the model with the category; generating, by an on-device query rewrite engine of the mobile computing device, an annotation that references (i) the particular entity that is other than the user of the mobile computing device, and (ii) one or more facts of the proper subset of facts that are stored in the model for the particular entity and that are pre-associated in the model with the category; transmitting, from the mobile computing device to a search engine, (i) the search query, and (ii) the annotation that references the particular entity that is other than the user of the mobile computing device, and the one or more facts of the proper subset of facts that are stored in the model for the particular entity and that are pre-associated in the model with the category, for processing; and receiving, by the mobile computing device and from the search engine, a result of processing the search query and the annotation that references the particular entity that is other than the user of the mobile computing device, and the one or more facts of the proper subset of facts that are stored in the model for the particular entity and that are pre-associated in the model with the category.