21 papers
Discovering Data Structures: Nearest Neighbor Search and Beyond
Omar Salemohamed, Laurent Charlin, Shivam Garg +2
We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and…
Limitations on Accurate, Trusted, Human-level Reasoning
Rina Panigrahy, Vatsal Sharan
We identify a fundamental incompatibility between the goals of accuracy, trust, and human-level reasoning in artificial intelligence (AI) systems, for strict mathematical definitio…
Convergent Evolution: How Different Language Models Learn Similar Number Representations
Deqing Fu, Tianyi Zhou, Mikhail Belkin +2
Language models trained on natural text learn to represent numbers using periodic features with dominant periods at . In this paper, we identify a two-tiered hierarchy…
FoNE: Precise Single-Token Number Embeddings via Fourier Features
Tianyi Zhou, Deqing Fu, Mahdi Soltanolkotabi +2
Large Language Models (LLMs) typically represent numbers using multiple tokens, which requires the model to aggregate these tokens to interpret numerical values. This fragmentation…
Understanding Contextual Recall in Transformers: How Finetuning Enables In-Context Reasoning over Pretraining Knowledge
Bhavya Vasudeva, Puneesh Deora, Alberto Bietti +2
Transformer-based language models excel at in-context learning (ICL), where they can adapt to new tasks based on contextual examples, without parameter updates. In a specific form…
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju +1
We present a unified framework for proving memory lower bounds for multi-pass streaming algorithms that detect planted structures. Planted structures -- such as cliques or biclique…