1. A method comprising: outputting, by a computing device and for display, a graphical keyboard comprising a plurality of keys; maintaining, by the computing device, a plurality of letter chains, wherein: each respective letter chain of the plurality of letter chains is associated with a respective cost value; each respective letter chain includes a different respective group of one or more characters; and each respective character of each respective group of one or more characters corresponds to a respective key of the plurality of keys; receiving an indication of a particular portion of a gesture detected at a presence-sensitive input device, the gesture comprising a plurality of portions; responsive to receiving the indication of the particular portion of the gesture, updating, by the computing device, based at least in part on the indication of the particular portion of the gesture, the plurality of letter chains; determining, by the computing device, for the particular portion of the gesture and based at least in part on a cost value associated with at least one of the plurality of letter chains, a candidate word; and outputting, by the computing device, for display, the candidate word.