Results 441 - 450 of 24335

Length generalization, the ability of sequence models to generalize to sequences longer than those encountered during training, remains a key challenge for transformers, especially in tasks requiring algorithmic reasoning. Existing theoretical understanding of length generalization is limited, often providing only asymptotic results or focusing on specific problem classes or architectural variants, while empirical approaches frequently rely on ad hoc and often fragile techniques.

In this work we introduce a novel framework for analyzing and proving length generalization bounds under specified, verifiable assumptions. A key outcome of the theory is the identification of a natural set of auxiliary tasks, intricately related to the primary task structure, such that strong performance on these auxiliary tasks, alongside the primary task, provably guarantees length generalization within the framework. This motivates a multi-task training procedure that explicitly optimizes performance on both the primary and the identified auxiliary tasks.

Empirical evaluations on a variety of synthetic benchmarks known to be challenging for length generalization, including sequence sorting, and reversal, demonstrate that our proposed method yields significant improvements in generalization to substantially longer sequences.

As machine learning systems become larger and more opaque, our relationship to them increasingly shifts from inspection to interaction. We evaluate, audit, benchmark, red-team, and delegate to systems whose internal behavior we cannot fully characterize. This may seem like a new challenge created by modern AI, but in many ways it is deeply aligned with longstanding themes in theoretical computer science.

This talk argues, through examples drawn from privacy auditing and delegation in principal-agent settings, that many areas of TCS can be viewed as studying reliable interaction with black boxes under limited observability. The goal is not always to open the black box, but to understand what guarantees remain possible when we cannot.