Skip to content

Validation: executable semantics for v3 (signature-based sites, solvers, exec, verdicts) - #2

Open
yizhou7 wants to merge 30 commits into
v3from
validation-v3-sites
Open

yizhou7 wants to merge 30 commits into
v3from
validation-v3-sites

Conversation

@yizhou7

@yizhou7 yizhou7 commented Nov 15, 2026 •

Copy link
Copy Markdown
Collaborator

Executable semantics for v3 models, for review with zhuominc. Supersedes #1 (validation-v3): this branch contains its commits and replaces its design. In #1, each pick and rmw carried a solver inside the library. Here the solvers leave the library: the semantics is generic over a signature of choice sites, and the solvers live in validation/.

Merge with squash. The history includes #1's design, which a later commit undoes.

Library change (lean/TVA): the part that needs a decision

  • Generic semantics. Prog, Step, Safe and Launch are written for any Sig: a type of sites, the type of each site's value, and what each allows (Sig.Allows), plus atomic updates (Sig.Upd, UpdAllows). Step.pick continues with any allowed value; nothing in the library runs a solver.
  • Triton's catalog (TVA/Site.lean, a new trusted module listed in TVA.lean): one constructor per semantic family, not per tl.* function.
    • Sites: guards, hints, partial lanewise operations, values up to NaN, addc/mulAdd/maxMin, conversions, platform requests (plat over PlatQ, dotAdd, dotScaledAdd), float and index reductions, padding, disabled lanes and lane order, and sumBcastMul.
    • Updates: add, xchg, cas, max, bit, red.
    • Each constructor carries executable data (a Decidable instance, a lanewise partial function, concrete operands), never an erased predicate.
    • The relations it needs moved, unchanged, to TVA/Triton/<File>/Rel.lean.
    • Site.other remains only for the scans, sort, reshape_any and make_tensor_descriptor.
  • Meaning preserved, and proved so. Each Allows is the previous predicate by definition: validation/Preserve.lean has one theorem per family, by Iff.rfl. The semantics sees a site only through its relation: TVA.Launch.Erase proves that erasure is a bisimulation of Step (Step.defer included). So a kernel and its erasure have the same Outcomes, and are WellBehaved and Correct together; kernels with equal erasures mean the same (Outcomes/WellBehaved/Correct.congr_erase). tl.max_constancy* take [DecidableEq β]; no claim uses them.
  • Programs are compared up to their relations. Two places compare continuations: Step.defer and UsesSharedAtomicResult. They now compare Prog.erase (each site and update replaced by its relation), not =. With =, data a constructor carries but its relation ignores would count as a dependence. For example, Upd.cas v v allows only new = old for every v, yet = tells different v apart. With erasure, programs compare exactly as in v3. The regression case is cas_self, cas_self_ne and cas_self_correct in Preserve.lean. The kit's constancy premises follow; no claim or oracle proof changes.
  • Claims. No claim statement changed, so the Claim.lean sha256s are unchanged. Three oracle proofs change: upd := tl.addUpd … becomes u := Upd.add … (three lines), plus one rw [bind_assoc]. All 41 oracle proofs check with validation/check_oracles.py, which now exits 1 on a failure and accepts only the axioms propext, Classical.choice and Quot.sound.

Executor and verdicts (validation/, nothing trusted)

Design and guidelines: validation/PICKS.md. Plan: validation/PLAN.md.

  • Solve.lean: four solver outcomes (Ans):

    • ok: a value with a proof;
    • empty: a proof that there is none, i.e. predicted undefined behaviour;
    • none: a gap (unsupported, failed search, bad or missing oracle answer), never undefined behaviour;
    • assumed: an unproved value, only at platform-dependent sites.

    It also defines typed replay records (Record) with occurrence numbers.

  • Solvers.lean: one solver per Site/Upd constructor. A supplied answer that does not fit the request is reported as badAnswer, never silently replaced by a default.

  • Exec.lean: exec/execLaunch, total (done, ub, stuck, outOfFuel), with exec_sound/execLaunch_sound: whatever is reported is a run of the semantics, provided the assumed values are allowed.

  • Verdict.lean: certified, conditional n, discrepancy (a candidate finding), inconclusive, unsupported. Each comes with a theorem saying what it claims (ofRes_certified, ofRes_conditional, ofRes_discrepancy, ofLaunch_certified).

  • ops/: single-operation tests of tl.* definitions through the executor, plus mutants.

    • device.py (GPU) has not been run yet.
    • With --self: 91 cases, of which 77 certified, 11 conditional (platform operations) and 3 not run (fp8 without a device).
    • 33 of 38 mutants caught; the 5 missed compute the same values as the real definitions on those inputs.
    • Malformed inputs or device outputs (wrong length) are harness errors (bad_case, bad_device), never a verdict.
    • A case where the model calls every lane undefined is inconclusive.
    • Conversions are compared by ConvRel itself: within a dtype, the same bits are required.
  • run_test.py TEST … / run_test.py --ops …: compiles the modules (including Preserve.lean), collects verdicts, and exits 1 on a discrepancy. tests/vec_add_f32.lean is certified; tests/solvers.lean exercises every outcome.

  • COVERAGE.md (generated) lists the 121 tl.* operations: 70 certified, 15 platform, 7 assumed, 9 with no solver.

Open

See PLAN.md, "Open questions". Next is phase 4 (each kernel's model against the device), which needs a GPU.

🤖 Generated with Claude Code

yizhou7 and others added 30 commits November 11, 2026 18:48
- validation/PLAN.md: the plan for testing TVA v3 against the device (phases 0-5), the
  change to Prog that running models needs (solvers on pick, a plat effect), and the
  decisions to make with zhuominc.
- validation/TRUST.md: phase 0. For every device fact, tl.* definition, launch-semantics
  assumption and claim, what validates it today; the gaps, and questions for zhuominc.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Prog.pick P k erased P and its witness type in compiled code, so no executor
could run a model. pick now takes a Solve P (code that proposes a value with
its proof, asking typed Hints for what it cannot compute), and rmw a solver for
its update; Step ignores both, so no model's meaning changes. The platform
operations (math, div, cvt into fp8, dot, dot_scaled) move to a new
constructor plat q k (PlatQ), whose relation is the old env-then-pick predicate.

Solvers for the guards, hints, integer division and shifts, conversions (all
but into fp8), exact float operations, reductions (oracle tree, checked),
padding and integer atomics; Solve.none at the mixed platform/fusion sites,
scans, sort, reshape_any, max_constancy and float atomic_add
(validation/PICKS.md). Safe and SafeA gain a plat rule; the platform rules keep
their statements.

No claim file changes. All 41 oracle proofs check; two need a plat case in an
induction over Safe (recompute_wu_bf16, streamk_matmul_f16).

Pending zhuominc's review. docs/index/ not regenerated (make_index.py needs
flock, not on macOS).

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Phase 3 of validation/PLAN.md. exec runs one program on a concrete memory (a
hash table, CMem, read through toMem) with an oracle for a fixed environment;
execLaunch runs a launch's programs one after another in grid order.
exec_sound: whatever exec reports, Step can reach; execLaunch_sound: a
finished launch is a Reach trace to a Done configuration with the reported
memory, a reported ub a trace to a StuckUB one.

tests/vec_add_f32.lean runs the claim's model on a small instance and checks
x + y (run_test.py). check_oracles.py checks every claim and oracle proof
against the built library without the sandbox. PICKS.md: the status of each
choice site.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…tructor

A pick whose predicate mentions the platform (e.P) cannot be answered with a
proof. Ans gains a third answer, assume b: a value with no proof, which
Solve.assume takes from the oracle through a Query that carries the operands
(Query.plat, Query.convert, Query.atomicAdd). An executor reports what it
assumed; Step ignores solvers, so no meaning changes.

Prog.plat q k becomes a definition, env fun e => pick (q.Rel e.P)
(Solve.assume (.plat q)) k: the old env-then-pick pattern. Step.plat,
Step.platUB and the plat constructors of Safe and SafeA are gone; Safe.plat and
SafeA.plat are theorems with the statements the rules use, so no rule proof
changes, and the two claim proofs that needed a plat case are back to v3's text.

Solvers that assume: dot_add, dot_scaled_add (the dot with c as accumulator),
float atomic_add, tl.convert into fp8, and every Prog.plat site.

All 41 oracle proofs check unchanged (validation/check_oracles.py).

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…erage

exec and execLaunch return, with their result, the values taken without proof
(Assumed); exec_sound and execLaunch_sound are conditional on each satisfying
its site's predicate.

validation/ops: one tl.* operation at a time, through exec. cases.py writes edge
and random inputs as bit patterns, device.py runs one-operation Triton kernels
on a GPU (not yet run), Ops.lean runs the library's definitions and compares
lane by lane with the relation each allows; undefined behaviour is localised
per lane, reductions match against candidate trees. Mutants (wrong copies of
definitions) measure the inputs; with --self the model stands in for the
device: every mutant is caught where it differs from the definition.

coverage.py writes COVERAGE.md, one row per tl.* operation (121): what exec
does at it, its cases and mutants. PLAN.md: phase 1 is the single-op harness;
assumed answers; plat as a definition. PICKS.md updated.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…icResult

Solvers are stored in `pick` and `rmw` nodes, so `=` on continuations also
compared solvers. A continuation that used an atomic's old value only in a
solver (`Solve.ok old _`) counted as using the result in
`UsesSharedAtomicResult`, and made `Step.defer`'s premise vacuous, so a
deferred `pick` could choose per old value.

Add `Prog.SameUpToSolvers` (with `refl`, `of_eq`, `bind_left`) and use it in
both places, and in the "result unused" premises of `Safe.rmw`, `SafeA.rmw`,
`SafeA.shared` and the `Acc` lemmas, which are now weaker requirements.
Claim proofs only pass the premise along and are unchanged.

docs/index/ not regenerated (make_index.py needs flock).

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Add TVA.Launch.Solvers: kernels the same up to solvers
(`Kernel.SameUpToSolvers`) have the same outcomes, are well behaved
together and are `Correct` together (`Outcomes.congr_solvers`,
`WellBehaved.congr_solvers`, `Correct.congr_solvers`). The proof is a
simulation (`Step.sameUpToSolvers`, `LStep`, `Reach`), with
`SameUpToSolvers.symm`/`trans`/`bind` for `Step.defer`'s premise.

All 41 oracle proofs check unchanged; standard axioms only.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
It was stale since the solver commits (Core, Triton, Proof.*), and now
also lists TVA.Launch.Solvers.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
The semantics (`Prog`, `Step`, `Launch`, `WellBehaved`, `Correct`) is
now written for any `Sig` (a type class): the sites a program may leave
open, what each allows (`Sig.Allows`), and the kinds of atomic update
(`Sig.Upd`, `Sig.UpdAllows`). `pick s k` and `rmw d a u sem sc k` carry
no solver; `Step.defer` and `UsesSharedAtomicResult` compare
continuations with `=` again, and `Launch/Solvers.lean` and
`SameUpToSolvers` are gone. The core files mention no Triton site.

Triton's signature is the new `TVA/Site.lean` (`Site.sig`), for now
only `Site.other P` and `Upd.other upd`, plus `Prog.plat`. Every
`tl.*` `pick` and `rmw` is one of those; the solver code (`*Ans`,
`Tree.solve`, `Padding.ans`, ...) is removed from `Triton/*.lean`
(it is in 2d69b79, for stage 2: a site per kind, solvers in
validation/).

Proof kit: `Safe`/`SafeA` have a general `site` constructor and
`Safe.pick`/`SafeA.pick` theorems for `Site.other` with the old
statements; `PlatQ.Out`/`Rel` are reducible; `Prog.plat_bind` in the
platform rules' simp sets.

Claim files unchanged (sha256). All 41 oracle proofs check, standard
axioms only, with three one-line oracle edits: two `pick` -> `site`
case names, and `rw [bind_assoc]` in ssd_bmm_chunk_bf16 (the old
`refine` hit an elaborator bug, "declaration has free variables").

validation/Exec.lean does not build until stage 2 (PICKS.md says so).

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…play, verdicts)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Ans carries ok / empty / none (Gap) / assumed, the last only with a proof
that the request is platform dependent (Solvers.Platform). Records carry
the request (site or update with its old value), the occurrence number and
the value; Record.Assumptions is the condition exec_sound will take.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Site.guard c (with Decidable c) for the 16 Unit guards (assume,
static_assert, conversion format checks, block pointers, descriptors,
dot_scaled), Site.hint for the decidable compiler hints. Both Allows
reduce to the old Site.other predicate (Site.allows_guard,
Site.allows_hint: Iff.rfl). max_constancy stays Site.other (no
DecidableEq on its element type). Proof kit: Safe.guard, Safe.hint and
the SafeA analogues. All 41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Site.lanes s α g for idiv, irem, shl, ashr, lshr; Allows reduces to the
old predicate (Site.allows_lanes: Iff.rfl). Safe.pick and SafeA.pick now
take any Site, stated with Site.Allows, so oracle proofs that applied them
to Site.other (streamk_matmul_f16's divisions) work unchanged. 41 oracles
pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Their relations (FloatV.MaxRel, RoundsTo, AddRel) move unchanged to
TVA.Triton.Arith.Rel, before the catalog. Each Allows reduces to the old
predicate (Site.allows_*: Iff.rfl). 41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
ItofRel, FtoiRel and ConvRel (with ofIntRel, FloatRel, ofFloatRel) move
unchanged to TVA.Triton.Convert.Rel. Allows reduces to the old predicates
(Iff.rfl). 41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Prog.plat picks at Site.plat e.P q. The mixed dot forms keep their
disjunctive relation in one site. AccAdd and tl.MulRel move unchanged to
TVA.Triton.Dot.Rel. Allows reduces to the old predicates (Iff.rfl).
41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
The depth bound is a number the operation computes (sumBound e.P n), so
the site carries no platform. CmpKey, argCombine, ArgRes and enabledBy
move unchanged to TVA.Triton.Reduce.Rel. Allows reduces to the old
predicates. 41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Site.pad (Padding moves unchanged to TVA.Triton.Memory.Rel), Site.anyVals
and Site.order for atomicWith. Allows reduces to the old predicates.
41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
tl.atomicWith and tl.rmwSeq take u : Idx s → Upd d instead of a relation;
each Upd.Allows reduces to the old relation (tl.addUpd, tl.maxUpd,
tl.bitUpd, RedOp.Upd, which move unchanged to TVA.Triton.Memory.Rel and
TVA.Triton.Desc.Rel). Data and relation depend on the same operands, so
UsesSharedAtomicResult and Step.defer see the same programs as before.
The kit's atomic rules take u; three oracle lines that named upd := now
name u := (route_histogram_i32 twice, streamk_matmul_f16). 41 oracles pass.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
One site with both branches, as the mixed dot forms. Allows reduces to
the old predicate. 41 oracles pass, unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…gress

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Stage 2 step 3 of PICKS.md. Solvers.lean gives instance Site.solvers :
Solvers, ported from 2d69b79 onto the four-outcome Ans. TQuery is the
oracle's question family; sitePlatform/updPlatform mark the sites where
an unproved device value is allowed. A supplied answer that does not
fit is Gap.badAnswer, not a silent default; a missing device answer is
the new Gap.noOracle. Float sums fall back to a balanced tree under the
depth bound; sumBcastMul gets a solver. Solve.lean gains Ans.pi,
transport and tag. tests/solvers.lean: 44 #guards. lean/TVA unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
exec is generic over [Sig] [Solvers] and total: Res is done, ub what,
stuck occ gap or outOfFuel, with the log of every request answered
(Record, numbered across a launch; the n-th request gets hints O n).
Disabled load lanes come from a Fill. exec_sound and execLaunch_sound
are conditional on Record.Assumptions. vec_add_f32 runs end to end with
every answer proved; tests/solvers.lean also runs exec on small
programs. run_test.py compiles Solve, Solvers, Exec and rebuilds a
module when one it imports changed.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…_test.py on them

Verdict: certified, conditional (assumed platform answers), discrepancy (candidate
finding), inconclusive, unsupported; computed from exec/execLaunch reports, with
ofRes_certified/conditional/discrepancy and ofLaunch_certified proved. Ops.lean ported
to Ans/Record/Res; run_test.py collects verdicts, has --ops, exits 1 on discrepancy.
coverage.py reads the catalog; COVERAGE.md regenerated.
PICKS.md and PLAN.md: drop the progress log, the dated status and the
superseded solvers-on-pick design; keep the design rules, the site table
(current names), soundness, verdicts and how to run. TRUST.md cites names,
not stale lines. LIBRARY.md, SEMANTICS.md, TVA.lean, Platform.lean,
Site.lean, Safe/SafeA docstrings: match the Sig/Site design.

check_oracles.py: exits 1 on any failure; checks axioms against an
allowlist (propext, Classical.choice, Quot.sound) instead of grepping for
sorryAx; fails clearly when `lake env` fails or no OUT_DIR is given.

Co-Authored-By: Claude <noreply@anthropic.com>
Library:
- PlatQ moves to TVA.Site, next to the sites that use it.
- Upd.other removed (unused); the Site.allows_* lemmas move to
  validation/Preserve.lean, which now covers every family.
- Safe/SafeA: the constructor is `pick` over `Site` again (no wrapper
  theorem), so the two oracle proofs that renamed it are back to v3's text.
- tl.max_constancy, max_constancyN: hint sites ([DecidableEq β]); a
  Preserve theorem each. No claim uses them.
- decForallSuccLt is private; formatting left by the mechanical edits.

Validation:
- run_test.py: per-user, per-library default build dir; clear errors for
  a missing build or arguments; compiles Preserve.lean.
- Dead code removed (Ans.weaken, ofFlat, fmtDType, Upd.other's solver,
  `#eval outs`); halves/strided are total; files closed; scripts +x.
- COVERAGE.md regenerated: 70 certified, 9 no solver.

Checked: lake build TVA TVA.Proof; all 41 oracles; run_test.py
vec_add_f32 solvers; --ops --self (85 cases: 71 certified, 11
conditional, 3 no device; 30 of 33 mutants); make_index.py --check.

Co-Authored-By: Claude <noreply@anthropic.com>
…icts

Semantics (review finding P1): Step.defer and UsesSharedAtomicResult
compared continuations with `=`, which now sees constructor data a
relation ignores (e.g. `Upd.cas v v` is `new = old` for every v, but
distinguishes v). They now compare `Prog.erase`, which replaces each site
and update by its relation (Sig.pred), so programs compare as in v3. The
kit's constancy premises (Safe.rmw, SafeA.rmw/shared) follow; claims and
oracle proofs are unchanged.

ops/ (P2-P4):
- inputs and the device's output are checked against the case's dims
  (`inLen`, `outLen`); a mismatch is `bad_device`/`bad_case`, and a lane
  missing on either side is a difference;
- a case whose every lane the model calls undefined is inconclusive;
  `compared` reports the defined lanes;
- tl.convert is compared by ConvRel where the platform plays no part
  (same bits within a dtype; exact from fp8 on finite inputs); new
  same-dtype and fp8-source cases.

Checked: build; all 41 oracles; run_test.py vec_add_f32 solvers;
--ops --self (91 cases: 77 certified, 11 conditional, 3 no device; 33 of
38 mutants, the 5 missed are equivalent on those inputs); a forged device
file (short output: bad_device; all-zero divisors: inconclusive; f32->f32
payload change: discrepancy); make_index.py --check.

Co-Authored-By: Claude <noreply@anthropic.com>
Review finding: Preserve.lean shows each site allows what the old
predicate did, and Program.lean said programs with the same erasure have
the same meaning, but nothing proved the latter, and Step.defer and
UsesSharedAtomicResult now depend on erasure.

Add TVA.Launch.Erase: erasure is a bisimulation of Step (Step.erase,
Step.unerase, Step.defer included), lifted through LStep and Reach to
Outcomes (ok, ub, hang), UsesSharedAtomicResult, WellBehaved and
Correct (`*.erase`: a kernel means what its erasure over Sig.pred
means). Corollaries `Outcomes/WellBehaved/Correct.congr_erase`: kernels
with the same erasure mean the same.

Regression in validation/Preserve.lean: a continuation passing the old
value to `Upd.cas old old` has constant erasure (cas_self) though the
programs differ (cas_self_ne), and such a kernel is Correct exactly when
the constant version is (cas_self_correct).

Docs point to the theorem; index regenerated.

Checked: lake build TVA TVA.Proof; all 41 oracles (standard axioms);
run_test.py vec_add_f32 solvers; make_index.py --check. Claim files and
oracle proofs unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
@yizhou7
yizhou7 marked this pull request as ready for review November 16, 2026 00:57

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant