Although today's branch predictors show high accuracy, the branch misprediction penalty is getting larger due to aggressive speculation and deeper pipelining. In order to reduce the miss penalty, we propose a fast and low-cost branch recovery scheme using the incremental register renaming (IRR) and the bit-vector based rename map table (BVMT). The IRR enforces the destination register number of the instruction stream to appear in non-decreasing order. With this incremental property of the IRR, the BVMT recovery scheme completely eliminates the roll-back overhead on branch misprediction. Thus, the instruction fetcher does not stop and it fetches instructions from the correct path immediately after the misprediction detected. The goal of our scheme is to prevent a processor from flushing the pipeline, even under branch misprediction. Consequently, the BVMT instantly reconstructs the map table to any mispredicted branch and it outperforms the conventional approach by an average of 10.93%.