4 papers
Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders
Faizanuddin Ansari, Debanjan Dutta, Swagatam Das
In-context learning is commonly formalized as inference from examples of a function. Partial orders instead combine transitivity, antisymmetry, and incomparability, so a finite pro…
Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
Debanjan Dutta, Anish Chakrabarty, Swagatam Das
Chain of Thought (CoT) lifts the expressive ceiling of bounded-depth Transformers, with characterizations tying the number of CoT steps to circuit complexity classes. What remains…
Assessing the Limits of In-Context Learning beyond Functions using Partially Ordered Relation
Debanjan Dutta, Faizanuddin Ansari, Swagatam Das
Generating rational and generally accurate responses to tasks, often accompanied by example demonstrations, highlights Large Language Model's (LLM's) remarkable In-Context Learning…
On the Existence of Universal Simulators of Attention
Debanjan Dutta, Anish Chakrabarty, Faizanuddin Ansari +1
Previous work on the learnability of transformers \textemdash\ focused primarily on examining their ability to approximate specific algorithmic patterns through training \textemdas…