A neural paraphrase generator receives a sequence of tuples comprising a source sequence of words, each tuple comprising word data element and structured tag element representing a linguistic attribute about the word data element. An RNN encoder receives a sequence of vectors representing a source sequence of words, and RNN decoder predicts a probability of a target sequence of words representing a target output sentence based on a recurrent state in the decoder. An input composition component includes a word embedding matrix and a tag embedding matrix, and receives and transforms the input sequence of tuples into a sequence of vectors by 1) mapping word data elements to word embedding matrix to generate word vectors, 2) mapping structured tag elements to tag embedding matrix to generate tag vectors, and 3) concatenating word vectors and tag vectors. An output decomposition component outputs a target sequence of tuples representing predicted words and structured tag elements, the probability of each single tuple from the output is predicted based on a recurrent state of the decoder.