REVIEW 11 cited by
On Limitations of the Transformer Architecture
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
What are the root causes of hallucinations in large language models (LLMs)? We use Communication Complexity to prove that the Transformer layer is incapable of composing functions (e.g., identify a grandparent of a person in a genealogy) if the domains of the functions are large enough; we show through examples that this inability is already empirically present when the domains are quite small. We also point out that several mathematical tasks that are at the core of the so-called compositional tasks thought to be hard for LLMs are unlikely to be solvable by Transformers, for large enough instances and assuming that certain well accepted conjectures in the field of Computational Complexity are true.
Forward citations
Cited by 11 Pith papers
-
Ehrenfeucht-Haussler Rank and Chain of Thought
A function's Ehrenfeucht-Haussler rank exactly equals the minimum chain-of-thought steps for a single-layer hard-attention Transformer, with matching lower bounds for iterated composition and the k-th-one function.
-
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
The paper shows that any (k−1)-round protocol for the k-step pointer chasing problem requires Ω(n/k + k) communication, improving the previous Ω(n/k − k log n) bound.
-
Attention-based representations for multi-task computation
For min/max readout, two attention heads beat one head by an exponential resource gap, and for n-bit parity and symmetric Boolean functions, heads times polynomial degree must reach the threshold degree, with matching...
-
When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning
When reflections localize early errors, in-context search solves exp-small pass-rate problems with poly sequential attempts; otherwise it offers no asymptotic gain over parallel sampling, and the update is learnable a...
-
Provably Overwhelming Transformer Models with Designed Inputs
A verification algorithm proves that a trained single-layer transformer is 'overwhelmed' by a chosen prefix, meaning its output is insensitive to any appended string of bounded length.
-
Lower bounds on transformers with infinite precision
One-layer infinite-precision softmax transformers need at least polynomial embedding dimension or output MLP size to compute function composition or SUM2.
-
Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory
A boundary-preserving semantic-compilation theorem converts known one-way, streaming, and contextuality separations into architecture-independent coordination-width lower bounds for AI state-tracking solvers, with thr...
-
(Im)possibility of Automated Hallucination Detection in Large Language Models
Automated hallucination detection is equivalent to identifying the true language from positive data: impossible for most countable collections without negative examples, and always possible with them.
-
Linear Correlation in LM's Compositional Generalization and Hallucination
Language models' next-token predictions for related knowledge are connected by near-linear transformations that persist through fine-tuning, explaining both compositional generalization and hallucination.
-
Constructing Set-Compositional and Negated Representations for First-Stage Ranking
Vector operations on learned sparse representations compose union, intersection, and negation queries without fine-tuning, and adding negative term weights to SPLADE improves negation handling.
-
Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
The paper claims pause tokens strictly increase constant-precision, constant-depth Transformer expressivity from a subset of AC0 to AC0 (and log-precision to TC0), but the constant-precision proof is not sound as written.
Discussion (0). Continue with ORCID to comment.