One embodiment of the present invention provides a system that identifies a synonym with N-gram agreement for a query phrase. During operation, the system receives a candidate synonym for the query phrase. Then, for each term in the query phrase, the system determines whether the term is a lexical synonym of a corresponding term in the candidate synonym or the term shares meaning with the corresponding term in the candidate synonym. If this is true for all terms in the query phrase, the system identifies the candidate synonym as an N-gram agreement synonym for the query phrase. The system then uses this identified N-gram agreement synonym to improve synonym mappings for query terms and/or query phrases.