Optimal Feature Acquisition for Transformers

We study the offline design of a cost-constrained reusable acquisition panel for structured inputs processed by a frozen pretrained transformer. Each candidate panel induces a full-template masked input that is passed through the encoder afresh, making the resulting embeddings—and hence downstream utility—panel dependent. For locally decomposable downstream objectives, we reduce this encoder-aware problem to cardinality-constrained local-factor-sum optimization. We establish NP-hardness, APX-hardness, and parameterized hardness, give exact algorithms parameterized by the pathwidth or treewidth of the induced primal graph, and prove matching conditional lower bounds under ETH and SETH, identifying these widths as sharp worst-case tractability parameters. We then derive width certificates from the attention geometry of multi-layer, multi-head transformers. Finally, by optimizing hard-structured surrogates and controlling truncation and propagation errors, we extend the framework to approximate attention structures and obtain an explicit fidelity–tractability guarantee.