Bidirectional Evolutionary Search: Breaking the Autoregressive Bottleneck in Language Model Self-Improvement

Paper: 2605.28814 Authors: Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, Yilun Du Categories: cs.CL

The Gap

Current self-improvement methods for language models—best-of-N sampling, tree search, reinforcement learning—rely on autoregressive generation guided by sparse verification signals (right/wrong at the end). This creates two bottlenecks: (1) candidates are confined to regions where the model already assigns high probability, making it hard to discover novel solutions, and (2) without intermediate feedback, the model wastes samples exploring dead ends. The result: on hard reasoning tasks, these methods plateau or fail to improve at all.

Problem: LMs stuck in local optima
    |
    v
Assumption: Autoregressive expansion + sparse reward
            traps search in high-probability regions
    |
    v
Method: BES = Forward evolution (recombine trajectories)
              + Backward decomposition (dense subgoals)
    |
    v
Evidence: Theory (escape entropy shell, exponential sample reduction)
          + Experiments (gains where SOTA fails)
    |
    v
Conclusion: Bidirectional search breaks the bottleneck

The Increment

One sentence: Before BES, language model search was a flashlight in a dark room—you could only see where the beam pointed. After BES, you have a map that shows shortcuts and a toolkit to cut through walls.

Core Mechanism

BES operates in two coupled loops. The forward search starts with the original problem and generates candidate solutions, but instead of only extending sequences token-by-token (autoregressive expansion), it also applies evolution operators: crossover (splice two partial solutions at a common checkpoint) and mutation (replace a segment with an alternative). These operators create candidates that lie outside the model’s natural probability distribution—solutions the model wouldn’t generate in a single rollout but can recognize as valid when assembled.

The backward search takes the original task and recursively decomposes it into verifiable subgoals using the model itself. For example, “prove theorem X” becomes “prove lemma A, then use A to prove X.” Each subgoal acts as a checkpoint. The forward search can now verify progress at these intermediate points, not just at the final answer. This dense feedback steers evolution toward productive regions.

The two loops interact: backward search provides the checkpoints where forward crossover can splice trajectories, and forward search validates whether the decomposed subgoals are actually achievable. The system iterates until it finds a solution or exhausts its budget.

Original Task
     |
     v
[Backward Decomposition]
     |
     +---> Subgoal_1 ---> Subgoal_2 ---> ... ---> Final Goal
              |              |                        |
              v              v                        v
         [Checkpoints for forward search]
              ^              ^                        ^
              |              |                        |
     +--------+--------------+------------------------+
     |
[Forward Evolution]
     |
     +---> Expansion: model generates next tokens
     +---> Crossover: splice trajectory_A + trajectory_B at checkpoint
     +---> Mutation: replace segment with alternative
     |
     v
Candidate Pool ---> Verify at checkpoints ---> Keep promising ones

Think of it like navigating a maze with a team. Standard search is one person walking forward, trying every turn until they hit a dead end or the exit. BES is different: one team member (backward search) stands at the exit and works backward, marking intermediate doors that must be passed through. Another team (forward search) explores from the entrance, but instead of just walking, they can teleport between marked doors (crossover) or try alternate routes between doors (mutation). The backward markers prevent wasted exploration, and the forward recombination lets you assemble a path from fragments that individually seemed unpromising.

Key Concepts

• Entropy shell: Imagine the model’s probability distribution as a landscape where height = probability. Autoregressive sampling walks downhill from the starting point, exploring only valleys the model already knows. The “entropy shell” is the narrow band of trajectories with similar total probability—most samples land here. Evolution operators (crossover, mutation) let you jump between valleys, reaching solutions that are low-probability as complete sequences but high-value when assembled from parts. It’s the difference between walking a trail versus cutting through the forest with a machete.

• Backward decomposition: Instead of asking “what comes next?” (forward), ask “what must come before?” (backward). The model generates a plan: “To solve X, first solve Y, then Z.” Each subgoal Y, Z becomes a checkpoint. This is recursive—Y might decompose further. The key insight: verifying a subgoal is easier than verifying the final answer, so you get dense feedback. It’s like debugging code by adding print statements at every function, not just checking if the final output is correct.

• Crossover at checkpoints: Two partial solutions that reach the same intermediate state can be spliced together. If trajectory A solves subgoal Y via path P1, and trajectory B solves the final goal starting from Y via path P2, crossover creates a new candidate: P1 + P2. This candidate might never appear in the model’s top-k samples because P1 and P2 individually have low joint probability, but their combination is valid. It’s like assembling a jigsaw puzzle: two people work on different sections, then snap them together at a shared edge piece.

Framework Shift

Before (expansion-only search):        After (BES):

Start                                  Start
  |                                      |
  v                                      v
[Autoregressive Expansion]          [Backward Decomposition]
  |                                      |
  +---> Token_1                          +---> Subgoal_1 --> Subgoal_2 --> Goal
  +---> Token_2                               ^         ^              ^
  +---> ...                                   |         |              |
  +---> Token_N                          [Forward Evolution]
  |                                           |
  v                                           +---> Expand
Verify: Right/Wrong?                          +---> Crossover (splice at subgoals)
                                              +---> Mutate (replace segments)
(Confined to high-prob regions,               |
 sparse feedback at end only)                 v
                                         Verify at each subgoal
                                         (Dense feedback, escape prob. shell)

One sentence: From walking a single path in the model’s probability landscape to building a map of the terrain and teleporting between waypoints.

Expert Assessment

Problem choice: This is a real gap. The autoregressive bottleneck is well-known in the community—AlphaCode, tree search methods, and RL fine-tuning all struggle when the model’s prior is misaligned with the solution space. The paper doesn’t manufacture the problem; it names something practitioners have been hitting for years. The timing is right: as models plateau on benchmarks, self-improvement is the next frontier.

Method maturity: The core ideas (evolutionary algorithms, backward chaining) are old, but the synthesis is clever. The theoretical motivation (entropy shell, exponential sample reduction) is hand-wavy but directionally correct—it’s more intuition than proof. The real contribution is showing these ideas work together in the LM setting. However, the method is complex: forward evolution + backward decomposition + checkpoint alignment. Simpler ablations (e.g., just crossover without backward search) would clarify what’s load-bearing. The paper hints at this but doesn’t fully isolate components.

Experimental integrity: Baselines are fair (best-of-N, MCTS, mainstream RL algorithms). The post-training experiments show gains where others fail, which is compelling. The inference-time results on AIME, GPQA, and LiveCodeBench are strong, but the paper doesn’t report variance or multiple seeds—hard to know if the gains are robust or lucky runs. The claim that BES “outperforms existing open-source frameworks” is supported, but the comparison is against open-source only; closed-source systems (o1, o3) aren’t included, so we don’t know where this sits in the absolute landscape. No major red flags, but I’d want to see error bars.

Writing quality: The abstract and intro are crisp. The method section is dense—too much notation, not enough intuition. Figure 1 does heavy lifting, but the text doesn’t walk through a concrete example end-to-end. The related work is thorough but reads like a checklist. The biggest missed opportunity: the paper doesn’t explain *when BES helps vs. when simpler methods suffice. If I rewrote one section, it’d be the experiments—add a failure analysis showing where BES still struggles and why.

Verdict: Weak accept — The method is novel and the results are promising, but the complexity and incomplete ablations leave questions about what’s essential. The paper advances the field but needs tighter analysis to be a strong contribution.

Takeaways

For practitioners:

1. Checkpoints as search structure: If you’re doing any form of search (RL, MCTS, sampling), decompose the task into verifiable intermediate states. Even without evolution, dense feedback beats sparse rewards.
2. Recombination over generation: When the model’s prior is weak, don’t just sample more—recombine partial solutions. This applies beyond LMs: any generative system where you can splice outputs at natural boundaries (code at function calls, proofs at lemmas, plans at subgoals).
3. Backward planning as a tool: Use the model to generate subgoals, not just solutions. This is cheap (one backward pass) and gives you a roadmap even if forward search fails.

Transferable technique: The “entropy shell escape” framing is useful for any probabilistic search. If your samples cluster in a narrow region, you need operators that jump between modes, not just refine within a mode. Crossover is one such operator; others include analogy-based transfer or constraint-guided generation.

What doesn’t transfer: The specific implementation (crossover at checkpoints, recursive decomposition) is tailored to sequential reasoning tasks. For tasks without natural decomposition (e.g., image generation, open-ended dialogue), the method needs rethinking.