A message suggestion service may use clusters of pre-approved messages to improve the quality of messages suggested to users. During a conversation, messages of the conversation may be processed with a neural network to compute a conversation encoding vector. The neural network may also be used to compute pre-approved message encoding vectors of the pre-approved messages. Distances between the conversation encoding vector and the pre-approved message encoding vectors may be used to select one or more clusters. Distances between the conversation encoding vector and the pre-approved message encoding vectors may then be used to select one or more pre-approved messages from the selected clusters. The selected pre-approved messages may then be presented as suggested messages to a user.