Is In-Context Learning Learning?
Authors: Adrian de Wynter
Venue: ICLR 2026 Poster (2026)
Keywords: LLMs
in-context learning
Primary area: foundation or frontier models, including LLMs
TL;DR: A large-scale evaluation to empirically characterise in-context learning as a learning paradigm, ablating out common drawbacks of LLM evaluation, and finding results contradicting or aligning with conventional wisdom

Abstract: In-context learning (ICL) allows some autoregressive models to solve tasks via next-token prediction and without needing further training.  This has led to claims about these model's ability to solve (learn) unseen tasks with only a few shots (exemplars) in the prompt. However, deduction does not always imply learning, as ICL does not explicitly encode a given observation. Instead, the models rely on their prior knowledge and the exemplars given, if any. We argue that, mathematically, ICL fits the definition of learning; however, its full characterisation requires empirical work. We then carry out a large-scale analysis of ICL ablating out or accounting for memorisation, pretraining, distributional shifts, and prompting style and phrasing. We find that, empirically, ICL is limited in its ability to learn and generalise to unseen tasks. Namely, in the limit where exemplars become more numerous, accuracy is insensitive to exemplar distribution, model, prompt style, and the input's linguistic features. Instead, it deduces patterns from regularities in the prompt, which leads to distributional sensitivity, especially in prompting styles such as chain-of-thought. Given the varied accuracies and on formally similar tasks, we conclude that autoregression's _ad-hoc_ encoding is not a robust mechanism for learning, and suggests limited all-purpose generalisability.

Published as a conference paper at ICLR 2026
Is IN-CONTEXT LEARNING LEARNING?
Adrian de Wynter
Microsoft and the University of York
adewynter@microoofe
ABSTRACT
In-context learning (ICL.) allows some autoregressive models to solve tasks via next-token prediction and without needing further training. This has led to claims about these model's ability to solve (learn) unseen tasks with only few shots (exemplars) in the prompt. However, deduction does not always imply learning, ICL does not explicitly encode given observation. Instead, the models rely on their prior knowledge and the exemplars given, if any, We argue that, math- ematically, ICL fits the definition of learning; however, its full characterisation requires empirical work. We then carry out large-scale analysis of ICL ablating out or accounting for memorisation, pretraining, distributional shifts, and prompt- ing style and phrasing. We find that, empirically, ICL is limited in its ability learn and generalise to unseen tasks. Namely, in the limit where exemplars become more numerous, accuracy is insensitive to exemplar distribution, model, prompt style, and the input's linguistic features. Instead, deduces patterns from regularities in the prompt, which leads to distributional sensitivity, especially in prompting styles such as chain-of of-thhhght... Given the varied accuracies and on formally similar tasks, conclude that autoregression's 's ad-hoc encoding is not robust mechanism for learning, and suggests limited all all-purpose generalisability.
INTRODUCTION
In learning theory, learning is tantamount to generalisation. Learning how to solve a task means that, after seeing examples of a task drawn with distribution P, a learner will have a bounded probability of error on classifying new inputs from some Q + P (Valiant 1984). In most traditional learning paradigms, a learner observes inputs from P. and then encodes them within its own knowledge (e.g., updating weights). Then it uses this knowledge to generalise to new examples. Autoregressive large language models (L.LMs) do not explicitly do that. Instead, they perform in-context learning (ICL., where they 'solve" (produce relevant outputs for) a task specified in natural language via next-token prediction (Brown et al. 2020). An L.M observes, but does not encode, the full training set through the prompt. Instead, it updates its beliefs ad hoc, where the beliefs are combination of the input (drawn from P) plus its own intrinsic knowledge (frozen weights). That is, it modifies its states at run-time to deteally-geeerall implies that the LLM is also expected to generalise to any task (unseen PP).
new observations for any Q. Reliance intrinsic knowledge
We argue, however, that knowing is not always the same as learning. Claims LLM's 'ss in-task generalisation (consistent performance w.r.t. any P within the task) and cross-task generalisation (consistent performance w.r.f any task) have divided the field. Theoretical characterisations on their learning power are usually limited, and hence Borenstein et al. (2024) argued that empirical explo- rations could help understand what can transformer- based models learn versus what they actually learn-a central motivation of our work. However, criticisms to empirical research on LLMs note that prompt-and mode- dependence makes hard to reproduce (Li et al.. 2025 De Wynter, 2025 Sclar et al. 2024), and that the terminology, methods, and results themselves are unreliable and could lead to misinterpretation (Huang & Chang 2023 De Wynter 2025 also Section 2
In this paper we examine to what extent ICL is effective learning paradigm. We begin by noting that, mathematically, ICL constitutes learning-ai as opposed to solely repeating internal knowledge-
We use "autoregressive model' and 'LIMM' interchangeably, with the assumption that the LLMSs discussed autoregressive.

---

Published as a conference paper at ICLR 2026
but remark that further work is required to fully characterise it. We then perform empirical studies accounting for some of the criticisms and shortcomings mentioned; namely, sensitivity to pretrain- natural language; prompting style and phrasing; and robust-
ing, memorisation, and dependence ness to distributional shifts in the observed training and test sets. Thus we focus on evaluating generalisation from data in context (unseen P until runtime, and fully-unseen Q); opposed to generalisation from a model's 's pretraining strategy.
Our experiments are on four LLMs, nine tasks, and ablations on prompting strategies, training distri- butions, and exemplar setups. The main results-that is, test set results-comprise 1.89M predictions per LLM. To our knowledge, our study one of the largest of its kind 2
1.1 FINDINGS
We ablate dependence on natural language and prompt phrasing, and use artificial alphabets to force LLMs learn the task solely from the observations. Hence, our findings seek to characterise ICL as a learning paradigm, and not as an evaluation of prompt-based problem-solving capabilities. These are:
1. In the limit (as the number of exemplars grows), the average accuracy gap narrows be- tween the LLMs tested, and all prompting strategies steadily improve accuracy. Likewise, semantically nonsensical prompts near or match their non-randomised counterparts.
2. ICL under altered training (exemplar) distributions is robust to positionality and proportion of labels in the limit. However, ICL is brittle altered test distributions (i.e., out-of- distribution; OOD) as the distance between train and test distributions grows, especially in ofain-of-thought (CoT: Wei et al. 2022b) and automated prompt optimisation (APO).
3. Closely-related tasks do not necessarily have closely-related performances, with average accuracy differences as large as 31 %. Moreover, traditional baselines (e.g.. decision trees and kNNs) outperform ICL average performance in half of the tasks evaluated.
Our findings contradict the notion that a few exemplars are required to solve a task: peak average accuracy was at 50- 100 exemplars-much higher than in reported negative (Lu et al. 2024 Sclar
ett al. 2024; Dziri et al. 2023 Delétang et al. (023) or positive (Brown et al. (0200] results from
LLM studies in natural- natural-language language and automata- based tasks, and independently confirms similar
results for natural-languaal
tasks (Anil et al. 2022 Agarwal et al. 2024). They, however, counter
2024 Errical the view that LLMs are brittle exemplar ordering or characterisation (Sclar et al.
et al. 2025 Zhao et al., 2025; Agarwal et al.) 22024), and align with the view that CoT and APO are good at solving some tasks (Merill & Sabharwal 2024; De Wynter et al.) [023a] Li et al., 2024). although we show that these are not robust to OOD, Finding 3 expands on the works that found that LLM accuracy decays with task complexity (Dziri al. 2023] Gupta et al. (2225] Merrill & Sabharwal 2024), but notes that analogous tasks have marked performance differences.
1.2 INTERPRETATION
Our findings are constrained to easily-verifiable tasks (e.g., parity checking or Hamiltonian-cycle verification) in single call. From within theoretical framework, find evidence that ICL presents signs of Icarning capabilities; but that is tied to the autoregressive paradigm, and not to any particular LLM, training strategy, prompting style. We argue that this is because ICL leverages statistical features from the prompt, as opposed to feature relations within the data. This ad hoc encoding mechanism implies that ICL's cross-task generalisability is limited to the representativeness of the data. Thus, we conclude that, from the perspective of our framework, ICL mathematically form of learning, albeit not robust one.
Remark that our work is constrained to non-natural language tasks, with our ablation on natural language limited to the instructions, not the datapoints. This setup forces LLMs to not rely on their intrinsic knowledge, and instead infer the full characterisation of the data from the prompt itself. This suggests differences with some claims on their emergent capabilities, but also raises the question to which semantic extent priors from the data impact (realistic) natural language tasks and its relationship to learning. This opens avenues for further systematic evaluation of their capabilities.
Code and data is in https:://github.com http:///ttttubbcooooo/deeetttt/s 1earnigg
2

---

Published as a conference paper at ICLR 2026
2 RELATED WORK
Evaluation of LLMs is active area of research, and coverage of its works is non-exhaustive. For broader surveys of this area we point the reader to Huang & Chang 2023). Li et al. (2025), and Qiao et al. 2023). For ICL in particular, see Zhou al. (2024). Early research focused on eval- uating whether RNNs, transformers, and other non-generative models actually performed learning (Borenstein al. 2024 Zhang al., 2023 Butoi al. 2025). These works, like ours, investigated the models' ability to learn formal languages, or subsets of first-order logic, and also found brittle- ness in OOD scenarios. A solution proposed by Dan al. (2022) involved passing in the encoding of the automaton generating the language we explore its viability for ICL in our work.
2.1 THEORETICAL EVALUATIONS
Theoretical research on what transformer based models can possibly learn often find negative re-
sults (Hahn & Rofin 2024 Strobl al. 2024a; Kleinberg & Mullainathan 2024). Even when it has been known for some time that the transformer (under certain assumptions) is Turinng-coplette
Pérez et al. 1 : Bhattamishra al. (020): Li & Wang 2025), Turing completeness by defini- tion requires an unbounded resource or finding an appropriate machine; which is itself undecidable, although approximable (Wei et al. 2022a). More constrained works with specific attention types could recognise languages in the class of constant-depth, polynomial-size alternating circuits. Con- cretely, those in AC (Hao et al., 2022); and partly TC ((Strobl 2023); (Li et al. 2024) for CoT), although as of yet it is unknown why (Strobl et al. 2024b). Nonetheless, Kleinberg & Mullainathan (2024) showed that next-token prediction is a different problem than judging membership (labelling data). Even their ability to model formal languages tends to find disparate results, depending on the assumption made (Strobl et al. 2024b). It is perhaps because of these findings that Borenstein et al. (024) call for empirical evaluation of effective capabilities of LLMs.
2.2 EMPIRICAL EVALUATIONS
Empirical LLM evaluation is complex and also marred with disparate accounts on their capabili- ties. This is often due to the influence of various factors, ranging from choice of model, statistical significance, or ablations with respect to natural language and memorisation (De Wynter 2025)
For example, it known that several LLMs suffer from data contamination (Carlini et al. 2023
Lee et al. 2023 De Wynter et al., 2023b) which could render benchmark- based evaluation unreli-
able; and that different measurements show less impressive results (Schaeffer et al., 2023 Altmeyer
et al. 2024). Likewise, Gupta et al. (2025); Dziri et al. (2023); Merrill & Sabharwal (2024): Liu
ict al. (2023) and [u et al. (2024) evaluated (and found weaknesses) in LLMs when generalising to unseen tasks, especially when using CoT and as the task complexity grew. On the other hand,
positive results such as that of Ontanon et al. (022)) and Borensteen et al. (2024) indicate that, for certain tasks, these weaknesses may not necessarily hold. Indeed, some positive results, such as that of Agaawal et al. (2024), showed that expanding shots improved performance in natural and non-natural language problems, albeit the main results were constrained to a single model.
Research has also attempted to determine whether the models understand the task as described by the prompt, usually with negative results (Webson & Pavlick [2022] Jang et al. 2023 De Wynter & Yuan, 2025 Mancoridis et al. 22025; Dziri et al. 2023) (Strobl et al. (2024a) Proposed explanations
to this related model size to sensitivity to semantics (Shivagunde el al., 2024 Long et al. 2024)
and inductive/selection biases Zhao et al. (2025); Chang & Bisk (2025) although this sensitivity
disappeared when the exemplars included instructions.
However, there were some-reasonable due to scope-gaps in the works above due to the limiting factors mentioned. Thus, we attempt to account for these in our work. Other attempts to explain ICL.
have been through benchmarks (Yauney & Mimno, 2024 Mirzadeh et al. 2025) Zhuo et al.
2024
Selar et al. 2024), mechanistic interpretations (e.g., subnetwork generalisation (Bhaskar et al.
2024
Kumon& & Yanaka 2025 Hu et al. 22025;; probing (Yin & Steinhardt 2025 Azaria & Mitchell 2023
Todd et al. 2024 Ju et al. (2044), ) Bayesian approaches (Xie et al. 2022 Edelman et al. 2024), or
more targeted evaluations, such as that of Chan et al. (2022). This latter work argues that ICL arises
from the distribution of the elements within the training data, along with the use of the transformer,
and it is driving argument for work.
3

---

Published as a conference paper at ICLR 2026
3 BACKGROUND: THE NEED FOR EMPIRICAL EVALUATION OF ICL
We discuss formalisms for learning and task similarity in Sections 3.1 and 3.2 and tie ICL to these in Section 3.3. noting that they partly overlook the mechanism behind ICL. Details are in Appendix [B]
3.1 A FORMAL DEFINITION OF LEARNING
We capture robustness in learning with a variation of the probably approximately correct (PAC) framework from Valiant (1984). We use PAC learning as it is the predominant model in compu- tational learning concretll, statistical learning theory-as well as in language acquisition (Mitkov] 2022 Niyogi 2006). also allows for some leeway to a learner through error tolerance. For comparison with other frameworks, see Appendix
We reframe PAC learning to focus on the learner. This is syntactical re-definition and does not alter the original framework. Suppose we wish to model binary classification task with features assumed to be drawn from some nonempty set X C R. These examples are labelled with an unknown function X + {0, 1}. In machine learning, (data)set D is sampled with some distribution P supported on X, D = {xx, c(z,)){z; ~ P}. A learner (algorithm) f: X + {0, 1} observes D until its empirical error Error(.) is bounded by some (0, 1/2), where
arror(f.D) 1
[f(()) c(x)] Sc (E
Σ
DI
Equation ! must holds for any other dataset E and distribution Q such that E ((2,, <(x:))) 2). where Q likewise supported on X; that is, if
Pr(error(f: (f, F)) 2 1 5,
for 8 (0, 1/2). Intuitively, a learner has learnt the task if has a (lower) bound on its error for any datapoint. Since P and Q are unspecified, f has learnt if it is robust changes in P Standard PAC learning has some limitations, especially around regular languages. Hence, our reframing is only to ground our discussion on strict definition of learning, as done by, e.g., Livni
e.g..Liivni et al. (2014).
3.2 TASK SIMILARITY
In formal language theory, collection of transition rules G (a grammar) generates instances (strings) using symbols from an alphabet to form language L. We assume all instances of task are gen- erated by its own G and Σ, with transition probabilities given by (chosen) P. This P is the same from Section 3.1 and, to the learner L may be known (or deduced), but not. Formal languages may be classified according to the (expressive) power of the automaton able to accept/reeect (recog- nise) an æ based on the query x E L?. Relevant to us are these recognisable by finite state automata (FSA), and pushdown automata (PDA). FSA read the input unidirectionally, changing their inter- nal state between accept and reject, and return either when finished. Tasks such as PARITY and Hamiltonian-cycle verification, require the automaton to track a set of states. PDA are FSA equipped with memory, and can solve these, more complex, tasks. They are considered more powerful than FSA. The autoregressive na- ture of LLMs allows for some memory, and hence they could be considered type of PDA. However, in this work treat LLMs as recognisers of unknown expressive power.
recognisable with FSA. Other tasks, like stack manipulation,
3.3 DEFINING ICL IN CONTEXT
In ICL, an LLM takes in a natural- string as a task specification (system prompt), and uses the input tokens (in natural language) 'solve" (learn) by predicting the following tokens recursively. Formally, Wang et al. (2023) formulate ICL classification
argmax Pr[s(xx) c(xx))=I, (0.1)
(3)
In the words of Niyogi 2006), any classifier 'worth their salt" should fulfil this condition.
4

---

Published as a conference paper at ICLR 2026
where 24 is the datapoint be labelled, and have used the notation from Section 3.1 How- ever, ICL sensitive to the system prompt. Thus, practitioners have resorted to various prompting techniques, which not accounted for in Equation Factoring in both get
argmax (r(f(rx) = c(zx)),, a ( ( (xx))) ((x))
(4)
where p is a system prompt, z; are example datapoints (i < k), and 24 is the instance to be classified. We let IT, 7 be functions that take in inputs 2; and return natural- natural-language representations π (x;;) = (ag, c(x,)) for < k (r. (xxx
zz). These could be, e.g., concatenation of the datapoint and the label (e.g., T(x))= = 'xy c(x;)"); and a datapoint conditioning for next-token (label) prediction, # (3rx) 5g :'. It could also be more complex (e.g., 'Let's think and solve step-by-step...". Both p and x (2;) may be empty, but not at the same time. At inference time, when computing c(Tx). the LLM conditions recursively on its observations from p..... T (zu), and its previous knowledge.
PAC learning does not limit how the learner learns. From Equation 4 it follows that ICL can be viewed as a (formal) learning process. Namely, a learner f: {p} X X - {0, is LLM with ~ Q, representations म and an optional system prompt p. We say that ICL learns e and X if Equation P holds for any X, Āt, P, and Q. This thus makes ICL strongly dependent on म and (the prompt), but does not specify to what extent, since depends on the autoregressive nature of the LLM (namely, the "scratchpad") and its own weights. Indeed, one consequence of Equation 4 is that as k grows, since p is constant, its contribution vanishes when equiprobable to the exemplars:
k exemplars 21..... 2k-1 P. an input instance to classify
Th. F1,..., , Ik--
k=11
Pr[Y|p, TT. 2 #x & Pr[p|Y]
(5)
where we let == f(xx) = c(zx): (x;;) = गH; and (x;)) = म. for readability. Conversely, the encoded exemplars have major contribution in the limit. Nonetheless, acterise π (e.g., which natural-language strings, if any, work better?). This thus calls for empirical evaluations as how effective ICL learning, accounting for P, p. n., and c.
reframings do not char-
4 METHODS
Sample prompts are in Appendix H and full task definition and characterisations with respect to ID/OOD are in Appendix Specifics on LLM calls are in Appendix F
4.1 FRAMING
We seek to find out if a learner (LLM) f can correctly and robustly decide if given x E Σ, sampled with some DD for some Σ and G. belongs to a language L. We let G. E, and L fixed for a task, but not always known to f. We measure correctness with accuracy, 1 error(f.-) and robustness with accuracy under the distributional shift. That is, we consider both in-distribution (ID) entries P and OOD entries
Q, for select values of 8 8= =|p |PP- O.
4.2 PROMPTING STRATEGIES AND SCOPE
We test prompts that perform single call to the LLM. More complex strategies, such as Tree-of- Thoughts (Yao et al. 2023) have good performance, but rely on multiple model calls per instance, and hence are not in the scope of our work. We also consider only single next-token prediction, as well as robustness system prompts (i.e., CoT and APO). Reasoning models like 03-mini (OpenAl) 2025). which have a baked-in non-controllable CoT, are thus not scope. The prompts tested are:
n-Shot Learning: Provide exemplars of input x and desired, formatted output # (1:). When do not provide a system prompt, we refer to as Modus Ponens.
Description: Add in the system prompt p. This is the usual way prompt LLMs.
APO: A meta-prompting ('prompting to prompt') approach where the LLM adapts its own system prompt p with development set. It has been shown that this strategy yields better perceived results
5

---

Published as a conference paper at ICLR 2026
than description (De Wynter et al. 2023a). We used the algorithm from Pryzant et al. (203) to generate p.
Direct Encoding (DE): Pass in the system prompt plus G and L. This is common in theoretical computer science; in addition, LLMs have been claimed to be capable of understanding code. Note
that DE is known to increase robustness to OOD in LSTMs and RNNs (Dan et al. 2022
Chain-of-Thooe (CoT): Generate a series of steps leading to the desired output with a predefined scheme in the system prompt.
Word Salad: Replace the natural strings from the description with random words. When we apply word salad the CoT prompt, call it salad-of-Thoughe (SoT).
These strategies may be mixed. For example, CoT with word salad and 5 exemplars 5-shot SoT. Word salad and SoT are considered only in Section 66.1 All prompts were with 0, 2, 5, 10, 20, 50, and 100 exemplars; except modus ponens (no zero-shot), and CoT/SoT (no 2-shot due to cost). All prompts had output format specifications (implicit in modus ponens) to facilitate parsing.
4.3 TASKS OVERVIEW
All tasks have their own Σ, and were selected for being closely-related tasks often seen in LLM evaluations, or well-known problems in computer science. All (except one) are decision problems We discuss this further in Appendix
to fit the model from Section 3
PARITY: (FSA) decide if given binary string has even zeros. Also known the XOR function.
Pattern Matching (FSA): decide if abcabb is a substring of a given string x C ba,
Reversal (PDA): given a string I#r c: Σ, decide if equals the reversed r. r-
Stack (PDA): given final and initial strings s, 80 C D and a series of operations Op, decide if 8 Op(so). The operations simulate a stack (push/stop/pop) and may or may be grammatical
(e.g., stack overflows).
Hamiltonian (FSA): given graph adjacency matrix form and path, decide it Hamiltonian.
Maze (Complete) (FSA): given maze, two segments of a path, and a sequence of moves, decide if the moves connect both segments. Segment separation is never more than three moves.
Maze (Solve) (FSA): given maze and a sequence of moves, decide if the moves form a valid path from start to exit.
Vending Machine (Verification) (FSA): given list of items and costs C, sequence of operations Op (add balance, purchase item), and initial and final balances by by. verify if by = Op(C') + by-
Vending Machine (Sum): Same as the verification version, but the learner must compute by = Op(C)= + 6, for unknown by. It has constrained set of moves, but unbounded states (N). This is the only task in our work that is not decision problem.
4.4 MODELS AND MEASUREMENT
We tested four LLMs: GPT-4 Turbo Open Al 2023). GPT-4o (OpenAl 2024), Mixtral 8x7B struct v01 (Jiang et al. 2024), and Phi-3.5 MoF. Instruct (Bilenko 2024). We measure performance with accuracy, and report standard deviation (a) indicate variation over an average. We use ordi- nary least squares (OLS) to measure changes. We set all outputs non-compliant with the requested format as zero, but revisit this Section 6.4 When reporting aggregate numbers, however, we do not factor in out-of-token emrrr. For baselines, we tested decision trees (DT), k-nearest neighbours (kNN), and a multilayer perceptron (MLP) in succession, and reported the best. We did not baseline base- problems arithmetic, since they are often solved with heuristics (e.g., A*).
4.5 DATA GENERATION
We created datasets per-task with automata with state transition probabilities drawn from a chosen D. They are synthetic account for (a) the task's G and Σ; and (b) ID and OOD. Every task has

---

Published as a conference paper at ICLR 2026
different manifestations of OOD (e.g. the size of maze). See Figure I for sample automaton and Appendix E for full description of the characterisation OOD per task.
All entries relied natural language as little possible (e.g. binary
strings or arbitrary symbols in Σ, such as /(/)// ). The training dataset was 2000 entries drawn from P. and also generated five balanced, deduplicated test sets, each from a Q such that ||P O1 for {0, 0.2, 0.45, 0.65, 0.85), where and the rest OOD. This allowed to measure the separation between distributions and the gradual change performance.
10
0 is ID,
Every test set is 2000 entries, but due to cost we only evaluated 1000. We also mislabelled entries w.p. 17 0.05 account for any potential memorisation. Hence, the maximum accuracy for any f that actually learns the task is 95%. We only use the training set for APO and the selected baselines. The full suite is 1.89M datapoints.
Figure 1: Data generator for PARITY. Each state has tran- sition probabilities 5, and an emission probability. There is a symmetric automaton with emissions at O.
5 RESULTS
We provide results on our analysis: general accuracy (Section 5.1 distributional shifts (Section [52];; and fine-grained analysis (Sec- tion 5.3). For detailed results, see Appendix G
5.1 OVERALL PERFORMANCE
The best average accuracies, per LLM, were in Pattern Matching (94+1%; solved the task), Hamil- tonian (85144%) and Vending Machine (Verification; 83.19%). Best accuracies in the worst- performing tasks were Vending Machine (Sum; 16), Reversal 111+, and Maze Solve (63=13). See Table for best-of and averaged results per-model over tasks; and Table 2 for aver- aged result data per-task over prompts. LLMs outperformed traditional baselines (c.g.. kNN) in best-of, but not average best, scenarios in all tasks except PARITY.
The best prompt per problem was CoT, in four tasks. The worst prompt was 2-shot modus ponens, in five tasks. The tasks where CoT underperformed (Pattern Matching and Hamiltonian) were not the same where it was the best-performer. In Maze Complete, however, modus ponens was the worst (2-shot; 9 and the best (100-shot; 5)= Without Vending Machine (Sum), the only non-classification task in our work, the accuracies numbers increased by 5 1 on average.
Better performances fits between per-model averages over shots (Table 2 Larger slopes (trends in accuracy improve- ments) were modus ponens (8.3) and lowest in COT (3.3). Mixtral improved the most with more shots, with an average slope of 7.3 (versus 5.8, 3.5, and 4.0 for Turbo, GPT-4o and Phi-3.5).
given by more shots, on average, when looking at the slope from OLS
Task
Turbo GPT-4o
Phi-3.5 Mixtral
Average (Best)
Average (Worst)
ML
PARITY
76
90
83
83
80:3
100-APO
16:220
2-m.p.
95
MLP
P. Match.
96
95
95
95
94-11
50-DE
24+-20
5-CoT
87
kNN
Reversal
71
77
54
55
61+11
100-CoT
20+-21
2-m.p.
72
kNN
Stack
86
92
66
76
13"
50-CoT
20++21
2-m.p.
72
kNN
V.M. (Ver.)
90
84
81::12
10-CoT
22:122
2-m.p.
DT
Maze (Comp.)
83
72
79
81
77::5
100-m.p.
91116
2-m.p.
Maze (Solve)
70
61
66
60
63:15
50-desc.
171200
0-APO
Hamiltonian
93
92
86
85
89-12"
100-desc
29118
0-CoT
V.M. (Sum)
18
20
15
20
16111
5-CoT
0-DE
Table 1: Maximum accuracies per-model per-problem and peak averages (per shots, over models). An is an average over fewer models due to out-of-token failures; means tic. The best prompts often included languael descriptions (CoT, APO, Description). The worst prompt was often 2-shot modus ponens: it lacks description and led to parsing errors in few-shot. Closely-related tasks had differences of up to accuracy. All baselines degraded in OOD except in PARITY.
7

---

Published as conference paper at ICLR 2026
Prompt
Turbo Slope
GPTT-4o
Phi-3.5
Mixtral
Avg. slope
Acc.
acc.
Shots
Modus Ponens
12.8
28++23
11.4
43+-20
5.2
50
3.9
50:-9
8.3++3.9
Description
3.4
57:16
56.13
4.4
5019
48119
= 2.2
DE
3.0
54.:5
1.4
58.13
5.5
501100
8.1
48:120
4.512.44
Word Salad
9.8
32:118
12.1
43122
11.5
39121
9.8
44:120
1111..6
APO
6.1
51+11
2.0
57+4
4.6
51+9
8.4
48+1
5,4 2.6
CoT
3.4
47:6
1.3
55+4
0.5
45+1
38+15
3.3+2.4
SoT
1.8
20:44
3.5
25:
0.3
26:44
1.8
22:55
1.6:2.2
OOD
Modus Ponens
-0.3
28:1
-0.6
43+1
-0.6
50+1
-0.2
5011
-0.4 = 0.4
Description
-0.5
5711
-0.8
56
-0.5
50+1
-0.5
48
-0.5 - 0.4
0.4
DE
-0.4
54+
-0.9
5841
-0.4
50+1
-0.1
48
-0.5+0066
Word Salad
-0.5
31+1
-0.1
43
-0.3
40
-0.2
44+-1
-0.2-+0.3
APO
-0.4
51+1
-1.0
57+1
-0.6
51+1
-0.1
48
-0.5+0.7
CoT
-0.6
4711
-2.7
5514
-1.3
45:2
-1.0
38111
-1.4199
SoT
0.1
20111
-0.6
25:11
-0.1
26
0.5
22:11
0.0:10.6
tasks. The rightmost column has the average slope for all LLMs. Word salad and SoT are not factored into our main results, but are discussed in Section 6.1 The effectiveness of the prompts depended the slope and large and positive slope means an increasing trend in accuracy, with larger slopes implying larger change. Shot slopes are positive, and the 8 slopes are slightly negative. This suggests that more shots improve accuracy in all prompts; but in OOD this is ineffective, defaulting the average and decreasing overall.
Table 2: Slopes and accuracies averaged
Average Accuracy (Modus Ponens)
Average Accuracy (With Description)
Average Accuracy (CoT)
Turbo
7403
Shots (9)
Figure 2: Per-model average accuracy results for (left to right) modus ponens, description, and CoT; plotted over shots (thick vertical lines) and per-shot 8 between them. On average. most prompts showed analogous behaviour in the limit, and robustness to OOD. CoT also showed converging be- haviour, although it was more brittle OOD. Every datapoint is an average over 1, 1,000 predictions.
5.2 DISTRIBUTIONAL SHIFTS
Distributional shift decreased accuracy as - 0.85. We evaluated the slope on the per-LLM accuracy averages between 8 = 0.85 and 5 0, per shot. All were negative. The largest (most sensitive to OOD) was CoT at -1.4, followed by APO (-0.5). The smallest was modus ponens, at -0.4 (Table 2). See Figure 2 for examples and Appendix G for full breakdown. GPT-4o was most sensitive to OOD inputs, with an average slope of -12 (versus -0.7, -0.4, and -0.3 for Phi-3.5, Turbo, and Mixtral). The largest impacts of 5 per task were in Reversal 1-1.7+1.55, versus Vending Machine (Sum) (lowest; 0.1 0.2). The average slope was -0.6
5.3 FINE-GRAINED BEHAVIOUR
In the breakdown per- prompt and per-task, LLMs had (1) similar behaviours over the tasks, but (2) inconsistency over the task type. The first was given by the LLMs having low a but similar accuracy in lask-by-task and prompt-by-prome difference among them (Figure 4 in the Appendix). The per-prompt shot slopes, averaged per LLM, were 8.3+3.9 (modus ponens), 4.4+2.2 (description), 4.5+2.44 (DE), 5.342.6 (APO), and 3.3+2.4 (CoT) (Table 2). As per the averaged slope's a, there was low variation between the type of LLM and the prompt over all tasks: 1.2+1.6 over shots. OLS fits over the per-shot a indicated that the model gap, as the shots increased, narrowed: -2.5+ similar pattern in the OLS fit
basis: all prompts had positive slope and low relative
8

---

Published as a conference paper at ICLR 2026
was noticeable in å slopes. Inconsistency when related tasks had gaps in peak performances: 31% (Maze (Solve) versus Pattern Matching), and 12% (Reversal and Stack; Table
ABLATION STUDIES
We present summaries of our ablation studies. Refer to Appendix for details and figures.
6.1 IMPACT OF LEXICAL FEATURES
We sought to understand to which extent lexicality (words) impacted ICL with respect the data features. We assumed that LLMs were pretrained mostly on natural and programming languages. We compared word salad with modus ponens and DE; and CoT with SoT. While word salad ver- sions of prompts started low-at some points with zero accuracy-they quickly reached relatively high maximum accuracies. Averaged per-LLM, the word salad versions matched the baselines to within or a/2 of their average and had the largest slopes. Word salad only randomised the system prompt, but SoT fully randomised the exemplars. It had major impact on accuracy, with the lowest average performance over shots (231:%% in any prompt due to its high eror rate, Some LLMs SoT obtained above-average accuracies certain tasks, such as GPT-40 in PARITY (63% at 100 shots), and Turbo in Stack (76% at 50 shots).
6.2 POSITIONALITY OF EXEMPLARS
On every call, all exemplars so far were equiprobable and fixed throughout ('unshuffled'). Here, randomised the position of the same exemplars within the prompt ('shuffled'), and also fully randomised the exemplars (drawn i.i.d. from the training set). There was a small variation in ac- curacy when the same exemplars were shufiled versus unshuffled. with the latter having slightly lower average accuracies and per-prompp slopes, albeit higher slopes per-LLM. The best-performing prompts for average accuracies when shuffled versus unshuffled were always the same. When fully randomising the exemplars, we only measured and compared GPT-4o. On average, fully randomis- ing the exemplars yielded lower accuracies, and had lower shot and higher å slopes.
6.3 IMPACT OF ALTERNATE DISTRIBUTIONS
We altered P in four setups: the fully randomised and shuffled exemplars from Section 6.2 imbalanced distribution with only negative labels; and a corpus with uniformly at random labels (both test and train) baseline. We only analysed and compared GPT-4o without Vending Machine (Sum). The imbalanced scenario achieved higher average accuracies than all setups, matching or outperforming the unshuffled baseline. However, in this case, the average a increased on every prompt and every setup. The random label baseline had better slopes than the unshuffled baseline. Of note is also CoT, which had negative shot slopes in all setups.
6.4 COMPLIANCE VERSUS LEARNING
We separated parsing errors (' ('compliance") from mislabelled instances ('learning") and re-calculated averages and slopes. Factoring out compliance increased perceived performance by understating or overstating magnitudes. For example, average shot and ó slopes were smoothed out, thus making- for example-CoT's sensitivity to OOD hard to spot.
7 DISCUSSION
As the 'training set' (i.e., the number of exemplars) grew, (1) LLM accuracy increased, and (2) the gap between LLMS and prompts narrowed. Both suggest that ICL as a learning paradigm depends less on the LLM and prompt and more the ability to perform autoregression. However, ac- curacies were not consistent across similarly-related tasks: Pattern Matching (FSA) was effectively solved, while Reversal (PDA) and Maze (Solve; FSA) had low accuracies. This suggests that au- toregression is limited in its ability to solve tasks. This could be related to the choice of prompt. However, observed that while all prompts were sensitive to OOD, the best prompts (Co' and

---

Published as a conference paper at ICLR 2026
APO) were both adaptive and more brittle. This suggests then that, although they are effective on leveraging the power of a PDA, they bias the learner towards the observed distribution. This, in tum, from the perspective of our framework, means that learning in ICL is not completely fulfilling the requirements from Equation 2 Thus, autoregression's 's ad hoc encoding via the prompt is not a robust learning mechanism. As extreme example, recall that Vending Machine (Sum) had non- zero accuracy but near-zero slope regardless of number of shots, thus indicating complete inability to learn the task.
Indeed, in the limit, accuracies were similar regardless of language and exemplar distributions, pro- vided that they remained fixed. Hence ICL learns the observed P, rather than fully generalising to the unseeen 2, since the fully randomised exemplars had lower accuracy than both the shuf- fled and unshuffled settings. Remark that the observed P did not change, and this phenomenon also could be explained as a manifestation of the bias-variance tradeoff. Given that the randomised labels baseline had lower 8 slopes, OOD brittleness is very dependent on ICL overfocusing on spurious features. This is especially visible in CoT, which had consistently negative d slopes across all variations of P. While description-baser prompts had the best peak accuracy, in the limit word salad reached equivalence with them. In SoT, some LLMs were still able to reach above-random scores in spite of the constant randomisation. This means that autoregression can distinguish data features from lexical relations, but cannot fully identify feature relations within the data. It also empirically confirms the remarks from Equation 4 that p's contribution vanishes in the limit.
Alternate explanations could be (1) contamination, and (2) tokenisation. Contamination could explain the accuracy in Pattern Matching, perhaps due to the (easy) Σ, {a, b, Other tasks, like Reversal, used more complex Σ and had lower scores, it could be argued that the LLMs had been pretrained in these tasks. However, good performances were also observable in Hamiltonian and PARITY; thus suggesting the ability to (almost) fully simulate an FSA, and not contamination. For (2), it could be said that an LLM trained on a task A will not necessarily solve a similar B if EA * Eg (ef., graph and maze traversals). could also explain the results from Vending Machine (Sum): arithmetic skills are impacted by BPE (Singh & Strouse 2024), the tokeniser which all LLMS studied implement. The implementation is not always the same. In the limit, LLM performance gap narrowed and thus tokenisation is not as relevant to ICL as the data features, although this only applied to decision problems, not arithmetic. Finally, our theoretical framework could impact our analysis of the conclusions. We argue that mathematically it is sufficient to define learning due to its ablation on the nature of the data and its focus on learning as a process. However, we refine and discuss this in Appendices C and D including further explanations on the accuracy gap observed.
8 CONCLUSION
In this work we began by noting that, mathematically, ICL did constitute learning. However, we also noted that further work was required to characterise it beyond the standard assumptions and limitations of the literature. Our experiments thus accounted for prompting style and phrasing, natural language, number of shots, input and output distributions, contamination, and pretraining strategies. We found that, although formally ICL is form of learning, empirically it is relatively weak. This is due our findings on its limitations and nuanced behaviours, different than originally reported. Concretely, in the limit, best-of average accuracies were given by 50-100 shots, and the differences amongst both LLMs and prompts decreased. Exemplar positionality, characterisation, labels, and wording were less relevant than the data features themselves-ever in SoT, LLMs learned the task in spite of its constant randomisation. Nonetheless, ICL also overfocused on spurious features from the observed distribution. It also showed marked differences in supposedly- tasks, and brittleness to OOD, especially in APO and COT.
Our findings indicate that, for example, brittleness to OOD means that LLM performance will not be chartcctrrtte by testing only few prompts, as the performance observed may be spurious. Hence, research on LLM capabilities must be done with caution and transparency, testing multiple prompts, shots, and distributions. Future work should characterise reasoning models: we conjecture that they will do better in our setup: but will also have difficulties in complex tasks (e.g., context- sensitive languages), brittleness OOD, and inconsistency over tasks. The latter also suggests that an open question remains on how to empirically measure what ICL does over what it can do; and then map it back the theory while accounting for natural language factors not studied in this work.
10

---

Published as a conference paper at ICLR 2026
ETHICS
Our work is a large-scale exploration of ICL over synthetic data. We are unaware of any potential misuse of this research, albeit we could have overlooked something. The volume of data in our work likely had a very high carbon footprint. While we argue that releasing the code publicly will have more benefits the community than potential harms, we have included disclaimers discouraging running the full suite. We expect this work to be one-off experimental work to determine ICL's feasibility as a learning paradigm, and thus our work focused on various open and closed models. This should make the work comprehensive enough also discourage re-running the full suite. We discuss limitations our work in Appendix
10 REPRODUCIBILITY STATEMENT
All code is included in the repository. It will be open-sourced under the MIT licence, Detailed methodology, included model versioning. in Appendix [] Prompts are Appendix [H] and also in the repository. Work has been done in both closed-source and open-source models. We set the temperature to zero throughout to ensure further reproducibility.
REFERENCES
Rishabh Agarwal, Avi Singh, Lei M Zhang, Bernd Bohnet, Luis Rosias, Stephanie C.Y. Chan, Biao Zhang, Ankesh Anand, Zaheer Abbas, Azade Nova, John Co-Reyes, Eric Chu, Fer- yal Behbahani, Aleksandra Faust, and Hugo Larochelle. Many-shot in-context learning. In The Tiiht Annual Conference on Neural Information Processing Systems, 2024. URL
Patrick Altmeyer, Andrew M. Demetriou, Antony Bartlett, and Cynthia C. S. Liem. Position: Stop making unscientific AGI performance claims. In Ruslan Salakhutdinov, Zico Kolter, Kather- ine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Pro- ceedings of the 41st International Conference on Machine Learning, volume 235 of Proceed- ings of Muchine Learning Rexeurch, pp. 1222-1242. PMLR, 21-27 2024. URL https: //proceedings ml www.ppaas/23333 htwp:///e22aaammee22222.... html
Dana Angluin. Queries and concept leaming. Mach. Learn. 2(4):319-342 April 1988. ISSN
0885-6125. 25. doi: 10.1023/A:1022221123333. URL https://doi wwwooo.or////// 102282 128753
oorg/10 10.
1023/A: 10.1///../3//
Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Sys- zSKYVeX7bC4
tems, 2022. URL https:: www.rewiew.w...........w. net.eeewwweeeeeeeeeeeeeeeeeeeeee net http//oormmmiiieeeeee/ www.rreeiii..eeeeooore.....eee
httpps:/openreeieww..c
Amos Azaria and Tom Mitchell. The internal state of an LLM knows when it's lying. Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Lin- guistics: EMNLP 2023, pp. 967-976, Singapore, December 2023, Association for Computational Linguistics. doi: 18.18/ 1 1/2023. 1/2023. findings-emmll.68. URL orq/2023. fww.iiigiinnniii emnlp 68/]
Chris Barrett, Riko Jacob, and Madhav Marathe. Format-langung---ontttinnndd path problems. SIAM Journal on Computing, 30(3):809 2000. doi: 10. 10.11337/5097753799333777777 URL https:
//doi.org/10. 1tt.://0.111//00073333399999939
Adithya Bhaskar, Dan Friedman, and Danqi Chen. The heuristic core: Understanding subnet- work generalization in pretrained language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pp. 44351-14363 Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 1/222 fttps://aae antho lgy. acl acl-oong.........o... 774/
URL

---

Published as a conference paper at ICLR 2026
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. In Raquel Fernández and Tal Linzen (eds.), Proceed- ings of the 24th Conference Computational Natural Language Learning, pp. 455-475, Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18655/112222.ccml-13333
URL petttss:/aclaattiiee htt.::ss//ecllantoooooo.or////// 2020 wtt.000..ooo1.....
Misha Bilenko. New models added to the Phi-3 family, available on Microsoft
Azure, 2024.
URL https: /ttts::/azzue.... www.osoftto....ommmmmmom wtw.r/oooo....cc/eeee/e////////a com/en-us/blog//
new models saabels--ddddde to the phi 3- fami ay- omoo-ooo-- azuree
Nadav Borenstein, Anej Svete, Robin Chan, Josef Valvoda, Franz Nowak, Isahelle Augenstein, Eleanor Chodroff, and Ryan Cotterell. What languages are easy to language-model? a per- spective from learning probabilistic regular languages. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pp. 15115-
15115-15134, 15134, Bangkok. Thailand, August URL
2024. Association for Computational Linguistics. doi: 10.
https::/acclattiie logy. wwwp////22222.. acl aonooog...l......... 8077]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. Proceedings of the 34th International Conference Neural Information Processing Systems, NeurlPS' 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Alexandra Butoi, Ghazal Khalighinejad, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian DuSell. Training neural networks as recognizers of formal languages. In The Thirteenth In- ternational Conference Learning Representations, 2025. URL cottps://openreviees tttt/forum?id=aallle00
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In International Confer- ence on Learning Representations, 2023. URL https::/oppnreete
net/ / forum?id=
TatRHT 1cK
Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang, Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learning in transformers. In Koyejo, S. Mohamed, A. Agar- wal, D) Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Pro- cessing Systems, volume 35, pp. 18878-18891. Curran Associates, Inc., 2022. URL. cctpapc.cppppppppppe httprr/essseepppee/2//ee//// file/ Paper- Coafrooooeeeeecepcc
Yingshan Chang and Yonatan Bisk. Language models need inductive biases to count inductively. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
Soham Dan, Osbert Bastani, and Dan Roth. Understanding robust generalization in learning regular languages. In Kamalika Chaudhuri, Stefanie Jegelka. Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 4630 4643. PMLR, 17-23 Jul 2022.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the Chomsky Hierarchy. In /1th International Conference on Learning Representations, 2023.
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal,
12

---

Published as a conference paper at ICLR 2026
Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of trans- formers on compositionality. In seveth- Conference on Neural Information Processing Systems, 2023. URL
Ezra Edelman, Nikolaos Tsilivis, Benjamin L. Edelman, Eran Malach, and Surbhi Goel. The evolu- tion of statistical induction heads: in-context learning markov chains. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS '24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385.
Federico Errica, Davide Sanvito, Giuseppe Siracusano, and Roberto Bifulco. What did do wrong? quantifying LLMs' sensitivity and consistency to prompt engineering. In Luis Chiruzzo, Alan Ritter, and Lu Wang (eds.), Proceedings of the 2025 Conference of the Nations of the Ameri- cas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 1543-1558, Albuquerque, New Mexico, April 2025, Association for Computational Linguistics. ISBN 979-8- 89 76- 189-6. doi: 10.18653/v 1/2035/112222... www.///2o..aaa-ooon..... URL http://s://aaaannoollooooooooeee
www.esaaaaallaa maw.i-long.lnn.. 73/
Edward Gibson and Kenneth Wexler. Linguistic Inquiry, 25(3), 1994.
Mark Gold, Language identification in the limit. Information and Control, 10(5):4474474 1967.
ISSN 0019-9958. doi: http:///oooooo////ooooossssss111 wtt.:tccccccccccm.eec crt.opaciiecttooooooc//e//////ta
URL https://wwwt
Kavi Gupta, Kate Sanders, and Armando Solar-Lezama. Randomly sampled language reasoning problems reveal limits LLMs, 2025. URL (Rthhtt::///rrae 1ttpxiiv.rrr/bb///55...... 0282
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Lun-Wa Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings the 62nd Annual Meeting of the Associ- ation.for Computational Linguistics ( (Volume 1: Long Papers), pp. 14973-155555 15008, Bangkok, Thai- land, August 2024. Association for Computational Linguistics. doi: 11653/v1/2024.ccl 800. URL https:t:///. a antho logy org 2024 acl lowllllooonnoooo 8007
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800 810, 2022. doi: 10. 162/tacl 00490. URL -1.
ogy.
Michael Y. Hu, Jackson Petty, Chuan Shi, William Merrill, and Tal Linzen. Between circuits and Chomsky: Pre-pretraining on formal languages imparts linguistic biases. Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9691-9709 Vienna, Austria, July 2025. Association for Computational Linguisties. ISBN 979-8- 89176-251-0. doi: 10.18653/v1/2000 122011/.c2-22ooo... 478. URL hattps://aclantteee orrg 22025.al-12 www.alcllloog.... 478/
Jie Huang and Kevin Chen-Chuan Chang. Towards reasoning in large language models: A sur- vey. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the As- sociation for Computational Linguisties: ACL 2023, pp. 1049 1065, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. (166:////222...minnn---a- wrg.elaanntoooooyooog//222..... windingsnnniiiee. acl.
URL
Joel Jang, Seonghyeon Ye, and Minjoon Seo. Can large language models truly understand prompts? case study with negated prompts. In Alon Albalak, Chunting Zhou, Colin Raffel, Deepak Ra- machandran, Sebastian Ruder, and Xuezhe Ma (eds.), Proceedings of The 1st Transfer Learning for Natural Language Processing Workshop, volume 203 of Proceedings of Machine Learning Research. pp. 52 62. PMLR, 03 Dec 2023. URL https: httts::/ .ww.eiiinnnsmm.......mmm.m..m..e mlr mlr..ress/ press/ v203/ jang 2a. atml
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gi- anna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie- Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang. Szymon Antoniak, Teven Le
13

---

Published as a conference paper at ICLR 2026
Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mixtral experts, 2024. URt/tttps:/ httptttpps//...../ooottt abs
Kent Johnson. Gold's theorem and cognitive science. Philosophy of Science, 71(4):571-592) 2004. doi: 10. 10.10/6/423752.
Tianjie Ju, Weiwei Sun. Wei Du, Xinwei Yuan, Zhaochun Ren, and Gongshen Liu. How large lan- guage models encode context knowledge? a layer-wise probing study. In Nicoletta Calzolari, Yin Kan, Veronique Hoste, Alessandro Lenci, Sakriani Sakti, and Nianwen Xue (eds.), Pro- ceedings of the 2024 Joint International Conference on Computational Linguistics, Language Re- sources and Evaluation (LREC-COLING 2024), pp. 8235-8246, Torino, Italia, May 2024. ELRA and ICCL. URL /
http://alllnttt wwtphhhwwwooooo...oooooooo 2024. www.-lreeaaaiiie 722/
Gerhard Jäger and James Rogers. Formal language theory: refining the Chomsky hierarchy. Philo- sophical Transactions of the Royal Society B, 2012. doi:
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. In Mathematical Aspects of Deep Learning. Cambridge University Press, 2022. doi: 10.1017/ 7781009025009.000
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67 95, January 1994. ISSN 0004-5411. doi: 10.1145/174644. 174647. https:::///eat
Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, 1994.
Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In The Thirty- eighth Annual Conference on Newral Information Processing Systems, 2024. URL https:
//openzeview.
Ryoma Kumon and Hitomi Yanaka. Analyzing the inner workings of transformers in compositional generalization. In Luis Chiruzzo, Alan Ritter, and Lu Wang (eds.). Proceedings of the 2025 Con- ference of the Nations of the Americas Chapter of the Association for Computational Linguis- fies: Human Language Technologies (Volume 1: Long Pupers), pp. 9529-8540, Albuquerque, New Mexico. April 2025. Association for Computational Linguistics. ISBN 979-8-89176-1888 432. URL httppps//aaaaaattoooooooooo////p
6. doi: 10.18653/v 00155/3/1/222...0 haacl-long 432/
Steffen Lange and Sandra Zilles. Relations between Gold-style learning and query learning. Infor- mation and Computation, 203(2)2211 2005, ISSN 0890-5401. doi: https//ddo.org//0.00//// ic.2005.08 08.000.000000. 018905401050000
http:://wwwww.... htt.:///wwww...aaaaaceee.......c
Jooyoung Lee, Thai Le, Jinghui Chen, and Dongwon Lee. Do language models plagiarize? In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 3637-3647, New York. NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394161. 399 URL wtt.ttt::///oiorrrtttt 0ttp://..11155545553333 3583199
doi: 10.1145/3543507.
Qian Li and Yuyi Wang. Constant bit-size transformers are Turing complete. In Advances Neural Information Processing Systems. Curran Associates, Inc., 2025. WtLhhhtp:://aaa http:::://axxi..orr
pdf hddf/256.... 12027
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems, In The Twelfth International Conference on Learning Represen- tations, 2024. URL httL:tttss//ppnreeeee
net forum 7id= 3EWTEy9MTH
Zongqian Li, Yixuan Su, and Nigel Collier. A survey prompt tuning. In ES-FoMo III: 3rd //tt:::://openreview
Workshop on Efficient Systems for Foundation Models, 2025.
idd JEMGDajQ1G
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representa- wwwp:/neffooommmmmmmmmmmm
fions, 2023. URL hhttpss///ppettt htt.://eww.....eeeooooooeeeeeana
14

---

Published as a conference paper at ICLR 2026
Roi Livni, Shai Shalev-Shwarte and Ohad Shamir. On the computational efficiency of training neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 14, pp. 855 863, Cambridge, MA, USA, 2014. MIT Press.
Quanyu Long, Yin Wu, Wenya Wang, and Sinno Jialin Pan. Does in-context learning really learn? rethinking how large language models respond and solve tasks via in-context learning. In First Conference on Language Modeling. 2024. URL https: /ttpps://peerrevee..co net forum?id-
12oJJCOESQ
Sheng Lu, Irina Bigoulaeva, Rachneet Sachdeva, Harish Tayyar Madabushi, and Iryna Gurevych. Are emergent abilities in large language models just in-context learning? In Lun Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 5098-5133 5139, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. N0.18663/11/222.accl URL htw.:pppss/acclannhoolaoyy.
.oo.g//o..0....1oooooooooooooo 279/
Marina Mancoridis, Bec Weeks, Keyon Vafa, and Sendhil Mullainathan. Potemkin understanding in large language models, 2025. URL httpp:://aaxi..orrrrrsr// htsp://ab///5505 21521
William Merrill and Ashish Sabharwal. The expressive power transformers with chain of thought.
In The Twelfth International Conference Learning Representations, 2024. URL hctps:
/oppnrevveww wwwp:nnnnn.oooimoeeoeem http://ww..tttooommmmeaaaaaaaaa1
Seyed Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models. In The Thirteenth International Conference on Learning Representationss 2025.
Ruslan Mitkov. The Oxford Handbook of Computational Linguissicss Oxford University Press, 06 2022. ISBN 9780199553691
doi: 10. 00.1199Xook6ochhh/77779999777699 000057777731111000000000000 .001.0001. httptts:: 7 7/doi. org/1..rg/1...m 1tt.////oo.....//oooooraaaaaaaa http///80119990 978019997369911 001.
0000 0001
Partha Niyogi. The Computational Nature of Language Learning and Evolution. The MIT Press, 2006.
Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. Making transformers solve compositional tasks. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.). Pro- ceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 3591-3607, Dublin, Ireland, May 2022. Association for Computational Lin- guistics. doi: 10. 10.11866 1633/
ac 1all-long- www.ong.... 2517
Open AI. GPT-4 technical report. Technical report, Open AI, 2023. URL https://arxiv.
org/ org/abs/ abtpab/3....7733//33
OpenAl. GPT-4o, 2024.
URL
got-40 40
OpenAl.
OpenAl
03-mini, 2025.
URL.
https://openal: com.ii.ccmmmi nddx
openai o3 miinmi
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Seikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is toring-complete. Journal of Machine Learning Research, 22(75):1-35, 2021. URL httpthttt///mml/ee httt::://mllr.rrg//pprrr///// 20-302. h
Leonard Pitt and Manfred K. Warmuth. The minimum consistent DFA problem cannot be approx- imated within any polynomial. J. ACM, 40(1):95-142,, January 1993. ISSN 0004-5411. doi: 10.1 1451138007. 138042. htt.htttss//dd..rr/////
138042
15

---

Published as a conference paper at ICLR 2026
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gener- alization beyond overfitting on small algorithmic datasets, 2022. URL
abs/2201. 02177
Reid Pryzant, Dan Iter, Jenry Li, Yin Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with "gradient descent" and beam search. In Houda Bouamor, Juan Pino, and Ka- lika Bali (eds.), Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing. pp. 7957-7968, Singapore, December 2023. Association for Computational Linguis- httttts::: / aacl anthelogyy.o org/20233
tics. doi: 10.
emn
p-ma ma 1 1..i..... 4 4947
Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen. Reasoning with language model prompting: A survey. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp- 5368-5393, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.1 294. URL htRpstss:// htw.l//ww...aaaaaaoooooo../o//.. http:///oooo...or//022....2--a-.
294/
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of thain-of-thought. In International Conference on Learning Reprexentations (ICLR), 2023.
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models a mirage? In Thinty-sevntth Conference Neural Information Processing Systems, 2023.
Dale H. Schunk. Learning theories: An educational perspective. Macmillan Publishing Co, Inc., 2012.
Melanie Sclar, Yejin Choi, Yulia Tsvetkov, and Alane Suhr. Quantifying language models' sen- sitivity to spurious features prompt design or: How learned to start worrying about prompt formatting. In The Twelfth International Conference on Learning Representations, 2024. URL
https::/cpeezeviiet net/ wwtp://eeee//teeeeeeeeeeee www.mriiuiooooo..... 2o-umnid-RL
Namrata Shivagunde, Vladislav Lialin, Sherin Muckatira, and Anna Rumshisky. Deconstructing in-context learning: Understanding prompts via corruption. In Nicoletta Calzolari, Min- Kan, Veronique Hoste, Alessandro Lenci, Sakriani Sakti, and Nianwen Xue (eds.), Proceedings of the 2024 Joint International Conference Computational Linguisties, Language Resources and Evaluation
2024). pp. 155509-4529 Torino, Italia, May 2024. ELRA and ICCL.
URL httts::////clllaa wwwpnttooooy...ooo ogy. 2024 rrecmmain. 4047
Thomas J. Shuell. Cognitive conceptions of learning. Review of Educational Research, 56, 1986. doi: https//db.oorg//0011110004444443
Aaditya K. Singh and DJ Strouse. Tokenization counts: the impact of tokenization on arithmetic in abs httpb///44..4444. 14903
frontier LLMs, 2024. URL
Burrhus Frederic Skinner. The behavior of organisms: an experimental analysis. Appleton- 1938.
Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold circuits, 2023.
Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. Transformers as transducers. Transactions of the Association for Computational Linguistics, 13:200-219, 02 2024a. ISSN 2307-387X. doi: 10. (t02/taclaa_00733 URL tacl_ 00736
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? a survey. Transactions of the Association for Computa- tional Linguistics, 12:543-561, 05 2024b. ISSN 2307-387X. doi: 10.1162/tac URL http::////oo..oo11..1111//////// a0066_000__003333_00000001133333
Edward Lee Thorndik.. Educational psychology. Vol. 1. The original nature of man. Teachers College, 1913. doi: http:://bi.agg//0000377/7777--
16

---

Published as a conference paper at ICLR 2026
Eric Todd, Millicent L. Li, Arma Sen Sharma, Aaron Mueller, Byron C. Wallace, and David Bau. Function vectors in large language models. In Proceedings of the 2024 International Confer- ence Learning Representations, 2024. URL https::/ net/ for. forum?idd
AwyxtyyMaa arXiv:2310.15213.
Leslie G. Valiant. A theory of the learnable. Commun. ACM, (CMM)77(1))1133411142 November 1984. doi: 10.1 (0.1145/1968.1) 1972. URL. https::/dbi.org/100 11t.//11...111166111
ISSN 0001-0782.
1972
Xinyi Wang, Wanrong Zhu, Michael Saxon, Mark Steyvers, and William Yang Wang. Large lan- guage models are latent variable models: explaining and finding good demonstrations for in- context learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Albert Webson and Ellie Pavlick. Do prompt-based models really understand the meaning of their prompts? In Proceedings of the 2022 Conference of the North American Chapter of the Asso- ciation for Computational Linguisties: Human Language Technologies, pp. 2300-2344, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 20.18653/v1/2022, naacl-main.167 URL (tttsst:s:/ htcp//aaaaaaa aoo.annhooogy..... 000p//2200 naacl main.167
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 12071-12083, Curran Associates, Inc., 2022a. URL httpps//pprocedd.ss.ss.eee nerriienerrppp cc wwtp:pppppppppppeeeeeeeeeee.eeep httpe/rrrrrroee/peeeeeeeee////er
file/ Aale/4ebfii Btl.////..AAAA330022222233333333 Coperr pdf
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V
Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 24824-24837 Curran Associates, Inc., 2022b. URL https://prrceeeddd/ ngs. fttpg//rsssrrssss///////eeeeeeer
file/ /ttp/955609613324efff424 o
abcalbaacca-eeeeee abcaf- pdd
R.M. Wharton. Approximate language identification. Information and Control, 26(3):236-255,
1974. ISSN 0019-9958. doi: http:://ooaarryroooooooooo09s092
URL https:
//www www.sccienedirect.ccom wtcpet.ccocccccccc /ttp://cccccccceee../../.aaaaaar
Noam Wies, Yoav Levine, and Amnon Shashua. The learnability of in-context learning. In
Thirth- Conference on Neural Information Processing Systems, 2023. URL hctps:
// //operevveww net/fformm d=#3JNGd7CCHM ffg
Adrian de Wynter. Awes, laws, and flaws from today's LLM research. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Findings of the As- sociation for Computational Linguistics: ACL 2025, pp. 12834-12854, Vienna, Austria, July https:
2025. Association for Computational Linguistics. ISBN 979-8-89176-256-3 //aclanthology. org. findings acc. 6647
Adrian de Wynter and Tangming Yuan. The thin line between comprehension and persuasion in 1lms. 2025.
00 01936
Adrian de Wynter, Xun Wang, Qilong Gu, and Si-Qing Chen. On meta-prompting abs/2312.06562, 2023a. doi: 00448550/anxiv22222066222 URL Utt.tttp:://www..o/oo.o 2lt../////aa23120550555222 06562
Adrian de Wynter, Xun Wang, Alex Sokolov, Qilong Gu, and Si-Qing Chen. An evaluation on large language model outputs: Discourse and memorization. Natural Language Processing Journal, 4: 100024, 2023b. ISSN 2949-7191. doi: https://bi..rg/lll.00...........
URL
www. www.ssciieeeeeieeecccc com http:///o........o.oo.o/..////aa
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations (ICLR), 2022.
17

---

Published as a conference paper at ICLR 2026
An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang, Jialin Wang, Jian Yang. Jianhong Tu, Jianwei Zhang. Jianxin Ma. Jianxin Yang, Jin Xu, Jin- gren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang. Mei Li, Mingfeng Xue, Na Ni, Pei Zhang, Peng Wang, Ru Peng, Rui Men, Ruize Gao, Runji Lin, Shijie Wang. Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wen- bin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Xuejing Liu, Yang Fan. Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu, Yugiong Liu, Zeyu Cui, Zhenru Zhang, Zhifang Guo, and Zhihao Fan. Qwen2 technical report. 2024. URL
https://arxiv. org. abs
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: deliberate problem solving with large language models. In Pro- ceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Gregory Yauney and David Mimno. Stronger random baselines for in-context learning. In First Conference on Language Modeling, 2024. URL http://///ppeeeeeeeeeeeeeeeeeeee wwt/forummfiicm
TRXOMPLUED
Kayo Yin and Jacob Steinhardt. Which attention heads matter for in-context learning? In Forty- second International Conference on Machine Learning, 2025. URL http:tts///opeeeeiiies net/ Eerum? 1ww.ddd/ccyCCCF...
Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck. On the paradox of learning to reason from data. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), aug 2023. URL http::/sttaraii... uslua
ledu/ http://apprrs/2hanngxxxxx222
Hao Zhao, Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. Is in-context learning sufficient for instruction following LLMs? In The Thirteenth International Confer- ence Learning Representations, 2025. URL https: http:///ppneeeee.eeeeeeee net www.:nrrtnorre forum?ioo 2id=
STEEDDv3ZI
Yuxiang Zhou, Jiazheng Li, Yanzheng Xiang, Hanqi Yan, Lin Gui, and Yulan He. The mystery of in- context learning: A comprehensive survey interpretation and analysis. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 14365- 14378, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. 0tt/3////222..m///// mamnl--main.799 mai...795. URL 795/
https://aclantholooe .rchy...rg/// org//0244--222000 2024. ewwlp-malaaaeeeee.
Jingming Zhuo, Songyang Zhang, Xinyu Fang, Haodong Duan, Dahua Lin, and Kai Chen. ProSA: Assessing and understanding the prompt sensitivity of LLMs. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 1976.1976. Miami, Florida, USA. November 2024. Association for Computational Linguistics. doi: 10.18653/v 1/2024 Sanding--emnlp1108 URL https: hta//aaaattthtt http///aaaaahhoo..... or24/024. f i nd ngs emn p. 108/
18

---

Published as a conference paper at ICLR 2026
A LIMITATIONS
One core limitation of our work is that LLMs are continuously updated, and this could make repro- ducibility difficult. To mitigate it, we have worked with open and closed-source LLMs, and provided detailed call parameters. Our evaluation is not cheap either: running synchronously single task per LLM could and has taken months, depending on hardware, and the aggregate cost for all calls could render further exploration prohibitive. Lower-volume testing or fewer tasks could provide simi- lar results, at the expense of statistical significance or ambiguity. Other testing, such as alternate paradigms (c.g., reasoning models) and prompting (multi-step. multi-call) were not evaluated in our work and could show more nuanced results.
Finally, interpreting the results from the ML baselines is nuanced. These are fast to train and iterate over, although they require larger amounts of data, and are also sensitive to OOD. We attribute this brittleness the input representation length. which is characteristic of all tasks except PARITY. No neural networks beyond an MIP were tested. It is known that LSTMs and RNNs excel at these tasks (Butoi et al. 2025), albeit also require significant data volumes.
B DETAILED BACKGROUND
B. PAC LEARNING
The original framework from Valiant (1984) centres itself the learnability of the concept class, rather than the learner. We reproduce it here and compare it to our rephrasing to describe generalisa- tion. For more thorough discussions on this framework, see Kearns & Vazirani [1994]. J. For formal, full description of in-context learning within the context of PAC learning, see Wies et al. (2023).
Suppose we wish to model a binary classification phenomenon with features assumed be drawn from some nonempty set X C {0. 1)m (the instance space). This phenomenon is labelled with function (the concept) c: X + 13 A set of concepts C {ci...., C& } is called concept class, A learning algorithm is then tasked with classifying samples ~ P, where P is supported on X. It selects a hypothesis (another concept) such that
error(h) = Pr Pr (c(x + h(x)].
(6)
z>p
To learn, the algorithm is given access to a function O: C X + {0, that provides i.i.d. samples with some distribution D. Then, concept class C over X is PAC-learabbe if an algorithm outputs an h E C such that
Pr [error(h) (h) I 1d21-6
for all e E C, any P. and E (0, 1/2) and 10,1/2), with an observed subset built with O. The algorithm is required to run in poly |c|. 1/6, Where the size |c| is the smallest way to represent e under a chosen map R: E + C. Stochasticity is accounted both calls to and the learner's is internal state.
Our framework has five core differences:
1. The learning algorithm a machine learning model.
2. The selected hypothesis is the learner's 's weights as function of the input, f(zx). Namely, accounting for autoregression, [(2) for z f(#==1).
3. The 'access' to O is replaced by preconstructed dataset observed during the prompt call.
4. We reframe Equation to work on the average empirical error of dataset, to align it with contemporary evaluation methods.
5. We replace the concept class C and the selection of said concepts with single function This can shown to be equivalent by composition by noting that e can act as the selector for the concept class C.
X can also be an Fuclidean space, X C Rd Concepts may also he equivalently seen as subsets of X.
19

---

Published as a conference paper at ICLR 2026
The last difference renders framework imprecise, but not weaker, when compared to standard PAC learning. PAC learning is known to have certain limitations. For example, deterministic finite automata and context-free grammars cannot be learnt in the standard PAC setting (Pitt & Warmuth, 1993 Kearns Valiant 1994] Niyogi 2006); and contemporary neural networks has been shown to be able learn beyond seen concept classes (see, e.g., Kalakauwauhh al. 2022). Our reframing avoids these limitations by removing the dependence on specific task (concept class) and instead assumes that a subset of X is labelled with some c, in line with the expectations on current LLMs. More importantly, neither of the points above detract from the definition of learning as generalisation.
B.2 AUTOMATA THEORY AND FORMAL LANGUAGE THEORY
A formal grammar 9 is a collection of strings from an alphabet N and production rules (maps) between them. S and N are sets of non-terminal and terminal symbols, and the empty symbol, respectively. These rules form a set (language) L. Grammars may be categorised based on their caaplexity-nameele the production rules -sing the Chomsky hierarchy. Each class is proper subset of the other.
The classes of automata (functions) needed answer whether phism between them and the classes of formal grammars in the Chomsky hierarchy. More complex languages require more complex automata, whose classes are also supersets of the others. This is because every automaton, with the exception of the Turing machine, is limited in a certain way. For example, FSA read the input (tape) symbol-by-symoo in one direction and single pass; change their internal state between accept and reject: and return either when the read is complete. They thus can recognise precisely the set of regular languages. Pushdown automata, or PDA, are equivalent to FSA but with a memory stack added, and can recognise context-free languages. See Appendix F for classifications of our tasks within the context of both automata and formal language theory. Remark that LLMs can perform recursion and feed their 'pseudo-state (namely, the token outputs) back into itself. This allows maintain a memory stack, albeit not fully controllable hence why CoT effective point: it templatises the memory stack.
for string x have isomor-
20

---

Published as a conference paper at ICLR 2026
C ALTERNATE MODELS OF LEARNING
In Section 3.1 we noted that PAC learning is the predominant model for learning in computational learning theory, and, specifically, learning theory. is also frequently used when modelling language learning (see, e.g., Niyoii 2006). However, it is not the only model of learning. or the only accepted definition of learning. For example, Gold's inductive inference framework (Gold, [967) is also sometimes used to model other language acquisition and learning (Johnson) 2004). and forms the basis of algorithmic learning theory.
Frameworks outside of computer science, such as those used in psychology and education, are also designed to formally define and measure learning. While the definition of learning has broad agree- ment (the ability to behave in given way based on experience; |Schunk 2012), measurement proto- cols differ amongst theories.
In this section we discuss alternate models of learning, from inside and outside of computer science. Specific algorithms and approaches, such as the Triggering Learning Algorithm (Gibson & Wexler 1994) pack-propagation are not covered here they may be framed in model of learning (e.g.,in terms of PAC learning |2y6g For non-computer science models, we focus on the two major theories with well-defined measurement protocols: behavioural and cognitive. We do not cover other frameworks, such as information theories of learning (Shuell 1986), since they explicitly require the learner to encode and retrieve knowledge for arbitrary periods of time, and this is not the case for ICL.
C.1 GOLD'S INDUCTIVE INFERENCE
In the inductive inference framework, the learner observes an infinite sequence of examples 21, E from some language generated by some grammar G. The sequence may contain duplicate elements. Let G(rx) be said sequence up to the hth element. It is said that learner f: E - E learns (and thus 9) in the limit if, based on a chosen metric d: E E + [0, 1].
lim k
= O.
(8)
Namely, it is said that f has learnt G (in the limit; in the Gold sense), if after k instances, the learner will correctly identify all observations from L. Remark that the choice of distance directly affects the definition, and that this learner only observes positive examples. In this framework. it follows thus that learning language (r. concept in PAC learning) is equivalent to fo-eventuullyypeefeel reproducing the grammar. In contrast, in PAC learning, learning is probabilistic and can only be done w.p.1 in the limit.
follows then that the main criticism this framework is that it is too rigid, as does not allow the learner to make mistakes. Reframings to allow for looser distance or threshold number of errors are effective at allowing more pragmatic learnability (Wharton 1974). Other variants, such as query learning (Angluin 1988) have also been shown to be equivalent to this framework (Lange & Zilles 2005). Nonetheless, they are weaker than the original statement (Niyogi 2006).
From theoretical perspective, Gold 1967) ) showed that the languages represented by deterministic finite automata and context-free grammars are not learnable in the limit. As noted Appendix ( PAC learning is also limited in its ability to learn certain formal problems. However, it is possible to create variants of one framework to learn languages that cannot be identified the other (Nyyogi 2006). Thus, Gold's and Valiant's frameworks are distinct and non-equivalent.
In the context of our work, we are more concerned about measuring learning. Since Equation 6 is a distance metric, may our reframing equivalently in the Gold sense, and setting (probabilis- tie) threshold 6 as before,
lim Pr 100
((za), = 0.
However, the statement around the probability of this threshold holding (Equation would be missing, and hence the conclusions that we could draw are weaker.
21

---

Published as a conference paper at ICLR 2026
C.2 BEHAVIOURAL THEORIES
Behavioural models of learning focus on how much feedback (reinforcement of correct guesses) as well as the developmental status of the leamne. While the autoregressive mechanism could account for feedback, the developmental status is more difficult to approximate. We argue that this could be considered the pretraining process. We include a small experiment with an untrained model in Appendix D
In the connectionist model of learning (Thorndike) 1913), learning is given by associations between experiences, and through trial and error. Experiments to measure this theory were carried across multiple months (e.g., participants had close their eyes and draw a line of a specified length hundreds of times for several days). From our work's perspective, measurement was done within the same P.
Another well-known model is that of operant conditioning Skinner (9338). This framework adapts closely to our work. Its full formulation includes the process by which learning occurs (c.g.. condi- tioning, reinforcement, etc), and may be found in Schunk (2012). In this section we limit ourselves to describe the measurement itself. This due through Skinner's s definition of generalisation, which involves the repeated response to input; and discrimination, which is varying the specific response based on the input. The core problem with generalisation this theory is that, since learning relies on reinforcement, responses cannot be given withou! having been given previously said reinforce- ment (i.e., there cannot be zero-shot learning). The explanation for humans is that they rely on the composition of previously-learl behaviours, and thus zero-shot learning may occur. For LLMs, this could also be argued based on the 'developmental status' of these learners: namely, the pretraining itself. Discrimination is also measured through zero-shot learning: namely, providing an appropriate response to an instance after being given general description of the task.
Fitting LLMS into Skinner's framework means that generalisation is measured through repeated presentation of exemplars (and their correct labelling). Zero-shot in this case means observing only the instance of the problem and not having any feedback. Concretely, this was zero-shot modus ponens; which, as we observed, had near zero-performance across the board-as expected since the tasks ablated for memorisation and the learner had no reinforcement. On the other hand, discrimination requires the task description itself. This is more akin to zero-shot learning in the Description, CoT, and DE scenarios; and, to a minor extent, word salad and SoT.
What ties all these frameworks together to PAC learning is that theories have a certain tolerance to learner error, which in turn makes them closer to this framework than to Gold's.
C.3 COGNITIVE THEORIES
In behavioural theories, learner variation studied by evaluating the impact of the environment and the previous reinforcement steps. In contrast, cognitive theories emphasise how the differences be- tween the prior knowledge of the learners, along with their own internal processes, impact learning- They also distinguish between learning and performance [Schunk (2012). This means that, for ex- ample, in these frameworks, a learner could acquire latent knowledge by observing the environment although never actually obtaining reinforcement. From the perspective of our work, this is visible in all prompts minus modus ponens, except that only in the zero-shot setting. is well-known that the way by which the learner is exposed to the task (e.g., demonstration, explanations, etc.), well as the feedback (success) directly affects the effectiveness of the learning process (Schunk 2012)). Our work accounts for the first aspect (e.g.. by the prompt style itself), but not the second. These, however, are more akin to how a reasoning model outputs text.
Ultimately, cognitive theories measure learning through success after reinforcement (or without, in the case of latent knowledge), as well as retention. Our work partially measure these. Same as in the behavioural theories, the tolerance error makes these frameworks closer to PAC learning than to the inductive inference framework.
22

---

Published as a conference paper at ICLR 2026
D RELATIONSHIP TO NATURAL LANGUAGE
D.1 IMPACT ON CONCLUSIONS
We noted throughout our work that the synthetic nature of our work could underestimate the perfor- mance of an LLM on realistic scenarios. The choice of synthetic data was to ablate out the LLMs' intrinsic knowledge, and instead focus on their ability infer features from the observed P. also allowed us to control every aspect of the data-from contamination to ID/OOD-to ensure fully 'sanitised" experiment suite. This practise known to be useful to study generalisation (Power al., 2022).
However, learnings based on synthetic data do not necessarily fully translate to natural- natural-language scenarios. This is because synthetic data setups overlook considerations ubiquitous to natural lan- guage, such as compositionality, feature distribution, and ambiguity. These are all encoded-in one way or another-in in pretrained LLMs.
Even when dealing with natural-langure problems which are fully unseen by an LLM (for example, language isolate), computational complexity comes into play. It is known that, under certain assumptions, natural language lies somewhere between context-free and context-sensitive grammars (Jäger & Rogers 2012), which, in turn-as per our results and the theoretical work from Section } makes these problems difficult to solve without any prior knowledge. On the other hand, the vast literature and success stories of LLMs suggest that further empirical work required to characterise what these models do, not what they could do.
Thus, our results are limited the ability of ICL draw conclusions from the data's features alone, eschewing any potential semantic priors induced by natural language. They must be interpreted with caution when considering their extension to natural language, particularly in tasks and evaluations which could rely model's ' latent knowledge.
D.2 IMPACT ON RESULTS
To follow the point on latent knowledge, we remark that a full evaluation of ICL should account for inductive bias-free learning. This means that the models must not have seen any of the data before, including natural language 55] In line with the empirical spirit of this work, and in order to confirm this, we ran the same experiments for PARITY, Pattern Matching, both Vending Machines, and Hamiltonian in all shots and 6. The learner was separate, randomly-initialised model (Qwen 1.B Instruct; Yang et al. (2024). The model had accuracy zero every task and setup, consistently showing responses such as "itian E uuzzle and * K 7) tk and thus having 100% error rate regardless of shots. brief examination of the finetuned model revealed consistent, albeit not necessarily accurate, responses (e.g., 61.6%, 73.5%, and 52.9% for modus ponens ID at 20 shots in PARITY, Pattern Matching, and Reversal, respectively).
The above aligns with results from the literature and our work, but also opens further areas of research. Namely, is known that priors are needed for ICL (Chang & Bisk 2025 Hu et al. 2025). Also, within our setup, we found that an LLM's linguistic capabilities do not impact ICL (ref. word salad and SoT), and that a sufficiently large number of exemplars suffices. gradual comparison of the learning (pretraining) process of an LLM with respect to its ability understand data features would provide much needed information as to which extent the natural- -langal- data impact ICL as learning mechanism.
'Recall from Appendix
C that, from the perspective of some theories, full zero-shot is possible.
23

---

Published as a conference paper at ICLR 2026
E FULL TASK DESCRIPTIONS
In this section we describe each task more precisely, and are summarised in Table 3 For concrete code examples, see the repository and Appendix H
PARITY Decide if a given binary string (0, 1}* has an even number of zeros. Here, Σ = {0. 1} and the automaton decides whether to append z Σ based on the transition probabilities. Emission is given by fixed probability of 1. Unlike most problems, PARITY's average length per ó was To.
relatively fixed, at 19 characters. The difference was the probability of each character occuring in sequence. PARITY is classified as a regular language and modellable with an FSA.
Pattern Matching Decide if a pattern abeabl is a substring of a given string x C Σ", where Σ = (a, b,c. The automaton is similar to PARITY's, with transition probabilities fixed by state e E 2) but dependent on 8. Strings with less than eight characters where rejected. In OOD scenarios, the sequence length grew to over five times the ID length. Pattern Matching is classified as a regular language and modellable with an FSA.
Reversal Given a string of the form Lrr, the goal is decide if l equals the reversed r, / r-1 The start of r is given by the delimiter # Same as PARITY, the selection of every string depends on transition probabilities 8. In this case, the alphabet was picked not be grammatical, > {gix, chite, %, ltintprk, / start) U (#) where 1,r C ( In OOD scenarios, the sequence length grows to over seven times the ID length as 5 increases. This variant of Reversal DCF language modellable with a PDA (Butoi et al. 2025).
Stack For a final string f,, starting string 80, and series of operations Op on a string, decide sy = Op(so). The operations simulate stack (push/stop/pop) and may may not be grammatical (e.g., stack overflows). Same as PARITY, the selection of every string depends on transition probabilitics 6. Here Σ = {0, 13 U {push, pop, stop, empty), s Sg {0, 1 and Op C " 1)ah In OOD scenarios, the sequence length grew to almost three times the ID length as increased. Stack is a DCF language modellable with PDA (Delétang al. (023).
Hamiltonian Given a directed graph in adjacency matrix form G, and path p. decide if p is Hamiltonian. Under this setup, this problem is classified as regular language and modellable with an FSA (Barrett et al. 2000). In OOD, the edges, and not the vertices, grew to up to 20% the original length. Consequently, the character description of the graph grew by up 32%, from 695 characters to 851.
Maze (Complete and Solve) Given a maze, two segments of the solution path, and a sequence of moves, in Maze Complete the task is to determine if the moves connect both segments. The separation between segments-but not the move sequence-is never longer than three moves. Maze Solve is given the full path and a longer sequence of moves. The task is to determine whether these moves lead to the solved maze (a valid path from start to exit). Both problems are classified as regular languages and modellable with FSA (Barrett et al.) 2000). In OOD scenarios, the maze size became larger, albeit the average path length remained somewhat stable.
Vending Machine (Verification and Sum) Given list of items and costs C. a sequence of opera- tions Op (add balance, purchase item), and initial and final balances bo, by, verify by Op(C)=b, (verification) or compute by + Op(C) + by (sum). For the purposes of this problem, the items and costs were given in natural language: biscuits cost 20, soda costs 25, and coffee costs 15. Here = (+ + +15, +25) U (coffee, biscuit, soda), or, without resorting to strings, the abelian group Arm = (10, 20, 15, 25), +). The first three states denote additions, the named states are subtrac- tions (item purchases), and the last state is the final balance by. Same as PARITY, the selection of every string C * depends on the transition probabilities 8. In Vending Machine (Verification), the learner must assert if the last part of the string, by. equals the sequence of operations. Hence, it is a regular language and modellable with an FSA. Since the strings are always up to length n, 4 is mnitely-generated abelian group, and thus the decision version of Vending Machine (Sum) is DCF language modellable with a PDA: it can be reduced to Stack with homomorphisms between the operations (e.g., push and pop versus add and subtract, respectively). and between the inputs
24

---

Published as a conference paper at ICLR 2026
Task
Label Balance
Average Lengths
Class
PARITY
49, 50, 50, 50, 50
18, 17, 17, 17, 17
FSA
Pattern Matching
50, 50, 50, 49, 50
40, 46, 62, 92, 179
FSA
Reversal
49, 50, 50, 50, 50
86, 186, 220, 312, 567
PDA
Stack
50, 50, 50, 59,
97, 169, 207, 235, 263
PDA
Hamiltonian
50, 50, 50, 50
Graphs: 695, 862, 773, 770. 851
FSA
Vertices: 10, 12, 11, 11, 12
Paths: 24, 27, 26, 26, 28
Maze Complete
50, 50, 50, 50, 50
174, 173, 173, 175, 178 429, 414, 423,459, 498 105, 104, 111, 118, 128
FSA
Maze Solve
50, 50, 50, 50, 50
FSA
Vending Machine (Verification)
50, 49, 49, 49, 49
FSA
Vending Machine (Sum)
Table Label balances (as an average of positive entries) and description (string) lengths for values of 5 {0, 0.2, 0.45, 0.65, 0.85). Every length depends strongly the design of the automaton: some lengths grow much more slowly than others (e.g., PARITY versus Reversal). Other depend the complexity of the task, opposed the input description length. For example, Hamilto- nian maintains a relatively stable average number of vertices, but the connectedness of each graph decision problem.
increases with d. Vending Machine (Sum) classed here because
(A 's set and, say, {00, 01, 10, 11}). In practice, the number of possible outputs is finite (albeit very large), but it requires the learner to keep track of a state. both OOD scenarios, the sequence length became longer, by up to 20%.
25

---

Published as a conference paper at ICLR 2026
F DETAILED METHODOLOGY
F.1 LLM CALL PARAMETERS
We tested four LLMs: GPT-4 Turbo, GPT-4o, Mixtral 8x7B instruct v01, and Phi-3.5 MoE Instruct. Details for each model are in Table
Model
Description
GPT-4 Turbo*
OpenAl model with context window of 128k tokens. Vorsion: GPT-4-0125.
GPT-4o
OpenAl model, higher-performing when compared to GPT-4 Turbo, and with 128k context window. Version: GPT-4-0125 fixture-of-experts model with 128k context window and 6.6B active parameters.
Phi-3.5-MoE-Instrue
Mixtral-8x77 -xh7B instruct v01
Mixture of of-experts model with 32k context window and 12.9B active parameters.
Table Models evaluated. For the models marked with x, details regarding architecture, parameter size, pretraining strategies have not been disclosed. All models are instruction-pretrainess
All models were called with temperature set to zero and maximum return tokens of 3 for all prompt- ing strategies, except CoT (1,024) and the system prompts generated by APO (512).
The APO algorithm was called with batch size of 1024, beam width 4, and search depth of
All work was done on a Standard ND40rs v2 instance in Azure, which is equipped with eight NVIDIA Tesla V100 GPUs with 32 Gb of memory each. Calls were made using either the Azure Open AI API (OpenAl models only) or calling directly the models on the instances. Every model was called up to five times to account for any potential parsing errors or rate limitations from APIs. The data analysis was carried out consumer-grade laptop.
F.2 BASELINES
The baselines were implemented in scikit learn (Pedregosa et al. 2011). For all tasks, the parameters were left default and used a random seed 13213. For every entry the string-based representation was mapped to integers mapped to Operators (e.g.. '+" or 'pop') also mapped to integers. Since most models required tapes of the same length, empty cells were mapped to - 1000. No simulations of state (e.g., the state of the stack after push) were included in the tape.
That is, for, example, 'Itintrr'' from Reversal was
26

---

Published as a conference paper at ICLR 2026
G DETAILED RESULTS
G.1 MAIN RESULTS
The full results of main results are in Figure 3 It can observed from the prompts that LLMs generally present the same average per-task behaviour, with minor changes depending on the prompt. In Table we present the results per LLM and task excluding Vending Machine (Sum).
HLSTT ACWRY Mado OARd
HATTT
PUST sere
www
branal
till wammuim
www wwwpiraaimmiin
10l Wipaatill
Markdurt Cid Dow
Madfer Auunay (ath
M0
Mestaroi Cnent
M01
Dal Bor
Figure 3: Complete set of performances per problem, including averages at the top. Observe how the averages do not necessarily correspond to the performance per-moder per-promp per-task. Con- sistent behaviours are that CoT not robust to OOD, and that tasks on average present the same approximate behaviour regardless of prompt.
27

---

Published as a conference paper at ICLR 2026
Prompt
Turbo Slope
GPT-4o
Phi-3.5
Mixtral
Avg. slope
Acc.
for
Shots
Modus Ponens
14.6
31+25
12.7
47+-22
5.9
56+10
5.7
53+110
9.1+2.9
Description
3.3
61+:5
1.5
63+3
6.2
55+11
9.8
51+21
1.0+1.9
DE
11.6
34+21
13.5
47424
12,9
43::2
11.7
47:22
5.2+1.9
Word Salad
6.7
$71112
2.3
62.1
5.1
57110
10.3
51:211
12.313.1
APO
4.2
50.17
1.8
60.1
0.8
4911
8.2
39.15
6.1.1..0
CoT
2.1
21:44
3.6
26.17
-0.1
27.1
2.0
22.15
3.6.1..33
5
Modus Ponens
-0.3
31
-0.6
47
-0.6
56
-0.3
53
-0.4:10.4
Description
-0.5
61
-1.1
63:11
-0.4
55
-0.2
51
-0.6=10.4
DE
-0.6
-0.1
-0.3
-0.3
47
-0.5=0.6
Word Salad
-0.5
57
-1.1
62111
-0.6
5741
-0.1
51
-0.3+0.3
APO
-0.8
5011
-3.1
6014
-1.5
4912
-1.0
3911
-0.620.77
CoT
0.0
21+1
-0.7
26+1
-0.2
27
0.3
22
-1.5++19
Table 5: Slopes and accuracies for every LLM, averaged over prompts and tasks, excluding Vending Machine (Sum). On the rightmost column is the average slope for all LLMs. Rows in bold (word salad and SoT) are not factored in our main results, but discussed in Section 6.1 The numbers changed when compared Table 2 but substantially, thus leaving our results unchanged.
28

---

Published as a conference paper at ICLR 2026
G.2 GRAINED BEHAVIOUR
As mentioned in the main section, when breaking down the results per-prompt and per-task, the LLMs had (1) similar behaviours over the tasks, but (2) inconsistency over the task type.
Behavioural similarity was given by the LLMs having low but similar accuracy task-by- task and prompt-by-pront
LLM Average Performance Trends Per Prompt
basis: all prompts had positive slope and low relative differ- ence among them (Figure 4 left). Indeed, the per-prompt shot slopes, averaged per LLM, were 8.3.13.9 (modus ponens), 4.4 (de- scription), 4.3 (DE), 5.6 (APO), and 3.3:2.4 (CoT) (Table 2b. The average of the slopes over shots is 5.241.6. We can hence ob- serve that there was low variation (a) between the type of LLM and the prompt over all tasks, and that the overall trend for all models, tasks, and shots is positive. An OLS fit over the per- shot indicated that the model gap, as the shots increased, narrowed: -2.6 This is visible the image to the left, where the mod- els start with a large gap on every task (namely, word salad and modus ponens), which narrows as shots increase. It is worth noting how CoT has a slight improvement, as noted earlier in its slope, but it remains relatively even when compared to higher-pent gigher-perfomming prompts (e.g., APO, DE). Indeed, the dotted lines in the image to the left, denoting the a over the slopes, indicates that most prompts progressively narrowed their differences in performance, although, again, CoT remained relatively steady. At a minor extent, this gap on average also narrowed in aggregates over 8: -0.
Stus
Figure 4: Averaged over all tasks and models, all prompts have a positive slope (5.2:t1.6) over shots, and a narrowing gap in their (-2.6=0..5.
Inconsistency over the task visible after observing that related tasks had gaps in peak perfor- mances: 31 % (Pattern Matching versus Maze (Solve)), and 12% (Reversal and Stack; Table This particularly important given that all-purpose solver (e.g., a universal FSA) should be able to, theoretically, have perfect performance on all tasks of the same class (r. regular languages). While stretch expect that from an LLM, it is worth pointing out that their general-purpose general- isability is hence (naturally) limited. It then follows that ICL as a learning process depends strongly on the features observed in-distribution. We cover this further in Section studies focused on evaluating this hypothesis.
The remaining ablation
29

---

Published as a conference paper at ICLR 2026
G.3 ABLATION: IMPACT OF LEXICAL FEATURES
Word salad prompts started with low, and sometimes zero, accuracies. In the limit, however, all prompts matched the average best-of non-salad performances up o, with the exception of Re- versal and Vending Machine (Sum). In the case of PARITY, Pattern Matching, Maze (Complete), and Vending Machine (Verification), the match was within a/2 (Table 6). This improvement was fast, with slopes of 9.8, 12.1, 11.6, and 9,8 (Turbo, GPT-4o, Phi-3.5, and Mixtral, respectively), for an average of 11 116..6. Compare with the slopes for description (4.4+2.22) DE (4.5+22.4), and modus ponens 38.3.. On average, word salad prompts were the most robust to 5, with val- ues of -0.2.10.3 (versus -0.4 -0.5+0.6, and -0.4:10.4, respectively), albeit were within the baseline o. See Figure 5 for side-by-side depiction of the prompts with respect to their non-salad equivalents (description and CoT).
Problem
Highest
Lowest
Highest (Word Salad)
Shots
PARITY
80
100-APO
16=20
2-m.p.
80
100
Pattern Matching
94.11
50-DE
24::20
5-CoT
92.13
Reversal
61:111
100-CoT
20:121
2-m.p.
51:11
100
Stack
731.14
50-CoT
20:121
2-m.p.
56.113
100
Vending Machine (Ver.)
81:12
10-CoT
22:222
2-m.p.
78 =
100
Maze (Complete)
77:5
100-m.p.
91:16
2-m.p.
7416
100
Maze (Solve)
6315
50-desc.
17:22
0-APO
544 6
50
Hamiltonian
89+-2*
100-dese
29-18
0-CoT
68 + 20
20
Vending Machine (Sum)
16
5-CoT
O-DE
+
100
Table 6: Highest and lowest accuracies, averaged by model. An asterisk denotes an average over fewer models (always excluding Mixtral); and means that there were multiple ties. Highlighted in grey are the prompts where word salad match within the average best-of accuracy from the non-word salad prompts, and blue these within a a/2. most cases, the match occurred at 100 and 50-shot, except in Hamiltonian, where the highest best-of was attained at 20 shot.
Unlike word salad, SoT had a major impact on accuracy. and had the lowest average performance over shots (23=4) in any prompt. This was due SoT's high parse error rate over almost all shots. In contrast, description had near-zero error rates, and modus ponens and word salad quickly converged to zero. Overall average shot and slopes in SoT hovered around zero (1.6+:2.2 and 0.0.00.6, respectively). This does not imply the LLMs were unable to solve all problems under SoT. Some LLMs in SoT obtained above-average peak accuracies in certain tasks: GPT-4o in PARITY (63% 100 shots), and Turbo in Stack (76% at 50 shots). However, high- gegh-eerfrming problems like Hamiltonian and Pattern Matching had 14 12% and ++ average accuracies, respectively.
30

---

Published as a conference paper at ICLR 2026
Average Accuracy (With Description)
Average Accuracy (Word Salad)
Average Accuracy (CoT)
Averagy Accuracy (ooS)
Figure 5: Average over all LLMs and tasks for the non-salad (left) and salad (right) prompts. Description-based prompts rarely performed poorly zero-shot for all LLMs but Mixtral, while word salad versions required five shots (Mixtral), ten (GPT-4o). more. However, word salad prompts eventually reached equivalence with their baselines (Table 6). (Hamiltonian, Maze (Complete) and PARITY) the prompts matched DE and modus ponens at be- tween 10 and 100 exemplars. On the other hand, CoT and SoT had different behaviours: CoT had an (average) modestly increasing trend which was not reproduced in SoT. However, this is an aggre- gate: tasks such as Reversal had the same brittleness to OOD than their CoT counterparts; and tasks such PARITY showed above-random best-of accuracies some tasks (Table 2}.
high-accuracy tasks
31

---

Published as a conference paper at ICLR 2026
G.4 ABLATION: POSITIONALITY OF EXEMPLARS
In all our experiments, all exemplars were equiprobable and fixed throughout the experiment (un- shuffled). In this experiment randomised the position of the same exemplars within the prompt (all prompts and LLMs; shuffled), and fully randomised the exemplars per call by drawing them i..d. from the training set.
We observed a small variation on accuracy when the same exemplars were shuffled versus unshuffled (Table 7 The latter had lower performances, and larger slopes per-LLM, these were 5.6 versus 5.8 (Turbo), 5.2 versus 7.3 (Mixtral), 4.2 versus 4.2 (Phi-3.5), and 3.1 versus 3.5 (GPT-4o) (shuffled and unshuffled slopes). However, per-prompt, these slopes were higher. The best average accuracies in the shuffled setting were always with the same best-performing prompt from the unshuffled case, and within the reported (e.g., 64-112% shuffled versus 61 11:111 1% unshuffled for Reversal at 100-CoT).
When fully randomising the examples, we only measured and compared GPT-4o (Table 8). Similar to the previous experiment, we observed variations on average and highest accuracies (c.g., 94%, 92%, and 93% highest for fully random, shuffled, and unshuffled. respectively, in Hamiltonian with description) although inconsistent (91%, 92%, and 71% in Stack CoT; 77%, 90%, and 90% in PARITY APO and DE). On average, however, fully randomising the labels yielded lower average accuracy (43%) versus shuffled and unshuffled (48% for both), and lower per per-prompt accuracy.
Prompt
Turbo
GPT-4o
Phi-3.5
Mixtral
Avg. slope
Shots Modus Ponens
12.8
34.122
10.2
44118
5.6
50.:10
50.17
8,914.0
Description
3.6
57-6
1.4
56=3
4.6
49::10
6.3
51=14
4.7 = 2.1
DE
3.6
55-6
1.0
59=2
5.8
49+10
5.8
50+17
4.9+2.5
Word Salad
8.8
28+16
12.1
43+22
11.4
41=21
9.1
45=19
11
APO
4.3
54.18
2.0
57
4.5
50:19
2.1
56-14
5.4 2.6
CoT
3.7
49:17
56
0.6
45::
39411
3.6
SoT
1.5
20-14
2.9
25
0.3
26:1-4
0.0
26:1.
0.5
OOD
Modus Ponens
34+1
-0.5
44
50+11
-0.2
50+1
-0.4 0.3
Description
-0.3
57+1
-0.8
56-1
-0.6
49+-1
-0.1
51
-0.5 + 0.6
DE
-0.4
55+1
-1.0
59-2 2
-0.4
49+1
-0.1
50
-0.5+0.7
Word Salad
-0.5
28111
-0.2
43
0.0
41
-0.3
4511
-0.310.3
APO
-1.0
57=1
5011
56
-0.6.0.6
CoT
-1.1
49112
-2.7
4
-1.1
4511
-1.0
39.11
-1.4.188
SoT
-0.2
20+11
-0.6
25=1
0.0
26
0.0
26 1
-0,2+0.6
Table Slopes and average accuracies for shots and 6, per prompt, with shuffled exemplars. Greyed out are the accuracies where the slope or accuracy was higher than the non-shuffled version from Table but the was higher. In blue are setups with higher accuracy and lower a. Top to bottom: average accuracies per-prompt were 14%, 53=7%, 5318%, 39-19%, 54=6%, 47-6%, and 24..3%
32

---

Published as a conference paper at ICLR 2026
G.5 ABLATION: ALTERNATE DISTRIBUTIONS
Due to cost, this section is limited to GPT-4o. In this experiment we altered P to show different distributions the model. These alterations were:
1. Randomised exemplars every call. This is the same setup from Appendix G.4
2. Fully random exemplars drawn i.ddd from the training set on every call. This is also the setup from Appendix [.4]
3. An imbalanced distribution of labels, showing only positive labels as exemplars.
4. A corpus with uniformly at random labels (both test and train) acting as baseline.
The results are in Table With the exception of the random baseline, all setups showed the ability to learn the underlying distributions: shuffled exemplars and the imbalanced scenario often matched or outperformed the baseline average accuracy over most tasks and prompts, with the latter attaining higher average accuracies and larger 5 and shot slopes. However, the a in the per-prompt accuracies were higher. The baseline had an average accuracy of 41-9%% most prompts stayed within the random-choic 50++5% accuracy, with the exception of SoT (24%).. Remark that this is expected, since every datapoint has the same probability of having any labels, and this is uncorrelated to the features themselves-i.c., unlearnable.
As in all previous experiments, in the limit we observed increasing trends in the shot-slopes and ó-slopes across setups and prompts, with average slopes of 4.3++4.2 and -0..++0.6 (Fig- ure left). These were shuffled setting, where all prompts but DE had improvements. However, this case, the av- erage increased for both slopes: 1.0.00.7 and -0.3 respectively. This was observed on every prompt and every setup, as most setups learnt the problem. Of note also CoT, which showed decreasing shot slopes across all se- tups: -1.1 for imbalanced labels, -1.1 for shuf- fled, and -2.5 for both fully random exemplars and random labels.
Altomate F Avcrage Permrcacc Trend For Prompt 46)
noticeable in the
Figure Average accuracies for alternate P. Most prompts had positive slopes, with the excep-
tion of CoT, which peaked fast and then started decreasing.
Prompt
Imh.
labels
Fully exemp.
rand.
Rand. labels Shuffled
Avg. slope
Shots Modus Ponens
12.6
48:122
8.6
191:14
7.7
38114
12.7
47:122
8.3:13.9
Description
1.9
63=3
1.1
591
0.1
49
1.4
62--2
4,4+2.2
DE
2.1
64=3
0.9
60+22
0.2
49
1.5
63-33
4.5+2.44
Word Salad
13.4
49-22
9.1
30+16
8.9
37+17
13.5
47424
11=4.6
APO
2.3
62
3.3
5816
0.8
49.12
2,3
62.14
5,4.1..6
CoT
-1.1
66-
-2.5
54.17
-2.5
41:1
-1.1
56-16
3.3.2244
SoT
2.9
26-6
2.2
25:15
2.2
24:15
5.1
24.17
1.6.1.22
8
Modus Ponens
-0.5
48
-0.6
29
-0.4
38
-0.6
47
-0.40.44
Description
-1.0
63=1
40.7
59
-0.2
49
40,9
62-11
-0.5+00.5
-1.1
64=1
-0.7
60:11
49
-1.1
63+1
-0.5+0.66
Word Salad
-0.0
49
-0.3
30
-0.0
37
-0.1
47
-0.210,3
APO
-12
62
-0.7
5811
-0.2
49
-1.1
62-11
-0,510.77
CoT
-3.0
56_4
-2.6
5413
-1.3
4111
-2.9
56114
-1.41199
SoT
-0.7
26-1
-0.7
25
-0.7
24
40.4
0.0
Table 8: Slopes and average accuracies for shots and 5, per prompt, on our evaluation of alterations of P. Greyed out are the accuracies where the slope or accuracy was higher than or equal to the non-shuffled version of GPT-4o's predictions; and in blue these where the was also strictly larger than GPT-4o's equivalent (Table 2 but excluding Vending Machine (Sum)). Top to bottom: average accuracies per-prompt were 37+179 53+2%, 54+2%, 37 19%, 5314,, 52-1%% and 25.6%.
33

---

Published as a conference paper at ICLR 2026
G.6 ABLATION: COMPLIANCE VERSUS LEARNING
The distinction between compliance with the prompt (returning parseable output) versus learning the task (returning a correct label) re- quires further scrutiny.
Prompt
MP
Desc
DE
APO
CoT
Compliance
43:110
5317
5316
5211
46118
Learning
5316
5613 5811
5713 5616
This is because, in the extreme case, dataset could be, for example, 99.9% parsing errors and one lucky guess, thus leading to inaccurate as- sessments performance. Hence, we separated parsing errors from mislabelled instances, and re-calculated the averages and slopes. Factor- ing out parsing errors increased the perceived performance an LLM, usually understating overstating magnitudes. This is because it be- comes harder for an LLM to have accuracies below 45% (Table 9 left), and average shot and slopes smoothed out (4.7+3.1 and -0.4+0.2 average, respectively) when compared to compli- ance and learning (r. 5.443.11, -0.5,,.33), thus making-for example-CoT's sensitivity to OOD hard spot (Figure 7).. In turn, this suggests that works should disclose the parsing strategies avoid misleading results.
Table 9: Average accuracy across all tasks and LLMs aggregated by prompt: it is slightly above average when not accounting for parsing errors. Large drops occur otherwise, with increases (up to double) a. This suggests that LLM compar- isons depend strongly measurement.
Average Accuracy (Col; C&L)
Average Accuracy (CoT;
Accursty
Shots
Average Accurscy (Modus Ponens: C&L)
Average Accuracy (Modus Ponens; L)
Figure 7: Comparison of select prompts when measuring reasoning as compliance and learning (left, labelled as C&L and counting parsing errors as mislabels), and only learning (right; not factoring in parsing errors) for CoT (top) and modus ponens (bottom). In learning, CoT's sensitivity to OOD is hard to spot as the performance curves are smoothed out. comparison, when evaluating compli- ance and learning, the evaluation has a smoother performance floor and accounts for the full dataset. Model convergence was still noticcable, as evidenced by the modus ponens plots.
34

---

Published as a conference paper at ICLR 2026
H PROMPTS
We show sample prompts for various problems and prompting strategies. For the full prompts, refer the repository. In Prompt we show the modus ponens and description prompts for PARITY; and in Prompt 2 a sample CoT for Pattern Matching, We also show in Prompts 3 and 4 the CoT and SoT versions of Maze Complete, and in Prompt the word salad version of Vending Machine (Solve).
This task is called PARITY. The strings in PARITY generated from probabilistic automaton. Your job is to learn what the likelihood of a string to labeled 0 or 1, and output the correct label.
In the limit where the automaton is deterministic, if the number of zeros in the input string even, the label is always 1. Else, it is O.
Given the data below, determine what is the most likely label for the given string and output ONLY the label. Data:
Every zumpus is shumpus. Polly is lorpus. Everything that is amenable, kind, aggressive, and grimpus is brimpus. Each impus wumpus and a tumpus. Wumpuses are impuses. Everything that is floral and shumpus is tumpus. Yumpuses are impuses, lorpuses, and sterpuses. Max is dull. Wren is a tumpus. Everything that transparent or a rompus is lempus. Alex is an impus or vumpus. Sally is temperate. Each yumpus is a zumpus. Everything that is fruity and numpus is grimpus. Every zumpus is not discordant. Everything that is windy or a gorpus a vumpus. Every yumpus is gorpus. Everything that is opaque, transparent, or jompus is lempus. Each rompus a lempus. Stella is large and small and a grimpus and a gorpus. Max is a sterpus or a jompus gorpus. Sam is wumpus rompus. Everything that is angry and a lempus is a sterpus. Sally is a gorpus, a shumpus, dumpus, tumpus. Everything that is snowy, sunny, and yumpus is lorpus. Everything that is transparent and vumpus is a brimpus. Everything that is small and vumpus is rompus. Everything that is a brimpus, a shumpus, or a wumpus is tumpus.
dumpus
tumpus. Everything that is bitter and tumpus
000011000001100000000000
0
0010010001100111001000
0
000010000000011000000
0
00001 00001100000110000000000
Prompt 1: Prompts for description (red), word salad (bluc), and modus ponens (grey) for PARITY. In the implementation these are the standard ChatML-forrmatte prompts, so the coloured lines are part of the system prompt, while the grey exemplars alternating between the user input (the binary string) and the assistant's response (the single bit). In zero-shot, the prompt includes specification of the output format ('Give your answer as single integer, and your reasoning in a line. For example:"). The reasoning cut off and does not affect the experiments. The list of words from word salad comes from the ontology by Saparov & He (023).
35

---

Published as a conference paper at ICLR 2026
This is pattern matching task. The strings in this task are generated from a probabilistic automaton. Each string is labelled 0 or depending on whether the pattern "abcabb" is (1) or is not (0) in the string.
Your job is to learn what is the likelihood of string to be labelled or 1, and output the correct label.
In the limit where the automaton is deterministic, if the pattern present in the string, the label is always 1. Else, it is O. Given the data below, determine what is the most likely label for the given string and output ONLY the label.
Data:
Let's think and solve this step-by-step. We read the string character-by-charattee and keep a tally:
We read "a". It is match. Our tally is: Now we move to the next character. We read "b". It is match. Our tally is: ab. Now we move to the next character.
We read "a". It not match. We clear our tally. Now we move the next character.
We read "a" It is a match. Our tally is: a. Now we move to the next character.
We read "b". It is match. Our tally is: ab. Now move the next character.
We read "a". It is not match. We clear our tally. Now we move to the next character. We read "b". It is not match. Now we move the next character.
We read "a". It match. Our tally is: a. Now we move to the next character. We read "a". It is not match. We clear tally. Now move the next character.
We read "a". It is a match. Our tally is: a. Now we move to the next character.
We read "a". It is not match. We clear
tally. Now move the next character.
We read "a". It is a match. Our tally is: a. Now we move to the next character.
We read "a". It is not match. We clear
tally. Now move the next character.
We read "a". It is a match. Our tally is: a. Now we move to the next character.
We read "a". It is not match. We clear tally. Now we move the next character.
We read "c". It is not match. Now we move to the next character.
We have reached the end of the string. The pattern "abcabb" is is not in the string.
So the answer is (
oxb.bhaacccccccaaccccccccccccooe Law.accabbaanuuannnnnnn
Prompt 2: Prompt for one-shot Pattern Matching CoT. As before, the exemplar (grey) contains both the sample pattern and a procodurally-geeeerae both the words in the system prompt (red) and the exemplars replaced by random words. The only things left are the pattern, labels, and the final output format.
CoT response keeping a tally (stack). During SoT,
36

---

Published as a conference paper at ICLR 2026
You are helping complete maze. You will be given maze almost solved, and sequence of moves to finish solving it.
Your job is determine whether the moves correct and will lead to solving the maze solved. You must always output O (incorrect) or (correct).
The path you must complete denoted by uninterrupted "+", and your completion starts at "?". Walls are denoted by "#", and the start and end are "S" and "E", respectively.
The first move you must verify is the one connecting the path "?"
Given the data below, determine what is the most likely label for the given maze and moves; and output ONLY the label. Data:
Solved maze: #S###*#*# #+++# #
#+# #hIft
#+++# #
####+## #
#?++# #
# # #I# #
## #*++++E
Missing moves: down.
Let's think and solve this step-by-step.
We begin at line 0. ThTs line does not contain "?"
We move then to line 1.
This line does not contain "?"
We move then to line 2.
This line does not contain "?"
We move on then to line 3.
This line does not contain "?"
We move on then to line 4.
This line does not contain "?"
We move on then to line 5.
This line contains "?"
The "?" character is at position the line. We will now perform a search on the neighbours to find the path. This has neighbours: ['down'] ] at [(6, 3)].
We select the neighbour (6, 3) ("down") and add it to our buffer. Our buffer is: ['down'].
This has neighbours: [ ['down'] at ()].
We select the neighbour at (7, 3) ("down"") and add it buffer. Our buffer is: ['down', 'down'].
This one has the following available neighbours connecting the path: ['right'] at [(7, 4)).
This has "4" neighbour at (7, 4) ("right"), so it connects to the path.
We add our buffer. Our buffer is now ['down', 'down', 'right'].
We are done!
Our final set of positions is down, and the solution says down,down.right. So the answer is
Prompt 3: Prompt for the CoT version (one-shot, user input omitted) of Maze Complete. red, the system prompt. In grey, single exemplar.
37

---

Published as a conference paper at ICLR 2026
This is string detection task. The strings in this task generated from probabilistic au- tomaton, described in the code below.
Each input is of the form LEFT#RIGHT. Each string labelled depending whether the RIGHT pattern is (1) or is not (0) a reversal of LEFT.
Your job learn what is the likelihood of a string to be labelled 0 and output the correct label.
Here's the code:
ALPHABET ['gffx, "chtte", "%", "Itintprk",
(")
MIN LEN =
def reversal tP)):s
n + states: ALPHABET "final"
tape = []
end_state "stop"
current.state "start"
states [a for a in ALPHABET] [end_state]
while True:
next_state random. rwwdom.chooieeeeeee choices(statess, weiglts=P(cureentsstee)100 if next_state etd_state:
break
else:
tapeaappendnnext state)
current_state next_state
return tape
Given the data below, determine what is the most likely label for the given string and output ONLY the label.
Data:
chttchhteefklinnppksss4555s5 (")) (*)) %%%%% 1.566%%990tiitppkkfccctttecttti
$ 44% S4iii
Prompt 4: System prompt (red) for the DE version (one-shot) of Stack along with a user input (grey). Remark that this setup the alphabet is explicitly defined, as well as the code used generate the output minus the weights for P.
38

---

Published as a conference paper at ICLR 2026
You are vending machine. You are given sequence of additions of balance (+10, +5, etc) a selection (soda, biscuit, or coffee).
Your job is output the remaining balance given the sequence. Each soda is worth 25, Each biscuit is 20. Each coffee 15. When someone selects soda, biscuit, or coffee, the value of the item is subtracted from the balance.
Given the data below, determine what is the most likely halance for the given string and output
ONLY the balance. Data:
loud orange shy, rompuses amenable rompuses lorpuses Max Vumpuses Grimpuses feisty muffled, opaque, Yumpuses rompus, gorpus angry, jompuses bitter sterpus vumpuses, shumpus luminous temperate luminous, Fae windy bitter, brown sweet, dumpuses, grimpus angry hot moderate grimpus, Rompuses lempus
+10,+ 10.bi0iu,, 1500,,55.fffe,,000,10000. 10.1 10.0su 10-- 10,oda,,
Let's think and solve this step-by-step. We start with balance of impus, gorpuses "+10", Rompuses brimpus, aggressive 10 impuses Lempuses impus rainy grimpuses, sunny zumpus, shumpus 10.
spicy, bitter "+10", lorpuses floral, gorpus 10 is tumpus wumpuses numpuses slow overcast, Sterpuses vumpuses 20.
aggressive impuses "biscuit", Each Sterpuses vumpus biscuit liquid mean 20 lempus fast dum- pus, fruity aggressive red, O.
sterpus, metallic "+10", numpus, wumpuses, brimpuses, 10 windy cold zumpuses sterpus zum- puses vumpuses, happy earthy, 10.
fruity tmpuuses "+5", sterpuses, lorpuses, jompuses, 5 brown, or hot, grimpuses Gorpuses wumpus Wumpuses happy 15.
yumpuses, an "coffee", Sam windy vumpuses, coffee tumpuses dull 15 dumpuses sweet feisty Polly brown, shumpuses, 0.
sweet, luminous "biscuit", large moderate brimpus, biscuit dumpuses, bitter, 20 brown zum- puses snowy gorpus Everything numpuses, O. brimpuses discordant, "+5", rompus, pellodi..jomuusee 5 wumpus sweet, Zumpuses zumpus, jompus, opaque lorpus Fae
bitter brown, "+10", bright, tumpus sour, 10 yumpus, gorpus Lorpuses discordant impuses lempuses wumpus slow, 15.
gorpuses shy, "+10", opaque fruity mean 10 Stella Rompuses windy wumpus rainy, happy, jompuses dumpus, 25.
spicy Lempuses "soda", Brimpuses bitter metallic, soda brown, tumpus, snowy, lorpus kind, temperate small moderate O.
nervous, vumpuses "+10", liquid moderate impus, 10 angry snowy bright gorpuses impuses, brown, Lorpuses brown 10.
We read "+10",, so we add 10 to our current balance and we now have 10. We read "+10",
add 10 to current balance and
have 20.
We read "biscuit", so we return a biscuit and substract 20 from our balance and now we have 0.
We read "+10",, we add 10
current balance and now have 10.
We read "45", so we add 5 to our current balance and we now have 15.
We read "coffee", so we return coffee and substract 15 from our balance and now we have
We read "biscuit", so we return a biscuit and substract 20 from our balance and now we have We read "45", so we add 5 to our current balance and we now have 5.
We read "+10",, so we add 10 to our current balance and we now have 15.
We read "+10", we add 10 to our current balance and we now have 25.
We read "+10", so we add 10 to our current balance and we now have 10.
Our final balance is 10. The answer is then 10
Prompt 5: Prompt with one exemplar for Vending Machine (Sum). blue, the SoT version of this prompt; and in red, the CoT version. For brevity, we omit lines for both CoT/SoT outputs. In grey are the lines shared by both prompts: the first line is the user input, and the other two are shared boilerplate for the CoT//oTT prompts for parsing. Observe how the relevant quantities do not change.
39


Reviews:
[{"review_id": "sb1C6OtZL3", "reviewer": "Reviewer_X2GS", "summary": "This paper investigates whether in-context learning in autoregressive models constitutes \"learning\" in the formal sense, using a variation of the PAC framework to define robustness in learning to ground discussion. They run an empirical study with 4 LLMs on nine formal, synthetic tasks to test this. The paper concludes that mathematically, ICL is a form of learning but limited in being able to learn the observed distribution in the prompt, rather than being able to generalize.", "questions": "- In equation 4, is it necessary to rename the datapoints to e_i from x_i? \n- I'm personally curious why there are such large performance gaps between the seemingly closely related tasks", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper tackles a fundamental question and provides an evidence-based answer based on formal definitions\n- The result that best-of-average accuracies are achieved with 50-100 examples in the limit challenges the current few-shot understanding\n- The study's scale and rigor is a strength", "weaknesses": "- The scope of the tasks studied in the paper is rather narrow. I understand the choice to use synthetic, formal tasks to enable a rigorous analysis and minimize reliance on pretrained natural language knowledge, it would be helpful to further sign post the scope of the findings throughout the paper (though the authors do acknowledge this), and add a discussion on which/how the findings may generalize to natural language tasks\n- I'd also love to see further motivation on why the paper adopted its definition of \"learning\", explore alternative definitions, and what that entails for the findings of the paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hVzr6RWlPp", "reviewer": "Reviewer_8VB7", "summary": "This paper seeks to answer whether in-context learning (ICL) in large language models (LLMs) constitutes genuine learning rather than memorization or pattern recognition.\n\nThe authors start by reframing PAC-learning to define ICL formally as a process that can, in principle, satisfy generalization criteria. They then perform a large-scale empirical study (1.89 million model predictions) across four LLMs (GPT-4 Turbo, GPT-4o, Mixtral-8×7B, Phi-3.5 MoE), nine formal-language tasks, and multiple prompting strategies (description, CoT, APO, direct encoding, word-salad, etc.).\n\nThey report that:\n\n1. Increasing the number of exemplars (shots) consistently improves accuracy, reducing model and prompt variance.\n\n2. ICL is robust to training-distribution perturbations but brittle under test-distribution shifts, especially for CoT and APO prompts.\n\n3. Closely related tasks show inconsistent performance gaps (up to 31%).\n\nThe authors conclude that ICL mathematically qualifies as learning but is limited by the autoregressive paradigm’s ad-hoc encoding and its sensitivity to distributional properties.", "questions": "1. Can you clarify what empirical behavior would falsify your claim that ICL “is learning”?\n\n2. Could you provide simpler visualizations (accuracy vs. shots, grouped by task type) and eliminate the overly detailed slope tables?", "limitations": "", "rating": 2, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The study covers a large number of models, prompts, and ablations—possibly one of the most comprehensive empirical ICL analyses on synthetic tasks.\n\n2. The paper tackles an important and widely discussed conceptual question—whether ICL counts as “learning”—and attempts to formalize this using PAC-style reasoning.\n\n3. The inclusion of open-sourced data, prompts, and methodology is commendable and aligns with ICLR’s reproducibility standards.", "weaknesses": "1. The paper repeatedly asserts strong conclusions (“ICL is learning in the limit”) without solid theoretical or causal evidence linking empirical findings to the formal definition. Long sentences and vague phrasing (“it leverages statistical features from the prompt”) obscure the actual mechanism being tested. \n\n2. The results section is dense and under-interpreted. While the experiments are numerous, the findings are mostly confirmatory (more shots → better accuracy; CoT → less robust OOD). \n\n3. Tables 1–2 and Figures 2–4 are difficult to interpret, filled with numeric slopes and variances but lacking qualitative takeaways or error analysis. There is no principled explanation of why related tasks diverge in performance or how exemplar count interacts with task complexity.\n\n4. The related-work section is unstructured and uncomprehensive. For example, it largely omits the extensive empirical literature on understanding how ICL operates (e.g., feature induction, model circuit analyses).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q2n4U6KOBB", "reviewer": "Reviewer_pfQS", "summary": "The paper characterizes learning as generalization to OOD examples. It evaluates the ability of ICL to perform such generalization on a range of tasks. It finds that generalization performance decreases with test examples that are increasingly OOD. It also evaluates this gap under specific conditions, e.g. with and without chain-of-thought reasoning or automated prompt optimization, or replacing natural language with nonsense words.", "questions": "see above for questions", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper poses an interesting question (\"is in-context learning learning\"), and makes an admirable attempt at trying to resolve a philosophical/theoretical question as an empirical exercise. It poses a particular formalism for the question. It does a good job at evaluating on a wide range of tasks and models.", "weaknesses": "I think that the main weaknesses of the paper are wrt to the framing:\n* the paper assumes a specific interpretation of learning. But there are many others. E.g. a more statistical view that evaluates learning as performance on a single distribution (from which we sample both training data and test data). Or e.g. an optimization view  that sees it as error minimization or loss minimization. Some interpretations of learning (and criticisms of the term \"in-context learning\" even require a permanent modification to the model, e.g. via weights). It should be acknowledged that this is just one particular interpretation of what learning is.\n* it is difficult to say what exactly is OOD. (a) it would be great if the paper could more explicitly describe the concrete choices for selecting the OOD distributions Q (if this is in the appendix, there should be a pointer. apologies if I missed it!). (b) I think the decision to use delta as a measure of distance actually really well supports a framing that OOD-ness is on a spectrum. This could be emphasized more. And I would recommend it not be definitely stated that \"ICL performs learning\"\nwhy is the analysis limited to binary classification? this should be raised as a limitation, or otherwise it should be explained why this is more general\n\nThe clarity of the exposition can also be improved. For example:\n* I think it will be especially helpful to clearly distinguish for the reader two things: generalization from pretraining data, vs generalization from the data in context (which is what's studied here). I didn't really understand what the paper was evaluating until section 4. It would be helpful if you said this earlier in the paper, and made that quite clear! E.g. something like \"We evaluate the generalization of ICL by evaluating k-shot learning from context, where the query (which follows the k-shot examples) is either from the same distribution or a different distribution.\" (please refine/correct as needed).\n* I'm confused about this statement: \"That is, it modifies its states at run-time to–ideally–generalise to new observations for any task and any Q\". Why should it also generalize to any task (the Valiant 1984 definition only seems to concern Q)?\n* I believe that `delta` is overloaded\n* section 3.1 \"features are labelled with an unknown function c\" -> perhaps \"examples are labelled…\" would be clearer. I initially misunderstood the setup as each x being just a feature of a larger example\n* in the contributions section, it's unclear what \"accuracy gap\" you are referring to\n\n\nSuggestions for missing citations:\n* citations: many-shot ICL. this paper looked at many of the same questions: increasing k, and also order sensitivity\n* the paper states that it takes \"LLMs as recognisers of unknown expressive power\" – but there's been a lot of formal work on this question. e.g. \"Constant Bit-size Transformers Are Turing Complete\", \"\"Chain of Thought Empowers Transformers to Solve Inherently Serial Problems\" and many more", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SFyGtUUu0k", "reviewer": "Reviewer_CLXz", "summary": "The paper presents a formal view of in-context learning (ICL) under a probably approximately correct(PAC)-style framework, where the prediction rule is treated as a learner conditioned on exemplars and prompt. The authors define an explicit ICL objective (Eq. 4) and argue that although ICL can be interpreted as a form of learning under this framework, its empirical behavior is largely driven by pattern matching associated with autoregressive inference rather than robust rule acquisition.\n\nThe empirical study evaluates four LLMs (two open source; two proprietary) on nine synthetic formal-language-style tasks, including FSA-type and PDA-type languages and simple arithmetic. Several prompting strategies are tested: few-shot with and without task descriptions, chain-of-thought, APO, direct token encoding, and randomized “word-salad’’ prompts.\n\nMain empirical observations:\n- Accuracy improves with additional exemplars across different model families during ICL, which shows model learn to fit exemplars; performance across models and prompt types becomes more similar at higher shot counts. Peak performance often appears around 50-100 shots, instead of at typical few-shot settings.\n- Performance is stable when exemplar distributions and ordering vary within a task, but accuracy degrades under test-time distribution shifts. Chain-of-thought(CoT) and APO prompts show the strongest degradation under these shifts.\n- Cross-task generalization is inconsistent. Tasks with similar underlying structure can differ by up to approximately 31 percentage points in peak accuracy. On roughly half of the tasks, simple supervised baselines (DT, kNN, MLP) achieve performance comparable to or better than ICL.", "questions": "see weaknesses section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- Provides a clear PAC-style formulation of ICL, giving a precise mathematical objective (Eq. 4).\n- Evaluates multiple model families (open-source and proprietary), multiple style tasks and multiple prompting strategies, reducing model-specific/task-specific bias and show conclusion can be applied generally.\n- Quantifies how performance changes with the number of exemplars, showing that gains often appear at higher shot counts (50-100) and use this to decouple the influence of prompt and examplars.\n- Distribution shift analysis to show the limitation of ICL", "weaknesses": "- The evaluated model set does not include recent models(all models were released last year). This limits the scope of the empirical claims, especially for open-source models, and it remains unclear whether the observed patterns (e.g., OOD brittleness) would hold for newer models especially there are many \"reasoning\" models. Although the authors mentioned \"running synchronously a single task for an LLM could take over four months\" but all model providers or routers support async call, which makes the claim of \"synchronously\" not a blocker.\n- Prior work has already discussed the role of data distribution in driving ICL behavior (e.g., [1]). The paper revisits related themes, although in a different synthetic-task setting.\n- The empirical coverage is restricted to single-call autoregressive prompting. The formal discussion gestures toward broader claims about ICL, but the results may not extend to multi-step or multi-call inference settings.\n- Parts of the presentation could be improved: legends in Figures 2-3 are difficult to read and Figure 2 should be before Figure 3. Also there are some typos like \"noting noting\" in Section 3.\n- The task suite focuses on formal-language classification and simple arithmetic. While this yields controlled evaluation, it is unclear how the reported effects transfer to more realistic natural-language tasks with richer structure.\n- Path/graph-style tasks are evaluated without strong algorithmic baselines. This makes it harder to determine whether the model is failing due to true reasoning difficulty or due to prompt/format limitations.\n\n[1] Chan et al., Data distributional properties drive emergent in-context learning in transformers, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h3n4eWkR1P", "reviewer": "Reviewer_ACYp", "summary": "The paper argues that ICL constitutes a form of learning. It first defines ICL in the PAC-style definition of learning and then conducts an extensive empirical study to support the claim. The work contributes towards a foundational understanding of ICL, characterizing ICL as a learning paradigm rather than just prompt-based problem solving. It shows interesting results that performance gaps between different LLMs and prompts reduce as the number of exemplars grow, suggesting that ICL emerges due to autoregression paradigm. Experiments further show that ICL relies on  ad-hoc pattern extraction from exemplars, which causes brittleness for shifted distributions and inconsistency across closely-related tasks. Another interesting finding show that lexical features has limited impact on the ICL performance given enough exemplars.", "questions": "1. In the introduction, the authors state that the study performs empirical studies on sensitivity to pretraining and memorization.  However, no experiments explicitly evaluate these factors. Memorization is partially controlled for through label noise, but its effects are not examined, and no experiments investigate the impact of pretraining sensitivity. Can authors please discuss these implications on ICL performance. \n\n2. Stack and Reversal tasks require saving state representation. In the studied inference-only setup, autoregressive transformers have no explicit memory. Poor performance on PDA tasks may therefore be due to architectural constraints rather than inherent limitations of ICL. It would strengthen the paper by including an analysis on how much of the difficulty is due to transformer architecture versus the properties of ICL.\n\n3. The study enforces strict parsing of model outputs, which I acknowledge is needed for consistent measurement. However, formatting failures are penalized the same as incorrect predictions, potentially mixing output style with task understanding. It would add transparency to the work, if the authors could clarify how much of the observed error is attributed to parsing issues rather than reasoning failures.\n\n4. What does 1.89M datapoints/predictions comprise? Provide more details about these datapoints. Specifically, does it count only the test predictions, or are the exemplars included in each prompt also considered datapoints? A breakdown of the total by task, number of shots, and OOD settings would help readers better understand the evaluation schema.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The work presents a clean and well-controlled evaluation of ICL, first setting up in the PAC-style learning definition and then empirically testing the theory w.r.t. different prompting strategies and task designs. \n2. The use of established tasks and prompt designs makes it easy to comprehend the setup. Further, the choice of formal-language based tasks provide a more principled probe to find if ICL learns underlying rules or statistical pattern matching.\n3. The experimental ablations are thorough and cover a good range of controlled conditions including prompting strategies, exemplar order and distribution shifts. \n4. It is an interesting insight that the exemplar ordering has limited effect, especially as the number of exemplars grow. This challenges the prior claims of success and brittleness in a few-shot setting. \n5. The inclusion of traditional baselines like kNN is important, which it often overlooked by many ICL studies.\n6. The paper is well written and easy to follow. The study contains all details in order to reproduce the results including prompt designs, call parameters and code.", "weaknesses": "The study claims that ICL emerges from a combination of prompt input and model’s intrinsic knowledge encoded in the learned weights. However, the experimental setup uses synthetic symbols with no semantic grounding. This restricts the model from leveraging its pretrained knowledge, which is a key component of how ICL functions in real-world natural language LLMs. Since the tasks in this study rely on artificial alphabets and rule-based structures, the findings may underestimate the ability of LLMs in semantically meaningful contexts, where stored knowledge plays a role during inference. Please discuss the implications of this design choice for generalizing the results to language-based ICL scenarios.\n\nMore questions and weaknesses are included in the Questions sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)