An alteration candidate for a query can be scored. The scoring may include computing one or more query-dependent feature scores and/or one or more intra-candidate dependent feature scores. The computation of the query-dependent feature score(s) can be based on dependencies to multiple query terms from each of one or more alteration terms (i.e., for each of the one or more alteration terms, there can be dependencies to multiple query terms that form at least a portion of the basis for the query-dependent feature score(s)). The computation of the intra-candidate dependent feature score(s) can be based on dependencies between different terms in the alteration candidate. A candidate score can be computed using the query dependent feature score(s) and/or the intra-candidate dependent feature score(s). Additionally, the candidate score can be used in determining whether to select the candidate to expand the query. If selected, the candidate can be used to expand the query.