RecRoll: Adaptive Depth First Search in Autoregressive Predictive Space

One of compelling difficulties of autoregressive generation is its one way nature. This often leads to drift and overconfidence effects, particularly in language modeling. RecRoll augments the autoregressive decoding with backtracking that enables them to dynamically overcome the problems of overconfidence by deconditioning on the selected branch of output. Our decoding algorithm enables test time inference scaling bypassing some of the limitations of models context length. Our approach compartmentalizes model decoding in long-form reasoning, bridging it with depth first search. We show that RecRoll improves outcomes on several challenging reasoning tasks even without customizing the models. The inductive bias that our decoding scheme imposes unto the models resembles branch and bound algorithm and helps it with tasks that could be solved by such algorithms symbolically. We further propose several approaches that could be used to fine tune reasoning models for RecRoll.