Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

LLM Priors for ERM over Programs

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that LLM-ERM—a propose-and-verify algorithm that uses a pretrained LLM to propose candidate programs and selects by empirical risk on held-out data—recovers exact short programs from about 200 examples, while gradient-base

desk verdict Solid empirical paper; the ERM/selection mechanism at the center of the framing is never ablated, and one revision is needed before the central claim is proven. read the letter →

arxiv 2510.14331 v3 pith:GC4LIP5N submitted 2025-10-16 cs.LG

Shivam Singhal , Priyadarsi Mishra , Eran Malach , Tomer Galanti This is my paper
classification cs.LG
keywords programsynthesisempiricalriskminimizationLLMpriorstatisticalquerydimensionparitylengthgeneralizationpropose-and-verifysampleefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Classical learning theory says short programs can be learned from few examples, but finding them by enumeration is exponentially expensive, while gradient-based training is cheap per step but can need exponentially many examples on tasks like parity. This paper argues that a pretrained LLM can break that trade-off: LLM-ERM uses the LLM to propose candidate programs, executes each on a validation set, and keeps the best one, with no gradient updates or feedback to the sampler. On parity variants, pattern matching, palindrome detection, and primality testing, it recovers the exact rule from roughly 200 examples and generalizes to input lengths far beyond the training distribution. Gradient-trained transformers, fine-tuning, and in-context learning fit the same data but stay near chance. If the pattern holds, LLM priors could be a practical search bias that restores ERM-style sample guarantees for computationally feasible program learning.

What carries the argument

The load-bearing object is the data-conditional proposal distribution over programs induced by a pretrained LLM. The paper's algorithm, LLM-ERM, draws k candidates from this distribution via prompting, executes each candidate on the data, and applies ERM-style selection on a validation set—so the generalization guarantees of finite-class ERM apply to the pool actually proposed, while the search cost is linear in k and m rather than exponential in program length. The matching theoretical result is the SQ-based lower bound for coordinate mini-batch SGD, which shows gradient learners need exponentially many iterations on parity-like classes even when a short program exists.

What would settle it

Run LLM-ERM on a family of short programs that are deliberately orthogonal to the LLM's prior—e.g., a random 256-bit mask XORed with the input, or a pseudo-random hash like SHA-256 parity—and check whether the 200-example validation selection ever finds a consistent program. If it does, the prior is not the limiting factor; if it stays at chance while length-first enumeration succeeds, the LLM prior is load-bearing.

Watch

Extended reading notes

Core claim

The paper introduces LLM-ERM: a propose-and-verify algorithm that replaces exhaustive enumeration over programs with an LLM-guided proposal process, while keeping empirical risk minimization on a held-out validation set as the selection rule. Given a labeled sample, the LLM is prompted to generate up to k candidate Python functions; each is compiled, run on the train and validation data, and the candidate with the lowest validation error is returned, stopping early when the error hits zero. This is ERM over the finite pool of proposed programs, so classical finite-class generalization bounds apply, but the search is biased by the LLM's prior rather than by length order. Empirically, on full,

Load-bearing premise

The method succeeds only if the pretrained LLM's proposal distribution contains a program that is consistent with the training examples and belongs to the target family; when it does not, as with SHA-256 parity, LLM-ERM stays at chance.

Editorial extensions

If this is right

  • ERM over the pool of LLM-proposed programs inherits the classical sample-efficiency of finite-class search: the paper's experiments show exact recovery from about 200 samples, with no gradient updates or feedback to the sampler.
  • Synthetic tasks like full/random parity and primality are solved by dimension-invariant programs, so test accuracy is 100% (or unbounded '∞%') across all input lengths, while SGD-trained transformers collapse to chance beyond the training length.
  • The theoretical result proves coordinate-wise online mini-batch SGD needs Ω(d ε² / B^{3/2}) iterations on classes of SQ-dimension d, which is exponential for parity, explaining why gradient search is sample-hungry even though short programs exist.
  • On tasks such as pattern matching and Dyck-2, LLM-ERM produces high-accuracy but not always exact parsers, and on SHA-256 parity it remains at chance; the paper's own failure cases delimit how much the LLM prior can do alone.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the proposal step is the bottleneck, LLM-ERM's success on any new task is a measure of the LLM's prior coverage, not a property of ERM itself; a practical way to use the method is to pair it with a proposed-pool diversity check that flags when all candidates are near chance.
  • The method suggests a broader design pattern for discrete learning: any strong generator of hypotheses (not only LLMs) can be combined with ERM-style validation to get sample-efficient program learning, so the result is likely to transfer to other generative priors.
  • The reasoning traces the paper publishes (e.g., Miller–Rabin convergence for primality, Gaussian elimination for random 10-parity) expose a compact record of the search; these traces could be reused to compile a cheaper proposer for a fixed task distribution, amortizing the LLM cost.
  • An untested extension is to let the validation set steer a second round of proposals (e.g., by prompting with the best candidate's errors), which would go beyond the paper's non-adaptive protocol; the trade-off is a possible violation of the clean ERM guarantee, so the benefit must be measured against the guarantee.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes LLM-ERM (also called LLM-PV in the abstract), a program-learning algorithm that replaces exhaustive program enumeration with an LLM-driven propose-and-verify loop: the LLM proposes up to k candidate Python programs, each is executed on a training/validation split, and the program with lowest validation error is returned, with early stopping when validation error reaches zero. The authors claim that this preserves the sample efficiency of finite-class ERM while avoiding the exponential search cost of enumeration, and that it outperforms SGD-trained transformers, fine-tuned LLMs, and in-context learning on a suite of algorithmic tasks (parity variants, pattern matching, palindrome, Dyck-2, primality, cellular automata parity, SHA-256 parity). The theoretical section gives a standard PAC bound for length-first enumeration and an SQ-based lower bound on coordinate-wise online mini-batch SGD. The empirical section reports that LLM-ERM recovers exact programs from about 200 examples on most tasks, while AdamW-trained transformers overfit even with 100k examples.

Significance. If the central claim is sustained, the paper would make a useful contribution: it demonstrates a concrete way to combine an LLM prior with discrete ERM-style selection, producing interpretable, executable programs with strong out-of-distribution generalization. The empirical study is broad and carefully executed: it includes multiple architectures, hyperparameter sweeps (batch size, learning rate), fine-tuning and ICL baselines, data-scaling experiments, and a negative control (SHA-256 parity) that shows the method's boundary. The reasoning traces (Figs. 1, 18, 19) are a nice interpretability addition, and the code is released. The paper is honest about the SHA-256 failure, which strengthens credibility. However, the significance is currently conditional: the novelty of the ERM-selection component is not isolated, and the theoretical lower bound does not apply to the actual optimization algorithm used in the experiments.

major comments (2)
  1. [Algorithm 1 / Section 3] The paper's central claim is that ERM-style selection on held-out data is what makes the method sample-efficient. But Algorithm 1's selection step (Steps 10-11) is never ablated. The paper only reports end-to-end LLM-ERM accuracy; it never reports the accuracy of the first LLM proposal or a no-selection baseline. The reasoning traces in Figs. 1, 18, and 19 show the LLM converging to the exact rule within a single response using internal train-accuracy feedback, which suggests that on many tasks the outer validation loop may be inert. If the first proposal is already correct, the method reduces to "ask GPT-5 to write the function," and the ERM framing is not load-bearing. A one-line ablation (accuracy of first proposal vs. best of k proposals, and whether early stopping is ever triggered by a later proposal) would resolve this. This omission directly affects the paper's main conceptual co
  2. [Proposition 2 / Section 2.3.1 vs. Section 4] Prop. 2 is a lower bound for coordinate-wise online mini-batch SGD with bounded per-coordinate gradients and fresh i.i.d. mini-batches. The empirical baselines in Section 4 use AdamW with full-parameter updates, a fixed training set of 200 examples, and repeated epochs (e.g., 200 epochs, batch size 20). Neither the coordinate restriction, nor the freshness of samples, nor the bounded-gradient assumption is satisfied. Therefore Prop. 2 does not explain the observed failures of the Qwen3/BLOOM baselines. The paper should either extend the reduction to AdamW/offline settings (which is nontrivial because AdamW's momentum and adaptive scaling change the query statistics), or explicitly state that the theory is not intended to explain the empirical gradient-based failures. As written, the theory is presented as if it supports the main negative empirical result, which is misleading.
minor comments (4)
  1. [Abstract and Section 1] The abstract uses 'LLM-PV' while the rest of the paper uses 'LLM-ERM'; the terminology should be unified. Also, the abstract says 'no feedback, adaptivity, or gradients,' but Algorithm 1 uses validation error for early stopping, and the Contributions section says 'LLM feedback proposes discrete edits.' Reconcile the wording to clarify that no validation feedback is used to adapt the sampling distribution.
  2. [Table 1 footnote] The footnote says 'Cellular Automata Parity, length n=100 took k=27 attempts,' but Section 4 states k=5 is used. Explain how this case is handled (e.g., a special budget) or adjust the text; otherwise this is an inconsistency in the experimental protocol.
  3. [Table 1 and Figure captions] The notation '∞%' should be explained in the caption or main text: it denotes that the synthesized program is dimension-invariant and therefore achieves perfect accuracy for all evaluated lengths, not a literal infinite accuracy.
  4. [Figure 6/7] The 'ERM lower bound' in these figures uses a particular L (Python program length) and |Σ|=128; this is an illustrative finite-class bound, not a fundamental lower bound. It would be clearer to state this explicitly in the caption to avoid over-interpretation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central derivations are standard PAC/SQ results and empirical successes are held-out measurements.

full rationale

The paper's derivation chain is not circular. Proposition 1 is a direct restatement of the standard finite-class PAC bound for length-first enumeration; its proof (App. B, Thm. 1/Cor. 1) follows Valiant and Shalev-Shwartz/Ben-David without importing the paper's own empirical claims. Proposition 2's SGD lower bound is proven inside the paper: App. B reduces coordinate mini-batch SGD to 1-STAT(b) and then to VSTAT via Feldman et al. (2018, Thm. B.4), then applies the external SQ-dimension lower bound of Blum et al./Reyzin. The citations to Abbe et al. (2021) and Barak et al. (2022), which include an author of this paper, appear only in an introductory intuition paragraph and are not load-bearing for the formal result. Algorithm 1 is an empirical propose-verify loop; the reported exact recoveries are tested on held-out sets and are not equal to the training/validation fit by construction. The main legitimate concern is experimental rather than circular: the paper never ablates the validation-selection step, so it does not quantify how much of the success is due to ERM-style selection versus the LLM's first proposal. That missing control, and the possibility that GPT-5's pretraining contains benchmark-like tasks, bear on attribution of the empirical effect, but neither is an equation-level reduction or a fitted parameter renamed as a prediction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The method's central reliance on GPT-5's pretrained weights is an unexamined external resource rather than a fitted parameter. The genuine free parameters are algorithmic knobs (k, theta) that affect the empirical tradeoff; no new physical or formal entities are introduced.

free parameters (2)
  • k (number of LLM proposal attempts) = 5
    Algorithm 1 sets k=5 in the main experiments; success probability and compute grow with k. Not fitted to data, but hand-chosen and central to the method's behavior.
  • theta (validation error threshold) = 0
    Early stopping threshold in Algorithm 1 is set to 0; requiring zero validation error is a hand-chosen stopping rule that interacts with sample size and the target class.
assumptions (5)
  • domain assumption Realizability: the target y lies in the program class L
    Section 2.1 assumes y in L; the ERM-style guarantee and validation selection are only justified in the realizable setting.
  • domain assumption Bounded coordinate gradients G for coordinate SGD
    Proposition 2 relies on each per-example coordinate gradient being bounded by G; the paper states this can be ensured by bounded inputs/weights or clipping, but it is not verified for the transformer experiments using AdamW.
  • standard math Feldman et al. Thm. B.4 simulation from 1-STAT(b) to VSTAT
    Used in the proof of Prop. 2 as an accepted theorem; not re-derived.
  • ad hoc to paper GPT-5 proposal distribution has sufficient mass on correct programs for the tested task family
    The empirical success of LLM-ERM depends on GPT-5 proposing near-correct programs from 100 training examples; this is not proven and fails for SHA-256 parity (Table 1).
  • domain assumption Class-balanced data and same generative distribution for test at each fixed length
    Evaluation tasks are synthetically generated and balanced; length-generalization claims rely on test inputs drawn from the same generative process at longer lengths.

how reviews work

0 comments
Cite this review

Pith. "Pith review of LLM Priors for ERM over Programs." pith.science (2026). https://pith.science/paper/GC4LIP5N

@misc{pith2026251014331,
  author       = {Pith},
  title        = {Pith review of: LLM Priors for ERM over Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GC4LIP5N}},
  note         = {Machine review of arXiv:2510.14331}
}
read the original abstract

We study program-learning methods that are efficient in both samples and computation. Classical learning theory suggests that when the target admits a short program description, for example a short piece of ``Python code'', it can be learned from few examples by ERM over the program class. However, this approach relies on enumerating candidate programs, which is typically exponential in the description length; gradient-based training avoids this explicit search but, for some families of short programs, can require exponentially many samples to succeed. We propose \textsc{LLM-PV}, a propose-and-verify recipe that enables ERM-style selection over a discrete program class without exhaustive enumeration: a pretrained LLM induces a proposal distribution over candidate programs, each proposal is executed and scored on a held-out validation set, and the best program is selected, with no gradient updates or validation feedback used to adapt the sampling distribution. Across algorithmic tasks including parity variants, pattern matching, and primality testing, \textsc{LLM-PV} often recovers the exact underlying rule from a small labeled set and generalizes far beyond the training sequence lengths, while SGD-trained transformers, fine-tuning, in-context learning, and classical ML baselines can fit the training data yet fail to generalize reliably. Together, these results suggest that pretrained LLM priors can serve as effective search biases for ERM, narrowing the gap between statistical and computational efficiency.

Figures

Figures reproduced from arXiv: 2510.14331 by the authors.

Figure 2
Figure 2. Trade-offs between sam￾ple and computational efficiency in pro￾gram learning. The proposed method (LLM-ERM) lies in the intersection. The challenge lies in computation. Exhaustive program enu￾meration guarantees that we will eventually find the needle, but only by sifting through an exponentially large haystack of can￾didate programs. Concretely, if the target program has length L over an alphabet Σ, then the number… view at source ↗
Figure 1
Figure 1. Side-by-side comparison of reasoning traces for two distinct learning tasks. Rules were [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. An illustration of LLM-ERM. A prompt from Str seeds the LLM to propose candidates, which are evaluated on train and validation sets. We track the lowest validation error and stop early when it drops below θ, or otherwise after k iterations. Algorithm 1 LLM-ERM: k-try LLM-guided search with validation Require: Str, Sval; attempts k; prompt Π; decoding (τ, M); threshold θ; optional batch b Ensure: Program u ⋆ with hyp… view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Prompt used in our LLM-ERM procedure. We run [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: LLM-ERM generalizes from 200 samples, while an SGD-trained LLM overfits. With only 200 training examples per task, LLM-ERM typically recovers the target function exactly. For each input length n (x-axis), models are trained and tested independently on sequences of that…
Figure 6
Figure 6. Figure 6: SGD-trained LLMs struggle on algorithmic tasks even with 100k samples. We train BLOOM-75M on Random 10-Parity (left), Cellular Automata Parity (middle), and IsPrime with negatives restricted to {1, 3, 7, 9} (right), each with 100k examples. Despite abundant data and pe…
Figure 7
Figure 7. Figure 7: SGD-trained LLMs can fail to learn algorithmic tasks even with 100k examples; LLM-ERM succeeds with 200. We compare the test performance of LLM-ERM and SGD-training of BLOOM-75M on Random 10-Parity (left), Cellular Automata Parity (middle), and IsPrime (Ends in {1,3,7,…
Figure 8
Figure 8. Figure 8: Fine-tuning pre-trained LLMs fails to overcome overfitting on algorithmic tasks. We fine-tuned Qwen3-1.7B on three tasks with 200 samples, training either the full model or only the top 2, 4, or 8 layers. While the models could fit the data, their test accuracy remaine…
Figure 9
Figure 9. Figure 9: Test accuracy for in-context learning with three large models also fails to generalize. The plots display the performance of Qwen3-30B-A3B-Instruct-2507 on all tasks when provided with 200 training examples in-context. Almost all of the observed test accuracy remains n…
Figure 10
Figure 10. Figure 10: LLM-ERM exhibits remarkable degrees of length generalization. We evaluate performance on IsPalindrome (left), Pattern Matching (middle), and Random 3-Parity (right). Both models are trained on a dataset of 200 samples with fixed input dimension (d=10) and evaluated on…
Figure 11
Figure 11. Figure 11: LLM-ERM generalizes from 200 samples, while SGD-trained LLM overfits. With only 200 training examples per task, LLM-ERM typically recovers the target function exactly, whereas SGD training of Qwen3-1.7B from scratch fits the training data but fails to generalize on mo…
Figure 12
Figure 12. Figure 12 [PITH_FULL_IMAGE:figures/full_fig_p019_12.png]
Figure 13
Figure 13. Figure 13: Fine-tuning pre-trained LLMs fails to overcome overfitting on algorithmic tasks. We fine-tuned Qwen3-1.7B, Llama3.2-1B, and Deepseek-Coder-1.3B on all tasks with 200 samples, training either the full model or only the top 2, 4, or 8 layers. While models could partiall…
Figure 14
Figure 14. Figure 14: Test accuracy for in-context learning with three large models also fails to generalize. The plots display the performance of Qwen3-30B-A3B-Instruct-2507(left), Qwen3-Coder-30B -A3B-Instruct (middle), and Deepseek-Coder-33B-Instruct (right) on classification tasks when…
Figure 15
Figure 15. Figure 15: Prompt used in in-context learning procedure. We run three models [PITH_FULL_IMAGE:figures/full_fig_p022_15.png]
Figure 16
Figure 16. Figure 16: Varying the batch size does not resolve overfitting. We train instances of Qwen3-1.7B on Random 10-Parity (left), Pattern Matching (00111111) (middle), and IsPalindrome (right), reporting train and test accuracy. Changing the batch size does not materially alter the m…
Figure 17
Figure 17. Figure 17: SGD’s failure to generalize is not due to poor learning-rate choices. We trained Qwen3-1.7B for 200 epochs (batch size 20) with learning rates η swept across seven orders of magnitude, reporting train and test accuracy as sequence length n varies. Results are shown fo…
Figure 18
Figure 18. Figure 18: Reasoning trace for inferring an equivalent rule for Cellular Automata Parity function. The model starts with simple heuristics, explores linear solutions over F2, and converges to a global XOR rule that perfectly matches the provided dataset, effectively inferring a …
Figure 19
Figure 19. Figure 19: Reasoning trace for learning a full-parity function. We list the candidate functions proposed by GPT-5-thinking when trained on 100 binary strings of length 50. (left) The sequence of candidates explored. (right) The rationale for proposing each candidate. The model s…

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. What Do Evolutionary Coding Agents Evolve?

    cs.NE 2026-05 unverdicted novelty 7.0 of 10

    Evolutionary coding agents achieve most benchmark gains through a small subset of edit types and by cycling previously deleted code lines rather than developing new algorithmic structures.

  2. ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

    cs.CL 2026-05 unverdicted novelty 7.0 of 10

    LLM reasoning traces can be compiled into reusable symbolic solvers that achieve high accuracy on program synthesis benchmarks at zero inference cost and transfer to other domains.

Reference graph

Works this paper leans on

57 extracted references · 3 canonical work pages · cited by 2 Pith papers

  1. [1]

    E. Abbe, P. Kamath, E. Malach, C. Sandon, and N. Srebro. On the power of differentiable learning versus pac and sq learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24340--24351. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/pap...

    2021

  2. [2]

    Aky \"u rek, D

    E. Aky \"u rek, D. Schuurmans, J. Andreas, T. Ma, and D. Zhou. What learning algorithm is in-context learning? investigations with linear models. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=0g0X4H8yN4I

    2023

  3. [3]

    Barak, B

    B. Barak, B. L. Edelman, S. Goel, S. M. Kakade, eran malach, and C. Zhang. Hidden progress in deep learning: SGD learns parities near the computational limit. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=8XWP2ewX-im

    2022

  4. [4]

    Barron and T

    A. Barron and T. Cover. Minimum complexity density estimation. IEEE Transactions on Information Theory, 37 0 (4): 0 1034--1054, 1991. doi:10.1109/18.86996

    work page doi:10.1109/18.86996 1991

  5. [5]

    Barron, J

    A. Barron, J. Rissanen, and B. Yu. The minimum description length principle in coding and modeling. IEEE Transactions on Information Theory, 44 0 (6): 0 2743--2760, 1998. doi:10.1109/18.720554

    doi:10.1109/18.720554 1998

  6. [6]

    Bhansali, A

    S. Bhansali, A. Jin, T. Lizzo, and L. Heck. Lego: Language model building blocks, 2024. URL https://arxiv.org/abs/2410.18287

    arXiv 2024

  7. [7]

    A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC '94, page 253–262, New York, NY, USA, 1994. Association for Computing Machinery. ISBN 0897916638. doi:10.1145/195...

    arXiv 1994

  8. [8]

    A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50 0 (4): 0 506–519, July 2003. ISSN 0004-5411. doi:10.1145/792538.792543. URL https://doi.org/10.1145/792538.792543

    arXiv 2003

Show all 57 references
  1. [9]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam's razor. Information Processing Letters, 24 0 (6): 0 377--380, 1987. ISSN 0020-0190. doi:https://doi.org/10.1016/0020-0190(87)90114-1. URL https://www.sciencedirect.com/science/article/pii/0020019087901141

    1987

  2. [10]

    L. Bottou. Large‐scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177--186. Physica Verlag, 2010

    2010

  3. [11]

    Brown, B

    T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Che...

    1901

  4. [12]

    X. Chen, M. Lin, N. Sch \"a rli, and D. Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=KuPixIqPiq

    2024

  5. [13]

    A. Daniely. Sgd learns the conjugate kernel class of the network. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, page 2419–2427, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964

    2017

  6. [14]

    Daniely and E

    A. Daniely and E. Malach. Learning parities with neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546

    2020

  7. [15]

    de Wynter

    A. de Wynter. Is in-context learning learning?, 2025. URL https://arxiv.org/abs/2509.10414

    2025

  8. [16]

    Alphaevolve: A gemini-powered coding agent for designing advanced algorithms, 2025

    DeepMind. Alphaevolve: A gemini-powered coding agent for designing advanced algorithms, 2025. URL https://deepmind.google/discover/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms

    2025

  9. [17]

    V. Feldman. A general characterization of the statistical query complexity. In S. Kale and O. Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 785--830. PMLR, 07--10 Jul 2017. URL https://proce...

    2017

  10. [18]

    Feldman, E

    V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64 0 (2), Apr. 2017. ISSN 0004-5411. doi:10.1145/3046674. URL https://doi.org/10.1145/3046674

    2017 doi

  11. [19]

    Feldman, W

    V. Feldman, W. Perkins, and S. Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM Journal on Computing, 47 0 (4): 0 1294--1338, 2018. doi:10.1137/16M1078471. URL https://doi.org/10.1137/16M1078471

    2018 doi

  12. [20]

    Giapitzakis, K

    G. Giapitzakis, K. Fountoulakis, E. Nichani, and J. D. Lee. On the statistical query complexity of learning semiautomata: a random walk approach, 2025. URL https://arxiv.org/abs/2510.04115

    2025

  13. [21]

    Grattafiori, A

    A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, A. Yang, A. Fan, A. Goyal, A. Hartshorn, A. Yang, A. Mitra, A. Sravankumar, A. Korenev, A. Hinsvark, A. Rao, A. Zhang, A. Rodriguez, A. Gregerson, A. Spataru,...

    2024 arXiv

  14. [22]

    D. Guo, Q. Zhu, D. Yang, Z. Xie, K. Dong, W. Zhang, G. Chen, X. Bi, Y. Wu, Y. K. Li, F. Luo, Y. Xiong, and W. Liang. Deepseek-coder: When the large language model meets programming - the rise of code intelligence. CoRR, abs/2401.14196, 2024. URL http://dblp.uni-trier.de/db/jou...

    2024 arXiv

  15. [23]

    H. Hu, C. He, H. Zhang, X. Xie, and Q. Zhang. Aprmcts: Improving llm-based automated program repair with iterative tree search, 2025. URL https://arxiv.org/abs/2507.01827

    2025 arXiv

  16. [24]

    M. Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45 0 (6): 0 983–1006, Nov. 1998. ISSN 0004-5411. doi:10.1145/293347.293351. URL https://doi.org/10.1145/293347.293351

    1998

  17. [25]

    Klivans and P

    A. Klivans and P. Kothari. Embedding Hard Learning Problems Into Gaussian Space . In K. Jansen, J. Rolim, N. R. Devanur, and C. Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz In...

    2014 doi

  18. [26]

    A. R. Klivans and A. A. Sherstov. Unconditional lower bounds for learning intersections of halfspaces. Machine Learning, 69 0 (2-3): 0 97--114, 2007. doi:10.1007/s10994-007-5010-1

    2007 doi

  19. [27]

    L. A. Levin. Universal sequential search problems. Problems of Information Transmission (Problemy Peredachi Informatsii), 9 0 (3): 0 115--116 (Russian original) / 265--266 (English translation), 1973. URL https://www.mathnet.ru/eng/ppi914

    1973

  20. [28]

    Loshchilov and F

    I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=Bkg6RiCqY7

    2019

  21. [29]

    Madaan, N

    A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, S. Gupta, B. P. Majumder, K. Hermann, S. Welleck, A. Yazdanbakhsh, and P. Clark. Self-refine: iterative refinement with self-feedback. In Proceedings of the 37th Inter...

    2023

  22. [30]

    D. A. McAllester. Some pac-bayesian theorems. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT' 98, page 230–234, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 1581130570. doi:10.1145/279943.279989. URL https://doi.or...

    1998

  23. [31]

    Llama 3.2: Revolutionizing edge ai and vision with open, multimodal models

    Meta AI . Llama 3.2: Revolutionizing edge ai and vision with open, multimodal models. Meta AI Blog, Sept. 2024. URL https://ai.meta.com/blog/llama-3-2-connect-2024-vision-edge-mobile-devices/

    2024

  24. [32]

    S. Min, X. Lyu, A. Holtzman, M. Artetxe, M. Lewis, H. Hajishirzi, and L. Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Y. Goldberg, Z. Kozareva, and Y. Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natu...

    2022 doi

  25. [33]

    Novikov, N

    A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog. Alphaevolve: A coding agent for scientific and algo...

    2025 arXiv

  26. [34]

    Pourcel, C

    J. Pourcel, C. Colas, and P.-Y. Oudeyer. Self-improving language models for evolutionary program synthesis: A case study on ARC - AGI . In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=z4IG090qt2

    2025

  27. [35]

    Power, Y

    A. Power, Y. Burda, H. Edwards, I. Babuschkin, and V. Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177, 2022. URL https://arxiv.org/abs/2201.02177

    2022 arXiv

  28. [36]

    L. Reyzin. Statistical queries and statistical algorithms: Foundations and applications, 2020. URL https://arxiv.org/abs/2004.00557

    2020 arXiv

  29. [37]

    Rissanen

    J. Rissanen. Stochastic Complexity in Statistical Inquiry Theory. World Scientific Publishing Co., Inc., USA, 1989. ISBN 981020311X

    1989

  30. [38]

    Robbins and S

    H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22 0 (3): 0 400--407, 1951. doi:10.1214/aoms/1177729586

    1951

  31. [39]

    Safran and O

    I. Safran and O. Shamir. Spurious local minima are common in two-layer R e LU neural networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4433--4441. PMLR, ...

    2018

  32. [40]

    T. L. Scao, A. Fan, C. Akiki, E. Pavlick, S. Ilić, D. Hesslow, R. Castagné, A. S. Luccioni, F. Yvon, M. Gallé, J. Tow, A. M. Rush, S. Biderman, A. Webson, P. S. Ammanamanchi, T. Wang, B. Sagot, N. Muennighoff, A. V. del Moral, O. Ruwase, R. Bawden, S. Bekman, A. McMillan-Major...

    2023 arXiv

  33. [41]

    Shalev-Shwartz and S

    S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132

    2014

  34. [42]

    Shalev-Shwartz, O

    S. Shalev-Shwartz, O. Shamir, and S. Shammah. Failures of gradient-based deep learning. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML'17, page 3067–3075. JMLR.org, 2017

    2017

  35. [43]

    L. Shen, A. Mishra, and D. Khashabi. Do pre-trained transformers really learn in-context by gradient descent?, 2024. URL https://openreview.net/forum?id=992eLydH8G

    2024

  36. [44]

    Shinn, F

    N. Shinn, F. Cassano, A. Gopinath, K. R. Narasimhan, and S. Yao. Reflexion: language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id=vAElhFcKW6

    2023

  37. [45]

    R. J. Solomonoff. A formal theory of inductive inference, part i and ii. Information and Control, 7 0 (1--2): 0 1--22, 224--254, 1964. URL https://www.sciencedirect.com/science/article/pii/S0019995864902232. Parts I and II

    1964

  38. [47]

    V. N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998

    1998

  39. [48]

    V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16 0 (2): 0 264--280, 1971. doi:10.1137/1116025

    1971 doi

  40. [49]

    Von Oswald, E

    J. Von Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th Internat...

    2023

  41. [50]

    R. Wang, H. Li, X. Han, Y. Zhang, and T. Baldwin. Learning from failure: Integrating negative examples when fine-tuning large language models as agents, 2024. URL https://arxiv.org/abs/2402.11651

    2024 arXiv

  42. [51]

    J. Wei, X. Wang, D. Schuurmans, M. Bosma, brian ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou. Chain of thought prompting elicits reasoning in large language models. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems...

    2022

  43. [52]

    A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. L...

    2025 arXiv

  44. [53]

    Yehudai and O

    G. Yehudai and O. Shamir. On the power and limitations of random features for understanding neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alch\' e -Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran ...

    2019

  45. [54]

    differentiation

    M. Yuksekgonul, F. Bianchi, J. Boen, S. Liu, Z. Huang, C. Guestrin, and J. Zou. Textgrad: Automatic "differentiation" via text, 2024. URL https://arxiv.org/abs/2406.07496

    2024 arXiv

  46. [55]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  47. [56]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  48. [57]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  49. [58]

    Simon, Hans Ulrich

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

    1968

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.