Conditional branch bytecodes are processed by a Virtual Machine Interpreter (VMI) hardware accelerator that utilizes a branch prediction scheme to determine whether to speculatively process bytecodes while waiting for the CPU to return a condition control variable. The VMI assumes the branch condition will be fulfilled if a conditional branch bytecode calls for a backward jump and that the branch condition will not be fulfilled if a conditional branch bytecode calls for a forward jump. Alternatively, the VMI makes an assumption only if a conditional branch bytecode calls for a backward jump or the VMI assumes that the branch condition will be fulfilled whenever it processes a conditional branch bytecode. The VMI only speculatively processes bytecodes that are easily reversible, and suspends speculative processing of bytecodes upon encountering a bytecode that is not easily reversible. If a VMI assumption is invalidated, any speculatively processed bytecodes are reversed.