1. A computer-implemented method, comprising: outputting, by a computing device having one or more processors and a presence-sensitive display device, a graphical keyboard comprising a plurality of keys associated with characters of a first alphabet of a first language, receiving, at the computing device, a user input comprising one or more touches on the presence-sensitive display device, constructing, at the computing device, a character lattice corresponding to the user input based on a spatial model, the character lattice being indicative of a spatial probability of one or more potential characters corresponding to the user input, constructing, at the computing device, a token lattice corresponding to the user input based on the character lattice, the token lattice being indicative of a collective spatial probability of one or more potential tokens corresponding to the user input, wherein each of the one or more potential tokens corresponds to a character candidate string comprising a group of characters representing a semantic or phonetic unit, constructing, at the computing device, a word lattice corresponding to the user input based on the token lattice and a language model, the word lattice being indicative of a probability of one or more potential words corresponding to the user input, the one or more potential words comprising one or more characters of a second alphabet of a second language, selecting, at the computing device, at least one particular potential word of the one or more potential words based on the word lattice, and outputting, via the presence-sensitive display device, the at least one particular potential word.