CS Paper Radar

Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparency

Baotong Zhang, Dean Foster, João Sedoc

cs.CL ·submitted 2026-09-21 17:00 UTC · v2
theoryhot direction

Abstract

When an LLM supplies an argument a user could not produce, how can the user decide whether to accept its claim? Inspired by interactive proofs, we pair a computationally unbounded LLM prover with a resource-bounded human verifier. The verifier checks requested details without seeing the LLM's internals; passed checks accumulate evidence toward an acceptance threshold. Given task-supplied bounds on false passes and human checking errors, we prove anytime-valid soundness against adaptive provers: the probability of ever accepting a false claim is at most a chosen error level. For a true claim, acceptance within the budget has probability at least the product of per-round probabilities that the LLM responds adequately and the human checks correctly, provided the threshold is reachable in time. Each additional check guards against false claims but gives a true claim another chance to fail. Which review lengths meet both error targets depends on the verifier's effort, cognitive load, expertise, and fatigue. With equal resources, we identify conditions under which the bounds certify a review by local checks but not a one-shot check. In LLM-only simulations on GPQA Diamond and Humanity's Last Exam, whether answers accepted without revision were more accurate varied by task and model pair.

Comment
44 pages, 3 figures, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Seal, Then Sample: Sampled Layerwise Proofs for Verifiable LLM Inference from GPT-2 to 70B

cs.CR cs.IR ·2026-09-23 ·Youki Lim, Sam Yong
code/data similarity 0.69
Abstract · 15 pages, 4 figures, 8 tables. Raw experiment logs and data tables: https://github.com/TrueOpen/slp-experiments

Verifying outsourced language-model inference requires a precisely identified computation and an audit whose cost a service can afford. We present Sampled Layerwise Proofs (SLP), a protocol and prototype that commits the boundary activations of every chunk of an inference trace, absorbs all commitments before any challenge is drawn, and then proves a verifier-selected subset of chunks together with the chunks that bind the prompt and the answer. Audit coverage becomes a runtime parameter over one set of commitments: on a TinyLlama-1.1B trace, proving seven of 47 chunks takes 22.0% of the time and 6.8% of the proof size of proving all 47. Because proof cost is dominated by weights rather than tokens, SLP packs concurrent requests into one trace under a block-diagonal causal mask and binds the prompt and answer of each request to its slot. Twelve packed requests are proved in 181.9 s, 6.5 times less than twelve separate proofs at the measured single-proof cost, and a simulated service proves twelve requests at 30.6 s per request with 0.6 s of verification each, rejecting a tampered answer. Disk-backed integer weights and streamed polynomial commitments let a single Llama-2-70B run complete on a 2 TB CPU host: 163 chunks sealed, five proved, a 4.34 MiB proof in 1,259 s, verified in 46.3 s without the weights. The proven object is a fixed-point canonical model; we trace a severe fidelity loss to the residual-stream bit width, repair it with an LLM-aware observer, and measure 84.8-84.9% argmax agreement with the floating-point reference over 334,705 WikiText-2 test positions. The limits are stated as precisely: guarantees cover proven chunks only, a fixed invalid chunk in the 70B setting is covered with probability 3/161, a manifest-only Fiat-Shamir schedule can be ground at 12.5 ms per attempt and needs an externally ordered challenge, and all measurements use a test reference string.

0.60

VeriHarness: Scaling Agentic Verification for Long-Horizon Tasks

cs.AI cs.MA ·2026-10-01 ·Caiqi Zhang, Rujun Han, Zifeng Wang, Zoey CuiZhu, Nigel Collier +2 more
similarity 0.66
Abstract

As LLM agents undertake increasingly complex, long-horizon tasks, verifying their outputs becomes increasingly challenging. We study how verification capability can be strengthened with a fixed base model, without access to reference answers or grading rubrics at test time. Repeated sampling yields multiple rollouts that can contain complementary correct claims, but we need a reliable verification mechanism to determine which claims to trust. We first find that disagreement often exposes correct alternatives, while consensus can conceal errors. These observations motivate VeriHarness, which turns the underlying LLM a generator uses into an agentic verifier by giving it a workspace, evidence tools, and reusable verification skills. A disagreement resolver checks competing claims against environmental evidence, while a consensus challenger tests shared claims and searches for omitted requirements. Their findings guide the selection and revision of the final artifact. Across five long-horizon workspace benchmarks and two frontier models, VeriHarness achieves the highest selection scores among the evaluated baselines. Evidence-backed revision further improves average performance, bringing gains over a single rollout to 6.2 points with Gemini 3.5 Flash and 6.4 points with Claude Opus 4.8. We further show that verification skills can self-improve from failure feedback, demonstrating VeriHarness as a novel and critical approach for scaling long-horizon agentic verification. We release the full pool of approximately 26,000 rollouts across all five benchmarks and both models, produced at a cost of over $100,000, to support future research on agentic verification.

0.43

Verification abundance, adjudication scarcity: what happens to mathematical knowledge when proof checking becomes free

cs.AI cs.LO ·2026-08-29 ·Maher Kallel, Mohamed El Louadi
position similarity 0.65
Abstract

In May 2026 an OpenAI model produced a counterexample to the Erdős unit distance conjecture. Five mathematicians published a human-verified version the same day, and the result entered the literature within weeks. In August 2026 the same laboratory published ten mathematical and theoretical computer science results, each accompanied by a machine-checkable Lean 4 certificate with no unproved steps. Four weeks later, one remained the subject of an unresolved dispute over whether its formalization meant what it claimed. We argue that this difference is structural. We distinguish three layers of verification: derivational validity, which a kernel checks; representational fidelity, whether the formal statement means the intended question; and epistemic significance. Only the first is mechanizable. Making it effectively free therefore does not eliminate verification work but shifts the burden to layers dependent on scarce expert attention. Measurements of the August corpus illustrate the shift. The kernel-checked proofs total 20.6 MB, while the statements requiring human audit total 55.6 KB, a ratio of 379 to 1. Yet those statements contain 218 bespoke definitions rather than relying on community-vetted ones. The audit surface is therefore small in volume but irreducibly expert. We argue that machine checking produces verification abundance while leaving adjudication scarce. We propose a six-category taxonomy of representational mismatch, a disclosure schema for machine-generated mathematical claims, and implications for software, cryptography, and regulated decision systems.

0.35

No Free Checker: A Survey of Verifiers for Robot Policies

cs.RO cs.AIcs.CVcs.LG+1 ·2026-09-08 ·Yang Wan, Xihang Yue, Zhirui Liu, Ziyuan Chu, Shuxun Wang +5 more
surveycode/data similarity 0.64
Abstract · Survey. 33 pages, 5 figures, 7 tables, 202 references. Covers reward models, success and failure detection, temporal-logic and formal verifi…

A verifier for robot policies reads a candidate behavior and returns a score for how well it did, used both to evaluate vision-language-action policies and to train them. Verifiers range from success detectors and reward models to runtime monitors, safety filters, and temporal-logic specifications. We survey roughly 150 verifiers and compare them along two properties. Availability is how much a verdict costs, how early in a rollout the verdict arrives, and how often a verdict can be asked for. Availability rises as verdicts get cheaper, earlier, and denser. Credibility is how much a high score tells us about the task. Credibility falls as the judgment becomes gameable and self-serving. We group the verifiers by who supplies the judgment: human verifiers, rule-based and formal verifiers, learned and pretrained verifiers, and model-intrinsic verifiers. Across the four families, we find that credibility falls as availability rises. Regardless of who supplies the judgment, there is no free checker. We then examine what validates a verifier itself, and how much a high score tells us. Three measures appear in the literature: agreement with human labels, the performance of the policy it trains, and behavior under reward hacking. We close with nine metrics that make a verifier claim checkable, and coordinates for the verifiers still to be built.

0.26

Who Verifies the Verifiers? Accountable Semantic Consensus for AI-Mediated Web Information Verification

cs.CR cs.DC ·2026-10-24 ·Yanna Jiang, Mingyuan Li, Xu Wang, Guangsheng Yu
theory similarity 0.64
Abstract

Large language models (LLMs) increasingly decide whether Web evidence supports online claims, often by voting over several assessors whose errors are presumed independent and benign. On the open Web, retrieved pages can steer the assessors that read them, and assessors from one model family fail together. We prove that even for independent assessors whose every output sequence is possible on both valid and invalid claims, any protocol that decides only from their outputs and always reaches an agreed verdict never rejects invalid claims or rejects valid ones with positive probability. We present Astral, which pins all assessors to one committed snapshot of the Web evidence. With up to f assessors faulty, Astral accepts a verdict only when 2f+1 assessors attest to it above a confidence threshold and no signed challenge stands. On five public benchmarks with two of seven assessors adversarial, Astral lowers pooled attack success to 21.5-53.1%, against 54.7-77.8% for majority voting. The cost is coverage, as without attack 16.0-61.7% of claims receive a binary verdict and the rest are disputed for audit. Our code runs at https://anonymous.4open.science/r/Astral-55F1.

0.30

Claim-Level Confidence Calibration for Reliable Decision Making with Large Language Models

cs.CL ·2026-08-23 ·Toghrul Abbasli, Kentaroh Toyoda, Yuan Wang, Li Chen
similarity 0.64
Abstract · In Proceedings of The 5th Workshop on Uncertainty Reasoning and Quantification in Decision Making (held in conjunction with ACM SIGKDD 2026)…

Large Language Models (LLMs) increasingly support decision-making in high-stakes domains, but they often hallucinate and express confidence that is misaligned with factual correctness. Response-level confidence is a coarse signal: a single generation can mix correct and incorrect statements, so a single number is not actionable for users that must accept, reject, or verify individual pieces of information. We study claim-level confidence calibration as a decision-relevant uncertainty signal: each response is decomposed into atomic, verifiable claims, and each claim is assigned a calibrated confidence using inference-time signals from consistency across samples and self-verification. Our framework operates in closed-box settings (no logits, no fine-tuning) and applies post-hoc calibration directly at the claim level, enabling selective intervention such as evidence retrieval or human review for low-confidence claims. Across TriviaQA and TruthfulQA we evaluate seven baselines on six recent models (Llama-3.1, Mistral, Qwen2.5, DeepSeek-R1, GPT-4, GPT-4o), and show that claim-level decomposition combined with post-hoc calibration reduces expected calibration error on factual questions while exposing failure modes on adversarial false-premise questions where decision-makers most need reliable uncertainty estimates.

0.26

ClaimScope: Label-Blind Witness Verification for Mathematical Claim Auditing

cs.AI cs.LG ·2026-10-15 ·Mushir Akhtar
publishedbenchmark similarity 0.64
Abstract · Accepted at NeurIPS 2026 Workshop (Mathematical Reasoning and AI)

Mathematical agents are commonly evaluated by answer accuracy or proof acceptance. We introduce ClaimScope, a 72-task benchmark for auditing proposed claims through a verdict, scope, counterexample, and repair. Tasks cover optimizer-state transport, finite-horizon affine recurrences, and exact $2\times2$ linear algebra. We evaluate Qwen3-8B with direct generation and four matched two-pass conditions, each starting from the same draft. A witness checker evaluates only the model's submitted state, without consulting reference verdicts or supplying a replacement witness. Its feedback still conveys information about validity: a verified refutation establishes that the claim is false, and rejection reasons can suggest structural fixes. In this evaluation, verifier feedback yields $23/39$ accepted counterexamples on invalid claims and $25/72$ safe completions, compared with $15/39$ and $20/72$ for checker-free generic feedback. Strict completion remains $17/72$; verdict accuracy changes from $47/72$ to $46/72$. The claim-grouped safe-completion difference is $.094$, with a bootstrap 95\% interval of $[.000,.198]$. All seven task-level gains follow horizon/input-length diagnostics. A post-hoc schema-only correction of the direct outputs reaches the same 25 safe tasks without another model call. These results separate claim classification from executable evidence, while locating the observed gains in witness-structure correction rather than demonstrating broader reasoning improvement.

0.34

Beyond the Verdict: Agentic Code Judging with Verifiable Feedback

cs.AI ·2026-10-13 ·Zheye Deng, Sha Li, Changlong Yu, Xin Liu, Qin Lu +2 more
similarity 0.63
Abstract · 28 pages

Test-time scaling for large language models (LLMs) can involve generating multiple candidate solutions for selection or revising an earlier attempt. To guide selection and revision, we need a verifier that can estimate candidate correctness and provide evidence of failure. In competitive programming, however, official judging systems provide authoritative verdicts under finite submission budgets, without revealing failure explanations or failing inputs. To provide informative feedback without consuming official submissions, we formulate a task in which a model judges and diagnoses a candidate program using only the problem statement and source code, with generated counterexamples serving as checkable evidence. To evaluate this task, we build USACO-JUDGE from the USACO 2026 contests, using accepted and unaccepted programs written by human experts and multiple LLMs. We then train ARBITER, a 35B mixture-of-experts (MoE) agentic verifier, with reinforcement learning in a generic execution sandbox. Training raises counterexample success on incorrect programs from 40.61% to 62.67% and mean binary verdict accuracy on USACO-JUDGE from 71.41% to 87.41%, approaching frontier verification performance. Beyond verification, ARBITER outperforms baselines in both code selection and refinement. In an IOI 2026 case study, ARBITER-guided refinement raises GPT-OSS-120B's expected score above the gold-medal threshold under the official submission limit.

0.56