What Accuracy Hides In Learned Transformer Programs

Jonathan Lee; Narmeen Oozeer; Philip Quirke

cs.LGOct 16, 2026

What Accuracy Hides In Learned Transformer Programs

Authors: Jonathan Lee, Narmeen Oozeer, Philip Quirke

Organizations: Martian

Abstract

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.

Figures & tables

Figure 1: We consider three distinct abilities: architectural expressivity, learning during training, and algorithmic verification.

Figure 2: By design Transformer Program models progressively restrict representations, attention and MLPs over training to finally learn discrete computations that enable code extraction.

Task	Token accuracy (%)	Sequence accuracy (%)
Histogram	100.00	100.00
Sorting	100.00	100.00
Reversal	99.96	99.79
Dyck 1	99.89	98.60
Dyck 2	99.35	95.75
Double histogram	98.41	97.45

Table 1: Token and sequence accuracy for the selected best grid baselines, not averages across seeds. See Appendices A.1 and A.2 for selection details and results across seeds.

Figure 3: The program counts seven correctly but cannot output seven because that answer label is absent from its classifier.

Figure 4: Histogram counterexamples guide training data enrichment and full model retraining. All five retrained hard neural models answer every input correctly across the 335,922 inputs of one to seven values drawn from six symbols.

Task	Token (%)	Seq. (%)	Counterexample found?	Checked domain or first failure
Histogram	100.00	100.00	No	Exhaustive through $N\leq 8$
Sorting	100.00	100.00	No	Exhaustive through $N\leq 8$
Reversal	99.96	99.79	Yes	First failure at $N=5$
Dyck 1	99.89	98.60	Yes	Failure at trained length $N=16$
Dyck 2	99.54	96.50	Yes	Failure at trained length $N=16$
Double histogram	100.00	100.00	No	Checked through $N\leq 8$

Table 4: Selected training results and verification outcomes.

N

includes special tokens. Clean verdicts apply only to the stated domains.

Figure 5: Double histogram during annealing toward discrete TP choices. Four of five seeds lose accuracy from soft peaks above 99.89%. Faint and solid curves show recorded and median filtered soft scores; the dashed blue curve shows temperature. Right labels give final program scores; only one retains 100%.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Required answer
Histogram	At each position, the number of occurrences of its input value.
Double histogram	At each position, the number of distinct values with the same frequency as its input value.
Sorting	All input values in ascending order, preserving multiplicities.
Reversal	All input values in reverse order.
Frequency ranking	Each distinct value once, in decreasing frequency order. Equal frequencies are ordered by first occurrence.
Dyck 1	At each prefix over one bracket type: balanced ( T ), valid but incomplete ( P ), or invalid ( F ). Invalidity persists through later prefixes.

Appendix

Table A1: Task specifications. Examples and definitions omit boundary tokens. The bracket tasks require a label for every prefix, not just a decision about the complete input.

Tasks	Ordinary input and boundaries	Total length
Sorting, reversal	Values 0 through 4; $1\leq m\leq 6$ ; BOS and EOS	$N=m+2$ , 3 to 8
Histogram, double histogram, frequency ranking	Values 0 through 5; $1\leq m\leq 7$ ; BOS	$N=m+1$ , 2 to 8
Dyck 1, Dyck 2	Fifteen brackets of one or two types; BOS	$N=16$
Addition	Digits 0 through 9, + , BOS; $d_{a},d_{b}\in\{1,2\}$	$N=d_{a}+d_{b}+2$
Addition with hints	Same operands and delimiters; one letter before each digit	$N=2(d_{a}+d_{b})+2$

Appendix

Table A2: Standard input supports. Here

m

counts ordinary values or brackets, and

d_{a},d_{b}

count operand digits. BOS and EOS denote beginning and end tokens.

Role	$L/H/M$	Seed
Highlighted histogram program	4/2/2	27983
Histogram repair baseline and retrained example	4/2/2	13877
Initial sorting program	3/16/4	27983
Selected sorting model after coverage enrichment	3/16/4	51229
Baseline frequency program	4/16/8	47389
Enriched frequency program	4/16/8	56543

Appendix

Table A3: Models and programs used in the main computational examples and repair checks. The histogram model with 42 exhaustive failures is not the highlighted program from Section 4.1 .

Task	Grid best	13877	27983	47389	51229	56543
Dyck 1	98.60	97.55	97.20	90.15	96.05	94.95
Dyck 2	95.75	81.90	91.70	86.50	84.40	96.50

Appendix

Table A4: Sequence accuracy in percent for greater bracket depth. The grid column is the selected best result, not a seed mean. The five remaining columns are individual six layer runs.

Addition, $L/H/M=3/16/8$
Recipe	13877	27983	47389	51229	56543	Mean
Carry balanced comparator	90.23	92.76	89.48	94.22	91.36	91.61
Position coupling	89.46	91.66	91.75	91.57	89.91	90.87
Entropy and longer training	91.79	96.98	93.32	92.71	90.34	93.03
Frequency ranking, $L/H/M=4/16/2$ , 250 epochs
Natural, request 20,000	80.90	81.78	82.40	81.84	81.97	81.78

Appendix

Table A5: Final token accuracy by seed, in percent, for the training comparisons discussed in Section 5.1 . Each task group has its own configuration and comparator. Dataset requests do not necessarily equal unique training set sizes.

Recipe	$L/H/M$	Seed	Epochs	Sequence result
Addition length sampling	4/16/2	47389	250	2.73 to 58.48
Hints length sampling	4/16/8	56543	250	39.66 to 65.20
Final addition	4/24/8	47389	150	76.30
Final hints	4/24/8	51229	500	84.22

Appendix

Table A6: Settings for the addition data recipes. All use dimension 16 and request 50,000 examples. Sequence scores are percentages. The length comparison and selected final recipe are different experiments.

Condition	13877	27983	47389	51229	56543	Mean
Histogram enrichment 0.45	0	0	0	0	0	0.0
Sorting natural baseline	13	9	4	9	20	11.0
Sorting high count 0.45	76	47	33	34	49	47.8
Sorting high count 0.15	262	85	62	31	67	101.4
Sorting high count 0.30	579	128	397	29	16	229.8
Sorting failure cases 0.30	13	15	51	22	67	33.6

Appendix

Table A7: Exhaustive hard neural failure counts across seeds. Histogram uses 335,922 inputs and sorting uses 19,530. Every sorting condition is checked on the same domain, even when its sampled test distribution differs.

Task	$L/H/M$	Seed	Result
Initial histogram	4/2/2	27983	Python failure at $N=8$ .
Initial sorting	3/16/4	27983	Python failure at $N=8$ .
Reversal	4/16/4	13877	Python failures at $N=5,6$ .
Dyck 1	4/16/8	47389	Replayed failure at trained length $N=16$ .
Dyck 2 grid	2/16/8	27983	Replayed failure at $N=16$ .
Dyck 2 depth recipe	6/16/8	56543	Model test failure at $N=16$ ; solver time limit reached.

Appendix

Table A8: Selected checks. All lengths include special tokens as defined in Table A2 . A failure establishes an incorrect answer for the specified artifact. No failure reported refers only to the stated checking method and domain.

Task	$N$	Ordinary input	Program answer	Required answer
Sorting	8	$[3,3,3,3,3,3]$	$[1,3,3,3,3,3]$	$[3,3,3,3,3,3]$
Reversal	5	$[3,1,3]$	$[3,3,3]$	$[3,1,3]$
Addition	6	$19+22$	$31$	$41$
Addition with hints	8	$9+99$	$107$	$108$

Appendix

Table A9: Further failing inputs for the initial sorting, reversal and final addition artifacts in Table A8 . Boundary tokens are omitted. The hints row omits letters to show the wrong arithmetic answer.

Contribution	Answer 6	Answer 7
Other contributions combined	$-57.205$	$-117.785$
First count, value 7	8.769	$-7.019$
Sum of counts, value 49	102.845	192.605
Total	54.409	67.800

Appendix

Table A10: Classifier contributions for the retrained histogram at the first ordinary position. The input is seven copies of 4. Values are rounded to three decimals after computing the totals.

Answer class	Baseline total	Enriched total
0	$-5.15765$	6.73346
1	10.88742	13.77100
2	3.82967	$-11.90848$
3	7.30950	9.03644
4	14.35276	13.76628
5	$-8.65461$	$-21.47170$

Appendix

Table A11: All classifier totals at the second output position of the frequency example. The main tables separate a selected count contribution from the remaining scores; this table checks the winner against all classes. BOS is not an output class in the enriched program.

Task	Layers	$H_{c}$	$H_{n}$	Computation
Histogram	1	0	1	Equality count and count label lookup
Reversal	2	1	0	Locate end, compute mirror position, copy token
Sorting	3	0	$V$	Value counts, cumulative counts and lookup decoding
Dyck 1	6	1	2	Causal balance and bracket matching
Dyck 2	6	1	4	Same construction with two bracket types
Addition	$n+2$	1	0	Carry propagation with fixed width output

Appendix

Table A12: Sufficient structural costs of the implemented reference programs.

H_{c}

and

H_{n}

are categorical and numerical heads per layer.

V

is the ordinary value vocabulary size and

n

is the operand digit width. These are construction costs, not minima.

Study	Runs	Hardware	Time
Baseline grid	2,160	GPU workers	About 260 to 415 GPU hours
Histogram and sorting repair	35	T4, five workers	About 3 to 8 GPU hours
Enriched frequency and double histogram	10	Shared GPU VM	11.19 hours
Addition length sampling	10	A100 40 GB	About 2.5 hours
Addition and hints, 150 epochs	10	A100, ten workers	About 45 minutes
Bracket models with six layers	10	A100 40 GB	About 2.8 hours

Appendix

Table A13: Training runs and approximate compute. The first two rows are extrapolated GPU hours under the assumptions below; remaining entries are elapsed execution windows. The estimated ranges describe alternative scenarios, not measured bounds or confidence intervals.

Transformer Interpretability

Transformer interpretability studies how attention, feed-forward layers, and hidden representations support model predictions and behavior.

See all 339 papers

Training Transformers as a Universal Computer
Apr 28, 2026Ruize Xu, Chenxiao Yang, Yanhong Li +1Transformer Algorithmic Reasoning
The University of Chicago · Toyota Technological Institute at Chicago · Allen Institute for AI
Transformers for Program Termination
Mar 25, 2026Yoav Alon, Cristina DavidStatic Code Analysis Transformer
University of Bristol UK
Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?
Sep 27, 2026Jiashu He, Jinxuan Fan, Xiao Xiao +2LLM Reasoning
University of Pennsylvania · University of Texas at Austin · Yale University

Apr 28, 2026J/K move · Enter open · S save

Training Transformers as a Universal Computer

Ruize Xu, Chenxiao Yang, Yanhong Li, David McAllester

The University of Chicago · Toyota Technological Institute at Chicago · Allen Institute for AI

Transformer Algorithmic Reasoning

Open paper AskPDF arXiv

We demonstrate that a small transformer can learn to execute programs in MicroPy, a simplified yet computationally universal programming language. Given procedure definitions together with an expression to evaluate, the transformer predicts small-step execution using PENCIL scaffolding for space-efficient execution within a bounded context window. After training on randomly generated, meaningless MicroPy programs, the learned transformer generalizes to various human-written programs including bit copying and flipping, binary addition and multiplication, and SAT verification and solving. We note that the trained model can achieve out-of-distribution generalization; i.e., evaluate novel programs from distribution on programs. Since MicroPy can express any computation, our results provide empirical evidence that a standard transformer can be trained to act as a universal computer.

Abstract

Transformer Interpretability

Explore similar work

Training Transformers as a Universal Computer

Transformers for Program Termination

Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?