Weaknesses
The paper has an important theoretical flaw, which is that the constructed lexinvariant LM *may not* be an LM. Let’s consider a concrete example:
In the paper, the authors claim that, given an arbitrary LM $p(\dotsm)$, one can construct a lexinvariant “LM” (call it $p'$) that is “almost equivalent” to $p$. The specific construction offered by the authors is $p'(x_1,\dots,x_n)=\mathbb{E}_{\pi}[p(\pi^{-1}(x_1),\dots,\pi^{-1}(x_n))]$. However, problems arise upon closer inspection. By this definition, we first have
$$
p'(X_1=x_1,X_2=x_2)=\frac{1}{2}p(X_1=x_1,X_2=x_2)+\frac{1}{2}p(X_1=x_2,X_2=x_1).
$$
On the other hand,
$$
p'(X_1=x_1,X_2=x_2,X_3=x_3)=\frac{1}{6}\sum_{\pi\in S_3}p(X_1=x_{\pi^{-1}(1)},X_2=x_{\pi^{-1}(2)},X_3=x_{\pi^{-1}(3)}).
$$
When we marginalize the above over $X_3$, we get
$$
p'(X_1=x_1,X_2=x_2)=\frac{1}{6}\Big(
p(X_1=x_1,X_2=x_2)+
p(X_1=x_1,X_3=x_1)+
p(X_1=x_2,X_2=x_1)+
p(X_1=x_2,X_3=x_1)+
p(X_2=x_1,X_3=x_2)+
p(X_2=x_2,X_3=x_1)
\Big).
$$
We can clearly see that, for most LM’s, the above doesn’t agree with the first marginal (unless they satisfy very special conditions)! This shows that, the constructed lexinvariant “LM” isn’t in fact an “LM”. It’s a sequence of incompatible joint distributions. In other words, one cannot construct a stochastic process based on the definition of $p'$ by invoking Kolmogorov’s extension theorem, because the marginals are incompatible.
Based on the this, the paper’s various premises and conclusions start to fall apart.
First of all, Theorem 2.1 becomes a “correct” but irrelevant result (it is slightly incorect in the sense that $p'$ is no longer a languge model). At best, Theorem 2.1 can be interpreted as that for an arbitrary LM, there exists a sequence of (incomptaible) conditional distributions such that, when $x_{1:T}$ is sampled from $p$, w.h.p., the (incompatible) conditionals are close to conditionals of $p$ (this is what appears to be what the proof is proving, though I have not checked the 6-page proof in the appendix too closely and can’t speak to its correctness). Such an understanding of this result would significantly undermine various claims in the paper in the following ways:
1. First, one cannot conclude from the paper that given an arbitrary LM, there exists a “symmetrized” (i.e., lexinvariant) approximation of it. Therefore, one cannot, at least in theory, conclude that as the context gets longer, the “distance” between some lexinvariant model to an arbitrary LM will approach 0.
1. It is also quite likely that there exists such counterexamples — an LM in which no symmetric LM is a good approximation of it over any context length. If the authors are trying to provide a proof in that direction in the future, they may want to make an attempt at finding such counterexamples.
2. Furthermore, the empirical evidence is inconclusive as to the question of whether the specific implementation of the lexinvariant LM approximates the true conditionals. One may also look at Figure 3 and 7 and say that the perplexity curves have flattened out and that there is a systemic bias between the lexinvariant model and the standard language model.
2. Next, since $p'(\dotsm)$ is a sequence of incompatible joints, it is unclear if sampling from such a sequence of conditionals will yield something that can be justified.
If the authors cannot repair this theoretical flaw, I cannot recommend the paper accepted as-is since the paper’s current narrative revolves around a “theoretical proof then empirical validation” narrative. If the theory turns out to be irreparable, the paper should be rephrased as a series of experiments without theoretical underpinnings.
Finally, a minor detail is that the presentation frequently switches notation for unclear reasons, which is very confusing. Most notably, it is unclear why the paper sometimes use $p$ but then immediately switches to $\mathcal{P}$ (e.g., in Eq.(3), $\mathcal{P}$ appears without introduction; similar situation happens in line 481).