Best-of-Evidence: Best-of-N Selection under Partial Verification
BoE framework optimizes candidate selection under partial verification, improving medical VQA accuracy by 0.4% with limited evidence budget.
Key Findings
Methodology
BoE employs a fixed candidate pool, representing claims via a signed candidate–factor graph. It allocates a limited evidence budget to select and perform heterogeneous checks, updating candidate utilities through Bayesian posterior updates and information value estimation. The core components include claim representation, evidence acquisition policy, and a score-based controller that sequentially chooses the most impactful checks. The framework leverages theoretical bounds on residual information capacity and shared factor queries, enabling efficient evidence reuse and decision optimization under partial verification. Experimental results on four medical VQA datasets demonstrate significant improvements over traditional BoN, especially when evidence is reliable and contrastive, with theoretical analysis confirming the O(log K) query efficiency advantage.
Key Results
- Across four datasets, BoE improved fixed-pool selection accuracy by an average of 0.4 percentage points, rescuing about 4.4% of original failures at C=16 budget. It outperformed baseline methods like pure BoN, random checks, and full-response judgments, especially in scenarios with high evidence reliability. Theoretical bounds on residual information confirmed that limited evidence capacity constrains potential improvements, while shared factor queries achieved logarithmic query complexity, reducing verification costs substantially.
- The experiments validated that BoE effectively re-ranks candidates by selectively acquiring diverse, decision-relevant evidence, leading to more robust and interpretable decisions. The method's ability to leverage partial, local evidence significantly enhances model performance in complex, real-world tasks such as medical diagnosis, where full verification is costly or infeasible.
- Ablation studies indicated that claim representation via signed candidate–factor graphs and the information value-based control policy are critical for performance gains. The results also highlighted the importance of evidence quality and channel reliability, with the framework showing robustness across different datasets and evidence types.
Significance
This work addresses a fundamental challenge in multi-modal reasoning: how to effectively utilize partial, local evidence for decision-making when full verification is impractical. By formalizing the problem and proposing a scalable, theoretically grounded solution, it advances both the theoretical understanding and practical deployment of evidence-driven inference systems. The framework enhances model robustness, interpretability, and efficiency, making it highly relevant for real-world applications such as medical diagnostics, legal reasoning, and complex question answering. It bridges the gap between local evidence checks and global decision quality, offering a new paradigm for resource-constrained inference under partial verification conditions.
Technical Contribution
The paper introduces a novel candidate–factor graph representation that enables reusing verified claims across multiple candidates, reducing redundant checks. It formalizes the evidence allocation problem as a Bayesian sequential decision process, deriving bounds on residual information and query complexity. The design of a score-based, greedy controller that maximizes expected utility under budget constraints is a key engineering contribution. Theoretical guarantees on query efficiency (O(log K)) and evidence reuse capacity provide rigorous foundations, while the integration of heterogeneous verification tools broadens applicability. These innovations collectively push the frontier of evidence-based inference in resource-limited settings.
Novelty
This is the first comprehensive framework explicitly addressing candidate selection under partial verification constraints, combining signed candidate–factor graphs with budgeted evidence allocation. Unlike prior works that rely on full-response scoring, BoE models local claims and their reusability, achieving logarithmic query efficiency. The theoretical analysis of residual information limits and shared factor queries distinguishes this approach from existing methods, filling a critical gap in multi-modal reasoning research where partial, fragmentary evidence is prevalent.
Limitations
- The framework's effectiveness diminishes when evidence quality is poor or the signal-to-noise ratio is low, limiting the ability to improve decision accuracy. In scenarios with extremely noisy or unreliable channels, the benefits of evidence reuse are constrained.
- Scalability issues may arise with very large candidate pools or complex claim graphs, as the computational overhead of maintaining and updating the signed factor graph could increase significantly.
- Dependence on high-quality, diverse verification tools and evidence sources poses practical challenges, especially in domains with limited or costly verification resources. Future work should focus on robustness to noisy evidence and adaptive resource allocation.
Future Work
Future directions include developing more robust evidence representations that handle noisy or ambiguous signals, integrating adaptive budget strategies that dynamically allocate resources based on evidence quality, and extending the framework to broader real-world tasks such as legal reasoning, autonomous diagnosis, and multi-turn dialogue systems. Additionally, exploring scalable algorithms for larger candidate sets and more complex claim graphs will be crucial for practical deployment. Theoretical extensions to account for non-Bayesian settings and multi-agent evidence sharing are also promising avenues.
AI Executive Summary
In the rapidly evolving field of multi-modal reasoning, the challenge of effectively utilizing partial, local evidence remains a critical bottleneck. Traditional approaches like Best-of-N (BoN) rely on complete candidate responses and assume reliable whole-response verification, which often fails in complex tasks such as medical visual question answering (VQA). These limitations motivate the development of more flexible, evidence-driven inference frameworks capable of operating under partial verification constraints.
This paper introduces the Best-of-Evidence (BoE) framework, a novel approach that maintains a fixed candidate pool while dynamically acquiring heterogeneous, local evidence within a limited budget. The core innovation lies in representing candidate claims via a signed candidate–factor graph, enabling the reuse of verified assertions across multiple candidates. The evidence acquisition process is guided by a Bayesian, score-based controller that estimates the expected utility gain from each potential check, prioritizing those with the highest information value.
Theoretical analysis reveals that residual evidence capacity bounds the potential for model improvement, and shared factor queries can achieve an O(log K) query complexity, significantly reducing verification costs compared to traditional candidate-level checks. Empirical evaluation on four medical VQA datasets demonstrates that BoE consistently outperforms baseline methods, rescuing up to 4.4% of failures and improving overall accuracy by 0.4 percentage points at C=16 budget. These results validate the framework's ability to leverage partial, reliable evidence for robust decision-making.
Overall, BoE offers a scalable, theoretically grounded solution for resource-constrained, evidence-based inference in complex multi-modal tasks. Its capacity to balance evidence quality, computational cost, and decision accuracy marks a significant step forward in the development of interpretable, robust AI systems. Future work will focus on enhancing evidence robustness, expanding to broader domains, and optimizing resource allocation strategies to further improve performance in real-world applications.
Deep Dive
Abstract
BoN improves model outputs by sampling several candidates and selecting one with a proxy score, but it assumes that complete candidates can be evaluated reliably. Many vision-language tasks instead provide only partial verification: a finding, span, value, region, or relation may be checkable even when no dependable whole-response verifier exists. Moreover, the same claim may recur across candidates with opposing stances, allowing one observation to support part of the pool and contradict another. We introduce Best-of-Evidence (BoE), an inference-time selection framework that keeps the BoN candidate pool fixed, represents reusable claims with a signed candidate--factor graph, and allocates a limited budget to evidence actions that can change the final choice. BoE formalizes selection under partial verification and provides a practical score-based controller, with the zero-budget case recovering the underlying BoN decision. Theoretically, we show that residual evidence capacity limits any evidence-driven improvement and that shared factor queries can achieve an O(log K) versus Θ(K) query separation in a factor-code model. Common-ledger experiments on four medical VQA settings show that BoE can improve fixed-pool selection and rescue some BoN failures when evidence is reliable, contrastive, and decision-relevant, while also revealing the channel-quality and candidate-generation limits that prevent universal gains.