Attacks on LCG with "self-XOR" output function?
To answer my own question, after some research and experimentation I came up with a fast algorithm to break such constructions (in fact the approach below works even if the increment $C$ is unknown).

As a preprocessing step, find a set of $m$ small weights $\lvert w_i \rvert &lt; W$ such that

$$\sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1}$$
where $k$ is some small integer defined later. Such a set of weights can be found rather efficiently (and in polynomial time in general) through lattice basis reduction, e.g. running LLL on the following lattice basis:
$$
\begin{bmatrix}
K A &amp; K A^2 &amp; \dots &amp; K A^m &amp; K \cdot 2^{n/2 + k} \\
1 &amp; 0 &amp; \dots &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; \dots &amp; 0 &amp; 0 \\
\vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; 0 \\
0 &amp; 0 &amp; \dots &amp; 1 &amp; 0
\end{bmatrix}
$$
for sufficiently large $K$, as shown by Lagarias and Odlyzko. In practice we expect such weights to exist when
$$m \log_2(W) \approx n/2 + k$$

Guess the lower $k$ bits of $X_0$, and use the LCG property to derive the lower $k$ bits of all $X_i$.

Use the $Y_i$ to obtain the lower $k$ bits of the upper half of all $X_i$. Denote $X^*_i$ as $X_i$ masked to only include those guessed upper bits, that is, $X^*_i = 2^{n/2} \times \mathrm{guess}$.

If we do some basic algebra we can notice that the congruence below follows from (1)


$$
\sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2}
$$

Since the $w_i$ are bounded by $W$ and we know the most significant bits of the variables involved, we can approximate this sum using our $X^*_i$. In fact we can evaluate it to within $\pm 2 m W \cdot 2^{n/2}$. Compute:

$$
Z = \sum_{i = 1}^{m} w_i \left [ X^*_{i + 1} - X^*_i \right ] \bmod{2^{n/2 + k}}
$$
and let $\Delta$ be the difference between $Z$ and either 0 or $2^{n/2 + k}$, whichever is closest to $Z$.

If $\Delta \geq 2mW \cdot 2^{n/2}$, our guess to the lower bits of $X_0$ is certainly incorrect. Otherwise, it is correct with probability $1 - 2mW \cdot 2^{-k}$ (this makes some assumptions about the distribution of the $Y_i$, but works in practice).

Try all $2^k$ guesses against different windows of outputs $Y_i$ (adjusting accordingly, note that the relation (1) still holds even if you shift all exponents by a fixed constant) until all but one fail to pass the test in step 6. The final candidate guess will be the lower bits of $X_0$.

Repeat all steps, guessing successively higher bits of $X_0$ until the entire internal state is recovered.


This turns out to be very fast as $k$ can be set to be not too much larger than $\log_2{mW}$, for the probability of a false positive in step 6 to be sufficiently small, e.g. 0.5; if $k$ is too small then we extract no information.
Given the above, we should try to force $W$ to be as small as possible in step 1 to minimize the number of bits $k$ to guess, so that, for example, $W \approx 2$, $m \approx n/2 + k$ so $k \approx \log_2(n)$ showing that this attack should scale very well with $n$.
I've implemented this and it works well and successfully recovers the internal state as expected for $n = 128$.
Also it's possible to extend this to unknown increment $C$, the only thing that changes is we need to guess the lower bits of $C$ at the same time as the lower bits of $X_0$ to be able to perform step 2, and everything else stays the same; we recover $C$ and $X_0$ simultaneously through the same process.

References
This approach was adapted from techniques described in &quot;Lattice Reduction: a Toolbox for the Cryptanalyst&quot;. This paper contains even more sophisticated techniques for attacking similar kinds of problems and is fairly readable.