25. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause at least one processor of a computing device to: output, for display at a display device, a graphical keyboard comprising a plurality of keys; receive, by the computing device, an indication of a gesture to select fewer than all of a group of the plurality of keys that corresponds to a candidate word, the indication of the gesture based at least in part on detecting an input unit at a plurality of locations of the presence-sensitive input device; responsive to the detecting and while the gesture has not yet terminated: incrementally update a plurality of letter chains, each letter chain including a different respective combination of letters associated with respective keys of the plurality of keys, wherein each respective letter chain is assigned a respective combined cost value of a plurality of respective combined cost values based on cost values for the respective keys of the plurality of keys, that are in proximity to the gesture; determine, based at least in part on the plurality of letter chains, a plurality of candidate words; output, based on a letter chain of the plurality of letter chains being assigned to a highest combined cost value of the plurality of respective combined cost values, the candidate word for display at a first location of the display device; and responsive to determining, based on the input unit no longer being detected at the presence-sensitive input device, that the gesture has terminated prior to selecting all of the group of the plurality of keys that corresponds to the candidate word, output the candidate word for display at a second location of the display device, wherein the second location corresponds to a text entry area.
25. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause at least one processor of a computing device to: output, for display at a display device, a graphical keyboard comprising a plurality of keys; receive, by the computing device, an indication of a gesture to select fewer than all of a group of the plurality of keys that corresponds to a candidate word, the indication of the gesture based at least in part on detecting an input unit at a plurality of locations of the presence-sensitive input device; responsive to the detecting and while the gesture has not yet terminated: incrementally update a plurality of letter chains, each letter chain including a different respective combination of letters associated with respective keys of the plurality of keys, wherein each respective letter chain is assigned a respective combined cost value of a plurality of respective combined cost values based on cost values for the respective keys of the plurality of keys, that are in proximity to the gesture; determine, based at least in part on the plurality of letter chains, a plurality of candidate words; output, based on a letter chain of the plurality of letter chains being assigned to a highest combined cost value of the plurality of respective combined cost values, the candidate word for display at a first location of the display device; and responsive to determining, based on the input unit no longer being detected at the presence-sensitive input device, that the gesture has terminated prior to selecting all of the group of the plurality of keys that corresponds to the candidate word, output the candidate word for display at a second location of the display device, wherein the second location corresponds to a text entry area. 26. The non-transitory computer-readable storage medium of claim 25 , wherein the gesture comprises a plurality of portions, wherein the non-transitory computer-readable storage medium of claim 25 is encoded with instructions that, when executed, cause at least one processor of the computing device to: incrementally update the plurality of letters chains for each portion of the plurality of portions.