From Trace Invariance to Certified Execution

Independent update streams may interleave, but corrections within a stream must remain ordered. Trace invariance captures this symmetry; certified execution additionally requires reusable semantic transitions. We separate three questions: what observations identify, what a learner recovers, and what its rollout preserves. For finite permutation primitives, we characterize exactly the ambiguity left by terminal composition labels: one operation order leaves a permutation gauge, while both orders restrict it to a common centralizer. For stochastic learners, terminal target probabilities uniformly above one half in both orders guarantee correct row-wise projection when the centralizer is trivial. We then characterize when decoded recurrent states admit a finite transition audit, and how known product structure reduces its worst-case size independently of the number of streams. Controlled synthetic PatchWorld experiments demonstrate the benefits of this separation. Product-state recurrence attains perfect joint accuracy with 2,048 training programs, and intermediate supervision raises held-out-composition accuracy to 0.9118. Projecting the same learned operator scores raises length-16 joint accuracy from $9.6\times 10^{-5}$ under soft rollout to 1.0 across seven seeds. These results connect identifiable primitives, semantic-state structure, and discrete projection to finitely verifiable compositional execution.