Automata Learned From an Ensemble's Disagreements Decide When the Ensemble Is Needed

Running five copies of a neural network and checking whether they disagree is the most reliable way to tell when a model is guessing, but it costs five times the compute. This proposal applies that idea to sequence models trained on structured, rule-like inputs, and asks whether the places where copies disagree can be written down once as a small state machine. The machine would be a finite automaton: a graph of discrete states with one transition per input symbol. At test time it would run alongside a single network for almost no cost and call the rest of the ensemble only when the input enters territory the machine marks as contested or unknown.

The mechanism is active automata learning, Angluin's $L^*$ algorithm, in which a learner builds a state machine by asking a black box what it outputs on chosen inputs and then repairing its guess when shown a counterexample. Our change is to make the black box an ensemble. Every query returns a vector of member outputs rather than a single label, so the learned states encode both what the networks compute and where they disagree. A second check comes from hidden-state clustering. The single deployed network's internal activations are mapped onto the automaton's states, and a mismatch between the symbolic state and the neural state is treated as a sign that the network has drifted. The core claim is that this gate spends ensemble compute more accurately than gates based on the softmax output, the network's predicted probability vector. The advantage should be largest on inputs longer than any seen in training and on prefixes the training data never covered, because the learner's own queries probe those regions and a held-out validation set does not.

What Exists and What Is Missing

Two papers extract automata from networks with $L^*$. Weiss et al. do this for recurrent networks (RNNs), splitting the hidden-activation space with an SVM only where a counterexample shows a conflict. Maene and Adriaensen extract Moore machines from single-layer Transformers using decision trees and SVMs. Both treat the network as one deterministic oracle and never measure uncertainty or calibration. Maene and Adriaensen also report a blind spot that motivates us: models trained only on valid strings lack error ("garbage") states. Weiss et al. supply our abstraction-refinement method and also a constraint, since $L^*$ keeps splitting states when the oracle is noisy. An ensemble teacher makes that risk worse, and the design below has to control it.

Three papers bind uncertainty to discrete states, but none uses active querying. LUNA clusters LLM hidden states offline into Markov chains to flag hallucinations and out-of-distribution inputs. CLUE classifies reasoning traces by their distance to success and failure centroids. ST-τ trains RNNs with stochastic transitions over $k$ prototype states and matches 10-model Deep Ensembles at out-of-distribution detection on ECG data. All three are passive and evaluate single models. ST-τ also fixes $k$ in advance and needs retraining, and its authors found that the purely discrete version underperforms the soft one. That finding constrains us. We do not ask the automaton itself to produce calibrated probabilities from hard states. Calibration comes from ensemble vote frequencies attached to each state, and the hard states serve only for routing.

On the compute side, Xia and Bouganis cascade ensemble members and escalate only inputs whose uncertainty falls inside a window $[t_1, t_2]$. Their policy reads only the output scores and treats the networks as black boxes. Guo et al. explain why output scores are a poor gate: modern networks are confidently wrong, temperature scaling cannot reorder their mistakes, and it does not hold up under distribution shift. Gating ensemble compute with an actively learned automaton combines these strands, and the file reports no prior work on it.

Research Program

The setting has a finite input alphabet, so $L^*$ applies directly. We train an ensemble of $M=5$ independently initialized RNNs or one-layer Transformers on a sequence task. Using AALpy, we run $L^*$ against the ensemble as teacher. A membership query on a string $w$ returns the vector $v(w)=(y_1(w),\dots,y_M(w))$ of member outputs, quantized for classifiers to accept or reject per member. Two prefixes are merged into one state only if every suffix produces the same vector. A state is therefore "contested" when its suffix behaviour includes split votes.

Equivalence queries are approximated by sampling strings that are random, longer than the training lengths, or produced by mutation testing in the style of Efficient Active Automata Learning via Mutation Testing. Sampling is weighted toward strings on which members currently disagree. To control state explosion from noisy members, two vectors are treated as equal when they differ in at most one vote, and the number of states is capped. We report how sensitive results are to this tolerance and cap.

Next we connect the automaton to the deployed network. Following Weiss et al., we fit a classifier from member 1's hidden state at each prefix to the automaton state reached by that prefix. Each state also stores two things computed on the training distribution: the frequency of ensemble agreement in that state, and how often the state was visited during validation.

At deployment only member 1 runs, together with the automaton, which reads the input symbols directly and costs almost nothing. The full ensemble is called when one of three conditions holds. The first is that the current or reached state is contested. The second is that member 1's hidden state is classified into a different state than the automaton reached, which signals that the network's internal state has drifted away from the rule it learned. The third is that the prefix reaches a state rarely or never visited in validation, the garbage states that positive-only training leaves out.

Confidence for non-escalated inputs comes from a per-state agreement frequency fitted on validation data. Escalated inputs receive the ensemble average. The analytical question is which of the three triggers carries the gain, and whether that changes with sequence length.

Baselines

The naive reference is member 1 alone with temperature scaling (Guo et al.). It costs one forward pass per input and shows how much risk an uncorrected single model carries at long lengths. The ceiling is the full 5-member ensemble at five passes.

The strongest competitor is the window-based cascade of Xia and Bouganis. It targets exactly our question: cutting ensemble compute while keeping ensemble-grade selective classification. On ImageNet, their EfficientNet-B2 cascade matches a single EfficientNet-B4's coverage at 5% risk (Cov@5) using less than 30% of the multiply-accumulate operations. The file contains no reported result on Lacuna for cascades on formal-language or sequence benchmarks. We will run it on the same ensembles, with $[t_1, t_2]$ tuned on the same validation split as our per-state statistics. Both methods will be compared at matched average member evaluations per input. Beating it means higher Cov@5, or lower risk at fixed coverage, at equal compute, on lengths four or more times the training length, without losing on lengths seen in training.

The second strong baseline is ST-τ, the closest single-model discrete-state method. It will be trained with the same architecture budget and a tuned $k$. Its sampling passes count toward compute.

SNGP, a single network made distance-aware with spectral normalization and a Gaussian-process output layer, will also be adapted to the recurrent encoder. It reports 0.846 ± 0.019 out-of-distribution AUROC on CIFAR-100, a vision result that is not directly comparable to ours.

Three ablations isolate the ingredients. The first replaces $L^*$ with passive LUNA-style clustering: k-means on hidden states from training data, a Markov chain, and disagreement attached to clusters. This tests whether active querying matters. The second learns the automaton from member 1 alone and attaches disagreement afterward, which tests whether the ensemble teacher matters. The third removes each of the three escalation triggers in turn.

Why not just…?

Why not just train a small probe on member 1's hidden state to predict ensemble disagreement? This is the most serious threat, and we include it as a baseline: a logistic regression or MLP gate trained on validation prefixes, run at the same compute. The probe sees the same hidden states we do. What it lacks is the symbolic state, which does not change with length, and the strings that $L^*$ generates outside the validation distribution. If the probe matches our gate at lengths four to thirty times the training length and on garbage-state prefixes, the automaton contributes interpretability but not efficiency, and we will report that outcome.

Why not just use the softmax window cascade? Guo et al. show that output confidence stays high on errors and under shift. Xia and Bouganis themselves found that plain confidence-threshold exits fail on out-of-distribution data. The window gate is still an output-score gate, so it should fail where member 1 is confidently wrong at long lengths. The length-sweep experiment tests this directly.

Why not just distill the ensemble into one model, or use ST-τ? Distillation compresses the ensemble's spread of answers into a single prediction and loses the structured disagreement. ST-τ fixes $k$ in advance and needs retraining. The proposed method works post hoc on any trained ensemble and selects the number of states from behaviour. ST-τ remains a real competitor on the ECG data, and we will compare against it at equal compute.

Proposed Experiments

The benchmarks are Tomita grammars, depth-bounded Dyck, 10-state random regular languages over three letters, Parity, and the email regex task. For each, we train at bounded length (for example 32) and test at lengths 100 to 1000. Out-of-distribution sets consist of invalid strings and long nested prefixes. Prior extraction work sets expectations for fidelity and cost. Weiss et al. report extracted DFAs that agree with the RNN more than 99% of the time at length 1000, and extraction under 2 seconds on Tomita grammars. Maene and Adriaensen report extraction in under a second on Dyck and Grid but noisy machines on Parity. Parity is therefore a stress test where our method may fail, and we report it as such. As a length-generalization reference for discrete states, SR-LSTM-P reaches a 0.020 error rate on deep balanced parentheses, against 0.543 for a plain LSTM.

As a stretch, MIT-BIH ECG with quantized input symbols tests whether the method survives contact with real data. It also allows a direct comparison with ST-τ.

The metrics are risk–coverage curves with Cov@5, AUROC for detecting errors and out-of-distribution inputs, ECE, and average member evaluations per sequence. Extraction cost is reported as membership and equivalence query counts and wall-clock time, so that the up-front cost of building the automaton is charged against the savings at inference.

The decisive check is the length sweep at matched compute of about 1.5 member evaluations per input. The proposal succeeds if the automaton gate beats both the window cascade and the hidden-state probe at long lengths and on garbage-state prefixes, and if removing active querying (the passive-clustering ablation) erases that gain. It fails if the probe matches it everywhere, or if the vote tolerance cannot stop state explosion on realistic ensembles.