Methods, systems, and apparatus, including computer programs encoded on computer storage media, for evaluating substitute terms. One of the methods includes receiving a query and identifying an original term occurring in the query. One or more substitution contexts are determined for the original term, wherein a substitution context includes one or more context terms and an indication of a position in the query of the original term and the one or more context terms. A score is determined for each substitution context of the one or more substitution contexts. One or more substitution contexts are selected based on the score of each substitution context. One or more substitute terms for the original term in the context of the one or more selected substitution contexts are determined.