Can abstract syntax trees be unparsed in subexponential time?
If the synthesized attributes compute a parse tree, then unparsing can be done in time linear in the size of the parse tree, assuming that string concatenation happens in constant time -- the obvious recursive algorithm on the parse tree will do the job.

I would guess XText is doing backtracking in order to minimize the number of parentheses in arithmetic expressions, line breaks, or some other pretty-printing criteria. However, for most languages it's possible to do that in linear time, as well. 

See Norman Ramsey, Unparsing Expressions With Prefix and Postfix Operators. Software—Practice and Experience, 28(12):1327–1356, October 1998.