> extracting every combination of attributes as separate strings (the example here, having 5 attributes, would produce 32 separate strings, and this grows exponentially with the number of possible attributes in the source string)

Actually I'm not sure we can avoid that if we want to build a meaningful phrase from attributes.
Typical example is the translation of plurals which can't be done properly with simple concatenating code (it works in English, "horse" -> "horse" + "s" -> "horses", but not in French, "chien" becomes "chiens" but "cheval" becomes "chevaux" for example, and many other languages have much more complex rules, see https://developer.mozilla.org/en-US/docs/Mozilla/Localization/Localization_and_Plurals).
So we can't assume we can build a meaningful phrase from bits. It will not work.

> avoiding interpolating attributes into the link phrase altogether, always displaying them to the side in parentheses

If we don't build a phrase (or part of one), but instead list attributes (live, cover, recording ... instead of "is a live cover recording of") it is much simpler i18n-wise, but much less human-oriented.

I'm not sure having 32 separate strings is much an issue by itself, but the code to choose which one to display will be rather long and complex.

I don't know if this helps in your case, but we have a control flow syntax that can give a little more flexibility:

{attribute:output_if_set|output_if_unset}

.

• {live:a|}

  will output "a" if the live attribute is set, or nothing if it's unset

• {live:|a}

  will output "a" if the live attribute is not set, or nothing if it's set

• {live:{medley:a|}|}

  will output "a" only if both the live and medley attributes are set

• etc., these can be nested to create whatever control flow you'd like

Of course this also might be very difficult to use effectively in many cases.

The only other solutions I can see are:

• extracting every combination of attributes as separate strings (the example here, having 5 attributes, would produce 32 separate strings, and this grows exponentially with the number of possible attributes in the source string)
• avoiding interpolating attributes into the link phrase altogether, always displaying them to the side in parentheses
• extending or improving the interpolation syntax somehow
• any other idea I haven't thought of