acceptodds
Under review as a conference paper at ICLR 2027

From Trace Invariance to Certified Execution

Abstract

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 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.

Primary area:
learning theory
Keywords:
trace invariance, certified execution, compositional generalization, finite-state models, identifiability, semantic state representations, discrete projection, neural algorithmic reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_mmtbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks when a learned model that tracks state over a stream of events can be trusted. It separates what the data determines, what training learns and whether step-by-step execution stays correct. Its main new result shows that final answers alone can, in principle identify operations like “add” and “multiply” when both orders are observed. It also shows with known structure checking 75 transitions guarantees correctness on every sequence. On a synthetic task, per-key memory and intermediate-state labels improve learning and rounding learned transitions keeps accuracy at 1.0 up to length 16 while probabilistic execution collapses.

Critical strengths

1.Under the stated assumptions, the paper shows that primitive operations can be recovered using only final-output labels. Seeing compositions in one order leaves an internal ambiguity, while seeing both orders removes it for PatchWorld arithmetic (Thm. 7, Cor. 9). The stochastic extension gives a checkable condition for recovering the true operations through argmax projection (Thm. 8).

  1. Soft and projected rollouts use the same learned scores, so their difference in length-16 joint accuracy isolates the execution rule. The matched-information baselines receive the same intermediate labels and the paper reports non-significant differences openly, including p=0.25p=0.25 for held-out composition. These controls strengthen the empirical evidence within the synthetic setting studied.
Critical weaknesses
  1. The main theory is not demonstrated by terminal-only training. Theorems 7–8 and Corollary 9 explain when final-output labels can identify the true operations. However, no terminal-only experiment meets Theorem 8’s recovery condition. With the reset prior, terminal-only TOF recovers about 55 of 75 rows on average, models passing the full audit use intermediate labels. The paper correctly separates identifiability from successful learning, but whether its training procedure can reach the sufficient condition remains unclear. Reporting the minimum terminal target probability would directly address this gap.

  2. The results depend on strong supplied information. Successful TOF models receive known semantic states, correct key routing, intermediate labels, and exact reset rules. The reset prior fixes 20 rows absent from training. The certificate checks the learned table against this reference, it does not establish that the supplied assumptions hold. Using identical scores for soft and projected rollouts isolates the execution rule, but Table 1b does not fully separate supervision, reset-prior and projection effects. Transition margins and a temperature-sharpened soft-rollout control would help show how robust the length-generalization advantage.

Questions for authors
  1. For each seed in Table 1b, what are the audit count and minimum correct-terminal probability across all states and arithmetic pairs in both orders? Does any seed satisfy Theorem 8? If so, does its projected table pass the length tests? If not, how close is the best seed to the threshold?

  2. For the Table 10 checkpoints, what are the smallest correct-transition and largest incorrect-transition probabilities? Do these explain the sharp accuracy drop from length three to four? How were checkpoints selected and soft distributions propagated?

  3. Does temperature sharpening of the same kernels improve soft-rollout accuracy at lengths four and sixteen while preserving their argmax choices? This would help distinguish transition-confidence effects from the benefit of projection.

Reviewer_Y4oSOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how a model can go beyond correctly handling event order and learn reusable operation rules that remain correct over arbitrarily long execution sequences. The theoretical analysis is fairly solid, and the experiments demonstrate some interesting phenomena. However, the paper does not provide enough evidence to explain why these phenomena occur or to establish the added value of the proposed method. The visual presentation is also poor and does not seem to have been carefully polished. Overall, the paper feels rough and is difficult to read.

Critical strengths
  • The paper makes a useful distinction between identifiability, recovery through training, and actual execution. This helps avoid confusing training failures with a lack of sufficient information.

  • The theoretical assumptions are stated carefully. The authors explicitly discuss requirements such as full combinatorial coverage, reliable assignments, a known state space, and independent variables. They also avoid treating successful tests on finite histories as a general correctness guarantee.

Critical weaknesses
  • The paper does not adequately explain why soft execution fails so quickly. In Table 10, TOF soft execution achieves perfect accuracy at the training length of 3, but its JGA drops to just 0.0046 at length 4. Such a sharp drop is possible, but simply attributing it to accumulated probability errors is not a sufficiently detailed explanation.

  • Theorem 8 shows that the primitive operations can be recovered using endpoint probabilities from two operation orders. However, the main TOF experiments use intermediate-state supervision, while the held-out composition experiment deliberately removes one of the operation orders. Therefore, these experiments do not directly test the endpoint-supervision guarantee, which is one of the paper's most distinctive theoretical results. The authors also acknowledge that they did not measure the required confidence condition. This leaves a gap between the theoretical claim and the experimental evidence.

  • The paper is very difficult to follow. The overall argument is not presented clearly, and many parts of the explanation are too vague.

Questions for authors

See the critical weakness.

Reviewer_J9y1OpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies learning to track the states of several independent keys from event histories. Events on different keys can be reordered while events on the same key cannot. The paper gives conditions under which terminal supervision identifies the underlying transition maps. Experiments use a single synthetic task, PatchWorld.

Critical strengths

None that I could substantiate, given that I could not follow the technical content well enough to assess it.

Critical weaknesses

I was unable to follow the language or the theoretical statements, so I cannot judge whether the claims are correct or significant.

  • Notation is introduced without definition or only implicitly. In Theorem 3, for example, F, h, z, and z_0 are not clearly defined before use. The same problem appears the later results.
  • The text relies on dense terminology that is not explained, e.g. "drive," "anchor," "gauge," and "semantic rows."
  • The core models TSF and TOF are defined only briefly in Section 4.1. The global GRU baseline is defined only in the appendix. Soft and projected rollout are never explained in accessible terms.
  • Figure 1 uses notation and results before they are introduced and is hard to parse. Figure 2 cannot be read without knowing what the global GRU, product TSF, TOF, and soft and projected rollout are. These terms are not explained in the caption.
Questions for authors
  • Please define all notation at first use, e.g., F, h, z, and z_0 in Theorem 3.
  • Please explain TSF, TOF, the global GRU baseline, and soft versus projected rollout in plain terms in the main text.
  • For each theorem, please state its takeaway in plain English.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.