I can't tell you if there are 'cadenza rules', although I've never heard of any. My own approach to that song would be first to listen to Wayne Shorter's original recording of it; it starts with the piano playing a short cadenza on 3 chords unrelated to the form and it's changes. I'd do that too, probably not necessarily exactly what the piano did.
Perhaps something that starts with G-7; play low Bb as a pedal tone, or maybe G instead, or maybe alternate; with elaboration between the pedals that illustrates the chord while introducing a motif. The motif, for me, is usually going to be something from Stravinsky, Copland, Holst, or other 20th century classical composers that I like.
Then to Bb-7, again with the pedal, reiterate the motif, maybe add a 2nd one.
Then to A-7b5 with the same kind of treatment; then to D7+9+5, ending with a phrase that's picked out in advance, telling the rhythm section what it is, so everyone's on the same page on when the candenza is going to be over. Rhythm kicks themselves into the groove.
That's just me though. For an audio example of great improvised cadenza playing, check out
, Bob Mintzer playing with the Danish Radio Big Band on his composition "Flying". He is running through the changes after introducing himself with some other material, starting at 7:30. In fact, I'd guess they're playing from my transcription of his hand-written score -- the chart and parts had been sort of lost to time I think, but I wanted to play it and offered to put it into Sibelius for him for free so we could have it. I met Bob a few months ago when I went to see him with Yellowjackets -- great guy, very nice, and what a player!
