A computing device is described that outputs, for display, a graphical keyboard comprising a plurality of keys. The computing device receives, an indication of a gesture detected at a presence-sensitive input device. The computing device determines, based at least in part on the indication of the gesture and at least one characteristic of the gesture, one or more keys from the plurality of keys. The computing device determines a character string based on the one or more keys from the plurality of keys. In response to determining that the character string is not included in a lexicon and a spatial model probability associated with the one or more keys from the plurality of keys exceeds a probability threshold, the computing device outputs, for display, the character string.