It means the output shape of some operator could not be determined before you actually execute the operator.
Boolean indexing is a good example, where the shape of the output depends on the sum of the second argument index
.
>>> data = mx.nd.array([[1, 2, 3],[4, 5, 6],[7, 8, 9]])
>>> index = mx.nd.array([0, 1, 1])
>>> out = mx.nd.contrib.boolean_mask(data, index)
>>> out
[[4. 5. 6.]
[7. 8. 9.]]
<NDArray 2x3 @cpu(0)>
I am not sure it is doable in relay, we could say it is minor usability improvement, but high-level deep learning frameworks like PyTorch, TensorFlow do support this kind of operators and their shape inference.