{"id":"ab4c2518-087d-4f81-bd12-0599b61da75d","arxiv_id":"2501.02825","paper_version":6,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"On randomly sampled 3-state DFA language tasks, foundation LLMs underperform n-gram baselines under pure in-context-learning prompts.","lead":"Large language models score below simple n-gram counters when asked to learn randomly generated mini-languages from examples in the prompt, on both completion and next-token tasks. The finding gives a reusable way to build contamination-free reasoning benchmarks and argues that in-context learning is weaker than it appears on unfamiliar, simple language patterns.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The load-bearing assumption is elicitation: large prompt-conditioned swings and missing COT data for most models leave open that a different ICL-only prompt would beat the n-gram baselines.","rationale":"Good-faith reading: the paper is a clean empirical measurement, with transparent baselines, confidence intervals, significance tests, and an honest limitation statement. The measured accuracies are not in dispute. The issue is the inference from those accuracies to a general claim about ICL. The strongest version of the claim—LLM ICL is weaker than n-gram statistics on randomly sampled DFA languages—can only be supported if the prompt set fairly represents the ICL capability of each model. The manuscript's own Table 2 is the best evidence that the representation is fragile: the same model can change by about 20 points when the prompt changes, even before any structure is revealed. The control-prompt results (DFA-COT, RED-GREEN) show this is not a capability ceiling, but those prompts are not ICL-only because they disclose the latent mechanism. The paper deserves credit for explicitly acknowledging the finite-prompt limitation and for reporting prompt sensitivity, but the acknowledgment does not remove the load-bearing nature of the assumption; it just makes the conclusion conditional. The additional inconsistency—open-weight models evaluated only with BASIC while the abstract claims both next-token and chain-of-thought results—reinforces that the empirical support for the broadest wording is thinner than it appears. A systematic prompt search targeting ICL-only variants is the natural check: it would either turn the conditional conclusion into a robust one or reveal that the measured underperformance is an artifact of the specific prompt family. Until that check is run, CONDITIONAL remains the right verdict, and my read does not move it.","tokens_in":30948,"tokens_out":7665,"duration_ms":79271,"concrete_test":"Run a pre-registered ICL-only prompt search on gpt-5 and o3-mini for the Transducer task. Use the same 30-example instances and no grammar/DFA/room information; vary instruction phrasing ('predict the next output', 'continue the annotated sequence', 'few-shot next-token prediction'), separators (commas, spaces, newlines), example order, and answer tagging, for roughly 20-30 variants. Select the best variant on a development set of 30 DFAs, then evaluate it on 100 held-out DFAs and compare with the 4-GRAM T baseline (91.1 mean). If the best ICL-only prompt reaches or exceeds 91.1, the paper's claim that LLM ICL uniformly underperforms n-gram models is refuted; if all variants remain below the 4-GRAM confidence interval, the elicitation concern is substantially mitigated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central move is from 'LLMs scored below n-gram baselines under two prompt formats' to 'LLM in-context learning is uniformly weaker than n-gram statistics.' That move requires that BASIC and BASIC-COT adequately elicit each model's ICL ability. The manuscript concedes in Section 4 that 'no finite set of prompts will be fully sufficient to capture all possible model behavior,' and Table 2 shows the same model moving by 10-30 points across prompt formats (o3-mini on Transducer: 72.8 BASIC, 86.1 DFA-COT, 92.4 RED-GREEN; gpt-5: 83.6 BASIC vs 96.7 DFA-COT). The control prompts reveal problem structure, so they do not count as ICL-only, but they demonstrate high sensitivity to instruction format. A second, independently verifiable gap: Table 2's caption states that only BASIC was used on the open-weight models, yet Section 4 says main results are the maximum over BASIC and BASIC-COT and the abstract claims underperformance 'both when used as next token predictors and in chain-of-thought.' For most evaluated models, no chain-of-thought result exists. If a reasonable ICL-only prompt (no structure disclosure) reliably closes the gap to 4-GRAM, the headline conclusion fails; absent such a search, the underperformance is conditional on the prompt set.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces two benchmarks for evaluating in-context learning (ICL) on randomly sampled 3-state DFA languages: a sequence completion task and a transducer next-token prediction task. With 30 in-context examples per instance, it compares open-weight and proprietary LLMs under BASIC and BASIC-COT prompts against parameter-free baselines (random, common-suffix, n-gram, brute-force). The main findings are that on sequence completion all tested LLMs fall below the 2-GRAM S baseline, on transducer all tested LLMs fall below the 4-GRAM T baseline under the tested ICL-only prompts, and comparisons against 4- to 6-gram baselines are statistically significant. The paper also reports that chain-of-thought rarely helps on the transducer task, that control prompts revealing DFA structure let reasoning models such as gpt-5 and o3-mini reach near-brute-force transducer accuracy, and it includes a detailed case study on the sum-modulo-3 DFA. The authors conclude that LLM ICL is not competitive with primitive n-gram statistics on wholly unfamiliar language reasoning tasks.","tokens_in":31129,"tokens_out":8071,"duration_ms":73922,"significance":"If the headline result held as stated, it would be a clean, well-controlled negative result about the limits of ICL on novel regular languages, with implications for how the community interprets few-shot performance on unfamiliar tasks. The benchmark design has real virtues: random DFA sampling reduces canonical-task bias; the n-gram, random, common-suffix, and brute-force baselines are parameter-free and defined independently of the models under test; the RANDOM S baseline explicitly measures rejection-sampling bias; and the paper includes supplementary controls for temperature, tokenization, non-answers, and example count. Statistical reporting with 95% confidence intervals and paired bootstrap significance tests is careful, and the sum-mod-3 case study is a useful qualitative bridge between LLM errors and n-gram behavior. My main reservation is not with the measurements but with the scope of the conclusion: the abstract and Section 5.2 state a general limitation of ICL, whereas the experiments establish underperformance for two ICL-only prompt formats, and for most models only one format was actually run. This is an elicitation gap, not a circularity or baseline problem.","major_comments":[{"comment":"The abstract claims underperformance 'both when used as next token predictors and in chain-of-thought,' but Table 2's caption states 'we only used BASIC on other models' and Section 4 defines the main results as the maximum over BASIC and BASIC-COT. Chain-of-thought was therefore not evaluated for the large majority of models, including all open-weight and code models and the gpt-3.5 models. The chain-of-thought claim should either be removed from the abstract or backed by running BASIC-COT on the remaining models; as written, the abstract reports evidence that does not exist.","section":"§4, Table 2 caption, Abstract"},{"comment":"The central conclusion that 'LLM ICL is unable to perform well at language inference' rests on the assumption that BASIC and BASIC-COT adequately elicit each model's in-context learning ability. The paper itself concedes in Section 4 that 'no finite set of prompts will be fully sufficient to capture all possible model behavior,' and Table 2 shows large prompt-conditioned swings for the same model (o3-mini on Transducer: 72.8 on BASIC T, 86.1 on DFA-COT T, 92.4 on RED-GREEN T; gpt-5: 83.6 on BASIC T versus 96.7 on DFA-COT T). The control prompts disclose the DFA structure and therefore cannot serve as ICL-only evidence, but they demonstrate that instruction format alone can move performance by more than the gap to 4-GRAM T. Since the headline claim is about a general limitation of ICL, the paper needs either a systematic search over ICL-only prompt variations (e.g., separators, answer format, example ordering, instruction phrasing, or diverse reasoning prompts that do not disclose structure) or a conclusion explicitly restricted to the tested prompts. The Section 6 caveat about the finite prompt set is in the right direction, but the abstract does not carry it.","section":"§4, Table 2, §5.2, §6"},{"comment":"The sentence 'we find that in general all LLMs underperform a 4-GRAM T model' should be qualified as holding for the ICL-only prompt family. In Table 2, gpt-5 reaches 96.7 on DFA-COT T and 96.6 on RED-GREEN T, and o3-mini reaches 92.4 on RED-GREEN T, both above the 4-GRAM T accuracy of 91.1. These results do not refute the ICL claim because those prompts reveal the underlying DFA structure, but the unqualified sentence is easy to misread as a statement about raw model capability that the paper's own data contradict.","section":"§5.2, Table 1, Table 2"}],"minor_comments":[{"comment":"The sentence 'LLMs do not posses the ability to generalize' contains a typo: 'posses' should be 'possess'.","section":"Introduction, first paragraph"},{"comment":"The sentence beginning 'Some have suggested that indicate that LLMs may possess emergent language reasoning abilities' is ungrammatical due to the duplicated 'that indicate that' clause and should be rephrased.","section":"§2.1, Related Work"},{"comment":"The caption should state explicitly that the table reports the maximum over BASIC and BASIC-COT for models where both were run, and BASIC only otherwise; this aggregation rule currently appears only in the body text.","section":"Table 1 caption"},{"comment":"The sentence 'some models requireed the use of 4 in parallel' contains a typo: 'requireed' should be 'required'.","section":"Appendix J"},{"comment":"Section 13 says no new assets are released, while Section 5 says a code zip file is attached; these two statements should be reconciled so that the reproducibility status is unambiguous.","section":"NeurIPS Checklist, Sections 5 and 13"},{"comment":"The abstract's phrase 'underperform n-gram models' is ambiguous because on the Transducer task many LLMs outperform 2-GRAM T; the body's precise claim concerns 4-GRAM T and above, and the abstract should match that specificity.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"To the editor: this is a carefully executed measurement paper whose main weakness is a scope mismatch between the evidence and the abstract's claims. The prompt-elicitation gap is real and load-bearing, but it is addressable either by adding BASIC-COT for the remaining models plus a broader ICL-only prompt search, or by substantially tempering the wording of the central claim. I would not reject the paper. I also noticed a possible inconsistency between the code-release checklist item and the statement that no new assets are released; the authors should clarify this during revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing to know: this is a carefully done empirical study that probably does show LLMs underperform n-gram baselines on 3-state DFA induction from 30 examples under the prompts tested. The stronger claim in the abstract — \"uniformly underperform ... both when used as next token predictors and in chain-of-thought\" — is not fully supported by the data as presented. Most open-weight models were only run on the BASIC prompt, so there is no COT result for them, and the \"wholly unseen\" language conflicts with footnote 1.\n\nWhat's genuinely new: a contamination-resistant benchmark built from randomly sampled 3-state DFAs (78,786 of them), a clean transducer task that avoids the world-model confound, and a systematic evaluation across a broad model zoo. The baselines are parameter-free, the statistics are careful (paired bootstrap, CIs, controls for temperature, tokenization, non-answers), and the appendices are unusually honest about non-response rates and prompt sensitivity. The case study on the sum-mod-3 DFA is a nice touch.\n\nThe soft spot is real but proportional. The conclusion that LLM ICL is weaker than n-gram statistics rests on the assumption that the finite prompt set (BASIC and BASIC-COT, maxed) adequately elicits each model's ICL ability. Table 2 shows 10–30 point swings across prompts for the same model (o3-mini: 72.8 BASIC to 92.4 RED-GREEN on Transducer). The control prompts reveal structure, so they don't count as ICL-only, but they show strong prompt sensitivity. The authors acknowledge this limitation in Section 4 and the conclusion, so it's not a hidden flaw — but the abstract and intro don't carry the hedge. Also, the abstract's \"uniformly\" overstates: for sequence completion, the 2-GRAM gap is not statistically significant for all models, and the significant comparisons are against 4–6 GRAM. The \"wholly unseen\" claim is contradicted by footnote 1, which admits 3-state DFAs are a small finite set.\n\nOne practical issue: the checklist says code is attached as a zip, but the arXiv version doesn't show it. A public repo with a commit hash would settle reproducibility.\n\nWho this is for: anyone working on ICL evaluation, benchmark design, or LLM reasoning limitations. It deserves a serious referee — the core measurement is likely correct and the benchmark is reusable, but the interpretive claims need reining in. I'd accept for review with a request to fix the abstract and make the prompt-elicitation limitation more prominent.","headline":"Solid core measurement, overreaching abstract: LLMs underperform n-grams on 3-state DFA induction under the tested prompts, but 'uniformly' and 'wholly unseen' overstate the evidence.","tokens_in":31760,"tokens_out":2514,"would_cite":true,"duration_ms":24480,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomly sampled grammar tasks show LLMs fall short of n-gram baselines.","keywords":["in-context learning","large language models","deterministic finite automata","regular languages","n-gram baselines","chain-of-thought prompting","language reasoning","novelty"],"falsifier":"The claim would collapse if a single LLM, given only example strings or transducer traces with no mention of grammar, DFA, rooms, or portals, matched or beat the 6-GRAM transducer baseline of 93.5% (or the 2-GRAM sequence-completion baseline of 83.3%) on the same sampled DFAs.","tokens_in":30664,"feed_emoji":"🤖","tokens_out":8697,"duration_ms":80667,"temperature":0.7,"pith_summary":"This paper tries to measure in-context learning (ICL) in isolation from everything an LLM has memorized. The authors generate tasks from randomly sampled 3-state deterministic finite automata, so every language is simple but unfamiliar, and compare LLMs to n-gram baselines that have no world model and no pretraining. Across a broad set of open-weight and proprietary models, with the better of two structure-free prompts chosen per model, LLMs uniformly underperform the baselines: below a 4-gram on the transducer task and, at best, just under the 2-gram on sequence completion. The result matters because it suggests that on entirely novel language structure, foundation-model in-context learning is not competitive with elementary token statistics, even with chain-of-thought prompting.","feed_headline":"Every tested LLM trails n-gram baselines on novel grammar tasks","feed_subtitle":"Even chain-of-thought prompting leaves every tested LLM below a 4-gram baseline on these tasks.","key_machinery":"The machinery is a benchmark built from randomly sampled 3-state deterministic finite automata over a three-letter alphabet. A DFA is the simplest finite-state machine that accepts or rejects strings, and three states is the smallest case with hidden state beyond the accept/reject output. Random sampling from the space of such DFAs is what removes training-corpus bias: the authors deliberately avoid canonical grammars. The argument is carried by comparing LLM accuracy under the best of two structure-free prompts against unparameterized n-gram baselines, which match token clusters rather than build world models. The 3-state design also lets the authors include a brute-force upper bound over all DFAs, showing the tasks are solvable in principle.","core_discovery":"The central claim is that LLMs uniformly underperform n-gram models at inducing simple but entirely unfamiliar languages from examples. The authors test next-token prediction on two tasks generated from randomly sampled 3-state DFAs with a three-letter alphabet: completing a prefix so the full string is accepted, and predicting the next transducer output bit. Taking the maximum over the two main prompt formats, BASIC and BASIC-COT, no LLM reaches a 4-gram on the transducer task, and on sequence completion the best LLM stays just below the 2-gram baseline, with all comparisons against 4- to 6-grams statistically significant. Because the n-gram baselines have no hidden state and no world model, the paper argues the failure cannot be blamed on task difficulty or on missing world knowledge; it is a limit of in-context learning on novel language structure.","pith_inferences":["My inference: the scaling experiment in Appendix D suggests LLM ICL improves with more examples on the transducer task but appears to converge near n-gram-level performance rather than toward the DFA-solving brute-force bound; a direct test would be to plot accuracy against example count past 600 and compare the asymptote to 6- and 7-gram baselines.","My inference: the RED-GREEN framing results show that how a task is described can move performance by roughly 20 points, so the same benchmark could be re-run with an automated search over paraphrased structure-free prompts before accepting a model-specific ICL ceiling.","My inference: because n-gram baselines are cheap and parameter-free, this evaluation design could be adopted as a routine sanity check in ICL benchmarks to distinguish genuine induction from recall of familiar patterns."],"forward_implications":["If the central claim is correct, in-context learning on genuinely novel tasks is weaker than primitive n-gram statistics for inducing simple regular languages.","Strong performance on canonical language and reasoning tasks should not be read as evidence of a general theory of language; the authors conclude that LLMs have learned models of particular languages rather than language in general.","Chain-of-thought prompting does not overcome the novelty gap when the problem structure is withheld, although explicit DFA framing does let reasoning models approach the brute-force upper bound.","The benchmark construction generalizes: sampling languages from larger DFA state counts guarantees by a pigeonhole argument that the sampled languages were not seen in training, providing a scalable way to evaluate ICL.","If current models are the target, the paper's results imply that ICL is not yet a path to replacing all machine learning with in-context learning."],"supporting_citations":[{"why":"This reference supplies the formal language hierarchy the paper uses, placing 3-state DFA languages as Type-3 regular grammars and hence the simplest nontrivial language class.","marker":"Chomsky (1959)"},{"why":"This reference establishes that transformers can perform genuine in-context learning in specially trained settings, motivating the separation of ICL from parametric knowledge in the evaluation.","marker":"Akyürek et al. (2022)"},{"why":"This reference shows transformers trained on 4-12 state DFA transducer traces can in-context-learn regular languages and beat n-gram models, which lets the paper argue its 3-state task is not inherently beyond transformer capability.","marker":"Akyürek et al. (2024)"},{"why":"This reference documents that pretraining term frequency affects few-shot reasoning, motivating the random DFA sampling that prevents canonical languages from leaking into the prompt set.","marker":"Razeghi et al. (2022)"},{"why":"This reference proves transformers can represent n-gram language models, so the n-gram baselines are a lower bound that a capable transformer should be able to match.","marker":"Svete & Cotterell (2024)"},{"why":"This reference introduces chain-of-thought prompting, the reasoning format used in the BASIC-COT and DFA-COT conditions.","marker":"Wei et al. (2022b)"},{"why":"This reference frames world modeling as latent DFA identification and finds transformers trained on DFA traces do not reconstruct the DFA, supporting the paper's separation of pattern matching from world modeling.","marker":"Vafa et al. (2025)"}],"fun_headline_variants":["LLMs underperform n-grams on novel grammar tasks","N-grams beat LLMs at inducing unseen languages","Chain-of-thought can't save LLMs from n-gram defeat","On fresh grammar, LLMs fall below 2-gram baselines","ICL limit: LLMs trail n-grams on simple new languages"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the finite set of prompts tried, mainly BASIC and BASIC-COT with the best result taken, adequately elicits each model's in-context learning ability, so that low scores reflect ICL limitations rather than prompt-format effects.","fun_headline_variants_meta":{"raw":{"variants":["LLMs underperform n-grams on novel grammar tasks","N-grams beat LLMs at inducing unseen languages","Chain-of-thought can't save LLMs from n-gram defeat","On fresh grammar, LLMs fall below 2-gram baselines","ICL limit: LLMs trail n-grams on simple new languages"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1482,"prompt_tokens":934,"completion_tokens":548,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":459}},"tokens_in":550,"tokens_out":548,"duration_ms":5140,"temperature":1.0,"reasoning_tokens":459,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:05:03.054801+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The claim would collapse if a single LLM, given only example strings or transducer traces with no mention of grammar, DFA, rooms, or portals, matched or beat the 6-GRAM transducer baseline of 93.5% (or the 2-GRAM sequence-completion baseline of 83.3%) on the same sampled DFAs.","supporting_citations":[],"review_version":1}