Filter stories
The idea of a filter type story is allow the player free roam initially but to track the results of their actions. In act 2 as they progress through the game the results of their actions restrict the options still open to them (and prune the branches that need to be written). In the final act they become committed to a single path which may contain few or no important choices.
Initially this looks very similar to the branching structure that was rejected for its exponential growth. However, here there are a known number of endings at the outset. Each of the blocks along the way may be complex, using one of the earlier structures.
Many dating-sim type games follow this type of story pattern. Initially the PC may have free reign to interact with potential love interests, but their actions will attract some and repel others. In the mid game their options for a partner become more limited, but interactions become more intense. Finally the player commits to one choice and the end game plays out.
Done well the player might not actually realise what is happening. They are, after all, getting the result they wanted; it's just that other players (or a repeat play through) will have a different outcome. The big disadvantage to the developer is that the end game is essentially several separate stories.