Methods and apparatus for determining whether query templates that have the same entity collection identifier are semantically equivalent query templates based on determining a similarity measure between the query templates. The similarity measure may be based on various factors. For example, in some implementations the similarity measure may be based on a number of the entities of the entity collection that instantiate both of the query templates in a record of past user queries. Also, for example, in some implementations the similarity measure may be based on a number of the entities of the entity collection that instantiate both of the query templates in a record of past user queries and are determined to be entities that satisfy a threshold level of entity similarity between the query templates. In some implementations, terms of two query templates that are determined to be equivalent may be determined to be synonymous.