1 Introduction↩︎

Many agent tasks are secretly finite-state: onboarding and support workflows, tool-use and API-call sequences, compliance and triage procedures, multi-step form repair. An agent can appear competent during training yet fail when the workflow is longer, noisier, or differently distributed—a symptom of having learned a reward-seeking shortcut rather than the task’s underlying state machine. This is the goal-misgeneralization worry [1], [2]: capabilities that transfer, but attached to a proxy objective. Prior demonstrations of it are behavioral and define the “true goal” informally; here the true latent state is an exactly known object we can both normalize against and read out, so the worry becomes measurable.

A clarifying point about what is hidden. The agent observes the entire emitted symbol prefix, and the latent dfa state is a deterministic function of that prefix. So this is not belief-tracking in the POMDP sense (no irreducible uncertainty to integrate); it is a computation/memory problem—whether the agent maintains a known-computable running function of its fully observed history. That places the testbed alongside the emergent-world-representation line (probing a sequence model for a latent state it was never shown; §2) and connects to the counting/length-generalization literature: the running function is exactly what recurrent nets compute inductively and attention-only models struggle to.

We turn formal-language recognition into a control problem. Instead of asking whether a model can classify a string, we ask whether an agent can steer a hidden automaton toward an accepting state, and whether in doing so it comes to represent the automaton’s latent state. The key move is that the automaton is fully known to the experimenter: we can (a) compute the optimal achievable return exactly, normalizing raw reward, and (b) read out the true hidden state at every step to probe the agent’s representation. Reward success and latent-state learning therefore become two separately measurable axes.

Thesis. Reward success and latent-state learning are distinct, separately measurable quantities, and whether they couple is governed by three axes the instrument turns independently (Figure 1): (i) optimizer strength; (ii) task structure—above all whether the automaton is a group-language (permutation) automaton, which a credit-assignment analysis and a held-out test establish as a high-precision, one-directional warning signal for the perception gap (a controllable-stabilizer/leverage refinement sharpens this in-sample but does not generalize); and (iii) how much observations reveal about the latent state. Weak RL leaves them decoupled; a stronger optimizer couples them except for the group-language class; and a label-free signal recovers state only as observations become informative. The contribution is the white-box, exactly-probeable instrument that lets us measure where on these axes a task sits rather than conjecture it. The instrument is also self-correcting: a pre-registered control overturned our initial reading in §5.2.

Contributions. (1) A measurement methodology for “did the agent learn the task state, or a reward shortcut?”: express the task as a hidden FSM, yielding for free an exact oracle for optimal/random/full-control achievable return (hence oracle-normalized reward), the exact latent state at every step for linear probing, and an off-policy supervised capacity upper bound. The recipe applies to any FSM-approximable task; hidden partial-control dfas are its cleanest instance. (2) A benchmark instance (PartialControlDFAEnv) with a taxonomy separating diagnostic automata from trivial ones. (3) An optimizer-strength characterization of reward\(\leftrightarrow\)state coupling, established by elimination and a pre-registered, multi-seed A2C-vs-PPO control that overturned our first reading. (4) An auxiliary-signal analysis distinguishing a privileged state auxiliary from a label-free observation auxiliary. (5) A pre-training structural warning signal for the perception gap (§5.5): permutation (group-language) structure, computable from \(\delta\) alone, which a credit-assignment analysis links to a starved learning signal (Appendix 8), tying the RL finding to the algebraic theory of automata, and which validates held-out on \(153\) capacity-controlled fresh automata as a one-directional, high-precision indicator (precision \(0.86\); permutation accounts for \(89\) of \(109\) perception gaps); a controllable-stabilizer/leverage refinement sharpens it in-sample only, and the prescribed fix closes the gap causally (Appendix 10). Two conclusions strictly require the exact probe and could not be drawn from reward\(+\)oracle alone: the perception gap and the planning gap. A preliminary cross-scale port of the full instrument to a no-CoT Qwen2.5-3B/7B LLM agent, which reproduces two of the three axes, is reported as an external-validity check in Appendix 11 and is not part of the main claims.

2 Related Work↩︎

Reward machines and automaton-structured RL expose the automaton behind a (possibly non-Markov) reward and let RL exploit it [3]; a parallel line infers the latent automaton, either to plan with [4] or to model history-dependent dynamics as a regular decision process via a finite transducer, with PAC guarantees [5]. We invert all of these: we hide the automaton and ask whether sparse-reward RL discovers its latent state as a byproduct of maximizing reward, using the known automaton purely as a measurement instrument—and our motivation is the dual risk that the agent instead latches a reward-correlated shortcut, the control analog of causal confusion in imitation [6].

Transformers, RNNs and counting. Counting tasks such as parity separate architectures: RNNs count inductively, whereas attention-only encoders (ac\(^0\)-bounded under hard attention) need positional tricks and tend not to length-generalize [7]–[9]; this Chomsky-hierarchy view of architecture-vs-task is mapped at scale by [10] and for transformers on regular languages by [11], with finite-precision RNN counting power characterized by [12]. Closest to our probe, [13] decode RNN hidden states against minimal-DFA states—the recurrent-net analog of our latent-state probe, but for supervised language recognition rather than sparse-reward control. Most directly, [14] show low-depth transformers can simulate any finite automaton, with constant-depth shortcuts for solvable semiautomata via Krohn–Rhodes, yet—crucially for us—these shortcuts are brittle and degrade as supervision gets sparser, while an LSTM stays at \(100\%\) on the same group automata. Our testbed reproduces and extends this separation inside an RL control loop with a hidden, sparsely-rewarded state, and gives it a normalized, probeable form. A precision point: the transformer literature draws two boundaries—the length-generalization boundary (roughly non-star-free) and the constant-depth simulation boundary (solvable vs.non-solvable). Our hard tasks (cyclic mod_k counters) are solvable but non-star-free; we therefore sit on the star-free / length-generalization boundary, where the sparse-supervision regime of [14] agrees with us, not on the solvable/non-solvable boundary. We connect this to the classical syntactic-monoid theory [15], [16]; star-free is a useful approximation, not exact (transformers length-generalize on some non-star-free languages such as \((aa)^\ast\) [9]), consistent with our finding that mod_2 (\(\equiv\) last bit) is easy.¹

Emergent world representations and probing. A model trained only to predict the next token can represent the latent state of the generating process—Othello-GPT encodes the board, linearly decodable and causally tied to predictions [18], [19], with parallels in chess and program semantics. This is our closest methodological relative; we differ in three ways: those models are trained by supervised next-token prediction on expert play, whereas we study sparse-reward RL under partial control; we supply an exact oracle and a known finite probe target, so world-model criteria can be checked exactly; and we deliberately drive reward and state apart. We adopt the probing safeguards this literature established—control tasks and selectivity [20], [21]—and run an interventional probe.

State abstraction and auxiliary tasks. Bisimulation/behavioral abstraction and predictive state representations—which, like us, define state through observable consequences rather than a posited hidden variable [22]—formalize “the state that matters” [23], [24]; unlike PSRs, our dfa state is known exactly and used for measurement, not learned as the agent’s state. Recurrent model-free RL is a strong POMDP baseline [25]. Auxiliary self-supervised objectives are standard under sparse reward [26]. Our auxiliary predicts the exact latent dfa state, so an independent probe can verify it installs the intended representation. Reward hacking benchmarks measure exploit rates behaviorally [27], [28]; we provide a white-box, exactly-probeable substrate where “did it learn the task state” is a measurable quantity, complementary to them.

3 The Hidden-Automaton Control Testbed↩︎

Partial-control dfa environment. A task is a dfa \(M=(Q,\Sigma,\delta,q_0,F)\). An episode of length \(T\) evolves \(q_{t+1}=\delta(q_t,a_t)\). At each step, with probability \(p_{\mathrm{control}}\) the agent chooses the symbol \(a_t\); otherwise the environment samples \(a_t\) uniformly. The agent observes the emitted symbol stream, whether the step is controllable, and time remaining—but never the hidden state \(q_t\). Reward is sparse and terminal: \(r=1\) if \(q_T\in F\) else \(0\). Full control trivializes most tasks (just emit the accepting word); partial control forces the agent to track the current hidden state and spend limited interventions wisely.

Exact oracle. Because \(M\) and the control distribution are known, the optimal acceptance probability is computed by backward induction over (state, steps-remaining): \[V(q,0)=\mathbf{1}[q\in F],\qquad V(q,r)=p_{\mathrm{control}}\max_a V(\delta(q,a),r{-}1)+(1{-}p_{\mathrm{control}})\,\mathbb{E}_a V(\delta(q,a),r{-}1).\] We report oracle-normalized success \(=\text{(empirical)}/V(q_0,T)\) (\(1.0=\) optimal), comparable across tasks, lengths and control probabilities, plus random and full-control ceilings.

4 Diagnostic Instruments↩︎

Linear dfa-state probe (on-policy): fit a linear classifier from the policy’s pre-head features to the true \(q_t\) on the agent’s own rollouts; report the held-out gap over the majority-class baseline, with balanced accuracy and a control-task/selectivity check [20] so a positive gap reflects representation, not probe capacity or visitation skew. Interventional probe (causal): edit the activation along the decoded-state direction and check whether the greedy action changes as \(\delta\) predicts—the test that distinguishes a representation the policy consults from one merely present. Supervised capacity (off-policy): train each encoder with full supervision to predict \(q_t\) from random play—the architecture’s capacity, decoupled from the optimizer. The on-policy probe conflates “the representation tracks state” with “the agent keeps the automaton in a small set of states”; we therefore report both.

5 Experiments↩︎

5.1 The oracle selects diagnostic tasks; the interface, not just architecture, governs capacity↩︎

The exact oracle (§3) immediately separates diagnostic from trivial tasks: contains_0010 is non-diagnostic (random reaches optimal), while parity and mod_k have optimal flat in length, so any degradation at longer horizons is pure failure-to-track. For the supervised capacity bound (predict \(q_t\) off-policy), a full-prefix GRU represents counting perfectly and length-generalizes to \(4\times\) training length (OOD accuracy \(1.00\)), whereas a window-MLP is window-bounded (chance OOD) and a plain transformer fails to length-generalize parity (\(0.55\), chance) despite full context—consistent with transformer-counting theory (§2). Every shortfall below is therefore a learning effect, not a representational one.

5.2 Is it the optimizer or the reward channel? A pre-registered control↩︎

Under deliberately weak on-policy RL (A2C, i.e.REINFORCE with a value baseline), the probe is at chance for every architecture—including the GRU we proved can represent these tasks—while reward is achievable: a strong reward/state decoupling. It is tempting to conclude “sparse-reward RL cannot install latent state.” We pre-registered a control to test exactly this (Appendix 7): recurrent PPO\(+\)GAE\(+\)advantage normalization vs.A2C on \(\{\)window-MLP, GRU\(\}\times\{\)parity, mod_3\(\}\), \(p_{\mathrm{control}}{=}0.5\), 5 seeds, with a \(2\times2\) (optimizer \(\times\) credit-scheme) de-confound. The control overturns that claim. PPO raises reward and drags the probe up, most clearly for the GRU (probe gap \(+0.01\!\to\!+0.20\) on parity, \(+0.02\!\to\!+0.21\) on mod_3; OOD reward \(0.50\!\to\!0.75\) on mod_3). The \(2\times2\) shows the optimizer (PPO machinery) is the dominant driver—at fixed credit scheme, A2C\(\to\)PPO moves the probe gap far more than broadcast-vs-discounted does at fixed optimizer, cleanly so on parity (Table 1). Credit is not irrelevant, though: on mod_3 discounting lifts A2C (\(+0.02\to+0.15\)) and, under PPO, broadcast edges out discounted return-to-go (\(+0.34\) vs.\(+0.21\)); the claim is optimizer-dominance, not credit-irrelevance. The surviving, sharper claims: coupling is optimizer-dependent; even with PPO recovery is partial and high-variance (gaps \(\sim{+}0.20\) vs.the supervised-capacity ceiling \({\approx}{+}0.48\)/\({+}0.60\)—the representational bound, distinct from the lower privileged-auxiliary ceiling reached by the shaping ladder below); and the recurrence advantage surfaces in RL only under PPO (GRU\(+\)PPO length-generalizes mod_3 OOD \(0.75{\pm}.20\); window-MLP \(0.55{\pm}.02\); transformer \(0.49{\pm}.04\)). We report this correction as evidence the instrument is self-correcting.

The chance probe is not an under-training artifact. A natural worry is that the probe sits at chance only because the weak optimizer was under-run. Two observations rule this out. First, recovery rises monotonically with optimizer competence at fixed budget. The ladder’s first three rungs are the A2C\(\times\)broadcast, A2C\(\times\)disc-RTG, and PPO\(\times\)disc-RTG cells of Table 1; the fourth adds oracle-potential shaping (\(F{=}\gamma\Phi(q_{t+1}){-}\Phi(q_t)\) with \(\Phi\) the oracle value, 5 seeds). On parity the probe gap climbs A2C \(+0.01\to\) A2C(discounted) \(+0.02\to\) PPO \(+0.20\to\) PPO\(+\)potential-shaping \(+0.30\), matching the privileged-auxiliary ceiling (\(+0.28\); the shaping potential is the oracle value, so meeting the privileged bound is expected); mod_3 rises likewise (\(+0.02\to+0.15\to+0.21\to+0.35\), ceiling \(+0.36\)), and reward tracks it the whole way. The signal is governed by optimizer strength, not training length—a stronger optimizer on the same data closes the gap to the representational ceiling. Second, on a genuinely hard counter the recovered fraction stays bounded well below the ceiling at the same budget (§5.4: all \(k\) share one PPO budget, yet PPO/ceiling falls to \(0.31\) at \(k{=}11\)).

5.3 Auxiliaries, and the observation-informativeness axis↩︎

Under the competent optimizer (GRU\(+\)PPO, 5 seeds) a privileged state auxiliary (predict true \(q_t\); an upper bound, not deployable) is nearly inert at low complexity—because PPO already recovers the state—but its benefit grows exactly where the base learner fails (under weak A2C, and at high complexity, §5.4). A label-free auxiliary (predict the next emitted symbol) is vacuous when emissions are state-independent—it adds nothing beyond the base learner, so the probe reflects sparse PPO alone: near chance (\(+0.03\)) where PPO is, and PPO’s own \(+0.14\) on mod_5 at \(\beta{=}0\) (Table 4)—and it can even degrade reward, because next-symbol prediction then has no gradient toward \(q_t\). That vacuity is a feature: it isolates “state revealed only through outcome reward.” Adding an observation channel of tunable informativeness \(\beta\) (a state coloring leaked with probability \(\beta\)) turns this into a controlled axis: on mod_5—where sparse PPO alone struggles—the label-free auxiliary flips from vacuous to fully effective as soon as observations carry any state, saturating already by \(\beta{=}0.10\) (probe gap \(+0.47\), reward \(0.93\), 5 seeds). A deployable label-free signal recovers latent state, and rescues reward, exactly to the degree observations are state-informative.

5.4 Scaling and the easy/hard boundary↩︎

Sweeping the mod_k family (\(k\in\{2,3,5,7,9,11\}\), GRU\(+\)PPO, 5 seeds; supervised capacity perfect at every \(k\)), the fraction of the achievable latent state that sparse-reward PPO recovers shrinks from \({\approx}1\) at \(k{=}2,3\) to \({\approx}0.31\) at \(k{=}11\), while the privileged auxiliary’s reward benefit grows from \({\approx}0\) to \(+0.25\)–\(0.43\) (Table 2). As a task becomes more stateful, agents trained on sparse outcome reward recover a shrinking fraction of its latent state, while the value of a state-tracking signal grows.

We then use the instrument as a falsification engine, authoring workflow shapes that each embody a candidate explanation for difficulty. Sparse PPO solves all of: reach-commit API stages; a long-range latch (a bit set once and held—so long-range distance is not the culprit); a threshold quota; and a terminal-invariant reconciliation (additive with a hold action, hence steerable to zero). The acute reward-vs-state gap and large auxiliary benefit appear only in hard-to-steer abstract counters. This falsifies, in turn, three intuitive predictors of difficulty—state count, long-range distance, and terminal-invariance alone—and isolates the real one: terminal-exact accumulation under poorly-controllable (mixing) dynamics.

The instrument also separates two failure modes. ends_with_1000 shows a planning gap: the probe is high (\(+0.62\)) yet reward is only \(0.41\)—the agent represents the state but cannot act on it—categorically different from the perception gap (mined_ean: reward gap \(0.82\), probe at chance \(+0.03\)). This is the one place the exact probe is indispensable, and we show it rather than assert it. A reward-only auditor sees only the behavioral signals—the oracle-normalized reward gap and the OOD reward drop—and these are nearly uncorrelated with the recoverable state across the suite (Spearman with the probe gap \(-0.29\) and \(-0.25\)). Among the nine tasks where the agent is visibly suboptimal (reward gap \({\ge}0.25\)), the behavioral signature is near-identical yet the probe spans \(0.03\) (mined_ean, perception) to \(0.65\) (ends_with_101, planning): behavior cannot tell a representation that is absent from one that is present-but-unused, though the two demand opposite fixes (Appendix 9, Fig. 2). The probe makes the distinction a measurement.

5.5 A pre-training structural warning signal for the perception gap↩︎

The verbal boundary has an exact algebraic form computable from \((\delta,p_{\mathrm{control}})\) before any training—which is what lets the instrument predict rather than merely report. Part 1 (must-accumulate): call \(M\) a permutation automaton if on its reachable states every symbol induces a bijection \(q\mapsto\delta(q,a)\); then no input ever merges states, the latent state never forgets, and the task recognizes a group language (non-star-free) [15], [16]. When some symbol collapses states (synchronizing), old symbols are forgotten and the state is a function of recent context—the regime a recurrent policy tracks locally. This separates the suite parameter-free and explains the \(k{=}2\) vs.\(k{\ge}3\) result: mod_2\(\equiv\)last bit (synchronizing, easy) while \(\texttt{mod\_k}{}_{k\ge3}\) (odd \(k\), where doubling is invertible) is a genuine group counter that must accumulate; no appeal to state count is needed (parity, 2 states, is hard; no_three_zeros, 4 states, is easy). This permutation property is necessary but not sufficient: it is the must-accumulate half, and a low-\(k\) counter like mod_3 is a permutation automaton yet still learnable because partial control buys enough leverage (Part 2). Part 2 (poorly-controllable): group structure alone is insufficient—workflow_reconcile is group-like yet learnable because it has a controllable hold (an identity transition that freezes the state once steered to accept). A scalar proxy is the control leverage \(L=(V_{\mathrm{opt}}-V_{\mathrm{random}})/(V_{\mathrm{full}}-V_{\mathrm{random}})\), read from the oracle. The precise predictor is the conjunction: group/permutation structure and low control leverage.

In-sample, the predictor is exact. Treating it as a \(\delta\)-only scorer—\(s=L\) for permutation automata, \(s={+}\infty\) otherwise—against the measured labels (hard \(\Leftrightarrow\) privileged-aux reward benefit \({\ge}0.20\)), it perfectly ranks the 15 designed tasks (ROC-AUC \(1.00\); every hard task \(L\le0.50\), every easy one \(L\ge0.519\)), survives leave-one-out cross-validation \(14/15\) (lone error workflow_reconcile at the boundary), and within the designed group tasks (mined pair excluded) tracks hardness monotonically (Spearman\((L,\text{aux benefit})=-0.83\)). The mechanism is argued, not merely observed (Appendix 8, under explicit rollout assumptions): for a permutation automaton the per-step credit-assignment signal decays geometrically in the uncontrolled steps remaining (to zero after one step for parity) unless a controllable stabilizer or a synchronizing/absorbing distinction keeps it \(\Theta(1)\)—the conjunction the predictor encodes, and the exact oracle confirms the decay empirically.

Held-out, permutation structure predicts the perception gap. The clean in-sample gap invites the worry that it is fit to a curated family, so we ran the full instrument on 153 fresh random dfas (stratified to populate both predictor classes; predicted from \(\delta\) before any RL; GRU\(+\)PPO, the original \(33\) at \(5\) seeds and \(120\) additional at \(3\) seeds, Appendix 10). The predictor targets the perception gap specifically—latent state that is representable yet not linearly recoverable from the trained agent—so we score it against linear state recoverability directly: a perception gap is linear probe recovery \(<0.5\) when the state is in fact recoverable. (This is the direct form of the in-sample aux-benefit criterion: a large privileged-aux reward benefit means the state was missing; here we read the missing state off the probe directly.) The probe’s train/test split is by episode, not by row, so autocorrelated within-episode activations cannot leak across it; an earlier row-level split gives the same headline (re-scoring moves \(2\) of \(153\) automata and leaves precision at \(0.86\)). We label on recoverability rather than on “reward present” because in this stratified random population the two mostly co-occur—reward is usually depressed for a gap as well (median normalized reward \(0.45\) across the \(109\) gaps; only \(2\) clear \(0.85\))—so the held-out claim is specifically state-blindness, while the clean high-reward-yet-no-state case is the one exhibited on the curated suite (mined_ean, above). The capacity confound is controlled directly: off-policy supervised probes saturate (val and OOD accuracy \({\approx}1.0\)) for the automata, so a low on-policy recovery is a genuine learning failure, not a representational limit (no mined_ean-style artifact). The Appendix 8 direction transfers as a one-directional indicator: when an automaton is permutation it is a perception gap with precision \(0.86\) (\(89/103\)), and \(89\) of the \(109\) perception gaps are permutation (recall \(0.82\))—so group structure is a high-precision warning signal for state-blindness on automata it never saw, not a guarantee of safety for non-group tasks (below). The original \(33\) reproduce exactly (\(19/23\), precision \(0.83\)); the \(4.6\times\) larger held-out set leaves the precision essentially unchanged, so the signal is not a small-sample artifact. Two caveats, both measured. First, the converse does not hold: non-permutation automata are heterogeneous (of \(50\), \(20\) perception / \(14\) planning / \(16\) solved), so structure flags that a perception gap is likely, not that a non-group task is safe. Second, the leverage threshold does not transfer (the conjunction’s recall collapses; the scalar \(L\) over-credits steerability), so we demote \(L\) to a within-group severity proxy (the in-sample Spearman \(-0.83\)) and drop the two-sided classifier. The finding is not architecture-specific: on the original \(33\) it replicates on an LSTM (precision \(0.78\), recall \(0.78\); \(22\) of the \(24\) GRU perception gaps are also LSTM perception gaps), with that architecture’s capacity equally saturated. The surviving claim is the well-supported one: permutation/group structure is a high-precision, mechanistically-grounded, held-out-validated predictor of the perception gap.

What generalizes cleanly is the fix. Even where prediction is imperfect, the predictor’s two named escape routes work as interventions on a known-hard task (Appendix 10, Table 4): on mod_5, latchability (adding a controllable hold, still a permutation automaton) lifts reward \(0.50{\to}0.89\) and the probe \(+0.17{\to}+0.27\) while cutting seed variance, and observability (the §5.3 emission channel at \(\beta{\ge}0.1\)) lifts them to \(0.93\) and \(+0.47\). The audit-and-fix loop—make the latent state latchable or observable—is thus a demonstrated causal intervention needing only the oracle and probe, not a perfect a-priori predictor.

5.6 Non-synthetic instances mined from real logic and logs↩︎

To test whether the failure mode arises in structure we did not author, we mine hidden dfas from real, deployed logic via RPNI [29], [30] (passive automaton learning) and run the identical instrument. We deliberately target checksum/divisibility code (ubiquitous, self-labeling, and structurally in our hard regime)—so this validates the pipeline and shows the hard structure exists in real code, not that it is common. mined_div7 (binary-value-divisible-by-7, recovered exactly, capacity \(1.0\)) reproduces the full mod_7 gap: sparse PPO is partial (\(0.65{\pm}.27\), probe \(+0.30\)) while both the privileged and a deployable label-free (\(\beta{=}1\)) auxiliary rescue it to optimal—the entire three-axis story on logic we recovered rather than authored. Conversely, all seven real process logs we mined [31]–[37] (procurement, clinical, two loan-application, building-permit, billing, and fines processes) are non-permutation: five mine to 2-state reach-commit automata and two are decide-late automata, and all are learnable. They lie outside the high-precision perception-gap class (permutation structure), and empirically none exhibits the gap. Real FSM structure thus spans both regimes—real checksums are permutation (perception-hard), real workflows are non-permutation and here learnable—so the perception gap is present in real, deployed logic but is not the common case among the logs we surveyed.

6 Discussion, Limitations, and Conclusion↩︎

The testbed converts a vague worry into a measurement. State-learning is gated not by the observation (once the full prefix is provided) nor by capacity (the GRU provably suffices), but by credit assignment and reward design: reward and latent-state learning couple only weakly and unreliably under sparse reward, the coupling strengthens with optimizer quality, and it degrades as the task grows more accumulation-heavy. Where the state is learned it is genuinely used: editing the hidden along the decoded-state direction shifts the greedy action to the \(\delta\)-predicted one far more than a norm-matched random direction (across the seven policies where an auxiliary installed the state, \(0.32\)–\(0.68\) vs.\(0.00\)–\(0.21\)). The practical reading is more reassuring than a doom result: any FSM-approximable workflow can be given an exact oracle and a state probe and audited white-box; permutation (group-language) structure is a reliable red flag for the perception gap (held-out precision \(0.86\) on \(153\) fresh automata, permutation accounting for \(89\) of \(109\) gaps, capacity controlled, §5.5); and the fix falls out and is causally confirmed (make the latent state observable or latchable and the gap closes). The audit, not a perfect a-priori predictor, is the deployable artifact—and all seven real logs we mined are learnable.

Towards LLM agents (preliminary). As an external-validity check we ported the whole instrument to a real LLM agent (Qwen2.5-3B/7B) and pre-registered the test (Appendix 11). Two of the three axes reproduce—structure as a representational counting-horizon limit, and optimizer strength as the predicted weak-optimizer outcome—but it does not yet produce a clean LLM-scale perception gap (no optimizer we ran lifts reward above random on a representable group counter within budget, the accumulation difficulty of §5.4 at scale). We frame this as a preliminary instrumentation check and release the instrument for the stronger-optimizer experiment.

Limitations. (i) Scale: the synthetic suite is small (\(\le11\) states, mostly binary); mined instances reach 20 states / 10-symbol alphabets, and the oracle/probe handle far larger, but larger automata remain future work. (ii) The optimizer-mediation effect is directionally clear but magnitude-uncertain (PPO recovery is partial and seed-variable), though an optimizer-strength ladder that climbs to the representational ceiling (§5.2) rules out an under-training artifact. (iii) The structural signal is mechanistically grounded (Appendix 8), but a held-out test on 153 capacity-controlled fresh dfas (Appendix 10) shows only the one-directional claim generalizes: permutation structure is a high-precision warning signal for the perception gap (precision \(0.86\); \(89/109\) gaps permutation), but the converse fails (non-permutation automata are heterogeneous) and the leverage threshold does not transfer (we demote \(L\) to a within-group severity proxy). The GRU result holds across \(153\) fresh automata, and on the original \(33\) replicates on an LSTM, with capacity controlled; a sharper predictor of which permutation automata are hardest, and of the non-group perception gaps, remains open, as does scaling beyond small automata; the causal fix, by contrast, transfers (Appendix 10). (iv) The hard regime is shown on non-synthetic logic, but the clean hard mined instance is a 7-state checksum we targeted; “real workflows tend to be learnable” rests on seven logs. (v) §5.3’s \(\beta{=}0\) vacuity cell is 3-seed (its \(\beta{\ge}0.1\) saturation cells are 5-seed). A hard instance mined from a richer real source with a saturated capacity bound is our top reach goal.

Conclusion. Hidden partial-control dfas are a cheap, exactly-probeable laboratory for stateful-agent reliability. Reward success and latent-state learning are distinct quantities whose coupling is governed by three measurable axes—optimizer strength, task structure (group-language structure as a high-precision, held-out-validated, one-directional warning signal for the perception gap, with a credit-assignment mechanism behind it), and observation-informativeness—and the instrument separates a perception gap from a planning gap. The reusable contribution is the recipe—express a task as a hidden FSM and obtain an exact oracle plus exact latent-state probes—for asking, of any agent, whether it learned the task or only the reward.

Reproducibility statement↩︎

The environment, exact oracle, probes, supervised capacity bound, and all training code are released (anonymized). Headline tables (§5.2–§5.4) are 5-seed with 95% bootstrap CIs; the \(\beta\) grid is 3-seed at its coarse points (\(\beta\in\{0,0.25,0.5,1\}\)) and 5-seed at the transition points (\(\beta\in\{0.10,0.15,0.20\}\) on mod_5, including the \(\beta{=}0.10\) saturation cell); the held-out validation (Appendix 10) is GRU over \(153\) fresh automata (the original \(33\) at \(5\) seeds, \(120\) additional at \(3\) seeds), with an LSTM cross-check on the original \(33\) (3-seed) and a per-automaton supervised-capacity control. Every linear state probe in the paper uses a train/test split by episode (no autocorrelated within-episode rows leak across the split); the released probe outputs also record the earlier row-level split, which shifts individual probe gaps by \({\le}0.02\) (within their CIs) and leaves the held-out precision at \(0.86\). The pre-registration of the §5.2 control is in Appendix 7. Full per-task grids, the mined-automaton pipeline, and selectivity analyses ship as released code and run logs. The LLM-agent instrument (NL environment, residual-stream probe, frozen and supervised capacity bounds, RL loop) and its pre-registration (Appendix 11) are released. The structural predictor, its in-sample ROC/leave-one-out evaluation, and its predictions over the random-dfa family are reproduced by a standalone, training-free script (predictor_eval.py: \(\delta\mapsto\) hard/easy); the held-out scores (§5.5, Appendix 10) are recomputed from the released run trees by analyze_randval.py; the credit-assignment quantities of Appendix 8 are computed exactly from the oracle.

Use of large language models↩︎

An LLM-based assistant helped implement the code, run the experimental pipeline, and draft parts of the text, working at every stage under the authors’ direction. The authors reviewed and verified the methodology, the results, and the writing, and accept full responsibility for all claims and content in this paper.

7 Pre-registration of the optimizer-vs-reward-channel control (§5.2)↩︎

The §5.2 correction rests on a control we fixed before running it, recorded here so the reversal reads as principled rather than post-hoc. Under weak on-policy RL the probe sat at chance for every architecture; we registered two competing explanations and a design to separate them.

Registered hypotheses. H\(_{\mathrm{opt}}\) (optimizer): the chance probe is an artifact of a weak optimizer; a stronger optimizer (recurrent PPO\(+\)GAE\(+\)advantage normalization) will raise the probe and reward together. H\(_{\mathrm{signal}}\) (reward channel): the chance probe is intrinsic to sparse terminal reward; the credit-assignment scheme (broadcast return vs.discounted reward-to-go), not the optimizer machinery, is what matters.

Registered design (fixed before seeing PPO results). A \(2\times2\) grid, optimizer \(\{\)A2C, PPO\(\}\) \(\times\) credit-scheme \(\{\)broadcast (\(\gamma{=}1\)), discounted-RTG\(\}\), crossed with \(\{\)window-MLP, GRU\(\}\times\{\)parity, mod_3\(\}\), at \(p_{\mathrm{control}}{=}0.5\), 5 seeds, identical network sizes, horizon, and evaluation protocol across cells; the GRU’s off-policy supervised capacity (\({=}1.0\)) was established first, so any cell’s shortfall is a learning, not a representational, effect.

Registered decision rule. Support H\(_{\mathrm{opt}}\) if the PPO cells raise the probe gap substantially over A2C holding the credit scheme fixed; support H\(_{\mathrm{signal}}\) if the discounted-RTG cells do so holding the optimizer fixed. Outcome (Table 1): the optimizer axis moved the probe (A2C\({\to}\)PPO at fixed credit scheme), the credit-scheme axis was secondary—supporting H\(_{\mathrm{opt}}\) and forcing us to overturn the too-strong reading that sparse-reward RL cannot install latent state. Recovery is nonetheless partial and seed-variable, the surviving (weaker) claim in §5.2.

8 Why permutation automata starve credit assignment↩︎

This appendix gives the mechanism behind the §5.5 boundary as two propositions under explicit assumptions, and confirms them empirically with the exact oracle; it is a mechanistic account, not a claim that sparse-reward RL provably cannot learn these tasks. Assumptions. An episode has horizon \(T\); at each step the action is the agent’s with probability \(c=p_{\mathrm{control}}\) and a uniform random symbol otherwise; the reward is the sparse terminal indicator \(R=\mathbf{1}[q_T\in F]\); we use the broadcast (\(\gamma{=}1\)) estimator \(\nabla_\theta J=\mathbb{E}\big[R\sum_{t\in C}\nabla_\theta\log\pi_\theta(a_t\mid h_t)\big]\), where \(C\) is the set of controllable steps. Crucially the policy \(\pi_\theta(a_t\mid h_t)\) conditions on the observed prefix \(h_t\) only (it cannot see future symbols); the result is stated for any such history-dependent policy, and the operator bounds below are over the resulting rollout distribution.

Define the state-influence of step \(t\) as the spread of the eventual acceptance probability over the latent state just after the step, \[\Delta_t \;=\; \max_{q,q'\in Q}\big| \,\rho_{s}(q)-\rho_{s}(q')\,\big|,\qquad \rho_{s}(q)=\Pr[\,q_T\in F \mid q_{t}=q\,],\quad s=T-t,\] where the probability is over the (random and controllable) symbols of the remaining \(s\) steps under the rollout policy. \(\Delta_t\) upper-bounds how much any decision at step \(t\) can change the return.

Proposition 1 (credit is bounded by state-influence). The contribution of step \(t\) to the policy gradient obeys \(\big\|\mathbb{E}[\,R\,\nabla_\theta\log\pi_\theta(a_t\mid h_t)\,]\big\|\le \Delta_t\cdot \mathbb{E}\,\|\nabla_\theta\log\pi_\theta(a_t\mid h_t)\|.\) In particular, if the acceptance probability does not depend on the symbol chosen at step \(t\), that step contributes exactly zero.

Proof. Condition on \(h_t\). By the score-function identity \(\mathbb{E}_{a_t}[\nabla_\theta\log\pi_\theta(a_t\mid h_t)\,g(h_t)]=0\) for any \(g\) not depending on \(a_t\). Writing \(\Pr[R{=}1\mid h_t,a_t]=\bar\rho(h_t)+\big(\Pr[R{=}1\mid h_t,a_t]-\bar\rho(h_t)\big)\) for any baseline \(\bar\rho(h_t)\), the first term integrates to zero and the residual is bounded in absolute value by the spread of \(\Pr[R{=}1\mid h_t,a_t]\) over \(a_t\), which is at most \(\Delta_t\) since each action only moves \(q_{t}\) within \(Q\). Cauchy–Schwarz gives the stated bound. \(\square\)

Proposition 2 (geometric decay for mixing permutation automata). Let \(M\) be a permutation automaton and let \(P\) be the one-step transition operator induced by a uniform random symbol, with second-largest eigenvalue modulus \(\lambda<1\) on the reachable orbit. If at least \(k\) of the \(s\) steps after \(t\) are uncontrolled, then \(\Delta_t\le C\,\lambda^{k}\) for a constant \(C\) depending only on \(M\). For parity (\(\mathbb{Z}_2\), \(\lambda=0\)) a single uncontrolled step gives \(\Delta_t=0\) exactly.

Proof sketch. Because every symbol acts as a bijection, \(\rho_s\) is propagated backwards by alternately applying the random-symbol operator \(P\) on uncontrolled steps and the policy’s action-mixture operator \(P_\pi\) on controllable steps. Both are convex combinations of permutation matrices, hence doubly stochastic, hence non-expansive in the span seminorm; and \(P\), being ergodic with second eigenvalue \(\lambda<1\), strictly contracts the span by a factor \(\lambda\). After \(k\) uncontrolled steps the span—and therefore \(\Delta_t\)—is at most \(\lambda^k\) times its value at step \(T\). For parity, one uniform symbol flips the bit with probability \(\tfrac12\), so \(q_T\) is uniform regardless of \(q_{t}\) and \(\Delta_t=0\). \(\square\)

Consequences. Each subsequent step is uncontrolled independently with probability \(1-c\), so in expectation step \(t\) has \(\Theta((1-c)s)\) uncontrolled steps after it and its credit is \(O(\lambda^{(1-c)(T-t)})\)—exponentially small in the steps-to-go for every intermediate step, with \(\Theta(1)\) credit surviving only in the last few steps. A permutation automaton therefore receives no \(\Theta(1)\) signal to represent or use the latent state at intermediate times; the only escapes are (i) a controllable stabilizer—a hold action that removes that step from the mixing dynamics, letting the agent freeze the state and keep \(\Delta_t=\Theta(1)\) (this is exactly workflow_reconcile, which is a permutation automaton yet learnable)—or (ii) a synchronizing/absorbing distinction, where \(P\) is not mixing and the span never contracts to zero (this is no_three_zeros, workflow_api). This is the §5.5 predictor, derived rather than observed.

Empirical confirmation. Computing \(\Delta_t\) exactly from the oracle (spread of \(\rho_s\) over latent state vs.number of intervening random steps) matches the theory to the digit: parity collapses to \(\Delta=0\) after a single random step; \(\texttt{mod\_k}{}\) decays geometrically (\(\Delta\approx2^{-r}\): \(0.50,0.25,0.125,0.031,\dots\) after \(r=1,2,3,5\)); workflow_api stays at \(\Delta\equiv1.0\) (absorbing accept/reject) and no_three_zeros stays high (\(\Delta\approx0.30\) out to \(16\) steps); workflow_reconcile decays like a counter under random play but its hold action lets the policy avoid the decay. The vanishing-credit regime and the predictor’s hard class coincide exactly.

9 Behavioral diagnostics cannot localize the failure↩︎

Figure 2 substantiates the §5.4 claim that an exact instrument sees what a behavior-only diagnostic cannot. Plotting every RL-evaluated task by its reward gap (\(1-\)val\(_n\), the strongest purely behavioral signal) against its probe gap, tasks at the same—large—reward gap span the entire probe range. A reward-only auditor would group mined_ean (perception gap, probe \(+0.03\)) with ends_with_1000 (planning gap, probe \(+0.62\)) as “the agent is failing,” yet they are opposite failures with opposite fixes. Across the suite the reward gap and OOD reward drop correlate only weakly with the probe (Spearman \(-0.29\), \(-0.25\)), confirming that no behavioral summary recovers the perception/planning distinction the probe makes directly.

10 Held-out validation of the predictor, and the causal fix↩︎

Fresh-DFA validation. To test whether the §5.5 predictor generalizes beyond the curated suite, we generated fresh random dfas (\(3\)–\(7\) states, \(2\)–\(3\) symbols), oracle-filtered to be diagnostic, and stratified to populate both predictor classes (the predicted-hard class—permutation with low leverage—is \({\approx}1\%\) of uniform-random diagnostic dfas, so a natural sample would need thousands). We report \(153\) such automata: an initial \(33\) (\(5\) seeds) and a \(120\)-automaton extension (\(3\) seeds) generated from a separate seed, \(4.6\times\) larger so the held-out estimate is not small-sample. The predictor was computed from \(\delta\) alone before any RL; we then ran the full instrument (GRU\(+\)PPO, \(6000\) iters). We control capacity directly: an off-policy supervised probe saturates (val and OOD accuracy \({\approx}1.0\)) on the automata, so a low on-policy probe is a genuine perception gap (state recoverable but not recovered), not a representational limit. We therefore label each automaton perception-hard if probe recovery \(<0.5\), planning-hard if the state is recovered but reward is suboptimal (val\(_n<0.85\)), else solved (Table 3). The Props 1–2 direction transfers: of the \(103\) permutation automata, \(89\) are perception gaps (precision \(0.86\)), and \(89\) of all \(109\) perception gaps are permutation (recall \(0.82\))—permutation structure is a high-precision, one-directional signature of the perception gap on automata it never saw. The original \(33\) reproduce exactly (\(19/23\), precision \(0.83\)); the larger set leaves precision essentially unchanged. Two caveats. The converse fails: non-permutation automata are heterogeneous (\(20\) perception, \(14\) planning, \(16\) solved of \(50\)), so group structure flags that state-blindness is likely, not that a non-group task is safe. We could not isolate a clean structural property shared by these non-group perception gaps (diameter, minimum image size, and mixing rate do not separate them), and notably they are largely not explained by the credit-vanishing mechanism (their acceptance-influence \(\Delta\) persists rather than decaying)—a mix of reward shortcuts (high reward, state unrepresented) and optimization failures. A structural account of perception gaps outside the group class is the one genuine open hole in the predictor story. And the leverage threshold does not transfer (the conjunction’s recall collapses, the scalar \(L\) over-crediting steerability—it waves through most of the easy_perm stratum, which are predominantly perception gaps), so we demote \(L\) to a within-group severity proxy. (On the original \(33\), the result replicates on an LSTM—precision \(0.78\)/recall \(0.78\), \(22/24\) GRU perception gaps shared, capacity equally saturated—so it is not a recurrence-cell artifact. A sharper predictor of which permutation automata are hardest, and of the non-group perception gaps, is open.)

permutation \(\to\) perception gap: recall \(89/109{=}0.82\), precision \(89/103{=}0.86\); leverage threshold (conjunction) does not transfer.

The causal fix transfers. Where prediction is imperfect, the prescribed design levers still work as interventions (Table 4). On mod_5 (predicted and measured hard), adding a controllable hold (latchability: mod_5_hold, which raises \(L\) from \(0.433\) to \(0.523\) and remains a permutation automaton) nearly doubles reward and roughly doubles recovered state, while sharply cutting seed variance; supplying an informative emission channel (observability, the §5.3 \(\beta\) lever) recovers the state and reward to near-optimal. Both are pre-registered as the predictor’s two named escape routes, and both close the gap.

11 An LLM-agent instrument: two of the three axes replicate at scale↩︎

The paper’s motivation is stateful agent reliability, so we ported the entire instrument to a real LLM agent and pre-registered the test (hypotheses and decision thresholds accompany the release). We render each step of PartialControlDFAEnv as natural-language tool I/O with the alphabet relabeled to arbitrary tokens (so a pretrained model cannot pattern-match “this is mod-\(k\)”) and the dfa rule kept out of the prompt; the agent emits one action token per controllable step with no chain of thought (so an activation probe is not undercut by state offloaded into emitted reasoning). The oracle transfers unchanged; we probe the residual stream at the action token with the same linear probe, selectivity control, and capacity bounds. We ran this on Qwen2.5-3B/-7B-Instruct on a single GPU (released code). Two of our three axes reproduce on a real LLM, which is the main message of this appendix.

Axis (ii), structure, replicates as a representational limit. A frozen pretrained model does not linearly encode the latent state (probe at chance for 3B and 7B on mod_5, gap \(0.03\)); a privileged supervised fine-tune (LoRA to predict \(q_t\), the LLM analog of our capacity bound) installs it, but only at short counting horizons (Table 5): parity capacity decays \(0.84\to0.63\to0.51\) as the horizon grows \(L{=}8\to12\to16\), while at \(L{=}8\) even mod_5 is representable (\(0.73\)). The limit is the length of the count, not the state-count—the star-free/length-generalization boundary of §2 (§5.2’s transformer result), now as a representational limit on a 3–7B transformer.

Axis (i), optimizer strength, replicates—and the weak-optimizer outcome was predicted. On a representable task (mod_5\(@L8\), capacity \(0.73\), oracle random \(0.20\)/optimal \(0.55\)), our REINFORCE-level loop (group-normalized return, no value baseline or GAE) does not raise reward and destabilizes (reward drifts below random as the policy leaves the base model). This is not a surprise but a consistency check: it is exactly the synthetic weak-optimizer (A2C) regime of §5.2, which also failed to install state and which the stronger PPO\(+\)GAE partially repaired. The reason we hit it first is compute, not design—a PPO\(+\)GAE optimizer for an LLM (a value head and GAE over the agent’s decisions) is heavier than the group-baseline loop. We therefore also implemented that optimizer—a scalar value head, GAE over the agent’s ordered decisions, and a clipped surrogate with multiple epochs—and confirmed it works: on a reach-commit control (workflow_api) it raises reward stably, where the REINFORCE loop stagnated. On mod_5\(@L8\), however, it still does not learn: conservative settings hold reward at the random baseline and aggressive settings destabilize it, with the state installed in neither case (frozen and post-PPO probe at chance, gap \(0.04\); reward \(\approx\) random, \(0.39\) normalized; capacity \(0.73\)). This mirrors the synthetic finding: synthetically PPO recovers reach-commit/local tasks but only partially recovers accumulation counters, and there only with \({\sim}30\times\) the updates; at LLM scale the competent optimizer likewise learns the local task and not the accumulation counter within budget. The optimizer-strength ordering (REINFORCE degrades \(<\) PPO stable-but-no-traction) and the accumulation-is-hard axis (§5.4) both reproduce.

Scope of the one thing we do not get. A single clean perception gap at LLM scale—reward clearly above random with the probe at chance and capacity saturated—never materializes, because no optimizer we ran lifts reward above random on a representable group counter within budget: the very accumulation credit-assignment difficulty the paper isolates blocks it at scale too. The blocker is thus optimization (the hardness of accumulation under sparse reward), not representation, so the open corner is a stronger / longer-trained LLM RL optimizer, not a larger model. We report this straight, and release the instrument (NL environment, exact oracle, residual-stream probe with selectivity, frozen and supervised capacity bounds, and both RL loops) so that corner can be filled directly.

References↩︎