This is a really interesting question and i've found there are three ways of dealing with it that i think are satisfying, obviously you can handle it however you want but these three work IMO:
1- Don't branch at each choice, rather think of the plot as linear but each choice records a value for the answer, say a value of 1,2 or 3, those values only pertain to certain events, that way when those choices become relevant you can pull a value check and tailor the content to fit, the main direction of the story doesn't then branch all the time rather you build up a series of values that are effectively context to the story, for example across 10 choices the first three effect everyone but only choice 5 and 7 really effect a specific character making the thing not route or branch dependant rather it's based on check of stored values.
This changes the "diagram" for the game from the branch of death thing to a line that picks up values as you go and then, when needed splits into a series of potential outcomes that then recombine into the main storyline again, of course continuity does become a problem but it's certainly a far better option than exponential numbers of branches.
2- Don't branch, web, different choices can end up with the same result, choices tie back together, perhaps the different routes share common elements and then go their separate ways again, "branches" aren't discrete, they dip in and out of each other in the way described by the train lines metaphor, choices just push you to a new line for while but ultimately the player can "recover" from certain choices this way, it's quite forgiving i've tried writing a game this way and it does work, however continuity can become a massive pain in the ass if the game goes on too long, the problem isn't that each branch bogs you down it's the potential routes that a player can go through before a given scene and tailoring the scene to fit it means lots of scene variants rather than lots of different scenes, it can become a head thrash if you too closely interlink scenes but a huge work load if you don't link closely enough, tough to do but it does work to a degree.
3- keep everything as discrete as possible for as long as possible. Be very conservative with branches to begin with, give choices but just store the outcomes, then when the story reaches a turning point apply the combined result of those choices, you'd need lots of if, and , not, or, xor logic stuff at the turning point but in that way you can reduce your work load by making each branching point further apart and more significant each time rather than over branching and making them feel less significant. This also could be useful narratively, it would give you a "steady state" to work in for a little while and give flavour and airtime to certain elements while accruing choice outcomes for the next major plot upheaval.
There is no perfect answer by any means but i agree with the fact that more freedom will generally lead to more work, pruning the potential "dud" choices out helps a lot as does removing choices that make no sense for the characters to make, a character with particular morality isn't going to make certain choices so screening out some potential choices would reduce work load, however this does cause there to be a "point of no return" in certain cases, it's a tough call for sure.