AIConfPaper
← Search

Samet Oymak

51 accepted papers

2026

Continuous Chain of Thought Enables Parallel Exploration and Reasoning

Halil Alperen Gozeten, Muhammed Emrullah Ildiz, Xuechen Zhang, Hrayr Harutyunyan, Ankit Singh Rawat, Samet Oymak
ICLR 2026poster

Modern language models generate chain-of-thought traces by autoregressively sampling tokens from a finite vocabulary. While this discrete sampling has achieved remarkable success, conducting chain-of-thought with continuously-valued tokens (CoT2) offers a richer and more expressive alternative. Our…

Cited by 0Source ↗code ↗Scholar ↗
2026

Learning to Correct: Reinforcement Learning for Multi-Attempt Chain-of-Thought

Muhammed Emrullah Ildiz, Halil Alperen Gozeten, Ege Onur Taga, Samet Oymak
ICML 2026poster

State-of-the-art reasoning models can utilize long chain-of-thought to solve sophisticated coding and math problems. During this process, the model often attemps at a solution multiple times by utilizing verification and self-reflection capabilities. In this work, we view a long CoT as a process whe…

Cited by 0Source ↗Scholar ↗
2026

SmartChunk Retrieval: Query-Aware Chunk Compression with Planning for Efficient Document RAG

Xuechen Zhang, Koustava Goswami, Samet Oymak, Jiasi Chen, Nedim Lipka
ICLR 2026poster

Retrieval-augmented generation (RAG) has strong potential for producing accurate and factual outputs by combining language models (LMs) with evidence retrieved from large text corpora. However, current pipelines are limited by static chunking and flat retrieval: documents are split into short, prede…

Cited by 1Source ↗Scholar ↗
2026

Stochastic Sparse Attention for Memory-Bound Inference

Kyle Lee, Corentin Delacour, Kevin Callahan-Coray, Kyle Jiang, Can Yaras, Samet Oymak +2
ICML 2026poster

Autoregressive decoding becomes bandwidth-limited at long contexts, as generating each token requires reading all $n_k$ key and value vectors from KV cache. We present Stochastic Additive No-mulT Attention (SANTA), a method that sparsifies value-cache access by sampling $S \ll n_k$ indices from the …

Cited by 0Source ↗Scholar ↗
2025

AdMiT: Adaptive Multi-Source Tuning in Dynamic Environments

Xiangyu Chang, Fahim Faisal Niloy, Sk Miraj Ahmed, Srikanth V. Krishnamurthy, Basak Guler, Ananthram Swami +2
CVPR 2025poster

Incorporating transformer models into edge devices poses a significant challenge due to the computational demands of adapting these large models across diverse applications. Parameter-efficient tuning (PET) methods (e.g. LoRA, Adapter, Visual Prompt Tuning, etc.) allow for targeted adaptation by mod…

Cited by 0Source ↗PDF ↗Scholar ↗
2025

Attention with Trained Embeddings Provably Selects Important Tokens

Diyuan Wu, Aleksandr Shevchenko, Samet Oymak, Marco Mondelli
NeurIPS 2025poster

Token embeddings play a crucial role in language modeling but, despite this practical relevance, their theoretical understanding is limited. Our paper addresses the gap by characterizing the structure of embeddings obtained via gradient descent. Specifically, we consider a one-layer softmax attentio…

Cited by 0Source ↗Scholar ↗
2025

BREAD: Branched Rollouts from Expert Anchors Bridge SFT & RL for Reasoning

Xuechen Zhang, Zijian Huang, Yingcong Li, Chenshun Ni, Jiasi Chen, Samet Oymak
NeurIPS 2025poster

Small language models (SLMs) struggle to learn complex reasoning behaviors, especially when high-quality traces are scarce or difficult to learn from. A typical approach for training such models combines a supervised fine-tuning (SFT) stage, often to distill reasoning capabilities from a larger mode…

Cited by 0Source ↗Scholar ↗
2025

Everything Everywhere All at Once: LLMs can In-Context Learn Multiple Tasks in Superposition

Zheyang Xiong, Ziyang Cai, John Cooper, Albert Ge, Vasilis Papageorgiou, Zack Sifakis +8
ICML 2025spotlight

Large Language Models (LLMs) have demonstrated remarkable in-context learning (ICL) capabilities. In this study, we explore a surprising phenomenon related to ICL: LLMs can perform multiple, computationally distinct ICL tasks simultaneously, during a single inference call, a capability we term task…

Cited by 3Source ↗PDF ↗Scholar ↗
2025

Extrapolation by Association: Length Generalization Transfer In Transformers

Ziyang Cai, Nayoung Lee, Avi Schwarzschild, Samet Oymak, Dimitris Papailiopoulos
NeurIPS 2025spotlight

Transformer language models have demonstrated impressive generalization capabilities in natural language domains, yet we lack a fine-grained understanding of how such generalization arises. In this paper, we investigate length generalization—the ability to extrapolate from shorter to longer inputs—t…

Cited by 0Source ↗Scholar ↗
2025

High-dimensional Analysis of Knowledge Distillation: Weak-to-Strong Generalization and Scaling Laws

Muhammed Emrullah Ildiz, Halil Alperen Gozeten, Ege Onur Taga, Marco Mondelli, Samet Oymak
ICLR 2025spotlight

A growing number of machine learning scenarios rely on knowledge distillation where one uses the output of a surrogate model as labels to supervise the training of a target model. In this work, we provide a sharp characterization of this process for ridgeless, high-dimensional regression, under two…

Cited by 3Source ↗PDF ↗Scholar ↗
2025

Provable Benefits of Task-Specific Prompts for In-context Learning

Xiangyu Chang, Yingcong Li, Muti Kara, Samet Oymak, Amit Roy-Chowdhury
AISTATS 2025poster

The in-context learning capabilities of modern language models have motivated a deeper mathematical understanding of sequence models. A line of recent work has shown that linear attention models can emulate projected gradient descent iterations to implicitly learn the task vector from the data provi…

Cited by 0Source ↗code ↗Scholar ↗
2025

Test-Time Training Provably Improves Transformers as In-context Learners

Halil Alperen Gozeten, Muhammed Emrullah Ildiz, Xuechen Zhang, Mahdi Soltanolkotabi, Marco Mondelli, Samet Oymak
ICML 2025poster

Test-time training (TTT) methods explicitly update the weights of a model to adapt to the specific test instance, and they have found success in a variety of settings, including most recently language modeling and reasoning. To demystify this success, we investigate a gradient-based TTT algorithm fo…

Cited by 1Source ↗PDF ↗Scholar ↗
2025

Theoretical Insights into In-context Learning with Unlabeled Data

Yingcong Li, Xiangyu Chang, Muti Kara, Xiaofeng Liu, Amit Roy-Chowdhury, Samet Oymak
NeurIPS 2025poster

Recent research shows that in-context learning (ICL) can be effective even when demonstrations have missing or incorrect labels. To shed light on this capability, we examine a canonical setting where the demonstrations are drawn according to a binary Gaussian mixture model (GMM) and a certain fracti…

Cited by 0Source ↗Scholar ↗
2025

TimePFN: Effective Multivariate Time Series Forecasting with Synthetic Data

Ege Onur Taga, Muhammed Emrullah Ildiz, Samet Oymak
AAAI 2025technical

The diversity of time series applications and scarcity of domain-specific data highlight the need for time-series models with strong few-shot learning capabilities. In this work, we propose a novel training scheme and a transformer-based architecture, collectively referred to as TimePFN, for multiva…

Cited by 1Source ↗PDF ↗code ↗Scholar ↗
2024

A Score-Based Deterministic Diffusion Algorithm with Smooth Scores for General Distributions

Karthik Elamvazhuthi, Xuechen Zhang, Matthew Jacobs, Samet Oymak, Fabio Pasqualetti
AAAI 2024technical

Score matching based diffusion has shown to achieve the state of art results in generation modeling. In the original score matching based diffusion algorithm, the forward equation is a differential equation for which the probability density equation evolves according to a linear partial differential…

Cited by 1Source ↗PDF ↗Scholar ↗
2024

CONTRAST: Continual Multi-source Adaptation to Dynamic Distributions

Sk Miraj Ahmed, Fahim Faisal Niloy, Xiangyu Chang, Dripta S. Raychaudhuri, Samet Oymak, Amit Roy-Chowdhury
NeurIPS 2024poster

Adapting to dynamic data distributions is a practical yet challenging task. One effective strategy is to use a model ensemble, which leverages the diverse expertise of different models to transfer knowledge to evolving data distributions. However, this approach faces difficulties when the dynamic te…

Cited by 1Source ↗PDF ↗Scholar ↗
2024

Can Mamba Learn How To Learn? A Comparative Study on In-Context Learning Tasks

Jongho Park, Jaeseung Park, Zheyang Xiong, Nayoung Lee, Jaewoong Cho, Samet Oymak +2
ICML 2024poster

State-space models (SSMs), such as Mamba (Gu & Dao, 2023), have been proposed as alternatives to Transformer networks in language modeling, incorporating gating, convolutions, and input-dependent token selection to mitigate the quadratic cost of multi-head attention. Although SSMs exhibit competitiv…

Cited by 83Source ↗PDF ↗code ↗Scholar ↗
2024

Class-Attribute Priors: Adapting Optimization to Heterogeneity and Fairness Objective

Xuechen Zhang, Mingchen Li, Jiasi Chen, Christos Thrampoulidis, Samet Oymak
AAAI 2024technical

Modern classification problems exhibit heterogeneities across individual classes: Each class may have unique attributes, such as sample size, label quality, or predictability (easy vs difficult), and variable importance at test-time. Without care, these heterogeneities impede the learning process, m…

Cited by 2Source ↗PDF ↗Scholar ↗
2024

Efficient Contextual LLM Cascades through Budget-Constrained Policy Learning

Xuechen Zhang, Zijian Huang, Ege Onur Taga, Carlee Joe-Wong, Samet Oymak, Jiasi Chen
NeurIPS 2024poster

Recent successes in natural language processing have led to the proliferation of large language models (LLMs) by multiple providers. Each LLM offering has different inference accuracy, monetary cost, and latency, and their accuracy further depends on the exact wording of the question (i.e., the spec…

Cited by 0Source ↗PDF ↗Scholar ↗
2024

Fine-grained Analysis of In-context Linear Estimation: Data, Architecture, and Beyond

Yingcong Li, Ankit Singh Rawat, Samet Oymak
NeurIPS 2024poster

Recent research has shown that Transformers with linear attention are capable of in-context learning (ICL) by implementing a linear estimator through gradient descent steps. However, the existing results on the optimization landscape apply under stylized settings where task and feature vectors are a…

Cited by 4Source ↗PDF ↗Scholar ↗
2024

From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers

Muhammed Emrullah Ildiz, Yixiao Huang, Yingcong Li, Ankit Singh Rawat, Samet Oymak
ICML 2024poster

Modern language models rely on the transformer architecture and attention mechanism to perform language understanding and text generation. In this work, we study learning a 1-layer self-attention model from a set of prompts and the associated outputs sampled from the model. We first establish a form…

Cited by 19Source ↗PDF ↗Scholar ↗
2024

Mechanics of Next Token Prediction with Self-Attention

Yingcong Li, Yixiao Huang, Muhammed E. Ildiz, Ankit Singh Rawat, Samet Oymak
AISTATS 2024poster

Transformer-based language models are trained on large datasets to predict the next token given an input sequence. Despite this simple training objective, they have led to revolutionary advances in natural language processing. Underlying this success is the self-attention mechanism. In this work, we…

Cited by 34Source ↗PDF ↗Scholar ↗
2024

Selective Attention: Enhancing Transformer through Principled Context Control

Xuechen Zhang, Xiangyu Chang, Mingchen Li, Amit Roy-Chowdhury, Jiasi Chen, Samet Oymak
NeurIPS 2024poster

The attention mechanism within the transformer architecture enables the model to weigh and combine tokens based on their relevance to the query. While self-attention has enjoyed major success, it notably treats all queries $q$ in the same way by applying the mapping $V^\top\text{softmax}(Kq)$, where…

Cited by 2Source ↗PDF ↗code ↗Scholar ↗
2024

Understanding Inverse Scaling and Emergence in Multitask Representation Learning

Muhammed E. Ildiz, Zhe Zhao, Samet Oymak
AISTATS 2024poster

Large language models exhibit strong multitasking capabilities, however, their learning dynamics as a function of task characteristics, sample size, and model complexity remain mysterious. For instance, it is known that, as the model size grows, large language models exhibit emerging abilities where…

Cited by 1Source ↗PDF ↗Scholar ↗
2023

Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learning

Yingcong Li, Kartik Sreenivasan, Angeliki Giannou, Dimitris Papailiopoulos, Samet Oymak
NeurIPS 2023poster

Chain-of-thought (CoT) is a method that enables language models to handle complex reasoning tasks by decomposing them into simpler steps. Despite its success, the underlying mechanics of CoT are not yet fully understood. In an attempt to shed light on this, our study investigates the impact of CoT o…

Cited by 29Source ↗PDF ↗code ↗Scholar ↗
2023

Max-Margin Token Selection in Attention Mechanism

Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, Samet Oymak
NeurIPS 2023spotlight

Attention mechanism is a central component of the transformer architecture which led to the phenomenal success of large language models. However, the theoretical principles underlying the attention mechanism are poorly understood, especially its nonconvex optimization dynamics. In this work, we expl…

Cited by 56Source ↗PDF ↗code ↗Scholar ↗
2023

On the Role of Attention in Prompt-tuning

Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, Christos Thrampoulidis
ICML 2023poster

Prompt-tuning is an emerging strategy to adapt large language models (LLM) to downstream tasks by learning a (soft-)prompt parameter from data. Despite its success in LLMs, there is limited theoretical understanding of the power of prompt-tuning and the role of the attention mechanism in prompting.…

Cited by 60Source ↗PDF ↗Scholar ↗
2023

Stochastic Contextual Bandits with Long Horizon Rewards

Yuzhen Qin, Yingcong Li, Fabio Pasqualetti, Maryam Fazel, Samet Oymak
AAAI 2023technical

The growing interest in complex decision-making and language modeling problems highlights the importance of sample-efficient learning over very long horizons. This work takes a step in this direction by investigating contextual linear bandits where the current reward depends on at most s prior actio…

Cited by 6Source ↗PDF ↗Scholar ↗
2023

Transformers as Algorithms: Generalization and Stability in In-context Learning

Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, Samet Oymak
ICML 2023poster

In-context learning (ICL) is a type of prompting where a transformer model operates on a sequence of (input, output) examples and performs inference on-the-fly. In this work, we formalize in-context learning as an algorithm learning problem where a transformer model implicitly constructs a hypothesi…

Cited by 191Source ↗PDF ↗code ↗Scholar ↗
2022

FedNest: Federated Bilevel, Minimax, and Compositional Optimization

Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, Samet Oymak
ICML 2022oral

Standard federated optimization methods successfully apply to stochastic problems with single-level structure. However, many contemporary ML problems - including adversarial robustness, hyperparameter tuning, actor-critic - fall under nested bilevel programming that subsumes minimax and compositiona…

Cited by 81Source ↗PDF ↗code ↗Scholar ↗
2021

A Theoretical Characterization of Semi-supervised Learning with Self-training for Gaussian Mixture Models

Samet Oymak, Talha Cihad Gulcu
AISTATS 2021poster

Self-training is a classical approach in semi-supervised learning which is successfully applied to a variety of machine learning problems. Self-training algorithms generate pseudo-labels for the unlabeled examples and progressively refine these pseudo-labels which hopefully coincides with the actual…

Cited by 17Source ↗PDF ↗Scholar ↗
2021

AutoBalance: Optimized Loss Functions for Imbalanced Data

Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, Samet Oymak
NeurIPS 2021poster

Imbalanced datasets are commonplace in modern machine learning problems. The presence of under-represented classes or groups with sensitive attributes results in concerns about generalization and fairness. Such concerns are further exacerbated by the fact that large capacity deep nets can perfectly…

Cited by 79Source ↗PDF ↗code ↗Scholar ↗
2021

Generalization Guarantees for Neural Architecture Search with Train-Validation Split

Samet Oymak, Mingchen Li, Mahdi Soltanolkotabi
ICML 2021spotlight

Neural Architecture Search (NAS) is a popular method for automatically designing optimized deep-learning architectures. NAS methods commonly use bilevel optimization where one optimizes the weights over the training data (lower-level problem) and hyperparameters - such as the architecture - over the…

Cited by 25Source ↗PDF ↗Scholar ↗
2021

Label-Imbalanced and Group-Sensitive Classification under Overparameterization

Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, Christos Thrampoulidis
NeurIPS 2021poster

The goal in label-imbalanced and group-sensitive classification is to optimize relevant metrics such as balanced error and equal opportunity. Classical methods, such as weighted cross-entropy, fail when training deep nets to the terminal phase of training (TPT), that is training beyond zero training…

Cited by 108Source ↗PDF ↗code ↗Scholar ↗
2021

On the Marginal Benefit of Active Learning: Does Self-Supervision Eat its Cake?

Yao-Chun Chan, Mingchen Li, Samet Oymak
ICASSP 2021accepted

Active learning is the set of techniques for intelligently labeling large unlabeled datasets to reduce the labeling effort. In parallel, recent developments in self-supervised and semi-supervised learning (S4L) provide powerful techniques, based on data-augmentation, contrastive learning, and self-t…

Cited by 0Source ↗Scholar ↗
2021

Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural Networks

Xiangyu Chang, Yingcong Li, Samet Oymak, Christos Thrampoulidis
AAAI 2021technical

Deep networks are typically trained with many more parameters than the size of the training dataset. Recent empirical evidence indicates that the practice of overparameterization not only benefits training large models, but also assists – perhaps counterintuitively – building lightweight models. Spe…

Cited by 63Source ↗PDF ↗Scholar ↗
2021

Sample Efficient Subspace-Based Representations for Nonlinear Meta-Learning

Halil Ibrahim Gulluk, Yue Sun, Samet Oymak, Maryam Fazel
ICASSP 2021accepted

Constructing good representations is critical for learning complex tasks in a sample efficient manner. In the context of meta-learning, representations can be constructed from common patterns of previously seen tasks so that a future task can be learned quickly. While recent works show the benefit o…

Cited by 0Source ↗Scholar ↗
2021

Towards Sample-efficient Overparameterized Meta-learning

Yue Sun, Adhyyan Narang, Halil Ibrahim Gulluk, Samet Oymak, Maryam Fazel
NeurIPS 2021poster

An overarching goal in machine learning is to build a generalizable model with few samples. To this end, overparameterization has been the subject of immense interest to explain the generalization ability of deep nets even when the size of the dataset is smaller than that of the model. While the pri…

Cited by 25Source ↗PDF ↗code ↗Scholar ↗
2021

Unsupervised Multi-Source Domain Adaptation Without Access to Source Data

Sk Miraj Ahmed, Dripta S. Raychaudhuri, Sujoy Paul, Samet Oymak, Amit K. Roy-Chowdhury
CVPR 2021poster

Unsupervised Domain Adaptation (UDA) aims to learn a predictor model for an unlabeled dataset by transferring knowledge from a labeled source data, which has been trained on similar tasks. However, most of these conventional UDA approaches have a strong assumption of having access to the source data…

Cited by 200PDF ↗Scholar ↗
2020

Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks

Mingchen Li, Mahdi Soltanolkotabi, Samet Oymak
AISTATS 2020poster

Modern neural networks are typically trained in an over-parameterized regime where the parameters of the model far exceed the size of the training data. Such neural networks in principle have the capacity to (over)fit any set of labels including significantly corrupted ones. Despite this (over)fitti…

Cited by 453Source ↗PDF ↗Scholar ↗
2020

Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View

Christos Thrampoulidis, Samet Oymak, Mahdi Soltanolkotabi
NeurIPS 2020poster

Contemporary machine learning applications often involve classification tasks with many classes. Despite their extensive use, a precise understanding of the statistical properties and behavior of classification algorithms is still missing, especially in modern regimes where the number of classes is…

Cited by 57Source ↗PDF ↗Scholar ↗
2019

Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Samet Oymak, Mahdi Soltanolkotabi
ICML 2019oral

Many modern learning tasks involve fitting nonlinear models which are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Due to this overparameterization, the training loss may have infinitely many global minima and it is critical to und…

Cited by 223Source ↗PDF ↗Scholar ↗
2017

Near-optimal sample complexity bounds for circulant binary embedding

Samet Oymak, Christos Thrampoulidis, Babak Hassibi
ICASSP 2017accepted

Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g. circulant matrices. While binary…

Cited by 0Source ↗Scholar ↗
2015

Parallel Correlation Clustering on Big Graphs

Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, Michael I Jordan
NeurIPS 2015poster

Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: an algorithm that serially clusters neighborhoods of vertices, and obtains a 3-approximation ratio. Unfortunately, in pr…

Cited by 111Source ↗PDF ↗code ↗Scholar ↗
2015

The proportional mean decomposition: A bridge between the Gaussian and bernoulli ensembles

Samet Oymak, Babak Hassibi
ICASSP 2015accepted

We consider ill-posed linear inverse problems involving the estimation of structured sparse signals. When the sensing matrix has i.i.d. standard normal entries, there is a full-fledged theory on the sample complexity and robustness properties. In this work, we propose a way of making use of this the…

Cited by 0Source ↗Scholar ↗