You can abstract a labyrinth into a list of possible approaches, and their stages, requirements, and results. In this way, you can choose what you want the results of different approaches to be like.
As just one possible example of this, perhaps you want the labyrinth to be a test of spiritual fortitude, and you anticipate the following approaches:
If a character follows with their right hand always on the right wall (a well-known technique that will eventually lead to an exit from most mazes), that character will start to realize their path seems quite tedious unless they are being unobservant. They may be tempted to stop doing that, but if not, they will find an exit after over an hour. However, it is the "mundane right" exit.
If a character follows with their left hand always on the left wall (an equivalent strategy to the most common), they will soon enter a part of the maze that right-hand-path followers will never reach. The maze will get darker and seem long disused, and if there were other people who could be heard from the first part of the maze, they will hear none. They will be tested for bravery and perseverance to not turn back. If they continue, they will later hear what sounds like activity and water down a right-hand passage. If they head that way, they enter the Left Temptation Sub-Maze. If they still persist in following left, they will eventually find the "far left" exit.
If a character starts using a long string to be able to keep track of their past path (the Theseus and Ariadne tactic) or dropping small items (the Hansel und Gretel tactic) or marking walls or some such, it will seem to work at first, and they will find their mark and realize which way they have come. However, they will then find they have traveled a very long time. Then they will start to have a sense of familiarity about their path. Then they will realize they are going in circles. Then they may discover a knot in the string, or the same crumbs, or altered marks. Someone else has changed their trail to a loop. Check to see if they panic. If not, and they abandon their technique, they may try a new technique. If they continue trying to use their marking technique, however, they will start to hear other footsteps. Another chance to panic. If they abandon their technique and try to avoid the other steps, they will get lost and may try another technique. If they seek out the steps, or continue using their technique, they'll meet a maze monster they'll need to deal with, and if they survive, they can continue using their technique, and will eventually find an exit.
If they use an alternating left/right pattern, they will never leave the maze until they change to another technique.
If a character ever becomes desperate, lost, or takes random passages, roll dice for every half hour, with a small chance of moving to a different part of the maze, or encountering someone else, and a very small chance of finding a "mundane exit".
If the character follows their intuition, they will be subconsciously guided by maze magic or spirits to an appropriate exit for their character.
If anyone ends up spending more than four hours in the maze, the hosts will come find you and tell you you failed your test, and lead you out.
Depending on what sort of world it is and what the spiritual fortitude theme is all about, there might be various rewards or effects of the different outcomes. I left out too a few possible details and random tables that could be added for more detail. These could also just be improvised by the GM.
A non-spiritual labyrinth could use a similar technique, but minus the meanings and the maze magic. For example, it could still be designed to lead the left and right followers to boobie-prize exits, with the more rewarding exits (it might just be a lot faster to take a different path at a certain point) requiring characters to notice clues or use their (character's) sense of direction or other senses, or to describe an approach that makes sense, or maybe just take middle paths instead of following side paths.
Another idea would be to have a maze that seems horribly complex, but then have options to follow various clues such as sounds, voices, foot tracks, strings or marks of past maze explorers, or even to follow, pursue or evade other people the PCs encounter in the maze.