Why is softmax considered counter-intuitive for multi-label classification? In the FB paper on Instagram multi-label classification (Exploring the Limits of Weakly Supervised Pretraining), the authors characterize as "counter-intuitive" their finding that softmax + multinomial cross-entropy worked much better than sigmoid + binary cross-entropy:

Our model computes probabilities over all hashtags in the vocabulary using a softmax activation and is trained to minimize the cross-entropy between the predicted softmax distribution and the target distribution of each image. The target is a vector with $k$ non-zero entries each set to $1/k$ corresponding to the $k ≥ 1$ hashtags for the image.
We have also experimented with per-hashtag sigmoid outputs and binary logistic loss, but obtained significantly worse results. While counter-intuitive given the multi-label data [...]

Why is this counterintuitive?
The sigmoid binary loss would encourage the true label logits to be much higher than 0, and the other logits to be much smaller than 0. I think everyone agrees that this is intuitive.
The softmax multinomial loss would encourage the true label logits to be roughly the same, and much higher than the other logits. The only real difference vs. the sigmoid binary is that the true label logits are now pushed to be close to each other. It does constrain the logits behavior  (the model now needs to keep all the true label logits in some small-ish range, except for an arbitrary per-image shift). I guess this constraint may help or harm depending on much it helps with regularization, but I don't think it would be considered counter-intuitive?
Is there anything else I'm missing?
(There's another difference: with softmax multinomial loss, only relative, not absolute, values of logits matter -- but that seems to be a very minor point.)
 A: It is actually the opposite of what you said "The sigmoid binary loss would encourage the true label logits to be much higher than 0, and the other logits to be much smaller than 0. I think everyone agrees that this is intuitive."
When applying the logit and taking binary cross-entropy loss, we encourage each output component to be independent of each other: one logit is higher doesn't push the other logits to be smaller. This is exactly the opposite of softmax, which encourages one logit to be higher while all others to be smaller. This is why it's counterintuitive, as indicated in the paper.
A: This was also confusing for me too! And I didn't quite think that the accepted answer or well, the only answer covered the source of confusion completely. The issue here isn't just with softmax, because even though you want to minimize the other logits, the loss will not converge unless the prediction and target vectors are nearly the same. If the target labels contained 1 for each present class, then because of softmax your loss will never converge -- its an impossible problem. But, in the mentioned paper the target labels are divided by k where k is the number of non-zero labels in the target vector. Then our loss function can converge.
However, now think about what this target distribution is saying. Given your input, X, it is equally likely that the classification should be any of the k-assigned labels. This is not true since this is not an either-or scenario rather AND! This is where lack of independence comes in and is covered by the first sentence of the second paragraph of the answer above, and I've reposted below.

When applying the logit and taking binary cross-entropy loss, we encourage each output component to be independent of each other

