acceptodds
Under review as a conference paper at ICLR 2027

WHEN ATTENTION FAILS ON FINITE FIELDS: GALOIS ALGEBRAIC REASONING NETWORKS WITH HARD COSET EXECUTION

Abstract

Exact algebraic relations need not align with similarity in a learned embedding space. We study this mismatch through a controlled coset-classification task over AES : labels depend on multiplicative ratios, while both classes have identical single-byte marginals. We introduce GARN, a Galois Algebraic Reasoning Network that separates learned interaction weights from exact field execution. Attention proposes interactions, fixed inverse and multiplication tables compute ratios, and learnable membership masks provide evidence for prediction and state updates. Across five seeds, GARN reaches 99.5% test accuracy with 256 labeled examples, whereas the tested Transformers, MLPs, and discrete relaxations remain near chance through 1,024 examples. With shuffled partners, GARN reaches 79.9%, compared with 67.0% for a fixed-adjacency probe. Template-free masks, alternative byte encodings, and corrupted-operator controls isolate the role of exact execution. These results identify operator access as a decisive source of sample efficiency and establish a practical interface between continuous interaction learning and discrete finite-field computation.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neural algorithmic reasoning, finite fields, relational inductive biases, sample efficiency, neuro-symbolic learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_7b7SOpenReview ↗
Rating
2(+1)
Confidence
2(−1)
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a synthetic classification task over the AES field GF(2^8). Each input is a sequence of byte pairs, and the label is whether every pair's ratio a−1ba^{-1}b lies in a fixed subgroup HH. Single-byte frequencies are the same in both classes, so the label depends only on relations between bytes. The proposed model, GARN, uses attention to propose byte pairs, computes their ratios exactly with fixed multiplication and inverse tables, and learns which ratios belong to HH. With adjacent pairs, GARN reaches 99.5% accuracy from 256 examples, while Transformers, MLPs, and discrete relaxations stay near 50% up to 1,024 examples. With shuffled positions, GARN reaches 79.9%, compared with 67.0% for a fixed-adjacency probe.

Critical strengths

The experiments are carefully controlled. The matched-marginal design makes single-byte frequencies the same in both classes, so the label depends only on relations between bytes. Replacing the exact tables with random ones drops GARN to chance, and template-free masks show that the gain does not rely only on supplying the target subgroup.

Critical weaknesses

Limited insight. The main finding follows naturally from the task design. The label is whether a−1ba^{-1}b lies in HH, and GARN is given exact tables that compute a−1ba^{-1}b. Once the ratio is computed, the remaining problem is to learn which of 255 values belong to HH. This is far easier than learning GF(282^8) multiplication from ≤1024 sequences. The default template bank also contains the target subgroup itself, so HardProbe with templates already reaches 100% at n=32n = 32. Given this setup, it is not surprising that access to the exact operator is what drives sample efficiency. The learned pairing is the only part of GARN that goes beyond the task definition, and the paper has little evidence that it helps. On shuffled data at n=1024n = 1024, pooling exact memberships over all pairs gets 96.9%, while GARN gets 79.9%.

Questions for authors

In the current task, the exact tables directly compute the quantity that defines the label. Can the authors show a task where the tables help but do not directly give the answer, for example a label that depends on a multi-step relation, or a real task

Reviewer_Sy8NOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks whether neural models can learn a finite-field relation from few labels. The proposed GARN uses attention to weight token pairs and computes all pairwise ratios exactly with fixed field tables. It scores the ratios with learnable membership masks and writes this evidence back into the token states. It shows superior results on synthetic coset classification compared to soft baselines without exact field arithmetic.

Critical strengths
  1. The benchmark is carefully designed to isolate the effect of the design choices which make the results reliable. Matching single-byte distributions removes frequency shortcuts. The adjacent, shuffled, and density-matched variants separate partner information from aggregate cues. Corrupting the field tables drops GARN to chance.

  2. The method shows superior results on synthetic coset classification compared to soft baselines without exact field arithmetic.

Critical weaknesses
  1. The architecture largely reproduces relation aware attention [1]. Thus a natural baseline is a standard Transformer whose attention scores include a learned bias for each exact ratio, as in T5's relative-position bias. RatioFeatTransformer adds the ratios as extra tokens, so it does not answer this question. Even so, it already nearly matches GARN on adjacent data (96.4% vs. 99.5% at n = 256) and beats it on shuffled data (85.2% vs. 79.9% at n = 1,024). [1] Peter Shaw, Jakob Uszkoreit, Ashish Vaswani. Self-Attention with Relative Position Representations
  2. The evidence does not isolate exact execution as a decisive source of sample efficiency. The baselines without exact field arithmetic also lack any relational inductive bias and get fewer optimizer updates at small training sizes (25 at n = 32 vs. 400 at n = 1,024), so their failure might not be attributed to the missing operator.
Questions for authors
  1. Could you compare GARN with a standard Transformer whose attention scores include the exact ratio as in T5's relative-position bias, optionally with Shaw et al.'s value-side ratio embeddings? This model receives exactly GARN's information through the standard mechanism. It can isolate whether the architecture adds beyond exact relative features.
5 comments

Thank you for the insightful and constructive review, and for recognizing the rigor of our benchmark controls (matched marginals, adjacent/shuffled variants, density checks, and corrupted tables). Below, we directly address your two primary concerns, including new empirical results evaluating relation-aware attention baselines.


1. Response to W1 & Q1: Relation to Relative Position Bias (Shaw et al. / T5) and New Empirical Baselines

Following Reviewer Sy8N’s suggestion, we implemented and evaluated Transformers using exact-ratio attention biases under our standardized benchmark.

Experimental Setup

To ensure a strictly controlled, apple-to-apple comparison:

  • Input Alignment: All models use identical SoftGF input representations, positional encodings, post-norm backbones, and masking of self-pairs (i=ji=j).
  • Protocols: All models share identical data splits and training schedules (AdamW, lr 10−310^{-3}, 25 epochs, gradient clipping 1.0) across 5 seeds. Checkpoints are selected by validation accuracy.
  • No Subgroup Templates: No model receives target subgroup templates or membership labels a priori.
  • Two New Baselines:
    1. RatioBiasTF (T5-style): Adds a learned scalar bias for each exact ratio to attention logits: sij(ℓ,h)=⟨qi,kj⟩dh+brij(ℓ,h)s_{ij}^{(\ell,h)} = \frac{\langle q_i, k_j \rangle}{\sqrt{d_h}} + b_{r_{ij}}^{(\ell,h)} (+2,048+2,048 params across 2 layers).
    2. RatioBiasValueTF (Shaw-style): Extends RatioBiasTF by additionally injecting learned value-side relation embeddings: oi(ℓ,h)=∑j≠iα~ij(ℓ,h)(vj(ℓ,h)+arijV,(ℓ,h))o_i^{(\ell,h)} = \sum_{j\ne i} \widetilde{\alpha}_{ij}^{(\ell,h)} (v_j^{(\ell,h)} + a_{r_{ij}}^{V,(\ell,h)}) (+34,816+34,816 params across 2 layers).

Empirical Results (5 seeds, mean ±\pm std)

ModelSubgroup PriorAdjacent (n=32n=32)Adjacent (n=256n=256)Shuffled (n=1024n=1024)Density-Matched (n=1024n=1024)
Transformer–SoftGF (concurrent control)None50.5±0.850.5 \pm 0.850.3±0.450.3 \pm 0.449.2±0.949.2 \pm 0.948.8±1.148.8 \pm 1.1
RatioBiasTF (T5-style scalar bias)None50.6±0.850.6 \pm 0.850.1±0.850.1 \pm 0.849.7±0.749.7 \pm 0.748.6±1.148.6 \pm 1.1
RatioBiasValueTF (Shaw-style bias + value)None52.7±2.052.7 \pm 2.071.9±5.371.9 \pm 5.385.2±1.8\mathbf{85.2 \pm 1.8}48.8±0.848.8 \pm 0.8
GARN–Free, no fold (Ours, template-free)None61.6±4.7\mathbf{61.6 \pm 4.7}96.4±4.2\mathbf{96.4 \pm 4.2}77.4±1.477.4 \pm 1.450.0±0.550.0 \pm 0.5
GARN (+ templates, reference)Order-1786.7±6.886.7 \pm 6.899.5±0.399.5 \pm 0.379.9±1.479.9 \pm 1.449.9±1.349.9 \pm 1.3

(Note: In the main text, GARN with order-17 templates reaches 99.5% at n=256n=256; the template-free variant is compared here to strictly isolate architectural interfaces without subgroup priors).

Findings & Architectural Takeaways

  1. Scalar Logits Biases (T5-style) Do Not Explain GARN's Gains: RatioBiasTF stays near chance across all settings, matching Transformer–SoftGF. Merely adjusting attention weights via scalar relative biases is insufficient for the network to extract discrete field membership without changing the aggregated value representations.
  2. Value-Side Relation Embeddings Substantially Alter Performance:
    • On Adjacent Data (Low-to-Moderate Budgets): GARN–Free retains a decisive advantage over RatioBiasValueTF (96.4±4.2%96.4 \pm 4.2\% vs. 71.9±5.3%71.9 \pm 5.3\% at n=256n=256). The minimum seed accuracy of GARN–Free (87.9%87.9\%) remains strictly higher than the maximum seed accuracy of RatioBiasValueTF (80.0%80.0\%). This shows that where structured partner interaction is present, GARN’s membership bank filtering and gated state write-back provide stronger inductive efficiency than linear value addition.
    • On Shuffled Data (n=1024n=1024): RatioBiasValueTF outperforms GARN–Free (85.2±1.8%85.2 \pm 1.8\% vs. 77.4±1.4%77.4 \pm 1.4\%). Here, standard attention augmented with value-side ratio embeddings effectively acts as a bag-of-ratios pooler across all pairwise relations, capturing global sequence-level cues.
  3. Density-Matched Control as a Sanity Check: Under the density-matched control, all four models collapse to chance (≈49%−50%\approx 49\% - 50\%). This indicates that the performance of RatioBiasValueTF on unconstrained shuffled data largely exploits aggregate sequence-level edge-density differences (as characterized in Lemma C.3), rather than unique planted-pair reconstruction.

2. Response to W2: Isolating Exact Execution vs. Optimizer Update Counts

The reviewer astutely notes that with fixed 25 epochs, smaller datasets receive fewer optimizer steps (2525 at n=32n=32, 100100 at n=256n=256, vs. 400400 at n=1024n=1024). We clarify why the soft-versus-hard gap reflects sample complexity rather than undertraining:

  • Transformer–SoftGF Stays Near Chance at 400 Updates: As shown in our new table above, at n=1024n=1024 (where all models receive 400 updates), Transformer–SoftGF still achieves only 49.2±0.9%49.2 \pm 0.9\%. If lack of updates was the primary barrier, 400 steps would yield non-trivial progress.
  • Extended Capacity and Training Controls (Appendix E.4): At n=512n=512, scaling Transformers to 6 layers, width 256, with prolonged cosine learning-rate schedules still leaves soft models at 49.9%∼51.8%49.9\% \sim 51.8\% (chance), whereas template-free GARN achieves 99.8±0.1%99.8 \pm 0.1\%.
  • Sample-Complexity Barrier (Appendix E.10): Soft Transformers do eventually solve the task, but require scaling the training budget to n=8192n=8192 (reaching 85.8±11.9%85.8 \pm 11.9\%). Because matched-marginal sampling removes single-byte label information, discovering discrete finite-field multiplication circuits from continuous gradients requires vastly more supervision under scarce data.

Conclusion & Revisions

We sincerely thank you for prompting this comparison. These empirical findings provide a more nuanced understanding of exact-ratio interfaces: scalar relative attention biases are insufficient, value-side relation embeddings are strong all-pair aggregators in permuted sequences, while GARN's gated write-back interface achieves superior sample efficiency when structured interactions must be resolved. We are incorporating these new baselines and the full 5-seed comparison table into Section 5 and Appendix E of the revised manuscript.

Thank you for the new baselines. They address some of my concerns. Could you clarify:

  1. Were the RatioFeatTransformer results obtained with the same splits, inputs, and training schedule as the models in your new table?
  2. Is there a result in the paper or rebuttal where template-free GARN clearly outperforms RatioFeatTransformer? In Table 4, the gaps at n≥512n \ge 512 are below one point, with both models near 100%.
Reviewer_HJAxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The task is to label a sequence of numbers based on ratios between pairs. The authors generate positive examples from ratios in a chosen set and negative examples from ratios outside it. The arithmetic takes place in a finite field, a fixed set of values with its own addition and multiplication rules. GARN uses lookup tables to calculate the ratios exactly. It learns how much weight to give each possible pair and combines the results over several rounds before predicting the class. Models given the arithmetic learn from fewer training examples. Some simpler models given the same arithmetic perform as well as GARN or better.

Critical strengths
  1. The experiments show a clear benefit from giving models exact arithmetic. The authors compare several models using the same data and repeat the experiments with different random seeds.

  2. GARN loses its advantage when the authors replace the correct arithmetic tables with random ones. This helps show that the supplied arithmetic contributes to the results.

Critical weaknesses
  1. Some simpler models given the same arithmetic perform as well as GARN or better. I am still unclear about what GARN's extra complexity adds. I would like the authors to show when it offers a clear advantage over these models.

  2. The authors highlight a result with 256 training examples, but they also use 1000 labelled examples to choose the final model. I would like the claim about needing few examples to account for both sets. I also want to know whether the other models improve if they train for longer.

Questions for authors
  1. When does GARN perform better than simpler models given the same arithmetic?

  2. Do the results still hold with fewer labelled examples used to choose the final model? Do the comparison models improve with longer training?

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

Dear Area Chair JSYV and Reviewers (Sy8N, HJAx, and 7b7S),

We sincerely thank the Area Chair for facilitating the discussion and the reviewers for their engagement. During the rebuttal period, we ran 80 new controlled experiments (5 seeds each) to evaluate relation-aware attention baselines and clarify our architectural boundaries. Below, we summarize our new findings and planned updates for the final version.


1. New Controlled Experiments: Relation-Aware Attention

Following Reviewer Sy8N’s suggestion, we evaluated Transformers with T5-style scalar ratio biases (RatioBiasTF) and Shaw-style value-side ratio embeddings (RatioBiasValueTF) under strictly aligned SoftGF inputs, self-pair masking, data splits, and training schedules (25 epochs, AdamW, no templates):

ModelSubgroup PriorAdjacent (n=32n=32)Adjacent (n=256n=256)Shuffled (n=1024n=1024)Density-Matched (n=1024n=1024)
Transformer–SoftGF (concurrent control)None50.5±0.850.5 \pm 0.850.3±0.450.3 \pm 0.449.2±0.949.2 \pm 0.948.8±1.148.8 \pm 1.1
RatioBiasTF (T5-style scalar bias)None50.6±0.850.6 \pm 0.850.1±0.850.1 \pm 0.849.7±0.749.7 \pm 0.748.6±1.148.6 \pm 1.1
RatioBiasValueTF (Shaw-style bias + value)None52.7±2.052.7 \pm 2.071.9±5.371.9 \pm 5.385.2±1.8\mathbf{85.2 \pm 1.8}48.8±0.848.8 \pm 0.8
GARN–Free, no fold (Ours, template-free)None61.6±4.7\mathbf{61.6 \pm 4.7}96.4±4.2\mathbf{96.4 \pm 4.2}77.4±1.477.4 \pm 1.450.0±0.550.0 \pm 0.5
GARN (+ templates, reference)Order-1786.7±6.886.7 \pm 6.899.5±0.399.5 \pm 0.379.9±1.479.9 \pm 1.449.9±1.349.9 \pm 1.3

Key Takeaways:

  1. Scalar Logits Biases Fail: RatioBiasTF stays near chance (≈50%\approx 50\%), showing that scalar attention reweighting alone cannot extract discrete field membership without modifying value representations.
  2. Value Embeddings vs. Gated Write-Back: RatioBiasValueTF excels at sequence-level pooling on unconstrained shuffled data (85.2%85.2\%), whereas GARN–Free retains a strong advantage on structured adjacent data (96.4±4.2%96.4 \pm 4.2\% vs. 71.9±5.3%71.9 \pm 5.3\% at n=256n=256).
  3. Density-Matched Sanity Check: All models drop to chance (≈49%–50%\approx 49\%\text{--}50\%) under density matching, confirming that unconstrained shuffled accuracy relies on aggregate edge-density cues (Lemma C.3).

2. Resolution of Key Reviewer Concerns & Scope

  • Scope vs. RatioFeatTransformer (Reviewer Sy8N): Template-free GARN and RatioFeatTransformer achieve comparable accuracy on adjacent data for n≥256n \ge 256 (97.1%97.1\% vs. 96.4%96.4\% at n=256n=256; 100.0%100.0\% vs. 99.8%99.8\% at n=1024n=1024), while RatioFeatTransformer leads on unconstrained shuffled data (85.2%85.2\% vs. 77.4%–79.9%77.4\%\text{--}79.9\%). GARN’s distinct properties are: (i) maintaining a fixed length-88 sequence without expanding O(L2)O(L^2) ratios into 6464 tokens, (ii) outperforming length-88 ratio-biased attention (RatioBiasTF / RatioBiasValueTF) on adjacent tasks, and (iii) exposing explicit [0,1]256[0,1]^{256} masks for optional subgroup template injection (86.7%86.7\% at n=32n=32).
  • Gain Over Fixed Probes & Sample Complexity (Reviewer HJAx): Without templates (Free masks, Table 3), GARN outperforms fixed HardProbe by +34.5%+34.5\% on adjacent data (97.1%97.1\% vs. 62.6%62.6\%) and +12.9%+12.9\% on shuffled data (79.9%79.9\% vs. 67.0%67.0\%, Table 2). Extended capacity/schedule controls (Appendix E.4) and scaling curves (Appendix E.10, requiring n=8192n=8192 for soft Transformers) confirm a genuine sample-complexity barrier rather than undertraining.
  • Diagnostic Framing & Shortcut Controls (Reviewer 7b7S): We thank Reviewer 7b7S for accepting our diagnostic framing and raising their score. Matched-marginal sampling, density controls (Table 5), corrupted tables (Table 6), and mixed-fraction tasks (Appendix E.10) systematically isolate algebraic execution from statistical shortcuts.

3. Planned Updates for the Final Version

As no revised PDF was uploaded during the discussion period, we commit to incorporating the following into the camera-ready version if accepted:

  1. New Section 5 Subsection: Adding Transformer–SoftGF, RatioBiasTF, and RatioBiasValueTF alongside GARN–Free (5-seed table and full hyperparameters).
  2. Explicit Scope & Budget Clarity: Stating the exact comparison among fixed-length GARN, ratio-biased attention, and 6464-token RatioFeatTransformer, and clearly reporting both training (n) and validation (1000) sample counts.
  3. Surfacing Appendix Controls: Highlighting extended training controls (Appendix E.4), n=8192n=8192 scaling (Appendix E.10), and mixed-fraction tasks in the main text.

Thank you again for your time, feedback, and fair evaluation.

Best regards,
The Authors of Submission 40143

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.