How is the VAE encoder and decoder "probabilistic"? In a VAE, my understanding is that the encoder takes in $x$, outputs a vector $(\mu, \sigma)$ that characterizes a certain normal distribution $q(z|x)$. Then we sample from this distribution to get a latent vector $z$, which goes into the "probabilistic" decoder to produce a generated output $\hat{x}$, which is how now, not-seen-before images, for instance, are generated in these generative models. My question is where there is randomness/stochasticity outside of the sampling from the normal in the latent representation layer. That is to say, once you learn the parameters $\theta, \phi$ that characterize the encoder and decoder neural networks, the neural networks are -- like any other neural networks -- deterministic function approximators. I can see there being an argument for the encoder "encoding a distribution" since it learns to output a vector $(\mu, \sigma)$ that characterizes a distribution, but I see no similar argument for the decoder, which will output the same $\hat{x}$ for a fixed sampled $z$ in the latent space. Similarly, would the encoder output the same $(\mu, \sigma)$ for a fixed input $x$? If so, how can the encoder be called "probabilistic" either?

In a VAE both the encoder and the decoder assign to an input a distribution. You correctly stated that for the encoder, but this is also true for the decoder: for the same latent input $\mathbf z$ you will always get the same distribution (often normal, so it is described by the decoder output $(\boldsymbol \mu, \boldsymbol\sigma^2)$), but sampling from it will give you different $\hat{\mathbf x}$ for the same $\mathbf z$.
