Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, relating to on-device query annotating. In some implementations, a search query is received, and a mobile device identifies a reference to a particular entity and a reference to a category based on the query. A model that is stored on the mobile device and stores one or more facts that are associated with one or more entities is accessed. A subset of facts from among the facts that are stored in the model for the particular entity is selected. The search query is annotated based at least on one or more facts of the subset of facts that are stored in the model for the particular entity. The annotated search query is transmitted, from the mobile device to a search engine, for processing. A result of processing the annotated search query is received by the mobile device.