Repository navigation
Conversation
- 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
marked this pull request as ready for review
November 16, 2026 00:57
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Executable semantics for v3 models, for review with zhuominc. Supersedes #1 (
validation-v3): this branch contains its commits and replaces its design. In #1, eachpickandrmwcarried 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 invalidation/.Merge with squash. The history includes #1's design, which a later commit undoes.
Library change (
lean/TVA): the part that needs a decisionProg,Step,SafeandLaunchare written for anySig: a type of sites, the type of each site's value, and what each allows (Sig.Allows), plus atomic updates (Sig.Upd,UpdAllows).Step.pickcontinues with any allowed value; nothing in the library runs a solver.TVA/Site.lean, a new trusted module listed inTVA.lean): one constructor per semantic family, not pertl.*function.addc/mulAdd/maxMin, conversions, platform requests (platoverPlatQ,dotAdd,dotScaledAdd), float and index reductions, padding, disabled lanes and lane order, andsumBcastMul.add,xchg,cas,max,bit,red.Decidableinstance, a lanewise partial function, concrete operands), never an erased predicate.TVA/Triton/<File>/Rel.lean.Site.otherremains only for the scans,sort,reshape_anyandmake_tensor_descriptor.Allowsis the previous predicate by definition:validation/Preserve.leanhas one theorem per family, byIff.rfl. The semantics sees a site only through its relation:TVA.Launch.Eraseproves that erasure is a bisimulation ofStep(Step.deferincluded). So a kernel and its erasure have the sameOutcomes, and areWellBehavedandCorrecttogether; kernels with equal erasures mean the same (Outcomes/WellBehaved/Correct.congr_erase).tl.max_constancy*take[DecidableEq β]; no claim uses them.Step.deferandUsesSharedAtomicResult. They now compareProg.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 vallows onlynew = oldfor everyv, yet=tells differentvapart. With erasure, programs compare exactly as in v3. The regression case iscas_self,cas_self_neandcas_self_correctinPreserve.lean. The kit's constancy premises follow; no claim or oracle proof changes.Claim.leansha256s are unchanged. Three oracle proofs change:upd := tl.addUpd …becomesu := Upd.add …(three lines), plus onerw [bind_assoc]. All 41 oracle proofs check withvalidation/check_oracles.py, which now exits 1 on a failure and accepts only the axiomspropext,Classical.choiceandQuot.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 perSite/Updconstructor. A supplied answer that does not fit the request is reported asbadAnswer, never silently replaced by a default.Exec.lean:exec/execLaunch, total (done,ub,stuck,outOfFuel), withexec_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 oftl.*definitions through the executor, plus mutants.device.py(GPU) has not been run yet.--self: 91 cases, of which 77 certified, 11 conditional (platform operations) and 3 not run (fp8 without a device).bad_case,bad_device), never a verdict.inconclusive.ConvRelitself: within a dtype, the same bits are required.run_test.py TEST …/run_test.py --ops …: compiles the modules (includingPreserve.lean), collects verdicts, and exits 1 on a discrepancy.tests/vec_add_f32.leanis certified;tests/solvers.leanexercises every outcome.COVERAGE.md(generated) lists the 121tl.*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