After playing Braid I figured the best solution was to copy... I mean, use, the same pattern of level selection. In Bennu, each world will have a different number of levels, and to unlock the next world the player will have to complete half of the levels on the current world. On each world the player will be able to play the levels in the order he prefers (although obviously the first levels will be easier than the last ones). The exception will be the boss levels, which the player will only access after completing all the other levels in the current world. This last behaviour is yet to be implemented.
The new level selection was implemented on the game map. Below each map location, the levels are represented as spheres close to a path that represents the steps the player will have to take to finish each world. When the player completes a level its sphere will be placed upon the path, while the incomplete levels remain outside the path.
Click here for a video.