It depends on your definitions. How do you define complex society? And how do you define taxes?

I would argue that any society is inherently a complex society regardless of scale, population, or continuity. A society requires the navigation of social and cultural rules that are both explicitly and implicitly taught. Complexity does not necessarily need monumental architecture in large urban settlements with a high degree of technological use. Complex could be as simple as a dense network of social bonds between kin, friends, and community members that is used to define rank. There does not exist a simple society.

Taxes also need to be defined. If you mean taxes to strictly be the payment of one person to a political authority using hard currency like coins and paper bills, there are plenty of complex societies that did not have taxes. But if you define taxes in broader terms as any good or service that an individual must provide to a political authority on a semi-regular basis, I cannot think of a complex society that did not have taxes.

Using this broader term for tax, taxes could be as simple as providing a portion of your year's crops to elites or religious leaders. It could also mean taking up arms to defend your community from outside attack should the need arise. And it could also mean dedicating a portion of the dry season to maintaining a religious structure, expanding an elite's house, maintaining community irrigation systems, constructing a new temple, etc.

Even societies in which power is shared among a group of elites in a corporate framework can achieve very complex societies. Teotihuacan of the Late Formative to Classic period (~100 BC - 600/700 AD) in the Basin of Mexico is a great example of a corporate system being able to achieve great success by constructing some of the largest pyramids in Mexico and having influence as far away as Guatemala. This was presumably accomplished by extracting tribute and labor from the city's citizens and possibly other allied or conquered settlements in the region. On the other hand, corporate power structures may be limited and can exert very little influence outside of their immediate area, such as the Teuchitlan culture of Jalisco, Mexico (300 BC - 550 AD) that I research. In the Tequila valleys where the Teuchitlan culture existed, elites did not have elaborate or large residential structures. They lived in simple homes on small platforms just like commoners. They expressed their power by extracting tribute in the form of labor to construct their bulls-eye shaped religious structures called guachimontones. These temples are the largest buildings in the area other than some ballcourts to play the Mesoamerican ballgame. The only other expression of power that elites had was in the form of their tomb in which they were buried. Elites that had more power were able to dig deeper shafts and more chambers for their remains and the remains of their family to be placed within. They also were able to be buried with a much larger number and higher quality grave goods than commoners. Commoners were often buried in simple pits with little to no grave goods.

Both of these examples differ greatly from the contemporary Maya ajaws to the south or the later Aztec huey tlatoani of the Postclassic/Contact period. In both of those cases power was held by a single individual rather than a group. But like Teotihuacan's rulers and the elites of the Teuchitlan culture, the Maya and Aztec extracted goods and labor as tribute from people rather than hard currency.

If someone does have an example of a complex society without taxes in the way that I have defined these terms, I would appreciate learning of it.