Adaptive Semantic Branching: Disagreement-Localized Cross-Trajectory Regeneration for Reasoning Candidate Expansion

Jeong-Yoon Kim, Tae-Yoon LeearXiv 2026 · arXiv

TL;DR

Adaptive Semantic Branching (ASB) is a training-free inference method that improves LLM reasoning by "cross-pollinating" different solution paths. By identifying exactly where two conflicting reasoning trajectories diverge, ASB generates new candidates that combine the stable prefix of one path with a local "insight" from another, recovering nearly 20% of previously failed math problems with minimal extra compute.

What Problem Does This Paper Address?

When Large Language Models (LLMs) tackle complex multi-step reasoning—like math problems—they often generate multiple "chains of thought" that lead to different answers. Standard techniques like Self-Consistency simply take a majority vote among these paths. However, if the model is stuck or makes a subtle early error, simply sampling more of the same might not help.

Existing "Tree-of-Thought" or "Graph-of-Thought" methods try to explore these branches more systematically, but they often require complex search algorithms or specialized training. The authors of this paper ask: Can we use the disagreements between already-completed trajectories to pinpoint where the model went wrong and generate a better "hybrid" solution?

Methods

ASB operates entirely at inference time without any additional training. The pipeline follows these steps:

  1. Initial Sampling & Clustering: The model generates seven independent trajectories. These are grouped into clusters based on their final answers.
  2. Step-Level Alignment: If there is a disagreement (more than one cluster), ASB selects a representative from each. It breaks the reasoning text into steps and uses Dynamic Time Warping (DTW) to align them. To do this deterministically, they use a word- and character-gram hashing encoder to turn text steps into vectors.
  3. Divergence Localization: The algorithm calculates a "persistent-divergence objective" to find the specific step where two trajectories start to look different.
  4. Directed Regeneration ($A \leftarrow B$): This is the core innovation. ASB creates a new prompt using:
  5. The Source Prefix ($P_A$): The reasoning from Trajectory A up to the divergence point.
  6. The Donor Insight ($I_B$): A short window (1-3 steps) from Trajectory B immediately following the divergence.
  7. The model is then asked to "continue solving" based on this new hybrid context.
  8. Adaptive Budgeting: To keep costs low, ASB only generates 2 or 3 extra "branch" trajectories per problem, and only if there was an initial disagreement.
The ASB pipeline: from initial sampling to directed regeneration.

Datasets

The authors evaluated ASB using a fixed manifest of 500 problems from the MATH benchmark. They used the Qwen2.5-7B-Instruct model as their base reasoner.

Key Insights and Ideas

  • Disagreement as a Signal: Instead of treating conflicting answers as failures, ASB treats them as a map. The point of divergence is likely where a critical decision or calculation error occurred.
  • Asymmetric Transfer: The operation $A \leftarrow B$ (Source A, Donor B) is fundamentally different from $B \leftarrow A$. One might provide a better starting prefix, while the other provides a more useful "hint." ASB evaluates both directions.
  • Lightweight and Deterministic: By using hashing for embeddings and DTW for alignment, the "overhead" of finding where to branch is negligible compared to the cost of the LLM generation itself.
  • Oracle Coverage Focus: The goal isn't just to pick the right answer, but to expand the "solution space" so that the correct answer exists somewhere in the pool of candidates.

Key Results

The study demonstrates that "cross-trajectory" hints are highly effective at correcting errors:

  • Increased Accuracy: Oracle candidate coverage (the percentage of problems where at least one generated answer is correct) rose from 89.0% to 91.0%.
  • Recovery Rate: ASB successfully recovered correct answers for 18.18% (10 out of 55) of the problems that the model initially failed to solve in seven tries.
  • Efficiency: On average, the method only required 1.15 additional generation calls per problem (8.15 total calls vs. the initial 7).
Table 1: Oracle candidate coverage and generation counts for the stored MATH-500 run (Qwen2.5-7B-Instruct; base seed 100).

Limitations and Future Work

  • Initial Pool Dependency: If all initial trajectories are wrong in exactly the same way (no disagreement), ASB has no signal to work with and defaults to the initial results.
  • Selection Logic: This paper focuses on generating the correct answer (coverage). A separate "selector" or "verifier" is still needed to pick that correct answer from the expanded pool for the final output.
  • Scaling: The authors suggest future work could involve testing ASB with larger models, different embedding techniques, or applying it recursively (branching from branches).
Table 2: Reference implementation settings for the MATH- 500 seed-100 run.

Summary updated

Abstract

Reasoning trajectories generated for the same problem often arrive at conflicting answers. These disagreements reveal alternative intermediate decisions that can be reused to explore new solutions. We introduce Adaptive Semantic Branching (ASB), a training-free inference procedure that turns cross-trajectory disagreement into targeted candidate generation. ASB first groups independently sampled trajectories by extracted final answer, selects a representative from each group, and aligns their reasoning steps with a monotonic dynamic program. A persistent-divergence objective identifies the point at which initially similar reasoning paths develop different continuations. For each selected directed pair, ASB retains the source trajectory's textual prefix, extracts a short reasoning window from a competing donor trajectory, and generates a fresh solution conditioned on both. A diversity-aware policy allocates up to three additional generations according to the answer-cluster structure. In a 500-problem MATH evaluation with Qwen2.5-7B-Instruct, ASB increases oracle candidate coverage from 445/500 (89.0%) with seven initial samples to 455/500 (91.0%), recovering correct candidates for 10 of the 55 initially uncovered problems. The method uses 576 additional generation calls across the evaluation set, averaging 8.152 calls per problem. We provide a precise specification of the branching operator, alignment objective, generation policy, and experimental configuration.
BibTeX
@misc{kim2026adaptive,
  author = {Jeong-Yoon Kim and Tae-Yoon Lee},
  title = {{Adaptive Semantic Branching: Disagreement-Localized Cross-Trajectory Regeneration for Reasoning Candidate Expansion}},
  year = {2026},
  eprint = {2611.07918},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07918},
}
Figure