P074 Guarantee-checking logic and its limits
What are the limits of automated guarantee-checking of workloads, and what recomputation fraction is needed to catch a falsified kernel?
Limits of automated guarantee checking of workloads.
Status
Analyzed Proposals and analysis only: random partial recomputation by the guarantee processor, local LLM-based checks, and the authors' own argument that fully automatic on-device compliance checking 'appears unlikely to be feasible'; Reuter, Marks & Baker (2026) give a formal framing (a policy over an algebraic graph; 'functional exclusion' left open). No recomputation fraction has been derived or measured for any detection probability; no automated checker has been run on camouflaged logs. Stated limits: static graphs cannot express mixture-of-experts routing; the relevance of Rice's theorem is 'unclear'.
a general-purpose way to verify each atomic computation is to use the guarantee processor to randomly re-compute a portion of each result
Posed by
- Petrie, Aarne, Ammann & Dalrymple (2025), Overview of Flexible Hardware-Enabled Guarantees (flexHEG Part 1):
Developing robust algorithms to locally check whether accelerator usage is compliant with guarantees.
(Recommended Research, p19, L815–816) (source states the problem but not the quantity the question asks for)
Also raised in: Petrie & Aarne (2025), Technical Options for Flexible Hardware-Enabled Guarantees (flexHEG Part 2); Peigné-Lefebvre, Nguyen & Wang (2026), Zero Knowledge Verification for Frontier AI Training Is Possible, arXiv 2606.05433; AI Security Forum, Requests for Discussion; Proofworks, Living Verification Documents.
Sub-questions
| ID | Sub-question | What the sources report |
|---|---|---|
| P074.1 | What fraction of outputs must be randomly recomputed to detect a falsified kernel at a stated detection probability given float nondeterminism and untrusted internal state? | open |
| P074.2 | What detection rate do automated local compliance checks (algorithms, local LLM reviewers, red-teamed frameworks) achieve on camouflaged non-compliant logs? | open |
| P074.3 | How many engineer-hours does a manual log audit of one large run take, and what fraction of planted non-compliance does it catch? | open |
| P074.4 | How often do compiler/engine optimisations change a model's algebraic graph, and what instruction-level ambiguities remain after external compilation? | open |
| P074.5 | Can static compute graphs express data-dependent MoE routing for verification? | a source suggests an answer (not checked) |
Sub-questions not yet stated precisely enough to check
| ID | Sub-question |
|---|---|
| P074.6 | Are Rice's-theorem limits practically relevant to static analysis of accelerator workload guarantees? |
| P074.7 | Can misspecified guarantee logic be exploited, i.e. does a non-compliant program exist that matches compliant outputs (functional exclusion)? |
| P074.8 | Can fully automatic on-device compliance checking work? |
Possibly relevant work found by automated search
Found by AI agents searching for this problem's sub-questions, mostly by keyword and citation in the OpenAlex scholarly database and on the web; a second AI pass reviewed each one, and we spot-checked some by hand. They seemed reasonably related, as far as one can tell from outside each paper's field. Some come from neighbouring fields, such as arms control and financial audit, and bear on the problem by analogy. Not reviewed against the status above; a paper listed here does not change that status. 928 of 1052 quotes checked word for word against the paper's text.
For P074.1: What fraction of outputs must be randomly recomputed to detect a falsified kernel at a stated detection probability given float nondeterminism and untrusted internal state?
Data
- problems.csv — one row per problem
- problem_status.csv — status, scope and evidence per problem
- problem_sources.csv — the posed-by quote and other documents per problem
- leaves.csv — all sub-questions, including those without a checkable form
- leaf_sources.csv — every source row behind each sub-question