Back to search

Boston University

Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness

Abstract

dc:description.abstract

This thesis explores Nearest Neighbor Algorithms across diverse areas of Machine Learning and Theoretical Computer Science. First, it advances the theoretical understanding of Sparse Transformer architectures that leverage k Nearest Neighbor primitives. Second, it introduces novel algorithms to enhance the adversarial robustness of efficient nearest neighbor search methods. Transformers have revolutionized machine learning, but their quadratic self-attention complexity poses challenges for long-sequence processing. To address this limitation, k-Nearest-Neighbor (kNN) attention enables each token to attend only to its k closest tokens, achieving improved efficiency. However, the theoretical foundations of kNN attention remain underexplored. This work establishes a rigorous framework for kNN attention, reformulating self-attention as expectations over softmax distributions and leveraging lazy Gumbel sampling with kNN indices for efficient approximation. Building on this framework, we propose novel sub-quadratic algorithms that approximate self-attention gradients using techniques such as Markov Chain-based estimation. Empirical experiments validate the effectiveness of these methods, demonstrating benefits in both training and inference. In parallel, we investigate adversarial robustness guarantees for computational search problems, particularly Approximate Nearest Neighbor Search via Locality Sensitive Hashing (LSH). While adversarial robustness has primarily focused on estimation problems, little attention has been given to protecting internal algorithmic randomness when returning specific data points. We extend the adversarial robustness framework by integrating differential privacy with fair near-neighbor algorithms to secure search problems under adversarial conditions. Additionally, we propose an alternative approach that foregoes fair algorithms, leveraging deterministic exhaustive searches on small data subsets. Furthermore, we demonstrate how "for all" guarantees in randomized algorithms yield efficient solutions in low-dimensional settings.

Degree

thesis:*
Name thesis:degree_name
Master of Science
Level thesis:degree_level
masters
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Haris, Themistoklis
Advisor dc:contributor.advisor
  • Onak, Krzysztof
ORCID dc:identifier.orcid

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53188

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Haris, Themistoklis. Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness. masters thesis, Boston University, 2024. https://hdl.handle.net/2144/53188