In one embodiment, a method includes receiving, at the mobile client system, a text string inputted into a query field by a first user, accessing, from a local data store, a set of grammar templates, each grammar template comprising query tokens referencing an object stored in the local data store, generating one or more natural-language suggested queries by matching portions of the text string to query tokens of the grammar templates, each suggested query comprising references to one or more of the objects stored in the local data store and the natural-language string of the matching grammar template, calculating a cost for each grammar template based at least in part on one or more portions of text string not corresponding to one of the query tokens, and displaying one or more suggested queries to the first user, each having a calculated cost below a threshold cost value.