# Boundary on the Table: Efficient Black-Box Decision-Based Attacks for Structured Data

arXiv: https://arxiv.org/abs/2509.22850 · HTML: https://mlsanity.com/paper/2509.22850/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 20 of 20)

- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Adversarial NLI: A New Benchmark for Natural Language Understanding](https://mlsanity.com/paper/1910.14599/) (2019)
- [TabPFN: A Transformer That Solves Small Tabular Classification Problems in a Second](https://mlsanity.com/paper/2207.01848/) (2022)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [TabLLM: Few-shot Classification of Tabular Data with Large Language Models](https://mlsanity.com/paper/2210.10723/) (2022)
- [CatBoost: gradient boosting with categorical features support](https://mlsanity.com/paper/1810.11363/) (2018)
- [Adversarial Attacks for Tabular Data: Application to Fraud Detection and Imbalanced Data](https://mlsanity.com/paper/2101.08030/) (2021)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Imperceptible Adversarial Attacks on Tabular Data](https://mlsanity.com/paper/1911.03274/) (2019)
- [Red Teaming the Mind of the Machine: A Systematic Evaluation of Prompt Injection and Jailbreak Vulnerabilities in LLMs](https://mlsanity.com/paper/2505.04806/) (2025)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Constrained Adaptive Attack: Effective Adversarial Attack Against Deep Neural Networks for Tabular Data](https://mlsanity.com/paper/2406.00775/) (2024)
- [VAULT: Vigilant Adversarial Updates via LLM-Driven Retrieval-Augmented Generation for NLI](https://mlsanity.com/paper/2508.00965/) (2025)
- [Don't Lag, RAG: Training-Free Adversarial Detection Using RAG](https://mlsanity.com/paper/2504.04858/) (2025)
- [Investigating Imperceptibility of Adversarial Attacks on Tabular Data: An Empirical Analysis](https://mlsanity.com/paper/2407.11463/) (2024)
- [TabAttackBench: A Benchmark for Adversarial Attacks on Tabular Data](https://mlsanity.com/paper/2505.21027/) (2025)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)

## Abstract (arXiv)

Adversarial robustness in structured data remains an underexplored frontier compared to vision and language domains. In this work, we introduce a novel black-box, decision-based adversarial attack tailored for tabular data. Our approach combines gradient-free direction estimation with an iterative boundary search, enabling efficient navigation of discrete and continuous feature spaces under minimal oracle access. Extensive experiments demonstrate that our method successfully compromises nearly the entire test set across diverse models, ranging from classical machine learning classifiers to large language model (LLM)-based pipelines. Remarkably, the attack achieves success rates consistently above 90%, while requiring only a small number of queries per instance. These results highlight the critical vulnerability of tabular models to adversarial perturbations, underscoring the urgent need for stronger defenses in real-world decision-making systems.