I left before they had decided what to do.
Is this because this is a past version of "I leave before they have decided what to do"?
Because "left" doesn't come before "decided".
There is a meaning distinction between these:
I left before they decided what to do.
I left before they had decided what to do.
The first one can have the nuance: I left specifically not to be there when they decide. The second one does not, and that form with the perfect would be used when the speaker wants to make it clear "I left before they decided, but not in order to avoid their decision".
This is essentially what the perfect aspect is doing, and is probably the reason why it doesn't matter that "to leave" takes place before "to decide". The point is that the action of leaving takes place before the the action of deciding is complete, i.e. perfect! "I did not run away to avoid the decision-making; I was just not there when that action completed". The completeness is expressed using the perfect aspect, and since this is all in the past it becomes the past perfect: the timing of a simple past is compared to the time of completion of a past perfect.
Perhaps these examples can make the semantic side of it clearer:
I signed the contract before they changed their minds. [Possibly: I signed the contract quickly so that they had no chance to change their minds.]
I signed the contract before they had changed their minds. [When they said they changed their minds, they did not now that it was already too late: I signed the contract, making it binding.]
What is the present version? In modern English we don't use forms like "now I eat breakfast" or "I go to work". These come across as archaic. Rather, the gerund forms are used -- unless it is about habitual performance, such as "I usually eat breakfast just before I go to work". This does not apply to one time actions or actions at the moment. So the present tense of your sentence is this:
I am leaving before they have decided what to do.
And it means: I am leaving, and as I leave, they are still undecided..
If we remove the perfect, it changes:
I am leaving before they decide what to do.
And now it it means: I am leaving specifically not to be there when they decide what to do.
The past tense doesn't strictly have the "in order to" nuance, but the present does.
I left before the police arrived. [Just stating a fact; or perhaps I left in order not to be there when the police arrived. Other choice of words can make it clearer, of course, like: I ran before the police arrived, etc.]
I am leaving before the police arrive. [I am avoiding the police.]
I am leaving before the police have arrived. [It looks like I am leaving the scene while the police are not yet here.]
Lastly note that forms like "I am leaving before they have decided" are not that common in everyday speech. This sounds very contrived; perhaps one might use it in a letter or other writing. It has the air of a detached commentary on the situation. It's better said like "I'm leaving them undecided"; "They are still undecided as I'm leaving"; "They haven't decided though I'm already leaving"; and similar.
Swan in Practical English Usage (p98) addresses this issue in his section on before:
In clauses with before, we often use present and perfect tenses to emphasise the idea of completion.
- He went out before I had finished my sentence. (= ... before the moment when I had completed my sentence.)
Note that in sentences like this, a past perfect tense can refer to a time later than the action of the main verb. This is unusual.
The perfect tense puts emphasis on completion. It points to the fact that something has been completed recently or is in process. So in this example a perfect tense in the second clause makes the allusion that they were in the process of making a decision but the narrator didn't wait for it to be done. It might even mean his leaving resulted in the decision not happening at all. The simple past tense carries no such implication. Another example would be: Their fuel ran out before they had crossed the border. Here the action in the second clause didn't happen at all because of the first event. A past tense may also not feel out of place here, but the perfect tense really puts the emphasis on the incompleteness of the action
You're right. Your sentence is the past form of I leave before they have decided what to do. The past form of leave is left, and the past form of have decided is had decided.
I think you are confused, because somebody taught you that you should use the past perfect in the case where one thing in the past comes before another in the past. This is true, but it's not the only way to use the past perfect.
To answer Mari-Lou A's question in the comments.
We also use the past perfect when we have something that's in the past tense, and we need to put it in the past tense again. It's like a double past tense.
For instance, compare these:
I bought a lottery ticket:
If I win the lottery, I will quit my job.
Use past tense to show that I didn't buy a ticket.
If I won the lottery, I would quit my job.
Now use the "double past" tense to show that it's an imaginary scenario in the past:
If I had won the lottery, I would have quit my job.