From Verification Failures to Reusable Guidance for Coding Agents
Organizations: University of Illinois Urbana-Champaign
Abstract
Coding agents need to establish that a program satisfies a specification and that the specification captures the requested behavior. We study how expert diagnosis of verification failures can become reusable guidance for this work. Our approach combines executable language definitions in the K framework with a kit of procedures for constructing specifications, repairing proofs, and auditing their adequacy. A human-guided development campaign on HumanEval, a benchmark of 164 Python programming tasks, achieves a 164/164 success rate with the semantics and the kit, measured by final AI audit Pass verdicts after two targeted repairs. To examine whether auditing detects problems that successful proofs leave unresolved, we construct 12 author-reviewed pairs of clean and defective packages. Every package passes its K proofs, and completed audits identify all defects and accept all clean packages. We then use KleverBench to test specification and proof construction for 31 programs with changed operator meanings. Comparisons with complete acceptance rules and equally long generic advice yield mixed results across two model and budget settings, motivating further work on selecting useful guidance within resource limits. Human-reviewed Optimism proofs establish expected pause reverts for six operations within declared input bounds under London semantics with unbounded gas. We report progress, difficulties, and lessons toward agents that deliver programs with checkable correctness arguments.
Figures & tables
| Semantics / kit | Pass | Concerns | Fail | Pass rate | Legit rate |
|---|---|---|---|---|---|
| Agent-authored / no kit | 23 | 41 | 100 | 14.0% | 39.0% |
| Supplied / no kit | 37 | 36 | 91 | 22.6% | 44.5% |
| Supplied / kit | 97 | 67 | 0 | 59.1% | 100.0% |
| Model | Rules | Generic | Kit | Kit–Rules | Kit–Generic |
|---|---|---|---|---|---|
| Luna | 15/31 | 15/31 | 19/31 | ||
| DeepSeek | 17/31 | 18/31 | 16/31 |
| Accepted attempts | Solved within four attempts | |||
| Semantics | Bare | Kit | Bare | Kit |
| Ordinary | 107/124 | 111/124 | 31/31 | 31/31 |
| Renamed | 90/124 | 109/124 | 29/31 | 30/31 |
| Swapped | 73/124 | 92/124 | 24/31 | 30/31 |
| All | 270/372 | 312/372 | 84/93 | 91/93 |
| 72.6% | 83.9% | 90.3% | 97.8% | |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Audit | Inputs and mechanical evidence | Judgment and independence boundary |
|---|---|---|
| Stage 2 | Candidate code, K artifacts, task statement, canonical implementation as behavioral evidence, and available checker results | Fresh model session examines semantics, specifications, and extensions. Canonical behavior is visible, so this is informed review. |
| Stage 6 | Prior audit and classification, frozen target/source identities, inventories, obligation correspondence, clean Lean build, and axiom checks in proof mode | Fresh session with the recorded producer model family. Treatment condition and prior review are visible. Adequacy, classification, and bridge judgments remain model decisions. |
| Defects detected | ||||
|---|---|---|---|---|
| Defect category | HumanEval tasks | Original | After retries | Clean accepted |
| Weak postcondition | 41, 53, 138 | 3/3 | 3/3 | 3/3 |
| Unsupported bridge | 54, 57, 120 | 2/3 | 3/3 | 3/3 |
| Source/proof mismatch | 8, 48, 42 | 3/3 | 3/3 | 3/3 |
| Incorrect semantics | 23, 49, 101 | 2/3 | 3/3 | 3/3 |
| Total | 12 pairs | 10/12 | 12/12 | 12/12 |
| Model / sample | Contrast | Kit-only | Control-only | Exact | Holm |
|---|---|---|---|---|---|
| Luna original | Kit–Rules | 8 | 4 | .3877 | .7754 |
| Luna original | Kit–Generic | 8 | 4 | .3877 | .7754 |
| Luna recovery | Kit–Rules | 8 | 3 | .2266 | .4531 |
| Luna recovery | Kit–Generic | 7 | 3 | .3438 | .4531 |
| DeepSeek original | Kit–Rules | 3 | 4 | 1.0000 | 1.0000 |
| DeepSeek original | Kit–Generic | 2 | 4 | .6875 | 1.0000 |
| Primary comparison outcome | Bare | Kit |
|---|---|---|
| Accepted | 270 | 312 |
| Rejected by pre-proof checks | 66 | 34 |
| Proof timeout | 28 | 4 |
| Proof error | 8 | 22 |
| All attempts | 372 | 372 |
| Acceptance constraint | Compatible archived bare instructions |
|---|---|
| Imports and claims only, no rule/syntax/configuration/context items | Explicitly stated. The agentic renderer incorporates these clauses. |
| Exact supplied program, symbolic initial state, no final existential weakening | Explicitly stated. |
| Coverage of required inputs | Weak preconditions requested, concrete coverage enforced by the checker. |
| Forbidden claim attributes | trusted , simplification , macro , alias , anywhere , owise , and priority are checked but not individually enumerated in that prompt. |
| Nine-program extension | Bare | Kit |
|---|---|---|
| Ordinary semantics | 31/36 | 35/36 |
| Renamed semantics | 27/36 | 31/36 |
| Swapped semantics | 14/36 | 14/36 |
| All | 72/108 | 80/108 |
| Selected initial runs | After targeted feedback | |||
|---|---|---|---|---|
| Example | Complete targets | Checked claims | Complete targets | Checked claims |
| HKG | 6/6 | 15/15 | 6/6 | 15/15 |
| DSToken | 5/6 | 18/28 | 6/6 | 28/28 |
| DSValue | 2/2 | 5/5 | 2/2 | 5/5 |
| Storage variable | 1/1 | 2/2 | 1/1 | 2/2 |
| Total | 14/15 | 40/50 | 15/15 | 50/50 |
| Selected initial activity | Input tokens | Cached input | Output tokens |
|---|---|---|---|
| HKG | 157,550,964 | 154,774,528 | 422,205 |
| DSToken | 149,267,850 | 146,764,928 | 427,152 |
| DSValue | 12,624,914 | 12,379,136 | 55,618 |
| Storage variable | 10,883,735 | 10,631,936 | 45,900 |
| Total | 330,327,463 | 324,550,528 | 950,875 |
| Implementation | Operation | Claims |
|---|---|---|
| OptimismPortal2 | proveWithdrawalTransaction | 11 |
| OptimismPortal2 | finalizeWithdrawalTransaction | 1 |
| L1StandardBridge | finalizeBridgeETH | 1 |
| L1StandardBridge | finalizeBridgeERC20 | 1 |
| L1ERC721Bridge | finalizeBridgeERC721 | 1 |
| L1CrossDomainMessenger | relayMessage | 1 |
| Paired evaluator outcome | Tasks |
|---|---|
| Both patches pass | 405 |
| Both patches fail | 85 |
| Baseline fails, reviewed patch passes | 8 |
| Baseline passes, reviewed patch fails | 2 |
| Total | 500 |
| Study | Agent/model | Resources | Endpoint and exposure |
|---|---|---|---|
| HumanEval historical | Codex 0.144.6, GPT-5.6 Sol, xhigh | Per-task kit/semantics hashes, K 7.1.293, Lean 4.22.0 | Stage 2 comparison, final Stage 6 separately. Development tasks, selected repairs. |
| HumanEval audit challenge | Codex 0.155.0-alpha.16.3, GPT-5.6 Sol, high | K 7.1.337, 24 isolated packages | Author-reviewed scopes and seeds. 24 original attempts; two capacity retries. |
| KleverBench Luna controls | Codex 0.149.1, GPT-5.6 Luna, high | Fixed fe49fb5 core, K 7.1.337 | 31 programs, three arms, one original attempt per cell. Four setup recoveries are separate. |
| KleverBench DeepSeek controls | Codex 0.149.1, DeepSeek-V4.1-Flash, high | Same task instructions, core and K image | 31 programs, three arms, one original attempt per cell. Provider transport and $0.10 cash allocation differ. |
| KleverBench historical | Codex 0.149.1, GPT-5.6 Luna | Kit fe49fb5 , K 7.1.337 | Four attempts, structural/coverage/proof checks. Exposure boundary unknown. |
| KleverBench extension | Same recorded Luna agent | Same kit, changed data/vocabulary | Separate nine-program cohort. |
| Kit snapshot | Skills | Bytes | Tokens | Distinct membership |
|---|---|---|---|---|
| Historical fe49fb5 | 8 | 111,020 | 24,966 | Includes on-paper reasoning |
| Released 5de7a09 | 8 | 118,181 | 26,202 | Includes client setup |
| Development 8a2f727 | 9 | 125,119 | 27,809 | Includes both |
| Observed difficulty | Retained procedure | Evidence requested |
|---|---|---|
| Symbolic state differs from invariant | Compare computation, bindings, and framed cells before revising mathematics | Residual state and matching repaired invariant |
| Helper rule replaces source execution | Classify the extension by its effect and establish the connection | Bridge-free execution theorem over the full matched context |
| Precondition removes difficult inputs | Review the complete intended domain and test coverage inputs | Rejected exclusions and documented case splits |
| Storage addresses alias | Apply writes in execution order and include the same-slot case | Claims covering aliased and distinct locations |
| Exception occurs after a log | State the execution boundary and model rollback at the call level | Raw-state and call-level claims |
| Accepted remote job loses its connection | Retain session and task identifiers and recover evidence | Task status, cancellation, and downloaded logs |