Pith. sign in

REVIEW 2 major objections 4 minor 241 references

For every nontrivial hypothesis class on an infinite input space, some ordering of the inputs makes every learner fail to identify some target past any given training level.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 20:42 UTC pith:K6GW4NPC

load-bearing objection A sound, elementary no-free-lunch theorem for hierarchy-uniform domain generalization, with an abstract that slightly oversells its scope. the 2 major comments →

arxiv 2607.16528 v1 pith:K6GW4NPC submitted 2026-07-17 cs.LG

Hierarchical Domain Generalization

Chenxiao Yang , Zhiyuan Li , Shai Ben-David , Nathan Srebro This is my paper
classification cs.LG MSC 68Q3268T05
keywords hierarchical domain generalizationout-of-domain generalizationidentification in the limitlength generalizationno-free-lunch theoremdomain complexitytrain/test partitionuniform generalization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper tries to prove that out-of-domain generalization — extrapolating from finite observed inputs to an entire infinite input space — depends not only on the hypothesis class but on the order in which inputs are revealed. It replaces i.i.d. sampling with an arbitrary domain hierarchy and asks at what level a learner can exactly recover the target function. The central result is a complete characterization: if the identifying level may depend on the target, countability of the class is enough; if it must be uniform over targets for a fixed hierarchy, finiteness is needed; but if it must be uniform over hierarchies, only finite domains work for classes with more than two hypotheses. A no-free-lunch theorem then shows that for any nontrivial class on a countable infinite domain, some hierarchy postpones identification beyond any prescribed training size, so no hierarchy-free guarantee exists. A careful reader should care because this reframes length generalization and other "train on short, test on long" claims as statements about a specific domain ordering, not about the model class alone.

Core claim

The paper's central claim is an exact trichotomy for hierarchical domain generalization, stated in terms of how uniformly the identifying level is chosen. If the level may depend on both the target and the hierarchy, a countable hypothesis class is sufficient and necessary (A1). If the hierarchy is fixed but one level must work for all targets, finiteness of the class is necessary and sufficient (A2). If the level must be chosen uniformly over hierarchies, then for any class with more than two hypotheses, only a finite input domain works (A3 and A4). The paper then strengthens this into a no-free-lunch statement: on a countably infinite domain, for any class with more than two hypotheses and

What carries the argument

The central object is the domain hierarchy: a telescoping sequence of finite observed regions that exhausts the countable input space, which determines the train/test split at every level. The proof engine is a pigeonhole fact about binary hypotheses: among any three hypotheses, the pairwise agreement sets cover the whole domain, so at least one pair agrees on infinitely many points; an adversary builds a hierarchy that reveals those agreement points first, forcing all learners to receive identical labels under two different targets for arbitrarily many levels. The quantitative workhorse is the class domain complexity — the first hierarchy level whose observed region separates every pair of

Load-bearing premise

The load-bearing premise is that the hierarchy of observed regions is arbitrary and can be adversarially chosen, with no requirement that early regions be statistically or structurally related to later regions; if hierarchies are restricted to natural orderings such as input length, the paper's own fixed-hierarchy results give positive guarantees and the impossibility no longer applies.

What would settle it

Exhibit any three binary hypotheses on a countably infinite domain whose pairwise agreement sets are all finite; the paper's pigeonhole step, used in Theorems 8 and 12, asserts this is impossible. Equivalently, a class with more than two hypotheses, a learner, and a fixed finite N for which the learner identifies every target by level N under every hierarchy would directly refute Theorem 8.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • A domain-generalization guarantee cannot be attributed to the hypothesis class alone; it is a property of the pair consisting of the class and the hierarchy, and any uniform guarantee on an infinite domain must fix and disclose the hierarchy.
  • Length-generalization bounds hold for the length ordering specifically; the same model family and complexity scale under a different hierarchy can have sublevel identifying bounds that grow arbitrarily fast, including noncomputably fast.
  • A bounded online mistake count does not imply target-uniform identification: the singleton-indicator class has mistake bound 1 but no common finite identifying level on the natural hierarchy.
  • Relaxing exact identification to small approximation error does not remove the hierarchy dependence; full-support evaluation distributions still allow disagreements to be postponed for arbitrarily many levels.
  • Restricting presentations to positive examples does allow fully uniform identification of infinite classes when distinct targets share only boundedly many positive points — for example, indicators of distinct affine lines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the argument is correct, evidence that a model 'learned a rule' from a training prefix is only meaningful relative to a specified input ordering; fitting one ordering can coexist with failure on any reordering that delays distinguishing inputs, so benchmark evaluations should report the exact ordering and probe alternatives.
  • A testable design heuristic follows: curricula that front-load points where candidate hypotheses agree are guaranteed to postpone identification, while curricula that interleave disagreement points cannot be defeated by this mechanism; ordering by a natural difficulty measure is therefore not automatically safe.
  • The paper leaves open the restricted-hierarchy question: which families of orderings (for instance, those defined by a fixed complexity measure with finite branching) admit uniform or near-uniform bounds? The paper's own fixed-hierarchy theorems suggest such positive results exist.
  • For LLM length generalization, the stratified no-free-lunch result implies practical bounds must specify the hierarchy in terms of tokens, digits, or reasoning steps; otherwise comparable claims across papers are not well-defined.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper formalizes hierarchical domain generalization as exact identification along an arbitrary nested exhaustion X̄=(X_n) of a countable instance space Ω. The learner sees all labels on X_n and must recover the target f on all of Ω. Four quantifier regimes are defined: A1 (level may depend on target and hierarchy), A2 (hierarchy-dependent but target-uniform), A3 (target-dependent but hierarchy-uniform), and A4 (fully uniform). The main characterization theorems state: A1 iff H is countable, A2 iff H is finite, and, when |H|>2, A3/A4 iff Ω is finite. The paper then introduces finite-complexity sublevels and sublevel domain complexity, discusses length generalization as a fixed-hierarchy instance, proves a class-level no-free-lunch (Theorem 12) and a complexity-stratified no-free-lunch (Corollary 13) showing that arbitrary hierarchies can force arbitrarily large identification levels, and closes with extensions to online mistake bounds, approximation, out-of-support distributions, and positive-only presentations.

Significance. If correct, this is a clean and useful formal contribution. It isolates the train/test domain partition as an irreducible component of out-of-domain generalization: for any nontrivial class on an infinite domain, no hierarchy-uniform exact-identification guarantee exists, and fixed-hierarchy quantities can be made arbitrarily large by changing the hierarchy. The proofs are self-contained and elementary; the countable-prefix argument for Theorem 1, the three-hypothesis covering argument in Theorem 8, and the inductive agreement-set construction in Corollary 13 all check out. The stratification in Section 4 gives a meaningful quantitative framework, and the positive-only result (Proposition 19) provides a nice contrast. The main weakness is that the abstract overstates the scope of the negative results; with explicit qualifiers added, the contribution is solid.

major comments (2)
  1. [Abstract; §3.3; Theorems 8, 12] The headline claim 'no matter how small the class or how large the training size, some partition makes generalization fail for some target' is not supported as stated. The formal results (Theorems 8 and 12) assume |H|>2, and §3.3 explicitly notes the two-element exception: for H={h,g} with |Eq(h,g)| finite, A3 and A4 hold with common bound |Eq(h,g)|+1, because every level n>|Eq(h,g)| must contain a point where h and g differ. Hence for such classes no hierarchy can make both targets fail once M>|Eq(h,g)|. Please qualify the abstract with 'for every class with at least three hypotheses' (or 'containing two hypotheses with infinite agreement') and 'over arbitrary domain hierarchies.'
  2. [Abstract; §6; Corollary 13] The negative results are existential over all hierarchies: for any M, some hierarchy delays separation past M. They do not show that fixed natural hierarchies, such as the length hierarchy Σ̄ in Definition 10, cannot support positive, quantitative guarantees — the paper's §6 says exactly that a length-generalization bound is a bound for the length hierarchy. The abstract and conclusion should therefore frame the contribution as 'no hierarchy-free or hierarchy-uniform guarantee' rather than as a general failure of domain generalization; otherwise the conclusion can be over-read as invalidating the fixed-hierarchy results in Sections 4–5.
minor comments (4)
  1. [§6, after Corollary 13] The sentence 'In particular, for some hierarchy, this function has no computable upper bound' is a valid but nontrivial consequence of the corollary: one must apply Corollary 13 to a nondecreasing unbounded B that dominates every computable function (e.g., a busy-beaver-type function). State this explicitly; as written it appears to follow simply from the per-B form.
  2. [§3.3, degenerate two-element case] For the two-element finite-agreement case, make explicit that the uniform bound works because |X_n|≥n under Definition 1; otherwise the phrase 'any sufficiently large observed region' sounds like a fixed-hierarchy statement rather than a uniform-over-hierarchies statement.
  3. [Figure 1] The caption's |H|>2 qualifier is easy to miss. Add a note near Figure 1 or in the abstract that the two-element finite-agreement class is the only nondegenerate exception to the A3/A4 characterization.
  4. [§7.3, Theorem 18 proof] The 'averaging over Q^n' step can be made explicit by defining indicator events for the two targets; the current wording is acceptable but slightly compressed.

Circularity Check

0 steps flagged

No significant circularity: the hierarchy-uniform impossibility theorems are proved from first principles; self-citations are illustrative and non-load-bearing.

full rationale

The core derivation chain runs from Definitions 1-7 through Theorems 1, 5, 8, 12 and Corollary 13. The main impossibility theorem (Theorem 8) is proved directly: assuming A3, the proof shows every pairwise agreement set Eq(f,g) is finite by constructing a hierarchy whose prefix lies inside Eq(f,g); since |H|>2 and labels are binary, the three pairwise agreement sets cover the infinite domain, forcing the domain to be finite. This is a contradiction argument from the definitions, not an assumption of the conclusion. Theorem 12 likewise constructs a point-by-point hierarchy whose first M points lie in an infinite agreement set of two hypotheses; any learner receives identical inputs under the two targets at level M, so one of them is not identified. The bound is existential and is not obtained by fitting any parameter to data; there are no fitted values called predictions anywhere in the paper. Corollary 13 is proved by an explicit inductive construction of a hierarchy that hides pairs in growing complexity slices; it does not invoke any external result for its force. The self-citations (Chen et al. 2025; Yang et al. 2026a,b) appear only in Section 5 as examples and motivation for length generalization and as a statement that Proposition 10 'recovers' a prior uncomputability result; the proofs of Propositions 10-11 and Theorems 12-13 are self-contained in the appendix and do not rest on those citations. Thus no central claim reduces to a self-citation chain or to an input by construction. The abstract's 'no matter how small the class' is missing the |H|>2 qualifier that appears in the theorems, and the negative results quantify over all hierarchies while fixed natural hierarchies (e.g., length) retain positive guarantees; this is a framing/scope concern, not circularity. The limitations section similarly flags the realizable, exact-identification, set-indexed restrictions without concealing any circular step.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No fitted parameters or hand-chosen constants appear in the central theorems. The paper’s contribution rests on its modeling assumptions: countable exhaustive hierarchies, deterministic realizable labels, arbitrary hierarchy selection, and finite sublevel complexity scales. These are all stated explicitly in the text.

axioms (5)
  • domain assumption The instance space Ω is countable and is exhausted by finite cumulative regions (Definition 1).
    All cardinality arguments (countable finite labeled prefixes, finite labelings, finite covering) and the no-free-lunch construction depend on this setup; continuous or uncountable domains are outside the model.
  • domain assumption Labels are deterministic, realizable, and binary; the learner receives all labels on X_n and must exactly recover f on all of Ω.
    The impossibility results are stated and proved in this model. Section I explicitly lists realizable deterministic labeling and exact identification as scope restrictions.
  • domain assumption The hierarchy ̅X is arbitrary and adversarial, and may be chosen to postpone distinguishing points.
    The proof of Theorem 12 needs the freedom to place an infinite agreement set at the beginning of the hierarchy. Without this freedom, fixed-hierarchy positive results for finite/countable classes would apply.
  • domain assumption Complexity scales c have finite sublevels and exhaustive union (Equation 6).
    Sublevel domain complexity and the stratified no-free-lunch corollary require that each Hₓ≤s is finite and that the union covers H; not every representation class admits such a scale.
  • standard math Littlestone’s classical mistake-bound theorem.
    Used in Section 7.1 to characterize uniform online mistake bounds; the proof is sketched in-house, but the result is classical background.

pith-pipeline@v1.3.0-alltime-deepseek · 21747 in / 17683 out tokens · 204477 ms · 2026-08-01T20:42:17.528944+00:00 · methodology

0 comments
read the original abstract

We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i.i.d. sampling with arbitrary domain hierarchies. We show that the central obstruction is not only the complexity of the hypothesis class, but the train/test domain partition through which evidence is revealed. In particular, no matter how small the class or how large the training size, some partition makes generalization fail for some target. These results suggest that modern generalization theory must treat domain structure as a first-class object.

Figures

Figures reproduced from arXiv: 2607.16528 by Chenxiao Yang, Nathan Srebro, Shai Ben-David, Zhiyuan Li.

Figure 1
Figure 1. Figure 1: Key characterization. Exact characterization of when a hypothesis class allows hierarchical domain generalization at levels that may depend on the target and hierarchy (A1), depend on the hierarchy but are uniform over targets (A2), depend on the target but are uniform over hierarchies (A3), or are uniform over both targets and hierarchies (A4). Throughout the figure, f ∈ H, X¯ ranges over hierarchies, and… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

241 extracted references · 63 linked inside Pith

  1. [1]

    Analysis of Representations for Domain Adaptation , booktitle =

    Shai Ben. Analysis of Representations for Domain Adaptation , booktitle =. 2006 , url =

    2006

  2. [2]

    Automatica , volume=

    Modeling by shortest data description , author=. Automatica , volume=

  3. [3]

    IEEE Transactions on Information Theory , volume=

    Minimum complexity density estimation , author=. IEEE Transactions on Information Theory , volume=

  4. [4]

    2007 , publisher=

    The Minimum Description Length Principle , author=. 2007 , publisher=

    2007

  5. [5]

    2008 , publisher=

    An Introduction to Kolmogorov Complexity and Its Applications , author=. 2008 , publisher=

    2008

  6. [6]

    Scaling Learning Algorithms Towards

    Bengio, Yoshua and LeCun, Yann , booktitle =. Scaling Learning Algorithms Towards

  7. [7]

    and Osindero, Simon and Teh, Yee Whye , journal =

    Hinton, Geoffrey E. and Osindero, Simon and Teh, Yee Whye , journal =. A Fast Learning Algorithm for Deep Belief Nets , volume =

  8. [8]

    2016 , publisher=

    Deep learning , author=. 2016 , publisher=

    2016

  9. [9]

    2014 , publisher=

    Understanding machine learning: From theory to algorithms , author=. 2014 , publisher=

    2014

  10. [10]

    Advances in Neural Information Processing Systems , volume=

    Structured Denoising Diffusion Models in Discrete State-Spaces , author=. Advances in Neural Information Processing Systems , volume=

  11. [11]

    2025 , eprint=

    Large Language Diffusion Models , author=. 2025 , eprint=

    2025

  12. [12]

    International Conference on Machine Learning , year=

    Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution , author=. International Conference on Machine Learning , year=

  13. [13]

    The Twelfth International Conference on Learning Representations , year=

    Consistency Large Language Models , author=. The Twelfth International Conference on Learning Representations , year=

  14. [14]

    International Conference on Machine Learning , year=

    The Diffusion Duality , author=. International Conference on Machine Learning , year=

  15. [15]

    2025 , eprint=

    Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions , author=. 2025 , eprint=

    2025

  16. [16]

    arXiv preprint arXiv:2505.14683 , year =

    Emerging Properties in Unified Multimodal Pretraining , author =. arXiv preprint arXiv:2505.14683 , year =

    Pith/arXiv arXiv

  17. [17]

    2025 , eprint=

    Esoteric Language Models , author=. 2025 , eprint=

    2025

  18. [18]

    arXiv preprint arXiv:2505.19223 , year=

    LLaDA 1.5: Variance-Reduced Preference Optimization for Large Language Diffusion Models , author=. arXiv preprint arXiv:2505.19223 , year=

    Pith/arXiv arXiv

  19. [19]

    The Thirteenth International Conference on Learning Representations , year=

    Think While You Generate: Discrete Diffusion with Planned Denoising , author=. The Thirteenth International Conference on Learning Representations , year=

  20. [20]

    2025 , eprint=

    Path Planning for Masked Diffusion Model Sampling , author=. 2025 , eprint=

    2025

  21. [21]

    2025 , eprint=

    Reinforcing the Diffusion Chain of Lateral Thought with Diffusion Language Models , author=. 2025 , eprint=

    2025

  22. [22]

    2025 , eprint=

    Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding , author=. 2025 , eprint=

    2025

  23. [23]

    2025 , eprint=

    FUDOKI: Discrete Flow-based Unified Understanding and Generation via Kinetic-Optimal Velocities , author=. 2025 , eprint=

    2025

  24. [24]

    https://arxiv.org/pdf/2410.01949

    Liu, Anji and Broadrick, Oliver and Niepert, Mathias and Van den Broeck, Guy , title =. Proceedings of the 13th International Conference on Learning Representations (ICLR) , month =. 2025 , url = "https://arxiv.org/pdf/2410.01949", keywords =

    Pith/arXiv arXiv 2025

  25. [25]

    2025 , eprint=

    Generalized Interpolating Discrete Diffusion , author=. 2025 , eprint=

    2025

  26. [26]

    Advances in Neural Information Processing Systems , volume=

    Simplified and Generalized Masked Diffusion for Discrete Data , author=. Advances in Neural Information Processing Systems , volume=

  27. [27]

    The Thirteenth International Conference on Learning Representations , year=

    Interpolating Autoregressive and Discrete Denoising Diffusion Language Models , author=. The Thirteenth International Conference on Learning Representations , year=

  28. [28]

    2025 , eprint=

    Muddit: Liberating Generation Beyond Text-to-Image with a Unified Discrete Diffusion Model , author=. 2025 , eprint=

    2025

  29. [29]

    2025 , eprint=

    Scaling up Masked Diffusion Models on Text , author=. 2025 , eprint=

    2025

  30. [30]

    2025 , eprint=

    Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data , author=. 2025 , eprint=

    2025

  31. [31]

    arXiv preprint arXiv:2503.20853 , year =

    Unified Multimodal Discrete Diffusion , author =. arXiv preprint arXiv:2503.20853 , year =

    Pith/arXiv arXiv

  32. [32]

    2025 , eprint=

    LaViDa: A Large Diffusion Language Model for Multimodal Understanding , author=. 2025 , eprint=

    2025

  33. [33]

    2025 , eprint=

    LLaDA-V: Large Language Diffusion Models with Visual Instruction Tuning , author=. 2025 , eprint=

    2025

  34. [34]

    arXiv preprint arXiv:2504.12216 , year=

    d1: Scaling reasoning in diffusion large language models via reinforcement learning , author=. arXiv preprint arXiv:2504.12216 , year=

    Pith/arXiv arXiv

  35. [35]

    2025 , eprint=

    MMaDA: Multimodal Large Diffusion Language Models , author=. 2025 , eprint=

    2025

  36. [36]

    2025 , eprint=

    Dimple: Discrete Diffusion Multimodal Large Language Model with Parallel Decoding , author=. 2025 , eprint=

    2025

  37. [37]

    2025 , eprint=

    dKV-Cache: The Cache for Diffusion Language Models , author=. 2025 , eprint=

    2025

  38. [38]

    2025 , eprint=

    dLLM-Cache: Accelerating Diffusion Large Language Models with Adaptive Caching , author=. 2025 , eprint=

    2025

  39. [39]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

    Simple and Effective Masked Diffusion Language Models , author=. The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

  40. [40]

    2024 , eprint=

    A Theoretical Perspective for Speculative Decoding Algorithm , author=. 2024 , eprint=

    2024

  41. [41]

    International Conference on Learning Representations , year=

    Energy-Based Diffusion Language Models for Text Generation , author=. International Conference on Learning Representations , year=

  42. [42]

    International Conference on Learning Representations , year=

    DiffuSeq: Sequence to Sequence Text Generation with Diffusion Models , author=. International Conference on Learning Representations , year=

  43. [43]

    Advances in Neural Information Processing Systems , volume=

    Attention is all you need , author=. Advances in Neural Information Processing Systems , volume=. 2017 , publisher=

    2017

  44. [44]

    BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding , author=. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) , pages=. 2019 , month=

    2019

  45. [45]

    Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pages=

    MaskGIT: Masked Generative Image Transformer , author=. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pages=

  46. [46]

    arXiv preprint arXiv:2405.19932 , year=

    Block Diffusion: Interpolating between Autoregressive and Diffusion Language Models , author=. arXiv preprint arXiv:2405.19932 , year=

    arXiv

  47. [47]

    Proceedings of the IEEE/CVF international conference on computer vision , pages=

    Scalable diffusion models with transformers , author=. Proceedings of the IEEE/CVF international conference on computer vision , pages=

  48. [48]

    arXiv preprint arXiv:2410.01600 , year=

    Entp: Encoder-only next token prediction , author=. arXiv preprint arXiv:2410.01600 , year=

    Pith/arXiv arXiv

  49. [49]

    arXiv preprint arXiv:2412.02975 , year=

    Theoretical limitations of multi-layer transformer , author=. arXiv preprint arXiv:2412.02975 , year=

    Pith/arXiv arXiv

  50. [50]

    Advances in neural information processing systems , volume=

    Chain-of-thought prompting elicits reasoning in large language models , author=. Advances in neural information processing systems , volume=

  51. [51]

    arXiv preprint arXiv:2205.10625 , year=

    Least-to-most prompting enables complex reasoning in large language models , author=. arXiv preprint arXiv:2205.10625 , year=

    Pith/arXiv arXiv

  52. [52]

    arXiv preprint arXiv:2203.11171 , year=

    Self-consistency improves chain of thought reasoning in language models , author=. arXiv preprint arXiv:2203.11171 , year=

    Pith/arXiv arXiv

  53. [53]

    Advances in Neural Information Processing Systems , volume=

    Tree of thoughts: Deliberate problem solving with large language models , author=. Advances in Neural Information Processing Systems , volume=

  54. [54]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Graph of thoughts: Solving elaborate problems with large language models , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  55. [55]

    The Eleventh International Conference on Learning Representations , year=

    Compositional semantic parsing with large language models , author=. The Eleventh International Conference on Learning Representations , year=

  56. [56]

    arXiv preprint arXiv:2210.02406 , year=

    Decomposed prompting: A modular approach for solving complex tasks , author=. arXiv preprint arXiv:2210.02406 , year=

    Pith/arXiv arXiv

  57. [57]

    arXiv preprint arXiv:2305.08291 , year=

    Large language model guided tree-of-thought , author=. arXiv preprint arXiv:2305.08291 , year=

    Pith/arXiv arXiv

  58. [58]

    arXiv preprint arXiv:2401.12954 , year=

    Meta-prompting: Enhancing language models with task-agnostic scaffolding , author=. arXiv preprint arXiv:2401.12954 , year=

    Pith/arXiv arXiv

  59. [59]

    arXiv preprint arXiv:2308.10379 , year=

    Algorithm of thoughts: Enhancing exploration of ideas in large language models , author=. arXiv preprint arXiv:2308.10379 , year=

    Pith/arXiv arXiv

  60. [60]

    Advances in neural information processing systems , volume=

    Large language models are zero-shot reasoners , author=. Advances in neural information processing systems , volume=

  61. [61]

    arXiv preprint arXiv:2211.12588 , year=

    Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks , author=. arXiv preprint arXiv:2211.12588 , year=

    Pith/arXiv arXiv

  62. [62]

    Advances in Neural Information Processing Systems , volume=

    Star: Bootstrapping reasoning with reasoning , author=. Advances in Neural Information Processing Systems , volume=

  63. [63]

    Advances in Neural Information Processing Systems , volume=

    Self-refine: Iterative refinement with self-feedback , author=. Advances in Neural Information Processing Systems , volume=

  64. [64]

    arXiv preprint arXiv:2112.00114 , year=

    Show your work: Scratchpads for intermediate computation with language models , author=. arXiv preprint arXiv:2112.00114 , year=

    Pith/arXiv arXiv

  65. [65]

    arXiv preprint arXiv:2004.05150 , year=

    Longformer: The long-document transformer , author=. arXiv preprint arXiv:2004.05150 , year=

    Pith/arXiv arXiv 2004

  66. [66]

    arXiv preprint arXiv:2001.04451 , year=

    Reformer: The efficient transformer , author=. arXiv preprint arXiv:2001.04451 , year=

    Pith/arXiv arXiv 2001

  67. [67]

    Advances in neural information processing systems , volume=

    Big bird: Transformers for longer sequences , author=. Advances in neural information processing systems , volume=

  68. [68]

    arXiv preprint arXiv:2009.14794 , year=

    Rethinking attention with performers , author=. arXiv preprint arXiv:2009.14794 , year=

    Pith/arXiv arXiv 2009

  69. [69]

    Advances in Neural Information Processing Systems , volume=

    H2o: Heavy-hitter oracle for efficient generative inference of large language models , author=. Advances in Neural Information Processing Systems , volume=

  70. [70]

    arXiv preprint arXiv:2407.14057 , year=

    Lazyllm: Dynamic token pruning for efficient long context llm inference , author=. arXiv preprint arXiv:2407.14057 , year=

    Pith/arXiv arXiv

  71. [71]

    arXiv preprint arXiv:2404.14469 , year=

    Snapkv: Llm knows what you are looking for before generation , author=. arXiv preprint arXiv:2404.14469 , year=

    Pith/arXiv arXiv

  72. [72]

    arXiv preprint arXiv:2403.09636 , year=

    Dynamic memory compression: Retrofitting llms for accelerated inference , author=. arXiv preprint arXiv:2403.09636 , year=

    Pith/arXiv arXiv

  73. [73]

    Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages=

    Learned token pruning for transformers , author=. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages=

  74. [74]

    arXiv preprint arXiv:2310.05736 , year=

    Llmlingua: Compressing prompts for accelerated inference of large language models , author=. arXiv preprint arXiv:2310.05736 , year=

    Pith/arXiv arXiv

  75. [75]

    Journal of Machine Learning Research , volume=

    Attention is turing-complete , author=. Journal of Machine Learning Research , volume=

  76. [76]

    International Conference on Learning Representations , year=

    The expresssive power of transformers with chain of thought , author=. International Conference on Learning Representations , year=

  77. [77]

    arXiv preprint arXiv:2411.01992 , year=

    Ask, and it shall be given: Turing completeness of prompting , author=. arXiv preprint arXiv:2411.01992 , year=

    Pith/arXiv arXiv

  78. [78]

    Transactions of the Association for Computational Linguistics , volume=

    What formal languages can transformers express? a survey , author=. Transactions of the Association for Computational Linguistics , volume=. 2024 , publisher=

    2024

  79. [79]

    arXiv preprint arXiv:2406.14197 , year=

    On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning , author=. arXiv preprint arXiv:2406.14197 , year=

    Pith/arXiv arXiv

  80. [80]

    arXiv preprint arXiv:2412.17794 , year=

    Memory makes computation universal, remember? , author=. arXiv preprint arXiv:2412.17794 , year=

    Pith/arXiv arXiv

Showing first 80 references.