acceptodds
Under review as a conference paper at ICLR 2027

A Neuro-Symbolic Approach to Length Generalization

Abstract

Length generalization (LG), which is the ability of a model trained on short inputs to correctly reason over substantially longer inputs, is a fundamental and challenging problem in learning to reason. Although chain-of-thought (CoT) training can improve LG, the challenge remains. Recent approaches have also introduced positional tags to indicate the tokens involved in each CoT step, biasing the model toward more structured reasoning. While effective to some extent, they still struggle to generalize to substantially longer inputs. In this paper, we propose a novel neuro-symbolic approach to LG for a class of reasoning problems, whose CoT input can use tags to indicate the positions of tokens involved in each reasoning step. The neural training attends only to these positions and their immediate neighbors, together with bounded control information. Instead of directly predicting the output sequence as in existing methods, our neural model predicts only a fixed set of actions that are independent of input length. The actions are executed symbolically outside the neural model to produce the next state. This is similar to how humans perform reasoning tasks. Due to the fixed local contexts and action set, the proposed method is length-invariant and can be applied to inputs of arbitrary length for the class of problems. We evaluate the proposed approach on 10 reasoning tasks, including parity, addition, subtraction, multiplication, and division. Despite training on short sequences, our method consistently generalizes to sequences of very long lengths, achieving perfect LG across the evaluated tasks.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
length generalization, neuro-symbolic reasoning

Reviews

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

This paper proposes a neuro-symbolic framework for length generalization. A Transformer predicts local computation results, pointer movements, and control actions based on the local neighborhoods of a fixed number of pointers and the current control state. An external symbolic program then executes these predictions and updates the state. Each task is trained separately using supervised algorithm execution traces, transforming the problem of solving long inputs into the repeated application of the same local policy. Experiments on ten synthetic tasks, including copying, parity checking, and arithmetic operations (addition, subtraction, multiplication, and division), report 100% accuracy on the tested longer inputs after training on shorter ones.

Critical strengths

None.

Critical weaknesses
  1. The motivation and practical value of this approach are unclear. If the goal is to solve these specific algorithmic tasks, a direct implementation already handles arbitrary input lengths, subject to computational resources. Once the algorithmic decomposition, state representation, pointer interface, and subroutine composition have been specified, why train a neural network to learn the remaining local rules instead of simply writing them in code? If the goal is to address length generalization in general-purpose models, training a separate policy for each task with task-specific algorithmic structure does not demonstrate progress toward that goal. The reported perfect accuracy on longer inputs therefore does not, by itself, establish the significance of the method. What does neural learning contribute beyond the algorithmic structure already supplied by the designer?
  2. The novelty over prior neural program execution methods is unclear. Neural Programmer-Interpreters already learned pointer-based actions, subprogram calls, and termination from execution traces, while Recursive NPI studied provable generalization to arbitrary input lengths. What fundamentally new capability or principle does the proposed local action predictor and symbolic executor introduce beyond these approaches? The paper should also clarify its contribution relative to structured scratchpad/CoT methods. Without these comparisons, the claim of being the first neuro-symbolic approach to length generalization is insufficiently supported.
Questions for authors
  1. If the algorithmic structure is already specified, why train a neural model to learn the remaining local rules instead of simply implementing them in code?
  2. What is fundamentally new about this approach compared with Neural Programmer-Interpreters, Recursive NPI, and structured scratchpad methods?
Reviewer_NEnHOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript focuses on length generalization, which remains an importent topic in current LLMs. It decomposed algorithmic reasoning into local action predictions by a transformer and deterministic execution by an external symbolic executor. Experiements show strong length generalization in 10 tasks. However the tasks are relatively simple, and the experimental validation is insufficient.

Critical strengths
  1. Noted a key issue regarding LG
  2. The experimental results are quite decent, achieving nearly 100% accuracy even on very long sequences
Critical weaknesses
  1. Current works on LG are shifting toward task universality [1][2]. While in this work, different computational structure are designed manually for each task. Even with a very high level of accuracy, it remains task-specific.
  2. Symbolic Executor seems to be python programs, and is there any fundamental difference between it and the tool-use capabilities of current agents? Demonstrating lower latency while maintaining the same level of accuracy may be more compelling, so I suggest adding further experiments.
  3. The underlying principles are not novel, which involve breaking down complex computations into smaller sub-steps. So what are the key differences between this paper and previous works [1][2][3]?
  4. Not clear how CoT trajectories for training are obtained. Furthermore, is it strictly necessary to endow an LLM with such capabilities through training, or could this be achieved via prompting?
  5. The tasks are too simple and lack sufficient coverage. They fail to account for tasks that may involve non-fixed, repetitive operations, and it is worth questioning whether a model trained with such CoT exhibits cross-task generalization?

[1] Hua Z, Zhang W, Lyu C, et al. The imitation game: Turing machine imitator is length generalizable reasoner[C]//International Conference on Learning Representations. 2026, 2026: 902-927.

[2] Hou K, Brandfonbrener D, Kakade S, et al. Universal length generalization with turing programs[J]. arXiv preprint arXiv:2407.03310, 2024.

[3] Hu Y, Kang S, Yang H, et al. Beyond single-task: Robust multi-task length generalization for llms[J]. Advances in Neural Information Processing Systems, 2026, 38: 42370-42421.

Questions for authors

‌See weaknesses.

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

This paper proposes a neuro-symbolic approach to length generalization, evaluated on simple algorithmic reasoning tasks. Authors aims to make each reasoning step length-invariant. Specifically, a Transformer predicts local actions from a few tagged positions, and an external executor applies them to produce the next reasoning step. Experiments show strong generalization ability across various tasks.

Critical strengths
  1. The paper tackles length generalization, a fundamental challenge in reasoning.
  2. The method achieves perfect accuracy on all evaluated tasks.
Critical weaknesses
  1. Limited generality. The method depends on hand-designed CoT traces, tag-movement schemes, etc. It is unclear how it can be applied to tasks without a known step-by-step algorithm. In other words, can this method be applied to more realistic reasoning problems?

  2. Overly simple benchmarks. All experiments are conducted on quite simple synthetic algorithmic problems. The vocabulary is limited, which might make the generalization much easier. I will suggest the author to use more complicated datasets for experiments.

  3. Unclear role of neural-symbolic. The method is highly symbolic. In this case, a simple lookup table might achieve the same results? It is unclear what the neural network actually contributes.

Questions for authors

see weakness

Reviewer_b9o4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

To fix length generalization, a small neural net emits a structured action each step (what to write, how three pointers move, which phase, whether to stop) and a deterministic symbolic executor applies it. The net uses radius-1 local attention plus positional tags and has only 137k parameters. Supervision comes from a differencer that recovers actions from consecutive states, so no manual action labels are needed. All 60 test cells score 1.000.

Critical strengths

The locality contrast is as sharp as an ablation gets. That turns length generalization from a scaling mystery into an answerable architecture question, at a parameter count anyone can reproduce cheaply.

The differencer removes the supervision bottleneck that usually makes such hybrids impractical — intermediate program states cannot be hand-labelled at scale, but state traces suffice here. This is the part most likely to be reused.

Critical weaknesses

No baselines are run, and the stress test covers only the three easiest tasks. Table 1 has no comparison against NoPE, ALiBi, position-scaling, length-augmented training, or a plain Transformer at matched 137K parameters — so "60/60" shows the architecture can solve these tasks, not that it beats anything (For Copy and Parity at L ≤ 8 a small Transformer may well also hit 1.000, while a variant in Table 5 sits at 0.43–0.54, shows that the design is not uniformly robust, and without baselines I cannot tell whether 0.5 is good or catastrophic.)

Questions for authors

What does a matched-parameter full-attention Transformer score on the same 60 cells, and what do NoPE / ALiBi / length-augmented training score on the stress-test tasks at L = 400–1000?

Why were the harder programs excluded from the stress test?

What is the Table 5 variant and why does it fail? Around 0.5 on a deterministic task usually indicates phase misalignment, which would be informative.

Is there an end-to-end accuracy number for a composed multi-stage program, and does error compound across child policies?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.