Pastoralism is a logical evolution of hunting after animals became domesticated. My point is that you didn't necessarily need a large hierarchical society to fend off against one.
The Huns and Mongols absolutely did have large hierarchical societies, though. The Mongol army had a decimal system organizing forces into groups of 10, 100, 1,000, and 10,000 men. This is about as explicitly hierarchical as it gets.