FLEET Algorithm Enhances Best-of-N Generation by Integrating Reward History into MCTS

FLEET is a new algorithm designed to enhance Best-of-N generation by making the sampling process aware of previous external rewards. Instead of blind sampling, it attributes rewards to specific tokens and uses Monte Carlo Tree Search (MCTS) to adjust logits for subsequent runs.

How It Works

The method identifies branching points by tracking logits with high entropy and varentropy, indicating model uncertainty. These states are stored in a vector store with metadata containing reward history and transition data. Retrieval uses cosine similarity, ensuring that high similarity corresponds to low KL divergence, preserving meaningful tokens. FLEET then modifies MCTS to rank top-k tokens and penalize suboptimal ones before applying the decoding strategy.

Performance Results

Tested on Llama 3.2 3B with greedy decoding and a penalty set to effectively zero probability for suboptimal tokens:

• GSM8K: Reached the sampling baseline with half the iterations (solving seven more tasks).
• LiveCodeBench v6 (easy split): Increased the score from 0.59 to 0.69 under the same budget, reaching the baseline in 9 iterations compared to 32.

The metadata store can be preserved as a prior for other tasks or used to enrich SFT/RL training.