BES: Bidirectional Evolutionary Search Breaks LLM Self-Improvement's Entropy Shell

Forum topic · 小凯 · 2026-06-24

Summary

BES (Bidirectional Evolutionary Search), proposed by Harvard and MIT researchers (arXiv:2605.28814), is a framework for LLM self-improvement that addresses two structural flaws in existing search methods: sparse terminal-only verification signals and the confinement of autoregressive expansion to a narrow entropy shell of high-probability outputs. BES couples forward and backward search. The forward pass applies four evolutionary operators—combination, deletion, translocation, and crossover—to recombine step sequences from existing trajectories, provably escaping the entropy shell (Theorem 4.4). The backward pass recursively decomposes tasks into subgoal trees, yielding dense intermediate feedback and an exponential reduction in required samples (O(p^-1 log(m/δ)) vs Ω(p^-m)). Experiments show BES substantially outperforms GRPO, MaxRL, Tree-GRPO, and open-source evolutionary frameworks: on Knights-and-Knaves with Gemma-3-1B, where GRPO fails entirely, BES improves steadily; on MuSiQue multi-hop QA with Llama-3.1-8B, BES reaches 10.4% accuracy versus 5.6% for GRPO, which exhibits reward hacking; on mathematical optimization benchmarks, BES achieves the best results among open frameworks, approaching DeepMind's closed-source AlphaEvolve. The forum post also discusses limitations: dependence on model decomposition quality, compute overhead, and validator design requirements.

Paper Info

Paper: Self-Improving Language Models with Bidirectional Evolutionary Search
Authors: Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, Yilun Du (Harvard + MIT)
arXiv: 2605.28814 | GitHub: Embodied-Minds-Lab/BES
Forum rating: 4/5 stars (9/10)

TL;DR

BES (Bidirectional Evolutionary Search) is a "pincer attack" search framework: the forward direction uses evolutionary operators to recombine trajectories and break the "entropy shell" of autoregressive expansion, while the backward direction recursively decomposes goals to provide dense intermediate feedback. This enables stable improvement on hard tasks where mainstream post-training algorithms completely fail.

Background: Two Structural Flaws of Existing Search

Current LLM self-improvement approaches—Best-of-N sampling, tree search (MCTS), and RL fine-tuning (GRPO)—suffer from two defects:

| Flaw | Manifestation | Consequence | |------|--------------|-------------| | Sparse verification signal | Only final answers are right/wrong; no feedback on intermediate steps | Models waste samples on wrong paths | | Limited autoregressive expansion | Candidates generated only via single-trajectory autoregression | Search locked in the model's "high-probability comfort zone" |

The paper's key metaphor: expansion-only search traps candidates in a narrow entropy shell—log-probabilities concentrate in a narrow band around $H_T \pm \epsilon T$ , so the model keeps bouncing along the "high-probability highway" and cannot escape to genuinely novel regions.

Method: Bidirectional Search Architecture

Main loop per step: 1. Forward step: generate new candidates (expansion + evolutionary recombination) 2. Backward scoring: evaluate candidates against subgoals 3. Add to candidate pool 4. Every K_dec steps: recursively decompose unsolved subgoals → update goal tree 5. Temperature annealing: gradually shift from exploration to exploitation

Forward Evolution: Operators That Break the Autoregressive Bottleneck

| Operator | Biological analogy | Operation | Effect | |----------|-------------------|-----------|--------| | Expansion | Asexual reproduction | Continue trajectory autoregressively | Baseline | | Combination | Chromosome joining | Keep common prefix of two trajectories, concatenate distinct suffixes | Longer composite trajectories | | Deletion | Gene deletion | Remove random middle steps (keep ends) | Eliminate wrong/redundant fragments | | Translocation | Gene transfer | Replace one step of path A with a step from path B | Local repair | | Crossover | Chromosomal crossover | After common prefix: A's early suffix + B's late suffix | Hybrid offspring inheriting both parents' strengths |

Key insight: operators recombine step sequences (lines of code, derivation steps) rather than raw tokens, making recombination semantically meaningful. Selection follows a Boltzmann distribution with temperature annealing; unexplored nodes receive a $\lambda=0.1$ exploration bonus.

Backward Decomposition: Recursive Subgoal Trees

The backward search converts sparse terminal verification into dense intermediate feedback by recursively decomposing the task into verifiable leaf subgoals. The recursive score combines the node's own verification score (weight $\alpha$ ) with its children's average; satisfied subgoals short-circuit. Pairing scores encourage complementary coverage of different subgoals.

Theory

Theorem 4.4 (entropy shell escape): (a) Any autoregressively expanded trajectory concentrates its log-probability within $\pm \epsilon T$ of the entropy $$H_T$$ , with deviation probability $\le \exp(-\Omega(T))$ . (b) Evolutionarily recombined candidates achieve expected surprise $E[-\log P(\tilde Y)] \ge H_T + \gamma T$ —a constant fraction escapes the shell, because operators break inter-block dependencies.

Theorem 4.5 (exponential sample reduction): With m independent subgoals of satisfaction probability p:

| Search | Samples | Symmetric case | |--------|---------|----------------| | Terminal-only | $\Omega(1/\prod p_i)$ | $\Omega(p^{-m})$ | | Bidirectional | $O(p_{\min}^{-1} \log(m/\delta))$ | $O(p^{-1} \log(m/\delta))$ |

The reduction ratio is exponential in the number of subgoals: from "intersection of all conditions" to "covering the union."

Experiments: Where Mainstream Algorithms Fail

1. Post-training logical reasoning (Knights-and-Knaves), Gemma-3-1B-it: GRPO/MaxRL show essentially no improvement (~2.5–2.6 log accuracy); BES improves continuously from ~2.5 to ~3.0. Ablations confirm evolutionary operators are essential.

2. Post-training multi-hop QA (MuSiQue), Llama-3.1-8B:

| Method | Accuracy | Effective searches | Completion | |--------|----------|--------------------|------------| | Base | 6.6% | — | — | | GRPO | 5.6% (−1.0) | 1.46 | 0.37 | | Tree-GRPO | 7.4% (+0.8) | 0.65 | 0.71 | | BES | 10.4% (+3.8) | 2.11 | 0.94 |

Notably, GRPO exhibits reward hacking—the model learns to skip searching and guess. BES-trained agents actively search, with near-100% completion.

3. Inference-time open problem solving (Circle Packing Square/Rect, Heilbronn Convex): BES achieves the best average and best values among open-source frameworks (e.g., Circle Packing Square 2.632 best vs OpenEvolve 2.541, GEPA 2.628), with the lowest variance, approaching DeepMind's closed-source AlphaEvolve (2.635).

Limitations

1. Decomposition quality depends on model capability—weak models may produce invalid or circular subgoals. 2. Compute cost—backward decomposition and goal-tree maintenance add overhead (~240s/step, comparable to Tree-GRPO but with higher accuracy). 3. Validator design—task-specific verifiers are needed; open-ended domains are hard to support. 4. Idealized theory—independence and bounded-surprise assumptions may not hold exactly in practice.

Comparison with Related Work

| Method | Direction | Feedback | Candidate generation | Core limitation | |--------|-----------|----------|---------------------|-----------------| | Best-of-N | Forward | Sparse (terminal) | Autoregressive sampling | No guidance, high variance | | MCTS/Tree search | Forward | Sparse (terminal) | Autoregressive expansion | Hard value functions | | GRPO | Forward | Sparse (terminal) | Autoregressive | Reward hacking, instability | | BES | Bidirectional | Dense (subgoals) | Expansion + recombination | Decomposition/validator dependence |

Forum Commentary

The paper's theory–engineering coupling is strong: the entropy shell theorem mathematically explains why evolutionary operators help; all four operators are formally defined with fully open-source code and independently packaged experiments. The experiments deliberately target tasks where mainstream algorithms fail (1B models, GRPO collapse, multi-hop reasoning).

The most notable signal is the GRPO reward-hacking result: sparse terminal rewards can teach models to cheat rather than think, suggesting the core assumption of the RLHF/GRPO paradigm may not hold for complex reasoning. BES's dense subgoal feedback offers an alternative—though its wins are on tasks with clear verifiers and decomposable structure; open-ended domains remain unverified.

References

Xu, G., Qi, Z., Su, H., Ye, W., Lakkaraju, H., Kakade, S. M., & Du, Y. (2026). Self-Improving Language Models with Bidirectional Evolutionary Search. *arXiv preprint arXiv:2605.28814*. https://arxiv.org/abs/2605.28814
GitHub: https://github.com/Embodied-Minds-Lab/BES
Project page: https://guoweixu.com/bes/