For most multi-label algorithms, they need to deal with each labels separately and directly. It would be easier if we can just treat the multi-labels as a matrix. So I don't think a joint label is a good idea here.
But I do like the idea about a special Attribute type. Do you have any thought about how it should look like? I think we need to at least be able to pull rows/cols, access each label.