As traditional media and information devices integrate with the web, they must abruptly support a vastly larger database of relevant items. Many devices such as internet-capable televisions and set-top boxes support traditional remote controls with on-screen keyboards for text input. These input methods are not well suited for text entry but are difficult to displace. To make these devices work well in a rich information environment such as the WWW, we must develop ways to improve text entry through this input bottleneck. We introduce QuickSuggest which significantly improves text entry speed for on-screen keyboards, much like query suggestions in a search text box can improve query input. QuickSuggest uses the same simple Up/Down/Left/Right/Enter interface common to remote controls, gaming devices and car input controls used to enter text. The paper describes QuickSuggest's novel adaptive user interface to make text entry more efficient and demonstrates quantitative improvements from simulation results on millions of user queries. User experiments also show ease of use and efficiency with no learning curve. Our results suggest that very simple input devices can be used to enter text covering a large vocabulary with surprising ease.