CS Paper Radar

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

Youki Lim, Sam Yong

cs.CR cs.IR ·submitted 2026-09-23 05:11 UTC · v1
code/data

Abstract

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.

Comment
15 pages, 4 figures, 8 tables. Raw experiment logs and data tables: https://github.com/TrueOpen/slp-experiments

Closest papers

Nearest neighbours by meaning across the whole index.

Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification

cs.AI cs.LOcs.PLcs.SE ·2026-10-07 ·Shuangjie Yao, Nikolaus Holzer, Mark Paul Santolucito, Baishakhi Ray, Suman Jana +1 more
benchmarktheory similarity 0.69
Abstract

Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It's a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals. Selection stays symbolic as a topological pass over the proof graphs. Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates. On five program verification benchmarks in Lean 4 including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.

0.12

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

cs.CL ·2026-09-21 ·Baotong Zhang, Dean Foster, João Sedoc
theoryhot direction similarity 0.69
Abstract · 44 pages, 3 figures, 6 tables

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.

0.38

Fresh-Challenge VDF Attestations for Model-Relative Response Latency

cs.CR ·2026-09-11 ·Ansar Yesmukhanov, Aruzhan Tlessova
benchmarktheory similarity 0.68
Abstract · 9 pages, 1 figure

Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? Verifiable delay functions (VDFs) make this possible in principle: evaluation requires T sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in the numerical value of T for standard constructions. Thus a delay can be astronomically large to evaluate yet succinctly represented and feasibly checked. A VDF proof for a chosen message alone is insufficient because it may be precomputed. We specify and analyze Fresh-Challenge VDF Attestations (FCLA), a protocol composition that binds a VDF to an unpredictable public challenge, a message, and independently auditable release and receipt records. Under explicit assumptions about VDF sequentiality, the challenge source, witness logs, and a calibrated upper bound on an adversary's sequential evaluation rate, an accepted FCLA transcript is inconsistent with post-challenge generation by an adversary in that bounded model. The result neither identifies a named claimant nor excludes relaying, outsourcing, or a faster unmodeled machine. A benchmark of the public reference implementation confirms the expected empirical separation between evaluation and verification on one documented machine. Our contribution is a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive.

0.45

PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication

cs.CE cs.AIcs.CRcs.MA ·2026-10-29 ·Bravish Ghosh
benchmarktheorycode/data similarity 0.67
Abstract · 50 pages, 9 figures, 15 tables. Specification, conformance vectors, verifier and benchmark: https://github.com/Cygnux-Labs/PCM-protocol

When one AI agent tells another that "the tests passed" or "a person approved this refund", the receiver has only the sender's word. A2A and MCP authenticate the channel, but the sender is the party in doubt, so a prompt-injected agent can launder fabricated facts and authority through a multi-agent system. We present Proof-Carrying Messages (PCM), a protocol in which each claim carries evidence: records from an append-only Merkle log that the agent cannot write, with inclusion proofs, signed by an attesting signer the agent cannot control. Receivers check messages offline and give each claim a three-valued result: proven, unproven or failed. A claim that rests only on the agent's own report is never proven. Authority travels as grant chains rooted in a recorded human approval, and the chains can only narrow. We specify four claim types, a typed caveat algebra, replay rules that survive restarts, and strict readings that make independent verifiers agree, and we prove the resulting security properties. On a pre-specified benchmark of 926 messages from real runs, 712 of them lies in 16 classes, PCM accepts 10 lies, all of them stale evidence (1.4%, 95% CI 0.8-2.6%). Plain A2A accepts all 712, and models of six deployed protocols (A2A with signed Agent Cards, uAgents, RFC 9421, SCITT, AP2, Verifiable Intent) accept 504-712. Two independent verifiers agree on all 926 verdicts, and verification takes about 1 ms.

0.23

Infrastructure for Verifiable AI: Where Proof Costs Go and How Hardware Can Help

cs.AR cs.CRcs.LG ·2026-11-12 ·Yihan Xia, Wenxin Xu, Taotao Wang
hot direction similarity 0.67
Abstract · 16 pages, 8 figures, 5 tables

Users of artificial intelligence services, including those powered by large language models and other transformer-based models, need assurance that inference and training follow the declared computation without exposing private models or data. Zero-knowledge proofs can provide this assurance, but proof generation remains expensive. Hardware acceleration research often reports gains for individual cryptographic operations, leaving their effect on the full cost of proving neural-network workloads, particularly large transformer models, unclear. We introduce a four-layer framework linking verifiable AI workloads, proof systems, cryptographic kernels and hardware platforms, use it to review the literature, and add original measurements of six provers and seven kernels to identify which costs matter in practice. Our measurements show that the dominant cost changes with the proof system and input length. In low-rank fine-tuning, the cost of opening commitments to fixed model weights remains nearly constant across input lengths from 64 to 2048, while the work associated with intermediate values grows. A 13-billion-parameter fine-tuning configuration exceeds the capacity of a 40-gigabyte graphics processor but completes on an 80-gigabyte device, showing why capacity must be assessed alongside execution time. Our kernel profiling further identifies instruction issue and synchronization limits that a bandwidth-only model misses. We use these findings to assess graphics processors, reconfigurable logic, custom chips and existing artificial intelligence accelerators. The resulting research agenda connects proof-friendly numeric formats, reuse of fixed-weight commitments, heterogeneous execution and shared benchmarks to the measured bottlenecks. Effective acceleration requires selecting hardware and proof-system optimizations around the cost profile of the target workload.

0.34

LLM-Assisted Automatic Security Proofs for Cryptographic Protocols: How Far Are We?

cs.CR cs.SE ·2026-09-28 ·Tianjian Liu, Shicheng Feng, Jin'ao Shang, Xiaoting Lyu, Bin Wang +3 more
similarity 0.67
Abstract · 12 pages, 12 figures

Large language models (LLMs) have shown strong potential for assisting software and security analysis tasks, yet their effectiveness in cryptographic symbolic protocol verification remains insufficiently understood. In this paper, we conduct the first systematic evaluation of the capability of state-of-the-art LLMs in cryptographic symbolic protocol verification. To quantify this capability, we propose \textsc{CRoST} (Coverage Rate of Solve Tree), a proof-based metric derived from the verifier's proof skeleton that measures the similarity between generated lemmas and reference lemmas. We then establish the rationale of \textsc{CRoST} through both theoretical analysis and empirical validation. The evaluation results show that state-of-the-art models achieve 38.82\% coverage on average, with 14.4\% of generated lemmas exceeding 80\% coverage, indicating that LLMs can already generate useful lemmas to a certain extent. However, they still exhibit non-trivial failure modes on complex multi-phase protocols, show diminishing returns under naive scaling, and incur substantial verification overhead. These findings clarify the practical potential and limitations of LLMs for protocol verification and motivate future work on complex real-world protocols.

0.22

Caleta: An Evidence-Oriented Trust Layer for Reproducible Local Large Language Model Inference

cs.SE ·2026-11-06 ·Joan-Marc Fisa
benchmark similarity 0.66
Abstract

Local large language model (LLM) inference is often described as private, verified, or reproducible without separating the technical claims behind those terms. This paper presents Caleta, an Apache-2.0 process supervisor and evidence layer around llama.cpp rather than a new inference engine. Caleta combines versioned manifests, exact-size and SHA-256 verification, controlled backend construction, a restricted OpenAI-compatible proxy, prompt-free execution records, benchmark reports, and a small conformance suite. Its contribution is the composition of these mechanisms into explicit contracts that distinguish integrity from authenticated provenance and privacy controls from operating-system isolation. We evaluate the implementation through static checks, 22 unit tests, deterministic end-to-end tests on Ubuntu, macOS, and Windows, and a pinned real-model experiment on Windows CPU using Qwen2.5-0.5B-Instruct Q4_K_M and llama.cpp b11981. The real experiment validates artifact verification, startup, model listing, non-streaming and server-sent-event chat, and conformance. Three independent benchmark invocations produced fifteen successful warm requests with no failures. In this single configuration, median time to first token was 18.066 ms and median decode throughput was 54.394 tokens/s. These descriptive measurements do not establish cross-engine superiority, output quality, energy efficiency, or hardware-general performance. Raw JSON, commands, and environment metadata are published. Remaining challenges include signed manifests, time-of-check/time-of-use replacement, operating-system containment, proxy-overhead measurement, and broader experimental matrices.

0.12

ClaimReceipt: Verifying Evidence Sufficiency and Coverage in Agent Evaluations

cs.AI cs.CRcs.MA ·2026-09-02 ·Peiying Zhu, Sidi Chang
similarity 0.66
Abstract · Submitted to Who Verifies the Agents? Toward Reliable Agent Development (NeurIPS 2026 workshop). 8 pages, 1 figure, 7 tables

Agent evaluations face two distinct evidentiary questions: whether a reported claim is recomputable from retained evidence (sufficiency), and whether the retained records cover the committed experiment set (coverage). Generic logs and hash-linked transcripts answer neither reliably. We introduce ClaimReceipt, a claim-relative receipt specification and selective verifier that binds typed transaction evidence to a signed experiment manifest and returns PASS, INVALID, or INCONCLUSIVE per claim. We freeze the specification before implementation (SHA-256 18d109...b81). On 1,392 historical buyer--seller records, a CR-2 verifier reproduces all five manually labeled audit verdicts, exactly replays 600 deterministic and 792 post-generation records, makes every one of 13 declared field groups non-redundant under tested ablations, and returns the expected result on 11/11 semantic faults with 0/8 false positives. We then run a separate prospective CR-3 epoch: 30 assignments are committed before inference, terminal receipts are signed and chained, and private evidence is encrypted for an auditor. Complete evidence yields coverage and accounting PASS; withholding one terminal receipt returns INCONCLUSIVE_COVERAGE, while withholding all private openings preserves coverage and protocol verification but makes economic claims inconclusive, exactly matching a preregistered prediction. Receipt instrumentation adds 0.021% of model-inference time and 9.9 KB per transaction. A specification-legibility probe indicates that our own frozen specification is not yet unambiguous to an independent reader. Claim verification therefore requires both claim-sufficient evidence and a committed universe against which omissions become visible.

0.38