Skip to content

[decision] D3: formulation of universal data handles generated from the Atlas #108

Closed

Description

@afflom

Decision for the authority, recorded by the completion plan #106. It blocks #122.

Question. What is a universal data handle (Dr. Virdee's theme), as LexLean's universal theorems?

Already fixed.

  • Handles are generated from the UOR Atlas, the stated generator of every LexLean proof, carried in every proof's header (C7). The native Atlas source exists (examples/uor-atlas, 293 entries in language/uor/atlas).
  • A handle pairs a kind with a content digest, as uor-addr's realization IRI and κ-label already do.
  • MNIST's facts (The model's facts as kernel-checked theorems (MN-07) mnist#6) are test cases the handles must reproduce: positive requantization multipliers, distinct per-class fc multipliers, the accumulator ranges, the unread conv2 positions, a saturation-free tap pairing, and the positive dequantization scale before the 3×3 pool.

Still open. What a handle carries, and the completeness statement over handles: for the declared objective, the program built from a datum's handles costs no more than any program computing the same function.


Generated by Claude Code

Activity

  1. humuhumu33 commented on Oct 23, 2026

    @humuhumu33
    Contributor

    D3: what a handle and the completeness statement can be built from today. Read from release/v0.4 at 936eb3df3. Facts that exist only in a draft or on release/v0.5 are marked as such. MNIST is read at 515f75f9f. This comment states facts and makes no recommendation. It leaves the realization grammar and the claim class to #107.

    The Atlas today

    • Package. language/uor/atlas/lexicon.toml declares lexlean.uor.atlas@1.0.0, language 1.0. It has 293 entry files under language/uor/atlas/entries/. Every entry has spec, id, category, surface_arity, frame, a [denotation] and one [[form]]. Two entries add signature and one adds [render].
    • What an entry is. Every one of the 293 denotations is kind = "document", module = "Atlas", and a component naming a declaration of the native source, for example UorAtlas.Blocks.D17. Categories: 291 label-word, 1 type-noun (atlas-presentation), 1 function (atlas-support, AtlasPresentation -> Nat). No entry field is a content digest. The kind-like fields are category and the denotation kind, which is document for all 293.
    • Native source. examples/uor-atlas is a language-1.0 project of 86 modules (80 Atlas modules, 6 under Prelude/), 24 MB of \coredata, which language 1.2 refuses (AU-13). Its declarations are kernel terms over roots, blocks, bitsets, Nat, Int and Rat. Not one source file names Gnaf, TargetSemantics, Certification, a fixed-width type (UInt8 to UInt64, Int8 to Int32), ByteArray, sha256, cost or steps (grep -l -w over src/, 0 files each).
    • Registers. language/uor/atlas-registers.toml holds 279 live labels (entry, line 19), 12 ambient (line 58), 2 non_denotable (line 64), 6 retracted and 1 superseded from line 66. The 279 live and 12 ambient labels are the 291 label-word entries. Its header says it "participates in the compiler-semantics digest".
    • How it is kept. No program generates the entries. validate-model audits them against the source: audit_atlas_registers, audit_atlas_denotations and audit_atlas_exercise (xtask/src/audit.rs:292, :457, :636; called at xtask/src/codegen.rs:64-67). The records under examples/uor-atlas/expected/ are regenerated by cargo xtask verify-examples, sharded in CI (VR-19, VR-23, EX-08).
    • Identity. language/uor/ is on neither exclusion list of crates/lexlean/src/lib.rs:155-180, so it is hashed into the 1.0, 1.1 and 1.2 compiler-semantics IDs (lib.rs:286-300). A change to an entry or to the registers moves all three.
    • Where a proof carries it. language/bootstrap.toml:31-35 registers the package with unconditional = true for language 1.0. bootstrap-1.1.toml and bootstrap-1.2.toml do not register it. The Atlas appears in a build record only as the fourth package of a language-1.0 module's lexicon closure, with its manifest_sha256 and tree_sha256 (examples/nat-add-zero/expected/build/lexicons/Main.closure.json, 8 such files in 4 examples). The closure of a language-1.2 module lists lexlean.core, lexlean.std.bool and lexlean.std.nat (stdlib/expected/build/lexicons/Sha256.closure.json). Generated language-1.2 Lean imports Init, runtime modules and the project's own modules (stdlib/expected/build/modules/LexLeanStd/Buffer.lean:1-5). No language-1.2 record, MNIST's included, names the Atlas. SPEC.md does not use "proof header".

    What already pairs a kind with a digest

    Pair Where What it carries What it does not carry
    Artifact declaration SPEC.md §17.12 rule 2 (lines 3292-3331), language 1.2 role (closed: parameters, table, vocabulary, binary, dataset), schema (closed: bytes, int_tensor{element, shape}, utf8_lines), sha256, length, type. It elaborates to W.bytes, W and the kernel theorem W.decoded (decide for tensors and lines, rfl for bytes). The digest is checked at link against [[artifact_source]] (LLR3007); "verification does not re-digest the emitted literal", so the link from digest to bytes "rests on construction". No theorem about W beyond W.decoded, no cost, no lower bound. MNIST's ten parameters are exactly this (src/Mnist/Params.lex.tex, int8, int32 and int64 tensors).
    Artifact as a constant of the program (#115) Draft PRs on release/v0.5: #228 (rows), #230 (TC-08), #238 (RB-18), #239 (SP-24, MD-14). Not on release/v0.4. TC-08: a literal is charged its node weight once per read. RB-18: a heap literal read from a function of no parameters is a once-per-thread constant. SP-24/MD-14: the decoded value is one literal of the lowered program, equal to the decoding of W.bytes. A cost per read of the datum, not a bound on any program that reads it. Nothing relates two programs over the same datum.
    Prepared artifact of a GNAF request compiler/src/Gnaf.lex.tex:114-118, SPEC.md §17.15 item 2 Prepared {kind : ActionKind, artifact : String}: the preparation action that produced it and the SHA-256 of its bytes, bound in the common initial state of every competitor. Only binds; it is charged by its action kind (free on a prepared boundary). No property of the bytes.
    Lexicon package in a closure lexlean/lexicon-closure/1 records id, version, manifest_sha256, tree_sha256, entry ids and categories. The Atlas is one, in language 1.0 only. No statement; it pins vocabulary.
    SHA-256 content identity (#126) release/v0.4: the compiler digests with the sha2 crate (crates/lexlean/Cargo.toml:27). The LexLean seam (crates/lexlean/sha256_package.rs, the certified rust-std/sha256 export) is on release/v0.5 only, closed 2026-10-20. Every source, semantic, artifact and attestation identity. LexLeanStd.Sha256 is language-1.2 source in stdlib/. A digest names bytes. It carries no kind and no theorem.
    κ-label (uor-addr, per the #110 comment) Outside LexLean. #127 (L5.2) is unbuilt and D7 is open. <axis>:<hex> of canonical bytes. The five compositions (G2, F4, E6, E7, E8) hash canonical forms of their operands. The #110 probe verified kappaLabel of one JSON value by rfl. No cost, no lower bound. Composition theorems over compare_bytes failed rfl (LLV7002).

    What §17.18 consumes, and the shapes MNIST#6 asks for

    Premise shapes of Certification (compiler/src/Certification.lex.tex:18-28, Fact at :67-76, SPEC.md lines 6324-6343), one premise per system of U_sys:

    Premise Fact Evaluated on
    excluded p the system is never admitted the domain argument at position p
    pays_at_least ps an admitted system costs at least the steps on positions ps plus its preparation the arguments at positions ps
    measured the system's whole status the whole domain
    reduced s a strictly cheaper admitted rewriting exists nothing: a schema among collapse, specialize_small, specialize_large
    bridge {slope, offset} (route representation) an admitted system costs at least slope * size + offset each system, measured or bounded

    Every fact is about one system on positions of the request's finite domain : List Value (Gnaf.lex.tex:206-220, Request), stable at larger fuel. No premise is a theorem quantified over every system of a kind or over every input. #122 states: "Without them certification must evaluate the whole universe."

    UOR-Foundation/mnist#6's facts, with the theorem shape each one has. "Closed" means a statement about the parameter values alone; "all inputs" means a statement quantified over the network's inputs. The consequence column quotes only what MNIST#6 states.

    # Fact Shape Over Consequence MNIST#6 states
    1 34 requantization multipliers positive positivity of every element closed; the monotonicity it implies is over all inputs "requantization is monotone and max pooling commutes with it"
    2 ten fc multipliers distinct pairwise distinctness closed none
    3 conv1 accumulator plus bias in [−205,015, 210,788] interval bound on b + Σ wᵢxᵢ all inputs in a code range none
    4 conv2 accumulator plus bias in [−1,477,999, 878,711] as 3 as 3 none
    5 pool reads rows and columns 0–11 of 14×14 (52 unread) read set of an index function the program, all inputs none
    6 int16 saturation possible for 28/104 and 113/1,600 pairs existence of a saturating input, counted closed per pair none
    7 a saturation-free pairing exists in every channel ∃ pairing ∀ input, no saturation closed per channel none
    8 dequantization scale before the pool positive positivity a value only the ONNX file holds (UOR-Foundation/mnist#15, D6) the graph that pools codes and the graph that pools after dequantizing "agree only under this fact"

    None of the eight is a statement about cost. Facts 1 and 8 are stated as conditions under which two programs agree.

    Probe

    Question. Can language 1.2 state MNIST#6's facts as theorems over a datum that pairs a kind with a digest, and prove them?

    Setup. The probe is a language-1.2 project committed nowhere. It holds MNIST's artifact files fetched at 515f75f9f, whose SHA-256 values equal MNIST's lexlean.toml. Each parameter is declared as MNIST declares it: role parameters, schema int_tensor, sha256 and length. lexlean was built at 936eb3df3, with Lean 4.32.1 pinned. The commands were these, from the project directory:

    lexlean fmt && lexlean lock && lexlean check
    lexlean verify
    

    Offline arithmetic. Before the probe, I recomputed facts 1 to 4 from the artifacts with Python. They hold as stated. The ranges in facts 3 and 4 are reproduced exactly when every input code ranges over [0, 255]: conv1 gives [−205,015, 210,788] and conv2 gives [−1,477,999, 878,711]. Other input ranges give other numbers, for example [−199,511, 199,564] for conv1 over [−128, 127].

    Statement Fact Proof form check verify
    multipliers_count: the conv1, conv2 and fc multipliers appended have length 34 1 decide passes passes
    multipliers_positive: every one of the 34 is positive 1 decide passes passes
    fc_multipliers_distinct: the ten fc multipliers are pairwise distinct 2 decide passes passes
    conv1_range_high, conv1_range_low: over the eight channels, the largest b + Σ_{w>0} 255·w is 210,788 and the smallest b + Σ_{w<0} 255·w is −205,015 3, closed over the parameters decide passes passes
    taps_agree: channel 0's taps read from conv1Weights equal a 25-element literal list decide passes passes
    channel0_high_literal, channel0_low_literal: for all x0…x24 in [0, 255], dot taps xs + b lies in [−156,080, 134,110], with the taps as literals 3, one channel, all inputs linear_arithmetic passes passes
    channel0_high_artifact: the same upper bound with the taps read from the artifact 3, one channel, all inputs linear_arithmetic passes rejected, LLV7002 (below)
    tap_bound: for every w and every x in [0, 255], w·x ≤ if w < 0 then 0 else 255·w the step of 3 for any datum linear_arithmetic passes rejected, LLV7002 (below)
    dot_below_high: for every weight list ws and input list xs with all codes in [0, 255], dot ws xs ≤ highSum ws 3 for every datum of the kind induction on ws generalizing xs, cases on xs refused while the step names the hypothesis (below) rejected, LLV7002, in both branches (below)

    The diagnostics, verbatim:

    • Naming the induction hypothesis in the step's linear_arithmetic is refused at link:
      error[LLT4001]: phase link: linear_arithmetic unfolds `hypothesis`, which is not a prior document definition
      
      Of the closed proof forms, simplify takes a hypothesis and does no order arithmetic, and linear_arithmetic does order arithmetic and takes no hypothesis (SPEC.md lines 2652-2667).
    • tap_bound, with the product left as an atom:
      error[LLV7002]: Lean rejected `HandlesProbe.Bound` (error): omega could not prove the goal:
      a possible counterexample may satisfy the constraints
        b ≥ 0
        255*b - c ≤ -1
        0 ≤ a ≤ 255
      where
       a := x
       b := w
       c := w * x
      
    • dot_below_high without the hypothesis. The empty-input branch needs highSum wr ≥ 0, which nothing states (a := w, b := highSum wr, constraints a ≥ 0, 255*a + b ≤ -1). The step leaves w * x, dot wr xr and highSum wr as atoms, unrelated.
    • channel0_high_artifact: simp over the named definitions does not evaluate the fold over the decoded artifact, so the accumulator stays one atom:
       z := dot
        (LexLeanCollections.listFold (fun acc p => acc ++ LexLeanCollections.listFold (fun acc r => acc ++ r) [] p) []
          [[[-1, -30, -63, -8, 18], [-74, -59, -6, 96, 33], …]])
        [x0, x1, …, x24]
      
      with the constraint z ≥ 134131. The literal-tap version of the same statement is accepted.
    • prim equal on Int is refused (LLT4001: primitive Equal requires a closed decidable scalar type), so distinctness is written with two less_than.

    The verified set is the 2 probe modules, with attestation 5090656a0506fc9abaaf12fb5b94d54ecbaaca222644a9da1d11e7a9fcaf763a: elaboration, leanchecker replay and the exact axiom audit. That run holds the eight passing theorems and none of the three rejected ones, which were removed after the first verify. The audited axiom policies are none for multipliers_count and taps_agree, [propext] for the other decide theorems, and [Quot.sound, propext] for the two linear_arithmetic channel bounds.

    Not probed: the conv2 range by decide over 3,200 weights, facts 5 to 8, any theorem whose statement names the digest or W.bytes (§17.12 rule 2 says verification does not re-digest the emitted bytes), and a universal monotonicity of requantization with the multiplier read from an artifact (examples/fold-laws/src/Kernels.lex.tex proves it with the multiplier as a literal).

    Ingredients of the completeness statement

    "For the declared objective, the program built from a datum's handles costs no more than any program computing the same function."

    Ingredient Where it is today What it carries What is missing
    Objective Present: Gnaf.Objective (Gnaf.lex.tex:200-204), SPEC.md §17.15 item 4 scalar, total cost over the domain, and vector, total cost and size Over a finite domain of arguments. Worst case or total cost over every admitted input is #107 item 2.
    Cost model Present: the calculus step accounting (§17.14), weighted operand sizes steps per primitive by operand weight; a literal costs 1 step on release/v0.4 (compiler/src/TargetSemantics.lex.tex:5260) Weight-once-per-read of a literal (TC-08) is in draft #230. Machine contracts are #119 (draft #290 on release/v0.5). Wall time stays open (C5).
    Universe of programs Present for requests: a grammar carrier with grammar_equality evidence, Gnaf.expandComplete fixed systems and dispatches over shared plans The realization grammar of a production root is #107 item 1 and #120.
    "Any program computing the same function" Present but unused: Scope.calculusPrograms and Scope.rustPrograms (Gnaf.lex.tex:189-197) names the scopes Every scope beyond the grammar is refused (uncovered_scope, §17.15 rule 12); C3 forbids the unrestricted universe.
    Same function Present: admission compares each system with the reference on each domain argument (Gnaf.statusOn). Equality over all inputs for folds is present (#117 closed, fold laws, PF-20..PF-23). equality on a finite domain; fold equalities by linear_arithmetic and law Equality over every admitted input is #120.
    A lower bound for every member Present for one system at a time: the premises above, proved sound for every request by the library (lower_bound_attainment, frontier_complete) per-system facts on domain positions No theorem quantified over a kind of datum or of system. This is #122.
    The datum Present: the artifact declaration role, schema, digest, length, decoded value, W.decoded The digest-to-bytes link is not a kernel fact.
    The handle (kind + digest + its theorems) Absent No declaration, no schema field, no register row.
    "Generated from the Atlas" Absent The Atlas is language-1.0 vocabulary over a mathematical source graph No relation from an Atlas entry to a kind, a digest, a program or a cost. Language 1.2 does not load the package.
    "The program built from a datum's handles" Absent No construction of a program from handles. The nearest is the artifact lowering of #115 (draft #239), which builds the program from the datum's decoded value.
    Export requiring the claim Present but unused: PX-06 evidence kind = "gnaf" is optional (SPEC.md line 9375, #121) a request and certificate path per root Required evidence is #121.

    Decision (D3). What is a universal data handle, as LexLean's universal theorems: what does a handle carry, and what is the completeness statement over handles, that for the declared objective the program built from a datum's handles costs no more than any program computing the same function?

  2. afflom commented on Oct 31, 2026

    @afflom
    MemberAuthor

    D3 decided.

    • Handle contents: a kind; the κ-label of its canonical form (the D7 package); and the census's Atlas witness: orbit representative, certified fibre size (orbit_count, action_fibre_count), and its sign class under K = R/{±1} where the computation has that symmetry.
    • Completeness: for the D2 worst-case transport objective, the program assembled from a datum's handles moves each distinct κ-class once (transport-once). No program in the declared universe that computes the same function moves fewer. The floor is the distinct-class count, proved as the value-oracle floor.
    • Must reproduce: MNIST#6's facts, as fixed above.

    Unblocks #122.


    Generated by Claude Code

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions