TRACE-QA: Task-routed constraint elimination for auditable multi-agent question answering

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.