The product replacement graph (PRG) of a group $G$ is the set of generating $k$-tuples of $G$, with edges corresponding to Nielsen moves. It is conjectured that PRGs of infinite groups are nonamenable. We verify that PRGs have exponential growth when $G$ has polynomial growth or exponential growth, and show that this also holds for a group of intermediate growth: the Grigorchuk group. We also provide some sufficient conditions for nonamenability of the PRG, which cover elementary amenable groups, linear groups, and hyperbolic groups.