Aug 2026· Journal of King Saud University: Computer and Information Sciences· Vol 38· 0 citations· 47 references
TL;DR
The proposed TRACE-QA, a training-free multi-agent protocol that routes each instance to a sparse set of reasoning operators, constructs option-blind necessity constraints, audits every candidate in a structured elimination ledger, revisits risky eliminations through global risk-aware rescue, and aggregates role-specialized judge votes, supports constraint-guided elimination as an auditable alternative to answer-first debate.
Abstract
Large language models (LLMs) remain vulnerable to answer anchoring, overconfidence, and fluent but unsupported justifications in binary and multiple-choice question answering. Recent answer-first debate frameworks force agents to inspect alternative stances, but they still spend substantial budget defending likely wrong answers and let a final judge consume long free-form interaction traces. We propose TRACE-QA, a training-free multi-agent protocol that routes each instance to a sparse set of reasoning operators, constructs option-blind necessity constraints, audits every candidate in a structured elimination ledger, revisits risky eliminations through global risk-aware rescue, and aggregates role-specialized judge votes. Under a unified three-seed protocol on HoVer, BoolQ, CosmosQA, and CommonsenseQA, TRACE-QA attains an average of 0.7731, exceeding the strongest common-protocol baseline (CFMAD) by 1.94 percentage points and improving on all five evaluation columns. Risk-aware rescue lowers the false-elimination rate from 5.2% without rescue to 1.4% and recovers 73.1% of recoverable false eliminations. We further evaluate structured graph reasoning on GraphSQA and a discrete in-toolset subset of Graph4real: TRACE-QA improves over text-only baselines, and with deterministic graph tools reaches 95.1%–97.8% accuracy across Graph4real scales. Full TRACE-QA remains substantially more expensive than chain-of-thought, but uses 19.7% fewer total tokens than CFMAD, and an adaptive variant saves 29.5% of its tokens at a 0.67-point accuracy cost. These results support constraint-guided elimination as an auditable alternative to answer-first debate, while exposing residual dependence on routing quality, ledger reliability, and backbone capability.
This work introduces Constraint-First Reasoning (CFR), a training-free two-stage prompting protocol that improves direct CoT on multiple backbones and positions CFR as a targeted test-time intervention whose benefit depends on recoverable constraints and reliable Stage 1 extraction.
Hongbo Ma, Bang Yang, Y. Cheng et al.· 0 citations
Large language models (LLMs) can generate fluent reasoning traces that nevertheless lead to incorrect answers, making response-level uncertainty estimation important for abstention, human review, and adaptive compute allocation. Existing approaches generally fall into three categories: passive single-trace methods use token-level confidence signals, sampling-based methods compare multiple complete traces at higher generation cost, and active prefix-based methods probe partial traces to study answer stabilization or preference transitions. However, none actively re-elicits an answer from a completed reasoning trace to measure its consistency with and support for the original answer. To address this gap, we introduce Trace-Conditioned Answer Consistency (TrAC), a correctness-supervised uncertainty quantification framework that combines active and passive signals anchored to one completed reasoning trace. Its active component, Prefix-Conditioned Elicitation (PCE), re-elicits a short answer conditioned on the completed trace and represents both its consistency with the original answer and its token-level probabilistic support. Its passive component, Trace Uncertainty Profile (TUP), summarizes how token-level uncertainty evolves throughout the original generation without additional decoding. A lightweight head then integrates the two representations into a response-correctness score. Across five mathematical reasoning benchmarks and three LLM families, TrAC improves macro AUROC by 1.8% and reduces AURC by 3.4% relative to eight-sample self-consistency, while using one complete reasoning trace and a short cached answer probe. When eight samples are already available, augmenting sample consensus with re-elicitation further improves macro AUROC by 4.3% and reduces AURC by 8.3%, without additional full-trace generation.
Dahai Yu, Lin Jiang, Rongchao Xu et al.· 0 citations
Search-augmented large language model agents are increasingly capable of solving knowledge-intensive tasks, but their behavior when a multi-hop question is fundamentally unanswerable remains poorly understood. Existing abstention benchmarks largely expose defects at the surface of single-hop queries and therefore cannot reveal failures that emerge only after valid intermediate reasoning and retrieval. We introduce HopRefusalBench, the first controlled benchmark of refusal within multi-hop search, comprising 889 unanswerable questions constructed from KILT-grounded entity paths. It crosses three causes of unanswerability (answer unknown, false premise, and underspecified context) with root, middle, and terminal topologies, making premise verification, intermediate-bridge validation, and terminal stopping separately observable. We further propose a final-outcome taxonomy spanning target-aware refusal, pseudo-refusal, hallucinated completion, and search-budget exhaustion, together with source-aware trajectory metrics for post-trigger continuation and token waste. Across ten frontier proprietary and open-weight models in search-augmented mode, the best model achieves a target-aware correct halting rate (TCHR) of only 42.9%. Root and middle items are consistently harder than terminal items, and all models attain their highest TCHR on false premises and their lowest on underspecified questions. Yet when pooled across categories, 84.7--98.4% of each model's explicit refusal-like responses identify the correct rationale, localizing the main bottleneck to committing to an appropriate non-answer; failed trajectories instead diverge into hallucination or search-budget exhaustion. These results establish refusal in multi-hop search as a consequential evaluation problem and provide a foundation for diagnosing and improving the reliability of search-augmented agents.
Jianan Xie, Xin Sun, Zhongqi Chen et al.· 0 citations
The hidden phenomenon accuracy-blind answer churn is called and the Snapshot Compatibility Audit is introduced, which estimates excess answer churn by subtracting same-snapshot repeat disagreement from cross-snapshot disagreement.
Large language model (LLM)-based search agents answer questions through multi-step interactions with external environments. However, providing complete execution trajectories to the LLM causes unbounded context growth and introduces noise. Existing compression methods reduce context at the cost of important details and often replace erroneous facts without repairing downstream reasoning derived from them. To address this problem, we propose ReTree, a self-correcting tree-structured memory mechanism for search agents. ReTree constructs a bounded per-step reasoning context while preserving source-linked evidence. It models search as an evidence tree whose nodes store bounded summaries, evidence, and revision histories. When newly retrieved evidence contradicts an earlier claim, ReTree traces back to the node where the claim was introduced, replaces outdated evidence, regenerates summaries, prunes affected branches, and resumes search. Source-grounded evidence provenance supports reliable conflict localization and keeps final claims traceable to retrieved passages. Experiments on four public question-answering and search benchmarks show that ReTree consistently outperforms Full-Trajectory ReAct, improving answer accuracy by up to 25.6 percentage points (pp); the average maximum per-step reasoning context of Full-Trajectory ReAct is $1.27$--$1.51\times$ that of ReTree. These results establish ReTree as an effective self-correcting memory abstraction for long-horizon search.
Aijun Yang, Qianxue Guo, Ziyi Huang et al.· 0 citations
The results show that QA evaluation should account for how inferential relations compose across a reasoning trace, rather than relying only on final answers or LLMs as verifiers.
Guneet Singh Kohli, Yuxiang Zhou, M. Schlichtkrull et al.· 0 citations