Proof-of-Perception: Certified Tool-Using Multimodal Reasoning with Compositional Conformal Guarantees

Arya Fayyazi; Haleh Akrami

cs.CVFeb 27, 2026

Proof-of-Perception: Certified Tool-Using Multimodal Reasoning with Compositional Conformal Guarantees

Authors: Arya Fayyazi, Haleh Akrami

Organizations: University of Southern California, Los Angeles, CA · Nuro, Mountain View, CA

Abstract

We present Proof-of-Perception (PoP), a tool-using framework that casts multimodal reasoning as an executable graph with explicit reliability guarantees. Each perception or logic node outputs a conformal set, yielding calibrated, stepwise uncertainty; a lightweight controller uses these certificates to allocate compute under a budget, expanding with extra tool calls only when needed and stopping early otherwise. This grounds answers in verifiable evidence, reduces error compounding and hallucinations, and enables principled accuracy-compute trade-offs. Across document, chart, and multi-image QA benchmarks, PoP improves performance and reliability over strong chain-of-thought, ReAct-style, and program-of-thought baselines while using computation more efficiently.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of the Proof-of-Perception (PoP) workflow. Each perception or reasoning operation is represented as a node in a directed acyclic graph (DAG). Each node is equipped with a conformal prediction head that provides calibrated uncertainty sets $\Gamma^{(t)}_{\delta}(x)$ , and a controller adaptively allocates computation based on these certificates, producing reliable and explainable outputs.

Panel of Figure 2 — Figure 2: Node-wise conformal coverage vs. average set size across pooled datasets (target $90\%$ ). Bars show mean coverage; thin caps indicate $\pm 1.0\%$ variation. We constrain set sizes (OCR: up to 5, boxes: up to 3), which keeps coverage near target without inflating candidate sets.

Dataset	Metric	Direct	M-CoT	MM-ReAct	ProgVLM	PoP (ours)
DocVQA-T1	EM	$69.8$	$72.1$	$74.3$	$75.0$	78.6
	Halluc. $\downarrow$	$17.9$	$15.4$	$12.7$	$11.9$	7.1
	$\bar{B}$ $\downarrow$	0.25	0.25	$14.8$	$13.9$	$11.2$
TextVQA	F1	$64.7$	$66.9$	$69.2$	$69.7$	72.9
	Halluc. $\downarrow$	$22.3$	$19.8$	$15.6$	$15.1$	9.3
	$\bar{B}$ $\downarrow$	0.25	0.25	$15.6$	$14.7$	$12.4$

Table 1: Main results. Higher EM/F1/CIDEr is better; lower Hallucination and

\bar{B}

(budget) is better. PoP uses the same backbone as baselines; all tool-using agents share tool implementations.

Variant	TextVQA		ChartQA-H
Variant	F1 $\uparrow$	Halluc. $\downarrow$	EM $\uparrow$	AbsErr $\downarrow$
PoP (full)	72.9	9.3	87.8	4.2
w/o CP (No-CP)	69.8	14.8	84.6	5.6
final-only CP	71.1	11.9	86.2	4.9
heuristic controller	72.1	10.7	87.2	4.6

Table 2: Ablations on TextVQA and ChartQA-H.

Panel of Figure 3 — Figure 3: Accuracy–compute frontiers. PoP attains higher accuracy for a given budget and avoids over-expansion once node certificates meet the target. Shaded bands indicate $\pm 0.4$ absolute variation across three seeds.

Explore similar work

Don't Show Pixels, Show Cues: Unlocking Visual Tool Reasoning in Language Models via Perception Programs
Apr 14, 2026Muhammad Kamran Janjua, Hugo Silva, Di Niu +1Tool Use in VLMs VLM Reasoning
Huawei Technologies, Canada · University of Alberta, Canada
Reasoning Theater: Disentangling Model Beliefs from Chain-of-Thought
Mar 5, 2026Siddharth Boppana, Annabel Ma, Max Loeffler +5Faithfulness of Language Model Explanations Language Model Probing
Goodfire AI · Harvard University, Cambridge, MA
Position: Reasoning After Perception Means Reasoning Without Vision
Jul 21, 2025Hongcheng Gao, Zihao Huang, Jingyi Tang +12Visual Reasoning VLM Reasoning
Tsinghua University · BIT · Peking University +6

Apr 14, 2026J/K move · Enter open · S save

Don't Show Pixels, Show Cues: Unlocking Visual Tool Reasoning in Language Models via Perception Programs

Muhammad Kamran Janjua, Hugo Silva, Di Niu, Bahador Rashidi

Huawei Technologies, Canada · University of Alberta, Canada

Tool Use in VLMs VLM Reasoning Large Vision-Language Models

Open paper AskPDF arXiv

Multimodal language models (MLLMs) are increasingly paired with vision tools (e.g., depth, flow, correspondence) to enhance visual reasoning. However, despite access to these tool-generated visual cues, MLLMs often fail to benefit from them. Existing approaches typically feed raw tool outputs into the model, but these dense, pixel-level representations are misaligned with the language-native reasoning strengths of LLMs, leading to weak perception and reliance on language priors. We argue that, in problems where vision tools can provide the necessary visual cues, the bottleneck is not more tool calls or larger MLLMs, it is how tool outputs are represented. We introduce Perception Programs (P

^2

), a training-free, model-agnostic method that rewrites tool outputs into compact, structured, language-native summaries that MLLMs can directly parse and reason over. Across six perception-centric tasks in BLINK, P

^2

consistently yields large improvements over base models and raw tool-augmented baselines. With GPT-5 Mini as the base model, P

^2

raises its accuracy from 41.35% to 86.47% on multi-view reasoning, from 52.42% to 81.45% on relative depth, and achieves a 22% average gain across tasks, setting new state-of-the-art results. Even on smaller MLLMs, e.g., InternVL3.5-4B and Qwen3VL-4B, we observe 15-40% absolute gains from P

^2

, surpassing prior agentic, supervised, and RL-based tool-use methods-without any training or model modifications.

Abstract

Explore similar work

Don't Show Pixels, Show Cues: Unlocking Visual Tool Reasoning in Language Models via Perception Programs

Reasoning Theater: Disentangling Model Beliefs from Chain-of-Thought

Position: Reasoning After Perception Means Reasoning Without Vision