An offline semantic processor of a resource-constrained voice-enabled device such as a mobile device utilizes an offline grammar model with reduced resource requirements to parse voice-based queries received by the device. The offline grammar model may be generated from a larger and more comprehensive grammar model used by an online voice-based query processor, and the generation of the offline grammar model may be based upon query usage data collected from one or more users to enable a subset of more popular voice-based queries from the online grammar model to be incorporated into the offline grammar model. In addition, such a device may collect query usage data and upload such data to an online service to enable an updated offline grammar model to be generated and downloaded back to the device and thereby enable a dynamic update of the offline grammar model to be performed.