{"id":"99358221-6118-40a6-95dc-5658bb46fb8b","arxiv_id":"2509.02491","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"RNNs trained on short ultimately periodic words achieve high out-of-distribution accuracy on most LTL-derived omega-regular language recognition tasks.","lead":"This paper tests whether recurrent neural networks can recognize infinite-word languages defined by linear temporal logic formulas after training only on short finite encodings. Most of the 27 automata tasks generalized perfectly to sequences eight times longer.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Rejected OOD sequences are generated with suffixes that never visit accepting states, so high OOD accuracy may reflect a shortcut rather than the DBA acceptance condition.","rationale":"The reader's weakest assumption identified the representativeness of the balanced path-based sampling; my analysis sharpens this into a concrete confound. The exclusion rule for rejected suffixes makes the generated distribution separable by the simpler rule 'accept iff the suffix ever enters an accepting state.' Because the OOD test set is generated through the same pipeline, high OOD accuracy does not yet establish recognition of the full omega-regular language. This does not make the paper's feasibility study worthless, but it means the headline claim is conditional on the sampling distribution being representative. Single-seed results are a secondary reliability concern, but the sampling confound is the more load-bearing issue. The CONDITIONAL verdict remains appropriate; no change to the reader's verdict is needed, though the revision should either evaluate on unconstrained sequences or narrow the claim accordingly.","tokens_in":7431,"tokens_out":10533,"duration_ms":110596,"concrete_test":"Use the released code to build an unconstrained held-out test set for each of the 27 DBAs: sample u and v as uniform valid paths without the exclusion rules, allowing rejected sequences whose suffix visits accepting states but whose v-cycle is non-accepting, and allowing accepted sequences that pass through rejecting sinks before reaching an accepting cycle. Label each u$v by exact DBA simulation or Spot and balance classes by rejection sampling. Evaluate the trained models on this set at lengths 65-512, and in particular on the excluded subclass of rejected words whose suffix visits an accepting state. If OOD accuracy drops substantially, the reported generalization is an artifact of the constrained sampler; if accuracy remains high, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that RNNs generalize to the target omega-regular languages, but the OOD test set is drawn from the same constrained generator used for training, and this generator appears to remove the genuinely hard cases. Section 2 states that when sampling rejected sequences, the authors 'prevent transitions to accepting states within the suffix v because if v contains a state transition to an accepting state, the resulting omega-word is likely to be accepted.' For a DBA, an accepted u v^omega must have v's orbit visit an accepting state at least once, so on this constrained distribution the label is exactly 'the suffix v ever enters an accepting state.' A model can therefore achieve perfect train and OOD accuracy by learning this simpler regular property, without implementing the true Buchi condition that an accepting state be visited infinitely often in the limit cycle. The hard rejected cases, where v visits an accepting state but the eventual v-cycle is non-accepting, are never generated. Since Section 3 describes the test data as produced with the same balancing pipeline, the 98.4% OOD figure cannot currently distinguish genuine language-level generalization from an artifact of the sampling heuristic. If the test set was instead generated independently, the paper should state that explicitly; as written, the only described generation procedure includes these exclusions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper trains single-layer vanilla RNNs to classify ultimately periodic omega-words u v^omega encoded as u$v, where the target language is the omega-regular language of a deterministic Büchi automaton (DBA) constructed by Spot from LTL formulas. Training sequences have lengths 2-64; test sequences have lengths 2-512, with out-of-distribution (OOD) defined as lengths 65-512. Across 27 LTL benchmarks (alaska_lift and acacia_example), the authors report mean OOD accuracy of 98.4%, with 92.6% of tasks achieving perfect or near-perfect accuracy, and they observe a strong positive correlation between DBA state count and the L2 norm of trained RNN parameters. The paper concludes that RNNs can generalize to omega-regular languages up to 8x the training length.","tokens_in":7689,"tokens_out":10413,"duration_ms":93345,"significance":"If the reported results are robust, this is a useful and original empirical contribution: it is the first study to show length generalization for RNNs on the ultimately periodic encoding of omega-regular languages, it covers non-toy DBAs up to 105 states, and the code is released. The paper is commendable for using Spot-derived DBAs as ground truth (avoiding circularity), for explicitly considering the bijection between UP-words and the derived regular language, and for diagnosing two failure cases. However, the significance is conditional on the evaluation being representative of the target language; the sampling bias described below currently undermines the central claim.","major_comments":[{"comment":"The rejection sampling in Section 2 (item (3)) removes, from the rejected sequences, all suffix strings v that contain a transition into an accepting state. This deletes exactly the hard negative cases in which v visits an accepting state but the limit cycle of v^omega does not contain an accepting state, i.e., the cases that require the full Büchi cycle condition instead of a simple reachability check. Since the test data in Section 3 is generated with the same pipeline, the OOD accuracy reported in Table 1 cannot currently distinguish genuine recognition of the omega-regular language from learning the simpler regular property 'the suffix never enters an accepting state.' The authors should either re-evaluate on an unbiased or independently generated test set (for instance, sampling DBA paths uniformly without the filtering constraint, or explicitly including hard negatives where v enters an accepting state but the eventual cycle is non-accepting), or provide a formal argument that the excluded sequences have negligible impact on language-level accuracy. As written, the central claim is not established.","section":"2, 'Sampling' and 3, 'Experiments'"},{"comment":"All reported accuracies are point estimates from a single training seed, and no error bars or confidence intervals are provided. Given that two of the 27 tasks exhibit validation collapse during training (Figure 3), the claim that 92.6% of tasks reach perfect or near-perfect generalization is not robustly supported; the percentage could shift substantially under different initializations. The authors should run multiple seeds at least on the tasks with apparent instability, or clearly frame the results as single-run evidence rather than a stable estimate.","section":"3.1, Table 1"}],"minor_comments":[{"comment":"The sentence 'The alphabet size of a DBA is 2|P| + 1' should be typeset as 2^{|P|} + 1; the exponent notation is missing and the current rendering is ambiguous.","section":"2, near the alphabet definition"},{"comment":"The transition label '¬ba∧ ¬b' appears malformed; please check the LaTeX and render it correctly, likely as '¬b ∧ a ∧ ¬b' or a similarly intended conjunction.","section":"Figure 1"},{"comment":"The sentence 'It is still possible to sample equivalent rejected sequences as this constraint is not applied to u' is unclear; consider rephrasing to explain what 'equivalent' means here, for example that the rejection constraint is only enforced on the v part while u may still pass through accepting states.","section":"2, 'Sampling'"},{"comment":"The sentence 'The test data was balanced for the lift formulas and for 20 of the acacia_example formulas. However, the training data was not balanced for the lift formulas and the 3 acacia_example formulas with unbalanced test data' is confusing; clarify which formulas have unbalanced test data and why the training data for them is also unbalanced.","section":"3, 'Experiments'"}],"recommendation":"major_revision","confidential_remarks":"The paper is written for a workshop (OVERLAY 2025) and is positioned as a feasibility study; for a journal, the evaluation bias is the main obstacle. The sampling bias is acknowledged by the authors in Section 2, but its consequences for the central claim are not discussed. I would encourage the editor to request the unbiased test-set evaluation before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first empirical study I know of that trains RNNs as recognizers for omega-regular languages, using ultimately periodic encodings. The headline result, 98.4% OOD accuracy on 27 DBA tasks, is solid as a feasibility claim, though the paper overstates it slightly by calling it generalization to the omega-regular language itself.\n\nWhat is genuinely new: the u$v encoding of ultimately periodic words is paired with a DBA-based labeling pipeline using matrix exponentiation, and they evaluate length generalization up to 8x beyond training. That is a real extension of the regular-language length generalization work. The correlation between DBA state count and trained model parameter norm (r=0.88) is a nice touch and worth taking seriously.\n\nWhere I would press: the results come from a single seed, no error bars. The test set is generated with the same balancing pipeline as training, so the OOD statistic measures generalization within that pipeline's biased distribution, not over the full omega-regular language. That is the main soft spot. The stress-test note about excluded rejected suffixes is, I think, a miss: for a DBA, u v^omega is accepted iff the path of v from delta(u) visits an accepting state at least once, because deterministic runs are periodic with period |v|. So the exclusion of transitions to accepting states in rejected words removes only words that would actually be accepted; there is no subtle 'visited once but not infinitely often' case in a DBA. The shortcut the note worries about is the true label.\n\nThe two failures (Acacia 13 and 22) are honestly reported but not resolved; the accepting-sink hypothesis is plausible but untested. That is fine for a short paper.\n\nOn balance, the central argument holds: RNNs can learn recognizers for these omega-regular languages under a tractable sampling scheme. Anyone working on neurosymbolic verification or on neural length generalization should read this. It deserves a serious referee; the single-seed issue is a revision request, not a desk rejection.","headline":"First solid feasibility study on RNN recognition of omega-regular languages via ultimately periodic encodings, with a real soft spot in the single-seed and biased test generation.","tokens_in":8179,"tokens_out":3125,"would_cite":true,"duration_ms":29697,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","68Q60","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"A recurrent network trained on finite prefixes from a deterministic Büchi automaton can recognize the omega-regular language on sequences up to eight times the training length.","keywords":["recurrent neural networks","omega-regular languages","linear temporal logic","Büchi automata","length generalization","ultimately periodic words","neurosymbolic verification","sequence classification"],"falsifier":"Train the same model on one small DBA, then test it on an exhaustive enumeration of all distinct ultimately periodic words up to length 512 rather than on a sample of 512 sequences; if exhaustive accuracy falls far below the sampled accuracy, the sampling distribution, not the network, would be doing the work.","tokens_in":1716,"feed_emoji":"🧠","tokens_out":3515,"duration_ms":90711,"temperature":0.7,"pith_summary":"The paper asks whether a recurrent neural network can learn to recognize an omega-regular language, a set of infinite sequences defined by a linear temporal logic specification, from finite training examples alone. Its answer is yes, on the evidence of 27 LTL-derived tasks with deterministic Büchi automata of 3 to 105 states: after training only on ultimately periodic words of length 2 to 64, the networks reached a mean out-of-distribution accuracy of 98.4% on sequences up to length 512, with 92.6% of tasks achieving perfect or near-perfect generalization. This matters because omega-regular languages are the specification language of reactive-system verification, and a network that generalizes across lengths could serve as a differentiable substitute for explicit automata in neurosymbolic verification tools. The paper restricts its claim to the tested length range and to deterministic automata, and it explicitly reports two tasks that failed to generalize.","feed_headline":"RNNs generalize to omega-regular languages at 8x length","feed_subtitle":"Trained on short finite prefixes, recurrent networks matched Büchi automaton acceptance in 25 of 27 tasks.","key_machinery":"The load-bearing object is the encoding of an ultimately periodic omega-word $uv^\\omega$ as the finite word $u$v$, which a known result shows forms a regular language in bijection with the original omega-regular language — so an RNN trained to classify these strings is, in principle, learning a canonical finite projection of the Büchi automaton from which the automaton can be reconstructed. The second component is the data-generation pipeline: sample $u$ and $v$ as uniform paths through the DBA, apply targeted rebalancing to counteract accepting and rejecting sink states, and label exactly by simulating the DBA, computing the transition matrix of $v$ and exponentiating it to check reachability of an accepting cycle. Together these pieces make infinite acceptance conditions finite and balanced enough for gradient training.","core_discovery":"The central discovery is that the acceptance behavior of a deterministic Büchi automaton can be learned by a vanilla RNN from finite encodings of infinite words. The paper represents an omega-word $uv^\\omega$ as the finite string $u$v$, relying on the fact that ultimately periodic words uniquely characterize an omega-regular language and stand in bijection with a derived regular language. Simulating DBA runs with matrix exponentiation supplies exact labels during data generation, and balanced path-based sampling prevents acceptance biases from dominating the dataset. Under this protocol, the trained networks reach 100% in-distribution accuracy on all 27 tasks and 100% out-of-distribution accuracy on 23 tasks, with an overall out-of-distribution mean of 98.4%. The paper further reports that the trained models' parameter norms correlate strongly with DBA state count ($r = 0.880$), which it reads as evidence that the networks internalize something like the automaton's structural complexity rather than merely memorizing the training set.","pith_inferences":["A testable extension: the $u$v$ encoding and exact labeling procedure are architecture-agnostic, so the same data generator could train transformers or state-space models, making the paper's protocol a reusable benchmark for length generalization on omega-regular languages.","The failure cases suggest a targeted intervention: train on sequences whose suffixes must remain in accepting sink states for long stretches, which would directly test whether the hypothesized sink-state memory limitation explains the observed performance collapse.","If the parameter-norm correlation with DBA state count is genuine, one could predict which specifications need larger or smaller networks before training, using only the automaton's structure.","The paper does not establish that the trained RNN actually implements a Büchi acceptance condition; extracting an automaton from the trained network and comparing it with the original DBA would settle whether the network approximates the language or merely fits the sampled distribution."],"forward_implications":["If the central claim holds, recurrent networks trained on $u$v$ encodings can be reused as approximate recognizers for their target omega-regular language in the tested length range, without maintaining the explicit Büchi automaton during inference.","The strong correlation between DBA state count and model parameter norm suggests that a model's learned complexity tracks the specification's structural complexity, which could help diagnose under- or over-parameterization in verification tasks.","The two failure cases show that perfect in-distribution accuracy does not guarantee length generalization; unstable validation accuracy during training is an early warning signal, and accepting sink states are a suspected source of difficulty.","Because the method is restricted to deterministic Büchi automata, the demonstrated capability covers recurrence properties but leaves persistence properties and non-deterministic Büchi automata open for future work.","The finite encoding preserves enough information to reconstruct the original DBA, so a learned recognizer of this kind could in principle be combined with automata-extraction or formal-verification routines to check what the network actually learned."],"supporting_citations":[{"why":"Supplies the foundational result that ultimately periodic words uniquely characterize an omega-regular language, justifying the finite $u$v$ encoding.","marker":"[13]"},{"why":"Provides the automata-construction toolchain that builds a DBA from each LTL formula, the source of all generated training and test sequences.","marker":"[14]"},{"why":"Establishes the baseline that RNNs generalize on regular languages, which the paper extends to omega-regular languages via the projective encoding.","marker":"[6]"},{"why":"Shows RNNs can efficiently represent regular languages, supporting the choice of RNN architecture.","marker":"[7]"},{"why":"Provides recent work on training neural networks as recognizers of formal languages that the method builds on.","marker":"[5]"},{"why":"Categorizes temporal properties as recurrence versus persistence, justifying the restriction to DBAs and recurrence properties.","marker":"[15]"},{"why":"Supplies the alaska_lift benchmark formulas used as tasks.","marker":"[22]"},{"why":"Supplies the acacia_example benchmark formulas used as tasks.","marker":"[24]"}],"fun_headline_variants":["RNNs learn Büchi automata, generalize to 8x longer sequences","Vanilla RNNs ace infinite-word acceptance at 8x length","Recurrent networks generalize to omega-regular languages 8x","RNNs match Büchi acceptance on 25 of 27 tasks, 8x longer"],"cache_read_input_tokens":10368,"weakest_assumption_plain":"The claim rests on the assumption that the balanced, path-based sampling of sequences produces a test distribution that fairly represents the full omega-regular language, so that high accuracy on the sample really means generalization to the language itself rather than only to the sampled paths.","fun_headline_variants_meta":{"raw":{"variants":["RNNs learn Büchi automata, generalize to 8x longer sequences","Vanilla RNNs ace infinite-word acceptance at 8x length","Recurrent networks generalize to omega-regular languages 8x","RNNs match Büchi acceptance on 25 of 27 tasks, 8x longer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000291,"raw_usage":{"total_tokens":1709,"prompt_tokens":963,"completion_tokens":746,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":664}},"tokens_in":579,"tokens_out":746,"duration_ms":7000,"temperature":1.0,"reasoning_tokens":664,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:37:40.862851+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the same model on one small DBA, then test it on an exhaustive enumeration of all distinct ultimately periodic words up to length 512 rather than on a sample of 512 sequences; if exhaustive accuracy falls far below the sampled accuracy, the sampling distribution, not the network, would be doing the work.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the foundational result that ultimately periodic words uniquely characterize an omega-regular language, justifying the finite $u$v$ encoding."},{"cited_title":"Delétang, A","cited_arxiv_id":null,"evidence_quote":"Establishes the baseline that RNNs generalize on regular languages, which the paper extends to omega-regular languages via the projective encoding."},{"cited_title":"4118–4135","cited_arxiv_id":null,"evidence_quote":"Shows RNNs can efficiently represent regular languages, supporting the choice of RNN architecture."},{"cited_title":"URL: https://openreview","cited_arxiv_id":null,"evidence_quote":"Provides recent work on training neural networks as recognizers of formal languages that the method builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the alaska_lift benchmark formulas used as tasks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the acacia_example benchmark formulas used as tasks."}],"review_version":1}