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.