acceptodds
Under review as a conference paper at ICLR 2027

SUCCINCTNESS IS NOT IDENTIFIABILITY: FINITE-EVIDENCE LIMITS FOR TRANSFORMER LENGTH GEN-ERALIZATION

Abstract

Modern Transformers can solve many algorithmic tasks at the lengths observed during training, yet fail on longer inputs. We argue that ffnite endpoint-only evi-dence may fail to identify the intended length-generalizing algorithm. We formal-ize this with the Length-Generalization Identiffability Dimension (LGID), deffned relative to an explicit hypothesis code, observation channel, and long-horizon dis-tribution. For hidden transducer tasks, we separate compact expressibility from identiffability in coded symbolic and programmatic reference classes: endpoint labels can leave compact splice shortcuts, while transition witnesses that cover observable-critical edges remove this shortcut family. Orbit compression remains a conditional corollary under hard equivariance. In controlled hidden-transducer diagnostics, trained Transformers are used as proxy learners for the evidence vari-able identiffed by the theory. Achieved or effective clean transition coverage pre-dicts latent-rule recovery. A train-only readout calibrator gives a behavioral clo-sure diagnostic under ffnal-state label coverage, while endpoint-only and extra-endpoint controls remain near the ffoor. Oracle-free selection and noisy-channel diagnostics show that selector quality is mediated by effective coverage. End-point/readout, transfer, and orbit diagnostics characterize the boundary between latent-rule recovery and full behavioral generalization.

Primary area:
learning theory
Keywords:
Length Generalization, Identifiability, Finite Evidence, Transition Coverage, LGID

Reviews

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

This paper studies when finite evidence is sufficient to support length generalization under a specified deployment protocol. It organizes the problem into four stages: Identification, Acquisition, Recovery, and Composition. The paper formalizes evidence sufficiency using version-space radii and introduces a prefix-trigger construction showing that information requirements can be non-monotonic when evaluating a single horizon, but are monotonic when correctness is required at all horizons up to a given limit. It further uses pair-state and killed operators to characterize endpoint disagreement and never-error survival during repeated execution. The framework is validated through controlled experiments on prefix-trigger families, Hidden Modular Color, bounded Dyck tasks, and Transformers, illustrating how similar endpoint performance can arise from different bottlenecks across the four stages.

Critical strengths
  1. A useful decomposition of length-generalization failures. The Identification–Acquisition–Recovery–Composition framework distinguishes information insufficiency, failure to obtain decisive evidence, imperfect recovery, and error propagation during execution. This is consequential because models with similar endpoint accuracy may fail for fundamentally different reasons and therefore require different interventions.
  2. Meaningful analysis of deployment-dependent behavior. The prefix-trigger construction demonstrates that information requirements may be non-monotonic under single-horizon evaluation but monotonic under cumulative evaluation. The pair-state and killed-operator analyses also clarify the distinction between endpoint correctness and never-error survival. These results expose limitations of evaluating length generalization using only endpoint accuracy or average local accuracy.
Critical weaknesses
  1. Limited theoretical novelty and insufficient positioning. Several formal results are relatively elementary once the proposed quantities are defined, including standard monotonicity, linear-recovery, convergence, and triangle-inequality arguments. The four-stage framework also substantially overlaps with established concepts from version-space analysis, teaching dimension, active learning, system identification, and automata learning. The paper does not sufficiently clarify what is technically new beyond reorganizing these existing ideas, which weakens its claimed theoretical contribution.
  2. A substantial gap between the framework and realistic neural length generalization. The validation is restricted to small, controlled systems with explicitly enumerable states and transition tables, such as 16-state HMC and bounded Dyck tasks. The composition diagnostics rely on reconstructing a discrete transition table and computing its operator, whereas realistic language models operate through high-dimensional continuous representations without an available finite-state abstraction. Consequently, the experiments demonstrate the framework in settings designed to satisfy its assumptions, but do not establish that the proposed diagnostics are applicable to realistic Transformer or LLM reasoning tasks.
Questions for authors
  1. What are the precise technical novelties of the four-stage framework relative to version-space analysis, teaching dimension, active learning, system identification, and active automata learning? In particular, which results should be regarded as new theoretical contributions rather than applications of standard arguments to newly defined quantities?
  2. How can the proposed Composition diagnostics be computed when the model does not admit a known finite-state abstraction or an enumerable transition table? Is there a principled procedure or approximation for applying the framework to standard Transformers or LLMs with continuous hidden states?
  3. What evidence supports the claim that the observed four-stage separation extends beyond tasks constructed around explicit finite-state dynamics? Are any existing results applicable to a less controlled neural length-generalization setting without access to the ground-truth state representation?
Reviewer_VawzOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

I had a very difficult time understanding this paper. Perhaps there is a targeted specialist community for which the paper is clearly written. I've published on length generalization and I've read 5-10 of the cited papers, so I think the submission is likely to be difficult for most of the ICLR audience. It's not just that the material is highly technical, but many key terms are never defined (see below).

In any case, here's my best attempt (no AI help): the paper decomposes the length generalization problem into a cascade of four "contracts" that must be met for length generalization to hold. It offers theory to help characterize the conditions under which each contract can be met, or when it "bottlenecks" length generalization. The empirical section uses synthetic data to "ask whether stage-specific objects distinguish failures that endpoint accuracy merges." This seems to mean showing that at least for some synthetic data, it is possible to run empirical checks at each stage.

Critical strengths

Length generalization is a fundamental problem for learning, and the paper proposes to decompose the problem into more fundamental elements, which would shed light on why length generalization is difficult in various cases.

Critical weaknesses

As noted above, my main problem with this paper is that it is written so as to be inaccessible to non-specialists. Without resolving this issue, it's hard to evaluate the paper on its substantive merits. If other reviewers feel more confident about the substantive merits of the work, the AC should feel free to focus on their reviews and disregard this one.

Questions for authors

I'll highlight just a few of my questions here:

  • 18: expression 1:d:Θ(2dlog⁡(1/δ))1 : d : \Theta(2^d \log (1 / \delta)), what does this mean?
  • 111: what does OeO_e mean?
  • 111: should f∗f^* appear on the LHS somewhere?
  • 120: what does LGID stand for?
  • 122: what does EAC stand for?
  • 142: what is a 3d3d-state predictor?
  • 182: what is m‾t\overline{m}_t?
  • 190: what is an HMC table?
  • 267: what is passive RPNI?
Reviewer_FPRFOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a four-stage framework for investigating length generalization: identification, acquisition, recovery and composition.

Critical strengths

I could not assess the technical strengths from the current presentation.

Critical weaknesses

I was unable to develop a sufficiently clear understanding of the central framework from the main text to really assess the scope, soundness and significance of the claimed results. My main problem is that the main paper does not give a clear and detailed presentation of its problem setting and most important results. It does not provide any self-contained or intuitive presentation of the theoretical statements. Understanding the framework repeatedly requires reconstructing mathematical objects from context. Furthermore, the paper never clearly defines the concrete problem setup it is trying to solve.

In the introduction terms like "finite evidence", "deployment protocol", "rare trigger", "3d-state prefix-trigger family" or output "saturation" are used before the reader is given an intuition of what the actual problem setting is.

The definitions, lemmas and theorems are repeatedly introducing new notation and symbols which are neither explained nor given an explicit mathematical type. Here an incomplete list of such occurences:

  • hh and gg on page 2,
  • f∗f^*, OeO_e, EtrainO\mathcal E_{\text{train}}^{O}, SS on page 3,
  • FsF_s in Theorem 3.2,
  • mˉt\bar m_t and ctc_t in Prop. 3.6
  • ...

Even though some intended meanings can be inferred or seem to be more explained in the appendix, these are essential to understand the paper or assess the soundness of the results. My general problem is that the main text repeatedly omits the definitions and construction details needed to understand the statements themselves.

These problems concern the definitions and constructions needed to understand the claims themselves, rather than their proofs. This prevents me from confidently evaluating the central contributions. I therefore recommend rejection in its current form.

Questions for authors

Please comment on the weaknesses above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.