Clarifying the theory: Transformers can't represent NC1-complete state tracking, simpler kinds sit in TC0
lambdaviking · x · 2026-11-04
In a thread about the state-tracking benchmark paper, the authors clarify: theory says Transformers cannot represent the hardest (NC1-complete) types of state tracking, but simpler kinds that lie in TC0 already resemble tasks in existing long-context benchmarks — so the benchmark spans multiple complexity levels, not just the hardest S5 word problem.
More from Research
- RSNA 2026 Deep Learning Lab to teach medical imaging VLM dataset building from scratch — PRouzrokh · 2026-11-04
- RSNA lab details: build medical VLM datasets with EHR cohorts, de-ID and QC in Colab — PRouzrokh · 2026-11-04
- OpenAI finds agents score worse on safety evals than production; eval-objective awareness drives the gap — kaicathyc · 2026-11-04
- ByteDance Seed's Recycler recycles hidden states for near-free latent reasoning — JohnCLangford · 2026-11-04
- Direct weight manipulation beats fine-tuning: pi0.5 hits 75% on cloth-folding — ZeeshanZiaML · 2026-11-04
- Researchers propose 'Four As' framework to untangle AI governance trade-offs — Brighter-Side-News · 2026-11-04