Skip to content

Answer Probing-Guided Search for Diverse Solution Exploration of LLMs

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Large Language Models, Answer Probing, Tree Search, Solution Diversity, Hidden State Representations

TL;DR

Addressing the issue where test-time tree search using response-level semantic embeddings fails due to stylistic and linguistic confounding, this paper proposes Answer Probing-Guided Tree Search (APTS), which probes potential intermediate answers and uses their hidden state similarity and perplexity to steer search toward genuinely diverse and valid reasoning solutions.

Background & Motivation

Generating multiple diverse and high-quality solutions with Large Language Models (LLMs) is of paramount importance across high-stakes domains such as code unit test synthesis, retrosynthetic pathway planning, and de novo molecular drug discovery. In these scenarios, practitioner utility relies not merely on obtaining a single consensus answer, but on discovering an ensemble of viable candidates spanning fundamentally distinct algorithmic logics or chemical scaffolds to maximize branch coverage or unlock novel chemical leads. However, contemporary LLMs inherently suffer from severe mode collapse and artificial hivemind behaviors during standard generation; even with extensive repeated sampling, generation trajectories tend to converge onto a single high-confidence pathway, severely constraining the exploration of valid alternative solutions.

To foster solution diversity without incurring prohibitive retraining overhead, existing test-time exploration methods generally bifurcate into stochastic sampling heuristics and structured search algorithms. Decoding-side adjustments, such as elevating sampling temperature or widening nucleus sampling thresholds, primarily induce token-level lexical variations rather than structural problem-solving divergences, often precipitating catastrophic drops in reasoning accuracy when temperature is scaled. Conversely, search-based methods such as Diverse Beam Search or SemDiD employ tree structures and prune redundant candidates guided by response-level semantic embeddings. However, thorough empirical inquiry reveals a critical flaw: LLM outputs tackling the exact same prompt exhibit extreme stylistic, structural, and discursive homogeneity. Shared explanatory signposts, boilerplate commentary, and syntactic framing yield high semantic similarity (averaging 0.95 in cosine similarity), preventing semantic embedding spaces from reliably discriminating fundamentally distinct mathematical derivations or algorithmic trajectories.

To resolve the confounding caused by linguistic noise, this work investigates which intermediate representation faithfully captures underlying solution divergence. Empirical geometric analyses demonstrate that token hidden states pooled over the final answer exhibit markedly superior separability across solution categories compared to full-response semantic vectors (achieving a pairwise AUROC of 0.94 versus 0.58). Motivated by this insight, the core idea is to introduce Answer Probing at intermediate reasoning steps by appending an answer-inducing prompt to elicit the model's immediate latent answer, subsequently leveraging the probed answers' hidden-state similarity as a diversity repulsion signal and their perplexity as a self-contained quality proxy to guide breadth-first tree search (APTS) toward diverse, valid reasoning paths.

Method

Overall Architecture

APTS operates as a breadth-first tree search algorithm that systematically assesses intermediate reasoning steps to balance path validity against solution diversity. Taking a complex problem prompt \(p\) as input, the goal is to produce \(M\) distinct, high-accuracy complete solutions. At each search depth \(d\), every currently retained reasoning node expands into \(W\) child nodes representing candidate next reasoning steps. For each expanded candidate, APTS appends an answer-inducing prompt and conducts greedy decoding to yield a probed answer, from which it extracts the token-level mean hidden state vector from the 32nd layer and its generation perplexity. Guided by an objective function that jointly evaluates quality and penalizes maximum similarity against already selected nodes, a greedy selection loop retains \(M\) non-redundant, promising nodes for the subsequent depth, iterating until maximum depth \(D\) or terminal completion.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Problem p and Intermediate Path r"] --> B["Answer Probing Mechanism<br/>Append π_ans and Greedy Decode Probed Answer PA"]
    B --> C["Dual Signal Extraction<br/>Extract Layer-32 Hidden State H(r) and Perplexity PPL(PA)"]
    C --> D["Diversity-Aware Greedy Selection<br/>Compute Repulsion Penalty DSi Against Current Selected Set S"]
    D --> E["Trade-Off Scoring & Node Retention<br/>Combine Quality 1/PPL and Diversity DSi to Select M Candidates"]
    E --> F["Complete Trajectories to Output Diverse Solution Set"]

Key Designs

1. Answer Probing Mechanism: Stripping Discursive Noise to Expose Latent Solution Tendency

To circumvent the vulnerability of full-response embeddings to superficial stylistic and linguistic markers, Answer Probing shifts evaluation from "how the reasoning trajectory is phrased" to "what final solution the intermediate state is bound to produce." Given an intermediate reasoning prefix \(r\), the algorithm constructs a probing context \(c = p \oplus r \oplus \pi_{\text{ans}}\), where \(\pi_{\text{ans}}\) is an answer-inducing prompt (e.g., "The final answer is"). The model then conducts deterministic greedy decoding to produce a short probed answer \(\text{PA} = (a_1, a_2, \dots, a_L)\). By forcing the model to collapse its current cognitive state directly into an explicit conclusion, Answer Probing exposes the latent mathematical or algorithmic direction encoded in that intermediate state. APTS extracts the hidden states \(h_i\) corresponding to probed answer tokens from the 32nd transformer layer (identified through layer-wise separability analysis as maximizing inter-cluster distance) and calculates their mean-pooled representation:

\[H(r) = \frac{1}{L} \sum_{i=1}^L h_i\]

This ensures that even when two intermediate prefixes share identical narrative structures, if they lead toward different ultimate solutions, their probed hidden state representations cleanly diverge in feature space.

2. Probed-Answer Perplexity as an Intrinsic Quality Proxy

Unconstrained diversity optimization during tree search frequently diverges into erroneous reasoning branches or hallucinations, necessitating a dependable node quality evaluation mechanism that avoids expensive auxiliary verifier models. Answer Probing naturally yields an intrinsic confidence metric: for the greedily generated probed answer \(\text{PA}\), APTS evaluates its token perplexity under the current reasoning context:

\[\text{PPL}(\text{PA}) = \exp \left( - \frac{1}{L} \sum_{i=1}^L \log p_\theta(a_i \mid c, a_{<i}) \right)\]

A lower perplexity score indicates that the model arrives at the probed answer with higher internal certainty and logical consistency from the current reasoning state. Empirical analyses confirm that because greedy decoding outputs high-probability tokens, the inverse perplexity values \(1/\text{PPL}\) are tightly concentrated within \([0.85, 1.00]\) across domains, functioning as a well-behaved, bounded proxy for reasoning correctness that guards against expanding invalid trajectories.

3. Diversity-Aware Greedy Node Selection: Dynamic Repulsion Steering Search Boundaries

During candidate expansion, each of the \(M\) active parent nodes produces \(W\) child step extensions, accumulating a candidate pool \(C^{(d+1)}\) of size \(M \times W\). To select the optimal subset of \(M\) nodes for the subsequent depth, APTS initializes an empty selected set \(S\) and executes \(M\) sequential rounds of diversity-aware greedy selection. In each round, for every unselected candidate \(c_i \in C^{(d+1)} \setminus S\), the algorithm evaluates a composite score \(V(c_i)\):

\[V(c_i) = (1 - \alpha) \cdot \frac{1}{\text{PPL}_i} + \alpha \cdot \text{DS}_i\]

where the diversity repulsion term \(\text{DS}_i\) is defined as the negated maximum cosine similarity between the candidate's probed hidden state \(H_i\) and the probed hidden states of all nodes already committed to \(S\):

\[\text{DS}_i = \begin{cases} 0, & \text{if } S = \emptyset \\ -\max_{c_j \in S} \cos(H_i, H_j), & \text{otherwise} \end{cases}\]

The hyperparameter \(\alpha \in [0, 1]\) modulates the trade-off between exploitation (accuracy) and exploration (diversity). As soon as a candidate representing a specific solution mode is selected into \(S\), its neighborhood is immediately penalized, compelling the search frontier to pivot toward alternative high-confidence paths with orthogonal solution tendencies.

Benchmark & Evaluation Protocol

The framework is evaluated across three cross-domain reasoning benchmarks demanding rigorous intermediate logic and diverse solution sets: Game of 24 (measuring Acc@16 and solution logic coverage Cov@16 over 204 problems with \(\ge 4\) equivalence classes); Forward Synthesis (evaluating RXN-Mapper reaction confidence Conf@16 and chemical scaffold diversity NCircle@16 based on pairwise Tanimoto similarity \(< 0.75\)); and TestCaseGen (evaluating unit test correctness Acc@16 alongside line coverage L-Cov@16 and branch coverage B-Cov@16). Primary evaluations utilize Qwen3-8B and GPT-OSS-120B, supplemented by cross-family validation on DeepSeek-R1-Distill-Llama-8B and closed-source evaluation on GPT-o3-mini.

Key Experimental Results

Main Results

APTS is compared against five representative test-time generation baselines: Repeated Sampling at varying temperatures (\(T \in \{0.5, 1.0, 1.5\}\)), Diverse Beam Search, SemDiD (NeurIPS 2025), GuidedSampling (ICLR 2026), and STARS (ICLR 2026). Sampling \(N=16\) outputs per problem, the quantitative comparisons are summarized below:

Model Method Game of 24 (Acc / Cov) Forward Synthesis (Conf / NCircle) TestCaseGen (Acc / L-Cov / B-Cov)
Qwen3-8B Repeated Sampling (\(T=0.5\)) 0.9479 / 0.6080 0.2820 / 7.275 0.7360 / 0.6889 / 0.5744
Qwen3-8B Repeated Sampling (\(T=1.0\)) 0.9559 / 0.6179 0.2823 / 7.630 0.7394 / 0.7056 / 0.5896
Qwen3-8B Repeated Sampling (\(T=1.5\)) 0.9289 / 0.6250 0.1513 / 7.130 0.6138 / 0.6859 / 0.5731
Qwen3-8B Diverse Beam Search 0.9311 / 0.6238 0.2784 / 7.775 0.7172 / 0.7063 / 0.5957
Qwen3-8B SemDiD (NeurIPS'25) 0.9553 / 0.6337 0.2782 / 7.930 0.7484 / 0.7188 / 0.6088
Qwen3-8B GuidedSampling (ICLR'26) 0.9240 / 0.6383 0.2783 / 7.715 0.6956 / 0.7192 / 0.6106
Qwen3-8B STARS (ICLR'26) 0.9525 / 0.6185 0.2794 / 7.800 0.7178 / 0.7118 / 0.6079
Qwen3-8B APTS (Ours) 0.9445 / 0.6913 0.2808 / 8.150 0.7322 / 0.7306 / 0.6232
GPT-OSS-120B Repeated Sampling (\(T=0.5\)) 0.9507 / 0.6046 0.4411 / 3.190 0.9347 / 0.7965 / 0.6927
GPT-OSS-120B Repeated Sampling (\(T=1.0\)) 0.9292 / 0.6211 0.4423 / 3.255 0.9319 / 0.8150 / 0.7197
GPT-OSS-120B Repeated Sampling (\(T=1.5\)) 0.9032 / 0.6695 0.2483 / 2.420 0.8753 / 0.8280 / 0.7363
GPT-OSS-120B Diverse Beam Search 0.8986 / 0.6319 0.4369 / 3.290 0.9297 / 0.8242 / 0.7335
GPT-OSS-120B SemDiD (NeurIPS'25) 0.9139 / 0.6544 0.4333 / 3.330 0.9294 / 0.8259 / 0.7368
GPT-OSS-120B GuidedSampling (ICLR'26) 0.8879 / 0.6432 0.4214 / 3.300 0.8941 / 0.8234 / 0.7322
GPT-OSS-120B STARS (ICLR'26) 0.9124 / 0.6344 0.4335 / 3.270 0.9281 / 0.8216 / 0.7324
GPT-OSS-120B APTS (Ours) 0.9053 / 0.6926 0.4499 / 3.665 0.9309 / 0.8335 / 0.7430

Across both model architectures, APTS achieves state-of-the-art solution diversity while preserving competitive solution correctness. Relative to Repeated Sampling at \(T=1.0\), APTS delivers an absolute improvement in Game of 24 coverage of \(+7.34\%\) on Qwen3-8B and \(+7.15\%\) on GPT-OSS-120B, alongside significant gains in chemical exploration (\(+0.41\) to \(+0.52\) NCircle) and code coverage (\(+2.50\%\) L-Cov and \(+3.36\%\) B-Cov on Qwen3-8B).

Ablation Study & Representation Analysis

To quantify how effectively different representations capture solution boundaries, the authors evaluate pairwise separability AUROC on Game of 24 across four representation variants (positive pairs share solution category; negative pairs belong to differing categories):

Representation Type Notation Pairwise AUROC Analysis
Response Semantic Embedding RespSem 0.57 Heavily confounded by shared stylistic patterns and signposts
Response Hidden States Mean RespHid 0.58 Intermediate reasoning tokens dilute answer divergence
Answer Semantic Embedding AnsSem 0.95 Separates identical final answers, but blind to intermediate nuances
Answer Hidden States Mean AnsHid (APTS) 0.92 Highly discriminative while retaining continuous reasoning trajectory geometry

When integrating these representations directly into the APTS tree search framework as the diversity repulsion signal (on Qwen3-8B): - Response-Level vs. Answer-Level: In Game of 24, RespSem and RespHid achieve Cov@16 of only ~0.60–0.62, whereas AnsSem and AnsHid exceed 0.66, with AnsHid reaching 0.6913. - Hidden States vs. Semantic Vectors: On TestCaseGen, AnsHid achieves an L-Cov of 0.7306 versus 0.7180 for AnsSem; on Forward Synthesis, AnsHid achieves an NCircle of 8.150 versus 0.7950 for AnsSem. This confirms that probed hidden states encode richer intermediate trajectory divergence than static text embeddings. - Component Contribution (\(\alpha\) Sensitivity): When \(\alpha = 0\) (quality-only search via \(1/\text{PPL}\)), Game of 24 accuracy peaks at 0.9807 (exceeding baseline 0.9559), validating probed perplexity as an effective correctness proxy. Introducing the repulsion term (\(\alpha > 0\)) immediately boosts coverage, finding an optimal trade-off around \(\alpha = 0.7\).

Key Findings

  • High Sampling Temperature Causes Degeneracy: Increasing sampling temperature to \(T=1.5\) incurs an average \(9\%\) drop in solution validity, and actually reduces valid diversity on Forward Synthesis and TestCaseGen due to an influx of unparseable, malformed candidates.
  • Computational Efficiency via Prefix Caching: Because child expansion and answer probing share long common prefixes, KV prefix caching and batched generation limit the wall-clock latency overhead of APTS to only \(1.46\times\) that of Repeated Sampling with identical sample counts (12.61s vs. 8.64s on a single A100 GPU).
  • Superior Sample Efficiency under Budget Matching: When baseline repeated sampling is allocated an equivalent token budget (\(N=29\) samples on Game of 24), APTS with only \(N=16\) final answers retains superior coverage (0.6913 vs. 0.6781), demonstrating that performance gains stem from targeted exploration rather than inflated compute.
  • Generalization to Closed-Source and Open-Ended Tasks: Adapting APTS to GPT-o3-mini by replacing hidden states with probed answer text embeddings and perplexity with semantic entropy yields consistent diversity gains (Game of 24 Cov@16 rising from 0.6796 to 0.7162). On LiveIdeaBench scientific idea generation, APTS achieves superior diversity (4.19 vs. 4.00) while maintaining top-tier idea quality (6.25 vs. 6.27).

Highlights & Insights

  • Answer Probing Makes Implicit Convergence Explicit: Rather than trying to parse ambiguous mid-reasoning text, forcing the LLM to output an immediate speculative answer surfaces the latent attractor basin toward which the intermediate trajectory is drifting.
  • Hidden State Trajectory Divergence Overcomes Embedding Homogeneity: Geometric projections show that while full-response semantic representations remain tightly clustered throughout generation, answer-level hidden state trajectories trace smooth, coherent paths that fan out into well-separated clusters, faithfully capturing reasoning branching.
  • Decoupled Quality and Repulsion Formulation: Combining inverse perplexity with a dynamic cosine repulsion penalty provides an elegant submodular-like selection mechanism that aggressively branches out while firmly suppressing hallucinations and erroneous shortcuts.

Limitations & Future Work

  • Exploration Overhead in Long CoT Scenarios: While prefix caching mitigates latency, generating \(W\) extensions and executing speculative probing at every search depth introduces non-negligible computational cost that scales with tree depth.
  • Susceptibility to Miscalibrated Confidence: The inverse perplexity quality proxy relies on the model's internal calibration. In edge cases where the LLM suffers from high-confidence systematic errors or knowledge blind spots, PPL may reinforce incorrect reasoning paths.
  • Strong Sampling Attractors: Error analyses reveal that for problems with trivial algebraic shortcuts (e.g., \(a \times b + c - c\) in Game of 24), base sampling distributions form overwhelming attractors that even maximum diversity penalties fail to escape, pointing to the need for complementary activation-steering interventions.
  • vs. SemDiD (Shi et al., 2025): SemDiD guides tree pruning using text-level semantic embeddings of partial responses. This paper demonstrates that full-response embeddings suffer from high stylistic overlap (AUROC 0.57), whereas APTS's answer-level hidden states achieve an AUROC of 0.92, offering far sharper resolution between competing solution paths.
  • vs. Certaindex (Fu et al., 2025): Certaindex probes intermediate answers strictly to estimate certainty for early stopping in reasoning chains. APTS generalizes answer probing into a dual-signal paradigm, utilizing probed answers both as a quality check and as a geometric repulsion vector for diversity exploration.
  • vs. STARS (Zhu et al., 2026): STARS applies Stiefel activation steering directly to internal layers to induce divergence, which risks destabilizing coherent logic and degrading accuracy. APTS conducts discrete path selection over unperturbed internal states, preserving model reasoning capabilities while expanding solution coverage.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Elegant identification of the stylistic confounding in semantic embeddings, coupled with an ingenious answer-probing hidden state formulation.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous validation across three distinct domains, multi-model architectures (8B to 120B and proprietary), representation ablations, and token-budget matching.
  • Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally structured narrative, transitioning seamlessly from empirical diagnostic analysis to mathematical formalization and comprehensive benchmarking.
  • Value: ⭐⭐⭐⭐⭐ Highly impactful for test-time scaling, automated testing, molecular generation, and synthetic dataset construction requiring high-diversity reasoning trajectories.