I know that Crytek use random jittering for their shadow map sampling to blur out any aliasing. But I dont understand how they get soft shadows in the case where the ShadowMap/Screenspace pixel density are very close to each other.

For example, take a scene where the pixel density for the shadow map was suitably match up, ie the case when you dont see any aliasing. In this case, when they sample the surrounding pixels of the shadow map, due to the pixel density being good, random shadow map samples would appear very close to the screenspace pixel and you would get sharp edges.

Such as in the case when applying PCF to a frame with very high resolution shadowmaps, that dont exhibit aliasing. You barely see the softness.

I guess what Im saying is that as you increase the shadow map size, wouldnt you also have to increase the sampling radius?

Keep the number of samples the same for speed, but maybe increase the amount by which each sample can be jittered? Or maybe some kind of screen-space solution?

Here's a screen-space blurring. Of course, in screen space, all blurs will give the same result regardless of pixel / shadow map texel ratio
http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/soft-edged-shadows-r2193

I was hoping to know how they determine how far out to make the samples. How can you determine the pixel / shadowmap texel ratio, in order to spread out the samples by more or less?