An approach for improving efficiency of speculative execution of instructions is disclosed. In one embodiment, a branch predictor entry associated with a particular branch instruction is accessed when the particular branch instruction is to be speculatively executed. The branch predictor entry may take on different values indicating whether a first possible path or a second possible path should be executed. Based upon a current value of the branch predictor entry, a predicted path for the particular branch instruction may be determined. Instructions along the predicted path may be executed, before the particular branch instruction is resolved. Once the particular branch instruction is resolved, a cost associated with executing the one or more instructions may be determined. Accordingly, the branch predictor entry may be updated by an amount that is commensurate with the cost.