Open Problems

Efficient Attention & State-Space Models

A Matched-Scale Testbed and Extrapolation Protocol for Testing Whether Toy-Scale Evidence Survives at Realistic Scale

Scope to testOpen
Possible candidate · 2/5 runs32 papers report this56% from 2025+

Generated automatically from the limitations stated in 32 papers (NeurIPS, ICML, ICLR), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.

The problem

Across theory-driven method papers, the empirical section reliably ends where the claim begins: guarantees about scaling, efficiency, or sample complexity are validated only on instances orders of magnitude below the regime where they matter, because realistic-scale runs are unaffordable for a single lab and no shared, property-matched task suites exist for buying at-scale evidence cheaply. The consequence is that scalability claims are effectively unfalsifiable — reviewers can neither confirm nor reject them, and methods whose advantages appear only above ~10⁸ parameters or on real data are adopted or discarded on faith. Because every group builds its own private toys, no evidence accumulates: the field cannot answer the basic question of how often toy-scale method rankings survive at realistic scale, so nobody knows what the current synthetic-only evidence base is actually worth.

Why it matters

Turns "scalability untested" from an unanswerable caveat into a measurable risk — reviewers can demand a registered two-scale check, practitioners get a rule for how much scale a validation needs, and toy tasks that demonstrably predict at-scale behavior become certified cheap proxies while misleading ones are retired.

Ways to approach it

Prior-work checks are free with an account. Results someone already ran are shown to everyone.

  1. 1

    Scale-transfer pilot audit (startable in a month): reproduce two or three published synthetic-only results, then re-run each once at a single realistic-scale anchor inside its own domain (e.g., a from-scratch ~150M-parameter language-model pretrain, or a public logged market dataset), same baseline at both scales. Measure: the headline-metric advantage at toy scale vs. anchor scale, whether the ranking flips, and the advantage-retention ratio. Even with small n, this yields the first quantified toy-to-anchor flip rate.

  2. 2

    Matched-scale suite construction: for ~8 task families, build instances at 4 scales spanning ≥3 orders of magnitude and *verify the match* — the structural parameter each theory targets (spectral decay, effective dimension, horizon ratio, utility curvature) must agree between toy and realistic instances, calibrated against real reference data where available. Measure property-match error across scales; a student starts by specifying the matching condition and generator for one family.

  3. 3

    Registered extrapolation protocol: with the suite in place, run a fixed baseline set at the three smallest scales, fit headline metric vs. scale, pre-register the prediction at the largest scale, then run it. Measure extrapolation error per method–metric pair and the earliest scale at which predictions stabilize within tolerance; distill into a released decision rule ("validate at scale *s* to trust a claim within ±x%").

Have a different approach?

Describe how you would tackle this problem and we'll look for papers that already do it. Free; your text stays private.

Free · 3 checks per day

Why it might fail

If the "matched" large instances turn out not to resemble the real workloads they stand in for, the measured transfer rates describe the testbed rather than reality, and the project reproduces the very gap it targets. A lesser risk is that only sub-decisive anchors are affordable, leaving flip rates measured below the regime where the claims bite.

Sub-problems

  • Empirical Benchmarking and Robustness of Algorithmic Mechanism Design on Real-World Platform Traces

    Theoretical mechanism design and algorithmic game theory models rely heavily on stylized parametric assumptions—such as linear utility kernels, softmax outcome distributions, and synthetic externalities—to evaluate algorithmic performance. Because these methods are evaluated almost exclusively on hand-crafted synthetic instances, their robustness, revenue, and welfare guarantees remain unverified under realistic agent behavior. Without empirical calibration against real-world platform and behavioral logs, designers cannot determine whether theoretical mechanisms succeed or fail when facing real human preferences and market friction.

  • Empirical Robustness and Scaling Benchmark of Modern Sketching and Low-Rank Approximation Methods

    Multiple recently proposed sketching and low-rank approximation methods have only been tested on tiny synthetic instances ($n \le 100$) with known, idealized rank structures. Consequently, it is unknown whether their theoretical advantages survive on large-scale, ill-conditioned, or real-world data matrices. Without rigorous comparative evaluation against standard baselines like randomized SVD and classical PCA across diverse spectral profiles, practitioners cannot determine which method to deploy in practice.

  • Benchmarking Meta-Learning and In-Context Learning Methods Beyond Synthetic Tasks

    Current empirical validations for meta-learning algorithms and theoretical in-context learning models rely almost exclusively on synthetic regression, toy HMMs, or low-dimensional linear tasks. Consequently, it is unknown whether the qualitative behaviors, convergence rates, and algorithmic advantages observed in these synthetic distributions persist in real natural language modeling and large-scale deep learning settings. Without empirical testing across both synthetic setups and real language tasks, researchers cannot determine whether existing meta-learning methods scale or fail outside controlled mathematical toy problems.

  • Empirical Robustness of Modern Bayesian Optimization Across Real-World Design Benchmarks

    Recent Bayesian optimization and model-based experimental design methods are evaluated almost exclusively on synthetic test functions or minimal toy instances. Consequently, practitioners in domains such as protein engineering, hardware accelerator design, and industrial logistics cannot determine whether reported theoretical advantages transfer to noisy, high-dimensional real systems. Without systematic cross-domain evaluation, algorithmic improvements remain unverified on non-idealized objective landscapes, leaving real-world experimental design reliant on older heuristics.

Evidence

Each paper's own statement of the limitation, verbatim.

Show all 32 papers

Nearest existing work

Related open problems

Efficient Attention & State-Space Models

Scope to testOpen

Evaluating Toy-Task Inductive Biases and Mechanistic Claims Across Standard Pre-training and Deep Architectures

Architectural mechanisms and efficiency claims developed for state-space models and efficient attention variants are overwhelmingly validated only on shallow (1–6 layer) networks trained on small synthetic or algorithmic tasks. Because these mechanisms have not been evaluated across standard natural language pre-training corpora or deeper architectures, the community cannot determine whether the reported properties persist, degrade, or dissolve at scale. Consequently, theoretical insights and inductive biases identified on synthetic benchmarks remain unverified hypotheses for real-world language modeling.

Strong candidate · 1/1 runs4 papers report this75% from 2025+
Generated automatically, not curated by hand. Automated prior-work checks catch about a third of existing work, so treat this problem as a lead to investigate.