PaperlayerView exact revision on arXiv

Source-linked AI summary

What Accuracy Hides In Learned Transformer Programs

Jonathan Lee, Narmeen Oozeer, Philip Quirke

arXiv:2610.22891v1cs.LG

TL;DR

Token and sampled-sequence accuracy can miss incorrect complete answers from learned Transformer Programs. This paper evaluates nine algorithmic tasks using accuracy measures, program inspection, and verification, then uses diagnosed failures to inform training-data changes. Those changes improve sequence accuracy on several tasks, and histogram retrains pass exhaustive checks within the bounded domain.

  • Problem

    Token accuracy and even perfect sampled sequence accuracy can miss incorrect complete answers, leaving failures within the training domain undetected.

    Source: §1 · p. 2

  • Method

    The paper evaluates nine tasks with token and sequence accuracy, verifies bounded domains, inspects failing programs, and uses diagnoses to guide training-data changes.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    Training-data changes informed by program inspection and counterexamples improved sequence accuracy on several tasks, and histogram retrains passed exhaustive evaluation within the checked bounded domain.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    Inspecting computations alongside accuracy and counterexamples can explain failures and inform training-data changes within the evaluated tasks and checked domains.

    Source: §1 · p. 2, §7 · p. 9

    Verification is restricted to stated input ranges: for double histogram, length-seven checks took around 100 minutes, while length-eight solving did not finish within eight hours.

    Source: §6.3 · p. 9

Abstract

from arXiv · show

Transformer Programs (TP) (Friedman et al., 2023) constrain a Transformer's architecture so that its learned computation can be extracted as readable Python code. TP expose learned computations, but token accuracy can hide incorrect complete answers. In this work, we examine how program inspection provides insights beyond accuracy scores and helps guide training. We first evaluated TP on nine algorithmic tasks. We compared token accuracy with accuracy on complete output sequences and checked for failures missed by sampled tests. Further, we assessed training data improvements informed by program inspection and failure analysis, finding gains in sequence accuracy on several tasks. We examined a counting task where a program achieved 100% accuracy on sampled test sequences but failed on another input using the symbols and lengths allowed during training. The program counted correctly, but the required answer was missing from its output labels. After adding training examples with larger counts, the retrained models passed exhaustive evaluation over the bounded domain. In the frequency ranking task, inspection showed how correct counts contributed to incorrect answers in programs trained before and after changes to the training data. Finally, we studied constraints imposed by TP training and operations. The TP training process can lead to accuracy losses late in training. Our reference constructions also show how composing the restricted TP operations can use many layers or large lookup tables.

1 INTRODUCTION

Transformer Programs make learned computations inspectable as executable Python, allowing researchers to trace mistakes and check correctness over defined input domains. The evaluation shows why accuracy scores alone are insufficient and how failures can guide training changes.

1 INTRODUCTION

  • TP constrain Transformer architecture so learned computations can be extracted as readable, executable Python and compared with required answers.This provides interpretability by construction and supports checking correctness over a defined input domain.Source: §1 · p. 1
  • Correctness requires expressivity, trainability, and verifiability, but TP training can lose accuracy as soft choices become discrete and verification is limited to small domains.Reference constructions may use many layers or large lookup tables, and are not claimed to be minimal.Source: §1 · pp. 1–2
  • A histogram program scored 100% sequence accuracy on sampled tests but returned six for seven copies of 4 because seven was absent from its answer labels.The program counted correctly, but the required answer was not among its available output labels.Source: §1 · p. 2
  • Program inspection and verification expose failures hidden by token accuracy or sampled tests, while tracing computations helps explain why answers are wrong.The paper combines complete-sequence evaluation with formal counterexample search and program execution to confirm errors.Source: §1 · p. 2
  • Adding larger-count examples produced histogram models that answered every input correctly within the exhaustively checked bounded domain.Training-data changes also improved sequence accuracy for addition and addition with hints; frequency-ranking inspection explained errors before and after enrichment.Source: §1 · p. 2

2 BACKGROUND

Transformer Programs restrict representations and operations to make learned computations extractable as code. The section defines the tasks studied and uses hand-written reference programs to examine expressivity without claiming that training will find them.

2.1 ARCHITECTURE

  • TP restrict representations, attention, and MLP operations so their learned computations can be inspected as executable Python.Categorical attention selects and copies values, numerical attention adds matched values, and MLPs act like lookup tables.Source: §2.1 · p. 2
  • Training sharpens continuous choices into discrete ones, but the soft model, hard neural model, and extracted program may give different answers.The model is optimized with gradient descent during the continuous relaxation; extraction converts the discrete computation into Python.Source: §2.1 · pp. 2–3

2.2 TASKS AND REFERENCE PROGRAMS

  • The experiments cover nine algorithmic tasks, with detailed program analysis focused on histogram and frequency ranking.Histogram outputs each value's occurrence count at every position; frequency ranking lists distinct values by decreasing count, breaking ties by input order.Source: §2.2 · p. 3
  • Hand-written reference programs show that a solution exists for a specified input range, but do not establish that training can find it or that it is minimal.The constructions are used to examine what the architecture can express.Source: §2.2 · p. 3

3 BETTER BENCHMARKING OF TP

The benchmarking protocol combines token and complete-sequence accuracy with verification and inspection of counterexamples. Baseline results show a gap between sampled scores and correctness over a domain, including a histogram failure missed by the sample.

3.1 EVALUATION PROTOCOL

  • 75% to 92% token accuracy contrasted with 3% to 40% sequence accuracy for frequency ranking, addition, and addition with hints.Sequence accuracy counts examples only when every scored position is correct; scoring masks determine which positions count.Source: §3.1 · p. 3
  • 90.50% sequence accuracy for an intermediate soft addition checkpoint fell to 14.16% exact match on answer digits in the extracted program.The final checkpoint of an annealed run is the evaluation standard because discretization does not guarantee preserved accuracy.Source: §3.1 · pp. 3–4
  • Verification searches for errors within specified alphabet and length bounds, confirms counterexamples by executing extracted code, and establishes correctness only over the checked domain.Alternatively, the program can be run on every input in the domain and its outputs checked against the task specification.Source: §3.1 · p. 4

3.2 BASELINE RESULTS

  • 32.0% to 97.5% was the baseline double-histogram sequence-accuracy range across seeds.Table 1 reports token and sequence accuracy for selected best grid baselines, not averages across seeds.Source: §3.2 · p. 4, Table 1 · p. 4

3.3 INITIAL AUDIT

  • A histogram program got every sampled test answer right, yet returned six instead of seven for an in-domain input of seven copies of 4.The failure motivates examining learned computations and possible training changes.Source: §3.3 · p. 4

4 UNDERSTANDING THE LEARNED PROGRAMS

Program inspection explains failures in histogram and frequency ranking beyond the answers they produce. Histogram counts seven correctly but lacks the output label, while frequency ranking can use a correct count in a way that favors the wrong answer.

4 UNDERSTANDING THE LEARNED PROGRAMS

  • The case studies trace learned-program computations to explain failures, rather than relying only on the answers produced.Source: §4 · p. 4

4.1 HISTOGRAM BEFORE ENRICHMENT

  • The histogram program counts seven correctly but returns six because seven is absent from its classifier’s available labels.The training data contained no examples requiring seven; adding them would make the label available.Source: §4.1 · p. 5, Figure 3 · p. 5

4.2 FREQUENCY RANKING BEFORE ENRICHMENT

  • In frequency ranking, the baseline repeats 4 because its correct count contribution reverses the score order and makes 4 the highest-scoring answer again.For [1, 3, 4, 3, 4, 4, 4], the required answer is [4, 3, 1], but the baseline returns [4, 4, 1].Source: §4.2 · pp. 5–6, Table 2 · p. 6

5 IMPROVING PERFORMANCE

Training changes targeted failures identified through counterexamples and program analysis, with the clearest exhaustive result on histogram. Final results show sequence-accuracy gains on addition tasks, alongside remaining errors and uneven training outcomes.

5.1 IMPROVING TRAINING

  • Training changes targeted larger histogram counts and frequency-ranking ties, but the frequency comparison also changed data volume, model size, and test-set ties.Those simultaneous changes mean the effect of adding tie examples alone was not isolated.Source: §5.1 · p. 6

5.2.1 HISTOGRAM

  • All five retrained hard neural histogram models answered all 335,922 inputs correctly for sequences of one to seven values drawn from six symbols.The training data was enriched with larger counts, including six and seven, which had been associated with baseline failures.Source: §5.1 · p. 6, §5.2.1 · p. 7, Figure 4 · p. 7

5.2.2 FREQUENCY RANKING

  • The enriched frequency-ranking program still returns a wrong answer because a correct count contribution reverses the score order at the second position.For answer 3, the weight subtracts 8.129 from its score; for answer 1, it adds 2.142.Source: §5.2.2 · p. 7, Table 3 · p. 7

5.3 FINAL RESULTS

  • Addition improved sequence accuracy from 2.73% to 58.48%, and addition with hints from 39.66% to 65.20%; selected final recipes reached 76.30% and 84.22%, respectively.Verification still found incorrect answers; double histogram’s selected program reached 100% sequence accuracy, but results ranged from 32.0% to 100.0% across five seeds.Source: §5.3 · pp. 7–8, Table 4 · p. 8

6 CONSTRAINTS AND LIMITATIONS

The section examines how training toward discrete choices and restricted operations constrain learned TP programs, and where correctness evidence and program explanations are limited. It reports accuracy losses during discretization, costly reference constructions, bounded verification, and input-specific frequency analyses.

6.1 TRAINING TOWARD DISCRETE CHOICES

  • 14.16% exact match on answer digits followed a 90.50% soft-model sequence accuracy checkpoint; continued training also ended 34.38 percentage points below its soft peak.The five enriched histogram seeds had soft sequence accuracies above 99.89%, but four lost accuracy and only one retained 100% in its final program.Source: §6.1 · pp. 8–9, Figure 5 · p. 8

6.2 COSTS OF REFERENCE CONSTRUCTIONS

  • Reference constructions can require n + 2 layers for addition carries or a frequency-ranking lookup table whose size grows roughly as N V.These constructions solve the tasks but are not claimed to be the most efficient methods.Source: §6.2 · p. 9

6.3 SCOPE OF THE EVIDENCE

  • Solver verification of double histogram took around 100 minutes at total length seven and did not finish within eight hours at length eight.The authors therefore executed the learned program on every length-eight input; positive correctness results remain limited to checked input ranges.Source: §6.3 · p. 9
  • Frequency-program analyses explain particular erroneous answers, but do not recover the full ranking algorithms.Both programs exceed 2,000 lines and have 96 learned attention and MLP components each; the findings concern this architecture and small algorithmic tasks.Source: §6.3 · p. 9

7 CONCLUSION

The conclusion reports that complete-answer evaluation and program analysis revealed failures missed by token scores and sampled tests. Inspection and verification informed training-data changes that improved sequence accuracy on several tasks, while correctness claims remain bounded by checked domains and analyses do not recover full ranking algorithms.

7 CONCLUSION

  • Changes to training data informed by program inspection and verification counterexamples improved sequence accuracy on several tasks.For histogram, adding examples with larger counts yielded correct answers for every input in the bounded domain checked exhaustively.Source: §7 · p. 9
  • Complete-answer checks and counterexamples exposed failures that high token scores and sampled sequence accuracy could miss.Program analysis traced particular frequency-ranking errors but did not recover the full ranking algorithms.Source: §7 · p. 9
  • Correctness evidence is limited to checked domains, while training toward discrete choices can reduce accuracy and reference constructions can require many layers or large lookup tables.Training results also differed across seeds.Source: §7 · p. 9

A.1 EXPERIMENTAL SETUP

The experimental setup covers nine algorithmic tasks, with task answers specified independently of training labels. The appendix defines the task specifications and gives examples for double histogram and frequency ranking.

A.1 EXPERIMENTAL SETUP

  • The first seven tasks come from the Transformer Programs benchmark, and the reproduction study adds addition and addition with hints.Each task assigns an output to every input position, though some positions are padding or filler rather than part of the answer.Source: §A.1 · p. 11
  • Required answers are defined independently of training labels, so histogram may require a count of seven even when sampled training labels stop at six.The task-specification table notes that bracket tasks require labels for every prefix.Source: §A.1 · p. 11, Table A1 · p. 11
  • Double histogram returns, at each position, how many distinct input values occur as often as that position’s value; frequency ranking orders distinct values by decreasing frequency, breaking ties by first occurrence.For example, [5, 4, 5, 4, 1] requires [5, 4, 1] for frequency ranking.Source: §A.1 · p. 11

A.1.1 INPUT DOMAINS AND SCORING

The appendix specifies the input supports and scoring conventions used in evaluation. It also documents corrections to the inherited addition generator and differences between historical and task-specific scoring.

A.1.1 INPUT DOMAINS AND SCORING

  • N is the input length before batch padding, including boundary tokens, delimiters, and hint letters; standard input supports are listed in Table A2.Appendix A.3 states the domains checked for correctness.Source: §A.1.1 · p. 11, Table A2 · p. 11
  • The corrected addition generator emits separate answer-digit tokens and allows one- or two-digit operands, unlike the inherited generator’s two identified restrictions.The balanced generator samples one-digit numbers from 0–9 and two-digit numbers from 10–99 without leading zeros.Source: §A.1.1 · p. 12
  • Token accuracy scores correct target positions, whereas sequence accuracy credits an example only when every scored position is correct.Token accuracy weights longer scored answers more, while sequence accuracy assigns one decision per example; boundaries and batch padding are excluded.Source: §A.1.1 · p. 12
  • The historical neural scorer includes <s> filler in Frequency Ranking and Addition, but the Python addition scorer excludes both filler and padding.For frequency-program examples, only required ranks at positions one through |U(x)| are considered.Source: §A.1.1 · p. 12

A.1.2 TRAINING DEFAULTS AND MODEL SELECTION

The baseline training grid spans multiple architectures and seeds, with fixed defaults for optimization, annealing, and evaluation. Reported data counts and selected results require care because requested examples may be duplicated and selected results are not always averages.

A.1.2 TRAINING DEFAULTS AND MODEL SELECTION

  • The baseline grid trained 2,160 models across 48 configurations per task, five seeds, and nine tasks.Configurations varied from one to four layers, two to 16 heads, and two to eight MLPs per layer.Source: §A.1.2 · p. 12
  • Training used Adam at learning rate 0.05, batch size 512, no dropout, 250 epochs, and temperature annealing from 3.0 to 0.01.Soft discrete-choice relaxations were used during training; final hard neural evaluation selected alternatives by argmax.Source: §A.1.2 · p. 12
  • Requested example counts can exceed the unique examples used, and equal epoch counts do not imply equal update counts.For natural frequency data, requests of 20,000 and 50,000 yielded 16,200 and 40,500 training examples, respectively.Source: §A.1.2 · p. 12
  • Reported results may show selected grid, intermediate, or intervention models rather than averages across seeds or configurations.Soft models, hard neural models, and extracted Python programs are distinguished rather than treated as interchangeable.Source: §A.1.2 · p. 12

A.2 TRAINING INTERVENTIONS

The appendix reports training interventions, exhaustive repair checks, program traces, reference constructions, and computational-resource estimates. Outcomes are specific to the selected artifacts and bounded domains, and several comparisons combine multiple recipe changes.

A.2.1 CAPACITY AND TRAINING PROCEDURES

  • Six-layer bracket models did not solve either task, while tested addition recipes showed no consistent improvement over their comparators.Position coupling did not improve mean token accuracy; entropy regularization helped two weaker seeds but hurt the strongest, and its recipe also requested more data. Both other tested recipes performed below their baselines.Source: §A.2.1 · p. 13, Table A4 · p. 13

A.2.2 CHANGING THE TRAINING EXAMPLES

  • Training-example changes targeted longer operands, high histogram counts, frequent ties, and a broader count distribution, but several comparisons changed multiple recipe components.The histogram recipe introduced count-seven labels; frequency enrichment also changed request size, dimension, and input-length range, while double-histogram training and testing used the modified distribution.Source: §A.2.2 · pp. 13–14, Table A6 · p. 14, Table A5 · p. 14

A.2.3 REPAIR ACROSS SEEDS

  • After histogram enrichment, all five seeds had zero failures across 335,922 legal inputs, while the baseline failed on all six inputs with maximum count seven.The baseline also failed on 36/216 inputs with maximum count six; label six was already available, so adding label seven alone cannot explain all repairs.Source: §A.2.3 · p. 15
  • Sorting repairs were inconsistent: the initial high-count recipe fixed all five identical length-six inputs but increased overall failures, and later mixtures did not establish reliable repair.At mixture fraction 0.30, one seed was clean while the mean failure count was 15 versus 11 for natural training; the success was selected from about 30 exploratory runs.Source: §A.2.3 · p. 15

A.2.4 VARIATION DURING ANNEALING

  • The enriched double-histogram recipe’s final sequence scores ranged from 32.01% to 100.00%, while an addition run’s 90.50% soft peak later ended at 56.12%.The addition program’s 14.16% Python answer score came from an epoch-71 checkpoint and 5,000 examples, not the final model or the decline during later training.Source: §A.2.4 · p. 15

A.3.1 PROPERTIES AND CHECKING PROCEDURE

  • Verification combines encoded task properties with replay of solver witnesses, and finite checks establish correctness only for the stated program and domain.A witness is confirmed only when Python replay produces a wrong required output; an unsat result depends on the encoding matching the program’s behavior.Source: §A.3.1 · p. 16

A.3.2 SELECTED CHECKS AND FURTHER FAILURES

  • The audit’s clean repair outcomes concern retrained hard neural models, while the initial histogram and sorting grid selections had counterexamples.Further cases include sorting that changes an input value, reversal that changes a palindrome’s middle value, and bracket-prefix errors; the examples are representative, not claimed shortest failures.Source: §A.3.2 · pp. 16–17

A.3.3 DOMAINS AND VERIFICATION COST; A.4.3 REFERENCE CONSTRUCTION COSTS; A.5 COMPUTATIONAL RESOURCES

  • Double-histogram solver checks reached total length seven in 5,923 seconds, but its length-eight solver attempt exceeded eight hours and was replaced by enumeration.Enumeration found no counterexamples among 279,936 inputs, but covered seven ordinary values rather than the enriched support’s maximum of eight. Reference constructions also require growing resources, including roughly N V frequency-table growth; compute estimates are assumption-dependent and complete project records are unavailable.Source: §A.3.3 · p. 17, §A.4.3 · p. 19, §A.5 · pp. 19–20
Loading 2610.22891v1…