From the Nature abstract cited:
"There is no theoretical reason to expect evolutionary lineages to increase in complexity with time, and no empirical evidence that they do so. Nevertheless, eukaryotic cells are more complex than prokaryotic ones, animals and plants are more complex than protists, and so on. This increase in complexity may have been achieved as a result of a series of major evolutionary transitions. These involved changes in the way information is stored and transmitted."
Rather than making an entropy or information argument for complexity I think the key question is does increasing complexity allow life to get a greater return on the energy invested to support that complexity? Does more complexity allow life to access an energy niche that is impossible without that level of complexity? If we think of the energy returned on energy invested then the mitochondria makes sense, as well as photosynthesis, predation and why the human brain uses only 12 watts of power.
From anthropology we know that the Rift valley experienced gradual but dramatic shifts in climate. This allowed species to adapt slowly to change but climate change happened fast enough to discourage specialization. Species that specialized went instinct but those able to switch strategies flourished. Using fire means hominids extracted a previously untapped energy source which physiologically means we evolved smaller stomachs and bigger brains. Cooking predigests food by breaking more complex molecules into smaller ones while also killing energy sapping parasites. Fire means we do not need night vision to hunt nocturnal animals. We can use the eyeshine from fire to spot even the best camouflaged nocturnal prey and predators in the darkness. Fire means we do not need to expend as much energy to stay warm. Without fur persistence hunting is easier. Groups of people have to be able tolerate each other without fighting around a fire which makes pack hunting easier.
Technological complexity did not really take off until agriculture. There was no need for writing and historical records until the creation of the complex society needed to support larger crop yields. Even trade makes sense in terms of opportunity costs being lowered for both parties in the transaction. Your energy is better spent creating what you have a comparative advantage in producing and trading for what is harder to produce on your own.
Agriculture is odd. The average hunter-gatherer worked between 10 and 20 hours a week and the average farmer does more work and is more vulnerable to climate shocks. But it makes evolutionary sense because a little bit of extra time devoted to agriculture means that the land can support a few orders of magnitude more people than land used by hunter-gatherers.
