At CRYPTO 2008 Stam [8] conjectured that if an $$m\!+\!s$$-bit to s-bit compression function F makes r calls to a primitive f of n-bit input, then a collision for F can be obtained with high probability using $$r2^{nr-m/r+1}$$ queries to f, which is sometimes less than the birthday bound. Steinberger [9] proved Stam's conjecture up to a constant multiplicative factor for most cases in which $$r = 1$$ and for certain other cases that reduce to the case $$r = 1$$. In this paper we prove the general case of Stam's conjecture also up to a constant multiplicative factor. Our result is qualitatively different from Steinberger's, moreover, as we show the following novel threshold phenomenon: that exponentially many more exactly, $$2^{s-2m-n/r+1}$$ collisions are obtained with high probability after $$O1r2^{nr-m/r+1}$$ queries. This in particular shows that threshold phenomena observed in practical compression functions such as JH are, in fact, unavoidable for compression functions with those parameters.