Unordered, variable-sized inputs arise in many settings across multiple fields. The ability for set-and multiset-oriented neural networks to handle this type of input has been the focus of much work in recent years. We propose to represent multisets using complexweighted multiset automata and show how the multiset representations of certain existing neural architectures can be viewed as special cases of ours. Namely, (1) we provide a new theoretical and intuitive justification for the Transformer model's representation of positions using sinusoidal functions, and (2) we extend the DeepSets model to use complex numbers, enabling it to outperform the existing model on an extension of one of their tasks.
This paper proposed a complex weights based multiset automata designed to represent unordered data. The main idea of multiset automata is that the transition matrices of the automata is pairwise commutative. To achieve this property, the authors proposed to restrict the transition matrices to be diagonal and shows that the latter is a close approximation of the former. The authors proceed to give two practical applications of the multiset automata: position encoding of the transformer and deepset networks. For the former, the authors showed that the position encodings from Vaswani et al. can be written as a weighted unary automaton and therefore it is a generalization of the original position encodings. For the latter, the authors extended the classical deepset networks into its complex domain, allowing more efficient representation of the data. 
I think this paper overall did a good job, and I really like the construction of the multiset automata and the theoretical guarantees the authors derived and the two applications are straight-forward to see. However I do find the motivation of this paper is a bit weak,  and I’m having a hard time finding the highlight of the paper. Therefore, I’m giving this paper a weak accept.
Here are some general comments:
How is the multiset automata learnt? For weighted automata, one classical way is to use spectral learning algorithm (see Balle et. al. 2014). In this paper, the learning aspect of the multiset automata was not mentioned. I assume that the authors use some kind of gradient descent to optimize the weights w.r.t the whole networks. However, I do think it’s important to let the readers know this key step.
For the first experiment on the position encoding. I really like the derivation here and it seems that theoretically, multiset automata should be a generalization of the position encodings. However, the experiments didn’t show much difference. Is there any potential explanation here? Moreover, what is the advantage of using multiset automata in transformers instead of the original position encoding? Is it the runtime is faster? Cause you only need to compute the diagonal parameters and thus drastically reduce the number of parameters? If so, a comparison of runtime might be useful here to further showcase the advantage of the multiset automata. 
For the first application, it is great that the authors shows the connection, but it seems that it just stops at the level of showing the position encodings can be viewed as a multiset automata. For example, what happens if you don’t restrict it to be sinusoidal functions? e.g. set the transitions to be diagonal and directly optimize with gradient descent? 
For the second experiment, I’m a little confused about the experiment setup and the baselines. First how do the authors incorporate multiset automata into the deepset models? In Figure 1, every neural architectures have this embedding layers with diagonal transition matrices, does this mean the multiset automata is applied to encode the input for every architecture? If so is it possible that the use of multiset automata in LSTM, GRU and deepset, is actually hurting the performance? Maybe a comparison with vanilla LSTM, GRU and deepset is also needed. 
Moreover, for the second experiment, the size of LSTM, GRU, deepset seems to be smaller comparing to the complex product layer in the authors’ architecture (about half of the size). It is true that the authors mentioned that with non-unary automata, the size of the automata is significantly larger, but is this set-up fair for the baselines, e.g. if you use 150 size of LSTM, will it perform equally well to the multiset automata?
In addition, I have a bit of difficulty understanding why three embedding layers are needed to learn the complex number, is it possible to learn r, a, b jointly with one embedding?
Is there some real data experiment done for the second application (the extension to deepset), to further showcase the significance of using complex domain?
Here are some writing comments (did not affect the decision):
In page 6, the bullet point “Diagonal polar”, what does (#1 above) mean? Same goes for (#2 above) in the latter point. 
In “Full matrix”, the sentence “…, and transition matrix using orthogonal initialization…” does not have a verb and is a bit confusing to read. 
Page 7, second paragraph, line 4, in the brackets. There are two sentences in the brackets, and it feels a bit heavy and it actually says something important. Maybe either put it out or leave it as a footnote?
Overall, I like the concept of the multiset automata, but I feel there is a lack of highlights to further showcase this paper. I feel maybe a further investigation of either of these application could make a great paper.