Source-linked AI summary
Answer Probing-Guided Search for Diverse Solution Exploration of LLMs
Yi Fang, Que Shen, Chengpeng Li, Boyi Deng, Wei Shi, Wenjie Wang, Fuli Feng, Fengli Xu, Dayiheng Liu
TL;DR
LLMs tend to converge on a single high-confidence solution, while response-level semantic embeddings can mistake linguistic and stylistic similarity for shared solution paths. The paper introduces Answer Probing and APTS, which use probed-answer representations and perplexity to guide diverse search, and reports consistently improved solution diversity with minimal accuracy impact.
Problem
LLMs often converge on one high-confidence reasoning trajectory, and response-level semantic embeddings can be confounded by linguistic and stylistic similarity when distinguishing genuinely distinct solution paths.
Method
Answer Probing probes potential answers from intermediate reasoning paths, while APTS guides tree search using probed-answer hidden-state similarity and perplexity.
Results
APTS consistently improves solution diversity with minimal impact on accuracy across three reasoning domains and two LLM architectures.
Takeaways & Limitations
Answer-level hidden states provide a more effective representation for separating solution categories than response-level representations, supporting solution-level diversity search.
Takeaways & Limitations
APTS adds computational overhead, mainly targets solution rather than semantic diversity, and requires intermediate hidden states and log probabilities in its original formulation.
Abstract
from arXiv · showhide
Generating multiple diverse and high-quality solutions is valuable for many applications, such as code-test generation and drug discovery. However, Large Language Models (LLMs) tend to converge on a single high-confidence solution during inference, limiting exploration of alternative valid solution paths. Existing test-time methods promote diversity through tree-like search and prune semantically similar branches using response-level semantic embeddings. However, we find that such embeddings are easily confounded by linguistic and stylistic similarities, making it difficult to distinguish genuinely distinct solution paths. To address this, we introduce Answer Probing, which probes the potential answer an LLM would reach from an intermediate reasoning path. We demonstrate that the hidden states of probed answers more effectively differentiate distinct solution paths than semantic embeddings, and the perplexity of probed answers serves as a practical proxy for reasoning correctness. Based on these findings, we propose Answer Probing-Guided Tree Search (APTS), which guides the tree search by the probed answers' hidden state similarity and perplexity. Experiments on three reasoning tasks across two LLMs show that APTS consistently enhances solution diversity, demonstrating its effectiveness and robustness.
1 Introduction
The paper motivates solution-level diversity because LLMs often converge on one high-confidence reasoning trajectory, while existing approaches can confuse linguistic variation with genuinely distinct paths. It introduces Answer Probing and APTS to distinguish, evaluate, and search diverse reasoning paths.
- Motivation: Diverse solution generation is valuable when applications require multiple high-quality candidates rather than one gold-standard answer.Examples include comprehensive software evaluation through diverse test cases and broader chemical-structure exploration in drug discovery.
- Motivation: LLMs often converge on a single high-confidence trajectory during inference, limiting exploration of other valid solutions.
- Existing Methods: Decoding methods may create token-level variation without producing genuinely semantically diverse reasoning paths.
- Existing Methods: Search-based methods explore candidate paths with tree search and prune branches using response-level semantic embedding similarity.
- Proposed Approach: Answer Probing probes potential answers from intermediate reasoning paths, using mean-pooled probed-answer hidden states for path distinction and perplexity as a quality proxy.
- Proposed Approach: APTS uses probed-answer perplexity and hidden-state similarity to select high-quality, non-redundant nodes for further tree-search expansion.
- Results: APTS improves solution diversity with only a modest impact on accuracy across three cross-domain reasoning tasks and two LLMs.
2 Preliminary Analysis
The preliminary analysis compares semantic and hidden-state representations for distinguishing solution categories and tracking reasoning trajectories. Answer-level representations, especially hidden states, separate divergent solutions more clearly than response-level semantic embeddings.
- 2.1 Experimental Setup: The study uses 204 Game of 24 problems, each with at least four solution categories, sampling N = 512 responses per problem from Qwen3-8B.Representations include response-level and answer-level semantic embeddings, plus response-level and answer-level hidden-state averages.
- 2.2 Answer-Level Representations Better Separate Solution Categories: PCA visualizations show response-level representations heavily overlap, whereas answer-level representations form clearer clusters aligned with solution categories.The comparison evaluates how well each representation distinguishes different underlying solution paths.
- 2.2 Answer-Level Representations Better Separate Solution Categories: Answer-level representations outperform response-level representations by 0.36 on average in pairwise AUROC for solution separability, 0.94 vs. 0.58.Full-response semantic embeddings also show average cosine similarity of 0.95, which limits their separability for responses to the same problem.
- 2.3 Hidden State Space Better Reveals Trajectory Divergence: Hidden-state trajectories from different solutions begin near one another and progressively diverge toward distinct endpoints, unlike semantic trajectories that remain overlapped.The trajectory analysis uses cumulative prefixes at 10%, 20%, ..., 100% of the reasoning process.
- 2.3 Hidden State Space Better Reveals Trajectory Divergence: These findings motivate using answer-level hidden states rather than semantic embeddings to reveal intermediate reasoning development and support Answer Probing.The hidden-state space provides a more discriminative view of trajectory divergence during generation.
3 Method
The method uses Answer Probing to derive answer-based quality and diversity signals from intermediate reasoning paths, then applies them in a breadth-first tree search. APTS selects promising, non-redundant nodes for further expansion using probed-answer perplexity and hidden-state similarity.
- 3.1 Answer Probing: Answer Probing appends an answer-inducing prompt to an intermediate reasoning path and prompts the LLM to generate a probed answer.The probing context combines the problem, partial reasoning path, and prompt π_ans, such as “The final answer is.”
- 3.1 Answer Probing: The hidden states of probed-answer tokens represent the intermediate reasoning path and can distinguish linguistically similar paths leading to different solutions.This representation exposes the latent solution tendency encoded in the intermediate state.
- 3.1 Answer Probing: Probed-answer perplexity provides a quality signal: lower PPL indicates that the LLM generates the answer more confidently from the current reasoning path.The probing procedure uses greedy decoding to eliminate sampling randomness, and prompt sensitivity is analyzed separately.
- 3.2 Answer Probing-Guided Tree Search: APTS performs breadth-first tree search, expanding each node into W children and selecting M candidates for continued exploration at each depth.Search ends at maximum depth D or when all active nodes have produced final answers.
- 3.2 Answer Probing-Guided Tree Search: APTS combines inverse-PPL quality with diversity relative to already selected nodes through a trade-off coefficient α during greedy selection.The candidate with the highest node value is selected in each round, and the process repeats for M rounds.
4 Experiments
Experiments evaluate APTS across three domains, two language models, representation choices, signal trade-offs, and search hyperparameters. APTS consistently improves solution diversity while largely preserving correctness, with modest computational overhead.
- Main Results: APTS achieves the best solution diversity across all three tasks and both evaluated LLMs.Compared with same-temperature Repeated Sampling, it improves Cov@16 by over 7% on Game of 24, the mean of L-Cov@16 and B-Cov@16 by over 5% on TestCaseGen, and NCircle@16 by 0.47 on Forward Synthesis.
- Main Results: APTS improves diversity with only a 0.6% correctness decrease, whereas increasing temperature to T = 1.5 causes a 9% average correctness drop.APTS explicitly evaluates candidate-path quality during search, while higher sampling randomness can produce superficially diverse but incorrect outputs.
- Efficiency and Generalizability: APTS introduces 1.46× latency over same-budget Repeated Sampling on Game of 24 with Qwen3-8B, yet is faster than budget-matched sampling with 29 responses.Under the budget-matched comparison, APTS also achieves higher diversity despite using 16 responses.
- Representation Analysis: Answer-level representations outperform response-level representations for solution diversity, and probed-answer hidden states outperform AnsSem on TestCaseGen and Forward Synthesis.The results indicate that hidden-state representations better distinguish different reasoning trajectories than semantic embedding spaces.
- Signal Roles: With α = 0, probed-answer PPL yields higher accuracy than Repeated Sampling, while increasing α steadily improves solution coverage.On Game of 24 with Qwen3-8B, accuracy is 0.9807 versus 0.9559; introducing any similarity penalty produces higher coverage than the baseline.
- Hyperparameter Sensitivity: Increasing node expansion width from 2 to 4 substantially improves diversity, while wider search adds overhead for marginal or negative gains.Width 4 provides a good trade-off, with the same diminishing-gain pattern observed across the reported tasks.
5 Related Work
Prior work diversifies LLM generation through prompt changes, decoding randomness, or search with semantic-embedding pruning. This paper positions Answer Probing as a mechanism that uses probed-answer signals to guide search beyond surface-level similarity.
- Diversity Generation of LLMs: Generation-side diversification includes decoding-based methods that vary temperature or top-p and search-based methods that explore and prune reasoning paths.The paper focuses on generation-side methods under a fixed prompt.
- Diversity Generation of LLMs: Semantic similarity can be confounded by linguistic and stylistic noise, limiting its ability to distinguish genuinely distinct reasoning paths.This motivates representations that better reflect underlying solution paths.
- Positioning of Answer Probing: Answer Probing extends intermediate-answer probing from certainty estimation and early stopping to diversity and quality signals for search.APTS uses hidden-state similarity between probed answers and their perplexity to guide node selection.
6 Conclusion
The paper introduces Answer Probing to obtain quality and diversity signals from potential answers generated from intermediate reasoning states, then uses those signals in APTS to guide tree search.
- 6 Conclusion: Answer Probing uses probed-answer hidden-state similarity to reflect reasoning-trajectory diversity and probed-answer PPL to reflect underlying reasoning quality.APTS selects candidate nodes that are both high-quality and diverse, improving solution-level diversity while maintaining strong overall performance.
Limitations
The paper identifies computational, task-scope, model-access, hyperparameter-transfer, and confidence-reliability limitations for APTS. It also reports layer-wise separability diagnostics for answer-level hidden states.
- Limitations: APTS requires multiple candidate paths and answer probing at each search depth, introducing additional computational overhead.The paper measures this overhead separately in its latency analysis.
- Limitations: APTS focuses on solution diversity rather than semantic diversity, which may make it less suitable for non-reasoning tasks such as creative writing.This limitation constrains the method’s task scope.
- Limitations: The original formulation depends on intermediate hidden states and log probabilities, limiting direct applicability to closed-source models.A separate experiment adapts APTS to GPT-o3-mini by replacing hidden-state signals with semantic embeddings and semantic entropy.
- Limitations: The trade-off coefficient α may not transfer reliably across all tasks and models, so the paper recommends selecting it with a small validation set.The probed-answer PPL quality signal may also be unreliable in rare or challenging cases where the model has blind spots.
- Diagnostic Analysis: Layer-wise analysis evaluates answer-category separability using average and minimum inter-class Euclidean distance and silhouette score.Larger distance values indicate better separation between solution categories.
B Quantitative Analysis of Solution Separability
Answer-level representations separate solution categories more effectively than response-level representations, while AnsHid is particularly useful for distinguishing intermediate reasoning differences. APTS remains robust to probing-prompt wording.
- Representation separability: Answer-level representations substantially outperform response-level representations for solution separability, with answer semantics benefiting from shared final answers.The analysis uses pairwise AUROC to distinguish same-category from different-category response pairs.
- Representation separability: AnsHid performs better than AnsSem for APTS, suggesting hidden states preserve intermediate reasoning information beyond final-answer semantics.AnsSem more directly separates responses by their final answers, whereas AnsHid better distinguishes intermediate reasoning processes.
- Prompt robustness: 0.9516 average cosine similarity across probing prompts indicates that probed-answer hidden states remain highly consistent despite wording changes.This comparison uses 100 randomly selected intermediate reasoning trajectories and three probing prompts.
- Prompt robustness: Final Acc@16 and Cov@16 remain very close across three probing formulations, indicating limited sensitivity of the full APTS pipeline to prompt wording.The evaluation is conducted on Game of 24 with Qwen3-8B.
D Inverse-PPL Distribution Analysis
The inverse-PPL quality term appears potentially unbalanced against bounded cosine similarity, but empirical values remain concentrated near one across tasks. This supports using a fixed trade-off coefficient in practice.
- Concern: The inverse-PPL term is unbounded while cosine similarity lies in [−1, 1], creating a potential unpredictability in the diversity–quality trade-off.The concern arises because the two terms have different numerical ranges in the node value function.
- Empirical behavior: Greedy decoding tends to produce relatively high token probabilities, concentrating inverse-PPL values close to 1.This concentration is offered as the reason the theoretically unbounded term can remain practically controlled.
- Empirical behavior: [0.85, 1.00] is the approximate range of actual inverse-PPL values used by APTS across all three tasks on Qwen3-8B.The values do not vary by orders of magnitude, so the quality term remains well-behaved in practice.
- Practical implication: A fixed α can work reasonably across different tasks because the observed inverse-PPL values remain tightly concentrated.The experiments cover Game of 24, Forward Synthesis, and TestCaseGen.
G Evaluation on Open-Ended Generation
APTS extends beyond explicit multi-solution tasks: it improves diversity while retaining strong quality on open-ended idea generation, closed-source models, and another model family.
- Open-ended generation: APTS achieves the best or near-best quality while consistently improving diversity on LiveIdeaBench for both evaluated models.LiveIdeaBench scores quality and diversity using multiple LLM judges on a 1–10 scale.
- Cross-setting robustness: Answer-probing-guided search transfers across model families and beyond explicit multi-solution settings.The evidence combines results from LiveIdeaBench, GPT-o3-mini, and DeepSeek-R1-Distill-Llama-8B.
- Closed-source models: The adapted APTS improves diversity over Repeated Sampling across all three tasks on GPT-o3-mini.The adaptation replaces hidden states with semantic embeddings and PPL with semantic entropy for closed-source models.
- Cross-family transfer: APTS achieves the best solution diversity on both Game of 24 and Forward Synthesis with DeepSeek-R1-Distill-Llama-8B.The reported diversity metrics are Cov@16 and NCircle@16.
J Latency and Efficiency Analysis
APTS adds inference overhead relative to repeated sampling but benefits from prefix caching and batching. Under matched token budgets, it becomes more effective as repeated sampling produces more duplicates.
- Latency: 1.46× wall-clock overhead is introduced by APTS over Repeated Sampling with the same sample count.Both methods reach a peak GPU memory of 72GB in the Qwen3-8B Game of 24 setup.
- Latency: Prefix caching and batching narrow APTS’s latency gap by reusing shared prefixes and grouping short continuations.The setup batches up to 640 expansions in one generation call on a single A100-80GB GPU.
- Budget-matched comparison: At K = 5, budget-matched Repeated Sampling can be comparable to or slightly better than APTS, but its marginal benefit decreases as K grows.APTS increasingly benefits from explicitly exploring alternative reasoning trajectories when repeated sampling generates duplicates.
- Budget-matched comparison: 0.6913 vs. 0.6781: APTS achieves higher Game of 24 coverage with 16 final answers than budget-matched Repeated Sampling with 29 samples.This result illustrates APTS’s greater sample efficiency under equal token budgets.
- Budget-matched comparison: 0.7306 vs. 0.7227 in L-Cov and 0.6232 vs. 0.6127 in B-Cov: APTS exceeds budget-matched Repeated Sampling on TestCaseGen with fewer generated cases.APTS uses 16 test cases versus 22 for budget-matched Repeated Sampling.
K Case Study and Error Analysis
The case studies identify two diversity failures: insufficient exploration across many solution categories and sampling collapse onto trivial cancellation patterns. The included figures and algorithm outline vary search settings and representation types, but the supplied passages do not report their outcomes.
- Case Study and Error Analysis: APTS covers only 3 of 9 solution categories for [2, 6, 10, 12] at α = 0.7.Six categories remain unexplored, while Cat 2 appears 7 times among 16 answers.
- Case Study and Error Analysis: The case-study analysis attributes the first failure to an insufficient diversity incentive under the current α and suggests increasing α could broaden exploration.This suggestion is specific to problems with many solution categories.
- Case Study and Error Analysis: For [2, 2, 4, 6], all 16 APTS answers produce the identical expression 6 × 4 + 2 −2.The problem has 5 solution categories, but only 1 is covered.
- Case Study and Error Analysis: Trivial cancellation patterns recur across problems with repeated numbers and act as strong attractors in sampling behavior.The cited examples include [2,6,6,12] →12×2+6−6 and [4,6,8,8] → 6×4+8−8.
- APTS Procedure: APTS performs answer probing during expansion and uses probed-answer perplexity for quality and hidden-state similarity for diversity during selection.The algorithm takes target response number M, expansion width W, and maximum search depth D as inputs and outputs M responses.