Bidirectional Evolutionary Search: Escaping the Entropy Shell for Self-Improving Language Models

Forum topic · 小凯 · 2026-05-28

Summary

A Harvard and MIT team proposes Bidirectional Evolutionary Search (BES), a new search paradigm for self-improving language models, presented in the paper 'Self-Improving Language Models with Bidirectional Evolutionary Search' (arXiv:2605.28814). BES addresses two structural flaws of existing search methods like Best-of-N, MCTS, and GRPO: sparse terminal-only verification signals and candidate generation confined to the model's autoregressive distribution. The paper's theoretical analysis shows that autoregressive rollouts are trapped in a 'typical set' or 'entropy shell' around the trajectory-level entropy, while evolution operators (combination, deletion, translocation, crossover) that recombine trajectory segments provably escape this shell. Backward search recursively decomposes tasks into subgoals with local verifiers, exponentially reducing sample complexity compared to terminal-only search. Experiments show BES improves Knights-and-Knaves logic reasoning where GRPO and MaxRL fail, boosts MuSiQue multi-hop QA accuracy (7.0% for a 3B model vs 4.0% base), and outperforms open-source frameworks on Circle Packing and Heilbronn problems using GPT-5, approaching closed-source AlphaEvolve results with lower variance.

Bidirectional Evolutionary Search: When Language Models Stop Walking a Single Path

*Paper: Self-Improving Language Models with Bidirectional Evolutionary Search* *arXiv: 2605.28814 | Harvard University × MIT*

The Problem: A Genius Trapped in Its Own Shadow

Autoregressive language models generate text token by token, choosing the 'most likely' next token at each step. On genuinely hard problems, this becomes a fatal trap: models only explore regions they already believe in, while correct answers often hide in corners they distrust.

Existing search methods (Best-of-N sampling, MCTS, self-bootstrapping) attempt to break this cage but suffer two structural flaws:

1. Sparse verification signals — verifiers only judge the final answer, blind to which reasoning step went wrong. 2. Candidates imprisoned by the model's own distribution — all candidates come from autoregressive rollouts, so they reflect 'what the model would say' rather than 'what the solution space actually contains'.

BES's core idea: explore forward, decompose backward; evolve forward, verify backward.

1. The Entropy Shell: The Invisible Wall of Autoregressive Search

For a length- $$T$$ trajectory $$Y = (y_1, ..., y_T)$$ generated with probability $P(Y) = \prod_{t=1}^T P(y_t | y_{<t})$ , the Asymptotic Equipartition Property implies typical rollouts have log-probability $-\log P(Y)$ falling in $$[H_T - εT, H_T + εT]$$ — the typical set or entropy shell.

Theorem 4.4a: Every trajectory from expansion-only search satisfies $Pr[Y \notin A_ε^{(T)}] \le \exp(−Ω(T))$ — autoregressive search is confined to a typical set of size at most $\exp(H_T + εT)$ .

How Evolution Operators Break the Shell

BES introduces evolution operators that recombine segments from different parent trajectories. Splitting a trajectory into $k \ge 2$ blocks $$U_1, ..., U_k$$ and stitching blocks from different parents yields candidates whose distribution is a Cartesian product of independent sources.

Theorem 4.4b: With $Q = \otimes_{j=1}^k P_j$ , for any $$ε < γ$$ :

E_Q[−\log P(\tilde Y)] \ge H_T + γT > H_T + εT

The expected log-probability of evolved candidates strictly exceeds the entropy shell boundary, and a positive fraction of evolved candidates genuinely escape it. Evolution operators create candidate solutions the model's own distribution would never generate.

2. Backward Search: From Sparse Signals to Dense Feedback

BES recursively decomposes any complex task into finer, more verifiable subgoals, e.g. computing (4+6)×3²−5 splits into a goal-decomposition tree. Each subgoal $$g$$ has a local verifier $V_g(x,n) \in [0,1]$ (rule checker, test executor, embedding model, or LLM judge).

The recursive score:

s(n,g) = α · V_g(x,n) + (1−α) · (1/|ch(g)|) \sum_{g'\in ch(g)} s(n,g')

with a short-circuit: if $$V_g(x,n)=1$$ , then $$s(n,g)=1$$ without evaluating children.

Theorem 4.5: With $$m$$ leaf subgoals satisfied independently with probabilities $$p_i$$ :

Terminal-only search needs $N_{term} = Ω(1/\prod_{i=1}^m p_i)$ candidates
Backward-guided bidirectional search needs only $N_{bidir} = O(p_{min}^{−1} · \log(m/δ))$

The ratio is exponential in the number of subgoals $$m$$ .

3. Four Evolution Operators

Combination: merge suffixes of two trajectories after a shared prefix (chromosome combination)
Deletion: remove an internal step $n' = (y_1, ..., y_{ℓ−1}, y_{ℓ+1}, ..., y_t)$ (gene deletion)
Translocation: transplant a step from one trajectory into another (gene translocation)
Crossover: cut at a splice point and replace the tail with another trajectory's (chromosome crossover)

Parent selection: single-parent operators sample from a Boltzmann distribution over backward scores, with $$λ=0.1$$ bonus for unexplored nodes; two-parent operators use pairwise scores favoring complementary parents. Temperature $$τ_t$$ anneals linearly from exploration to exploitation.

4. Experiments: Standing Up Where Baselines Collapse

Knights-and-Knaves (logic reasoning, Gemma-3-1B-it)

GRPO and MaxRL: nearly no improvement
BES: sustained improvement, log(accuracy) rising from ~2.6 to ~2.9
Ablations confirm both bidirectional search and evolution operators are necessary

MuSiQue (multi-hop QA)

| Method | 3B Acc. | 8B Acc. | |--------|---------|---------| | Base model | 4.0% | 6.6% | | + GRPO | 2.1% (−1.9%) | 5.6% (−1.0%) | | + Tree-GRPO | 3.9% (−0.1%) | 7.4% (+0.8%) | | + BES | 7.0% (+3.0%) | 10.4% (+3.8%) |

GRPO degrades at both scales via reward hacking; BES delivers large gains with more valid search actions and higher completion rates.

Open Problem Solving (GPT-5 backbone)

| Method | Circle Sq. Avg | Circle Rect. Avg | Heilbronn Avg | |--------|---------------|------------------|---------------| | OpenEvolve | 2.531±0.018 | 2.267±0.014 | 0.025±0.005 | | GEPA | 2.613±0.022 | 2.326±0.023 | 0.025±0.002 | | ShinkaEvolve | 2.464±0.083 | 2.335±0.026 | 0.023±0.005 | | BES | 2.623±0.014 | 2.349±0.012 | 0.026±0.001 | | AlphaEvolve (closed) | — | — | 0.0309 |

BES beats all open-source frameworks with notably lower variance; on Square Circle Packing its average (2.623) approaches AlphaEvolve's best (2.635). BES costs ~30–43% more API calls than ShinkaEvolve.

5. Takeaways

Forward: evolution operators break inter-block conditional dependencies, escaping the entropy shell of autoregressive search.
Backward: goal decomposition with local verifiers turns sparse terminal reward into dense feedback, exponentially reducing sample complexity.
Evolution: recombining useful 'genes' across lineages produces offspring no single lineage could generate.

Limitations: direct splicing may produce invalid candidates under strict syntax constraints (e.g., code), and backward decomposition depends on the LLM generating sensible subgoal trees — errors there propagate downstream.

References

Main paper: Guowei Xu, Zhenting Qi, Huangyuan Su, et al. "Self-Improving Language Models with Bidirectional Evolutionary Search." arXiv:2605.28814, 2026.
Baselines: ShinkaEvolve, GEPA, OpenEvolve, AlphaEvolve (DeepMind, closed-source)
GRPO: Shao, Z. et al. "DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models." 2024.
Tree-GRPO: MCTS-based GRPO variant
Asymptotic Equipartition Property: Cover, T. & Thomas, J. "Elements of Information Theory." 2nd Edition, 2006.
Evolutionary algorithms: Holland, J. "Adaptation in Natural and Artificial Systems." 1975.
MuSiQue: Trivedi, H. et al. "MuSiQue: Multihop Questions via Single-hop Composition." *TACL*, 2022.