Multimodal interaction with grammar-based speech applications may be facilitated with a device by presenting permissible phrases that are in-grammar based on acceptable terms that are in-vocabulary and that have been recognized from a spoken utterance. In an example embodiment, a spoken utterance having two or more terms is received. The two or more terms include one or more acceptable terms. An index is searched using the acceptable terms as query terms. From the searching of the index, permissible phrase(s) are produced that include the acceptable terms. The index is a searchable data structure that represents multiple possible grammar paths that are ascertainable based on acceptable values for each term position of a grammar-based speech application. The permissible phrase(s) are presented to a user as option(s) that may be selected to conduct multimodal interaction with the device.