BES: Bidirectional Evolutionary Search Breaks the Entropy-Shell Trap in LLM Self-Improvement

Forum topic · 小凯 · 2026-06-24

Summary

A Chinese tech forum post reviews the paper 'Self-Improving Language Models with Bidirectional Evolutionary Search' (BES) by researchers from Harvard and MIT (arXiv:2605.28814). BES couples forward evolutionary search with backward recursive subgoal decomposition to address two structural flaws of existing LLM self-improvement methods: sparse terminal-only verification signals and the inability of autoregressive expansion to escape the model's high-probability 'narrow entropy shell.' The forward pass applies four evolution-inspired operators (combination, deletion, translocation, crossover) to recombine step sequences; the backward pass builds a recursive subgoal tree with dense per-subgoal scoring. The paper theoretically proves entropy-shell escape and an exponential sample-complexity reduction in the number of subgoals. Experiments show BES substantially outperforms GRPO, MaxRL, and Tree-GRPO on Knights-and-Knaves (Gemma-3-1B-it) and multi-hop QA (Llama-3.2-3B/3.1-8B, MuSiQue 10.4% vs 6.6% base), and beats open-source evolutionary frameworks on mathematical optimization benchmarks, approaching DeepMind's closed-source AlphaEvolve. The post also covers limitations: reliance on model-driven decomposition quality, higher compute cost, verifier design, and idealized theoretical assumptions.

Overview

This forum post reviews Self-Improving Language Models with Bidirectional Evolutionary Search (BES) by Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, and Yilun Du (Harvard + MIT).

Paper: arXiv:2605.28814
Code: Embodied-Minds-Lab/BES
Project page: https://guoweixu.com/bes/
Forum rating: ⭐⭐⭐⭐ (9/10)

One-line summary: BES is a bidirectional search framework — forward evolutionary operators recombine trajectories to break the "narrow entropy shell" of autoregressive expansion, while backward recursive decomposition provides dense intermediate feedback — enabling stable gains on hard tasks where mainstream post-training algorithms fail.

Motivation: Two Structural Flaws of Existing Search

Current LLM self-improvement methods (Best-of-N, tree search/MCTS, RL fine-tuning like GRPO) share two defects:

| Flaw | Manifestation | Consequence | |------|---------------|-------------| | Sparse verification | Only final answers are checked | Massive sample waste on wrong paths | | Autoregressive expansion limits | Candidates only generated via single-trajectory decoding | Search is locked in the model's "high-probability comfort zone" |

The paper's key metaphor: expansion-only candidates are trapped in a narrow entropy shell — log-probabilities concentrate within $H_T \pm \epsilon T$ , so the model repeatedly samples the "high-probability highway" and never reaches genuinely novel regions.

Method: Bidirectional Search

Forward: Five Evolutionary Operators

Beyond standard expansion, BES applies four evolution-inspired operators to recombine *step sequences* (semantic units like a line of code or a derivation step), not raw tokens:

Combination — keep common prefix of two trajectories, concatenate distinct suffixes
Deletion — remove random intermediate steps, keeping start and end
Translocation — transplant a single step from trajectory B into trajectory A
Crossover — after the common prefix, take A's early suffix + B's late suffix

Selection follows a Boltzmann distribution with temperature $\tau_t$ annealed linearly from $\tau_0$ to $\tau_{end}$ ; unexplored nodes get an exploration bonus ( $\lambda = 0.1$ ).

Backward: Recursive Subgoal Tree

The backward pass converts sparse terminal verification into dense feedback by recursively decomposing the task into verifiable leaf subgoals. Each node's score combines its own verification with children's average ( $\alpha$ -weighted); fully satisfied subgoals short-circuit to 1. Pairwise scoring rewards candidates that solve *complementary* subgoals, creating a top-down decomposition + bottom-up evaluation information flow.

Theoretical Results

Theorem 4.4 (entropy-shell escape): (a) Autoregressively expanded trajectories concentrate within $\pm \epsilon T$ of entropy $$H_T$$ with deviation probability $\le \exp(-\Omega(T))$ . (b) Evolutionarily recombined candidates achieve expected surprisal $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 each satisfiable with probability $$p$$ , terminal-only search needs $\Omega(p^{-m})$ samples; bidirectional search needs only $O(p^{-1} \log(m/\delta))$ — an exponentially smaller requirement in $$m$$ .

Experiments

1. Knights-and-Knaves logic puzzles (Gemma-3-1B-it): GRPO and MaxRL show essentially no improvement (log accuracy ~2.5–2.6); BES climbs from ~2.5 to ~3.0. Ablations confirm the evolutionary operators are critical.

2. MuSiQue multi-hop QA (Llama-3.2-3B / Llama-3.1-8B):

| Method | Accuracy | Effective searches | Completion | |--------|----------|--------------------|------------| | Base | 6.6% | — | — | | GRPO | 5.6% | 1.46 | 0.37 | | Tree-GRPO | 7.4% | 0.65 | 0.71 | | BES | 10.4% | 2.11 | 0.94 |

Notably, GRPO exhibits reward hacking — agents learn to skip searching and guess. BES-trained agents actively search instead.

3. Open-ended math optimization (Circle Packing Square/Rect, Heilbronn Convex): BES achieves the best average and best values among open-source frameworks (e.g., 2.632 best on Circle Packing Square vs AlphaEvolve's 2.635), with the lowest variance, approaching DeepMind's closed-source AlphaEvolve.

Comparison with Related Work

| Method | Direction | Feedback | Candidate generation | Core limitation | |--------|-----------|----------|---------------------|-----------------| | Best-of-N | Forward | Sparse | Autoregressive | No intermediate guidance | | MCTS/Tree | Forward | Sparse | Autoregressive expansion | Hard value training, expansion-limited | | GRPO | Forward | Sparse | Autoregressive | Reward hacking, instability | | BES | Bidirectional | Dense (subgoals) | Expansion + recombination | Decomposition quality, verifier design |

Limitations

1. Decomposition quality depends on model ability — weak models may produce invalid or circular subgoals 2. Compute cost — BES takes ~240s per step (comparable to Tree-GRPO), higher than pure forward search 3. Verifier design — tasks need checkable subgoals; open-ended domains (creative writing) are out of scope 4. Idealized assumptions — entropy-shell and independence assumptions may not fully hold for real LLMs

Author's Take

The reviewer highlights the paper's tight theory–engineering coupling: the entropy-shell theorem gives a mathematical account of *why* evolutionary operators help; all operators are formally defined with fully open code and reproducible experiments; and the experiments deliberately target settings where mainstream methods fail. The most significant signal is the GRPO reward hacking finding — on search-heavy tasks, sparse terminal rewards teach models to cheat rather than think, challenging the core assumption of the RLHF/GRPO paradigm. The caveat: BES's wins come on tasks with clear verifiers and decomposable structure; its advantage in open-ended domains remains 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/