Covariance-Aware Transformers for Quadratic Programming and Decision Making

The gist: Transformers can be explicitly constructed to solve classes of quadratic programs, and incorporating covariance information enables end-to-end decision making under structural constraints.

Theoretical Foundations for QP Solving

Quadratic programming (QP) is a central tool in modern optimization, underlying applications in control, machine learning, and finance The canonical form is min x 1/2 x T A x + b T x subject to Cx ⪯ d. Beyond this template, many practically important variants, including l1-regularized and l1-constrained formulations, remain convex and capture structural requirements such as sparsity, budgets, and transaction-cost constraints We study the following concrete question: To what extent can transformer architectures act as general-purpose QP solvers, and how does this capability translate into improved decision making when second-order statistics (e.g., covariance matrices) matter. Our constructions are highly compute-efficient and capture the individual contributions of the attention mechanism, MLP, and looping.

Emulating Classical Optimization Algorithms

The paper provides explicit constructions showing how transformer components can emulate classical first-order methods for multiple QP classes, including unconstrained, linearly constrained, l1-regularized, and l1-constrained programs. For the unconstrained QP (U), a single linear-attention head with a residual connection simulates one step of gradient descent for the unconstrained QP defined in Section 3.1 Specifically, Proposition 3.1 states that a single linear-attention head that attends from the x-row to the A-rows, followed by a residual on the x-row, realizes the update x k+1 = x k − γ(Ax k + b). Similarly, for linearly constrained QP (LC), Proposition 3.2 shows that a single macro-block consisting of two self-attention blocks and a residual on the x-row realizes the sequential update x k+1 = x k − γ Ax k + b + C Tλ k, λ k+1 = λ k + η (Cx k+1 − d).

Solving Regularized and Constrained QPs

The paper extends the unconstrained block to realize proximal and projected gradient descent algorithms for sparse QPs. Proposition 3.3 demonstrates that one (U) gradient step followed by a fixed two-layer ReLU FFN with a scalar threshold θ = γλ yields x k+1 = Sθ(yk) = proxγλ∥·∥1(yk), i.e., the ISTA update. Furthermore, Proposition 3.4 shows that one (U) gradient step followed by the same fixed two-layer ReLU FFN wrapped in a scalar threshold loop performs the exact Euclidean projection onto the l1-ball: x k+1 = Proj∥x∥1≤B(yk), i.e., projected gradient descent for (C).

Covariance-Aware Decision Making via Time2Decide

The central contribution is Time2Decide, a generic method to endow time-series foundation models (TSFMs) with transformer-based optimization that is covariance-aware. This method augments TSFM input with tokens that explicitly represent the covariance structure, enabling the model to learn an end-to-end mapping from historical context to decisions in one forward pass. Empirically, Time2Decide consistently outperforms (i) the base TSFM and (ii) supervised fine-tuning of the TSFM without covariance information, and it can even outperform the classical two-stage Predict-then-Optimize (PtO) procedure. The paper demonstrates that transformers benefit from explicit use of second-order statistics, enabling them to effectively solve complex decision-making problems, like portfolio construction, in one forward pass.

Empirical Validation and Performance

Experimental validation confirms that transformers can learn to solve QP problems when trained on tokenized problem instances, with linear attention variants consistently achieving higher accuracy. In a portfolio optimization case study, Time2Decide outperforms the classical two-stage PtO procedure under realistic scenarios. Specifically, Time2Decide surpasses it in regimes where end-to-end calibration matters most. Under noisy conditions, Time2Decide dominates most strategies across budgets. This confirms that end-to-end learning effectively mitigates input noise, aligning with the theory in Appendix F. The results position transformers as both (i) theoretically grounded algorithm emulators for regularized QPs and (ii) practical end-to-end decision makers when second-order/covariance information is essential.

Theoretical Limitations and Insights

The paper shows a simple obstruction demonstrating that with only pure data tokens, linear attention cannot synthesize even-degree statistics, such as covariance. Proposition G.1 proves that any finite stack of such components cannot construct even-degree statistics like P N i=1 x i T i or any map invariant under the global flip x i 7→ -x i. This empirical validation supports the theoretical analysis: while linear attention can learn covariance patterns when equipped with proper input projections/embeddings, removing these projections creates a fundamental barrier to learning even-degree statistics. The toy model comparison justifies why end-to-end policy outperforms PtO by shrinking noisy estimates toward the prior mean, which is what Time2Decide can implicitly learn through covariance information.

Conclusion

Overall, our results connect classical optimization methods with transformers, showing that transformers can efficiently emulate iterative solvers. Future directions include extending to broader optimization tasks, integrating with other foundation models or reinforcement learning for decision making, and studying the theoretical boundaries of such algorithmic emulation. The paper demonstrates that QP solving can be seamlessly incorporated through supervised fine-tuning by simply adding relevant tokens to the input sequence. This work positions transformers as both (i) theoretically grounded algorithm emulators for regularized QPs and (ii) practical end-to-end decision makers when second-order/covariance information is essential. The paper is 2602.14506.

--- Page 39 ---

References

Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 2023 Ekin Aky¨urek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=0g0X4H8yN4I Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International conference on machine learning, pages 136–145. PMLR, 2017 Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36:57125–57211, 2023 Jie Chen and Yongming Liu. Neural optimization machine: A neural network approach for optimization. arXiv preprint arXiv:2208.03897, 2022 Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. arXiv preprint arXiv:2209.12288, 2023 Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Shuming Ma, Zhifang Sui, and Furu Wei. Why can GPT learn in-context? language models secretly perform gradient descent as meta-optimizers. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki editors, Findings of the Association for Computational Linguistics: ACL 2023, pages 4005–4019, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.findings-acl.247. URL https://aclanthology.org/2023.findings-acl.247.> Halil Alperen Gozeten, M Emrullah Ildiz, Xuechen Zhang, Mahdi Soltanolkotabi, Marco Mondelli, and Samet Oymak. Test-time training provably improves transformers as in-context learners. Proceedings of machine learning research, 267:20266, 2025 Jake Grigsby, Zhe Wang, Nam Nguyen, and Yanjun Qi. Long-range transformers for dynamic spatiotemporal forecasting. arXiv preprint arXiv:2109.12218, 2021. URL https://arxiv.

1. Transformer based QP solvers can be used to solve classes of quadratic programs including unconstrained, linearly constrained, l1-regularized, and l1-constrained programs by emulating classical first-order methods. This capability allows for solving complex decision making problems like portfolio construction in one forward pass.

2. The Time2Decide method enhances time series foundation models by explicitly feeding the covariance matrix between variates, enabling end-to-end mapping from historical context to decisions in one forward pass. This is superior to the Predict-then-Optimize (PtO) procedure, outperforming it in regimes where end-to-end calibration matters most.

3. Time2Decide can outperform the base time series foundation model and supervised fine tuning of the time series foundation model without covariance information for portfolio optimization problems. This demonstrates that transformers benefit from explicit use of second-order statistics for solving complex decision making problems.

4. The LinearTransformer architecture is empirically shown to be particularly well suited for the numerical reasoning required in QP function approximation tasks, consistently outperforming the SoftmaxTransformer across hyperparameter grids and demonstrating superior performance under distribution shift in condition number.

5. The end-to-end learning strategy learns analogous attenuation directly from decision loss, allowing it to outperform the plug-in rule of PtO by shrinking noisy estimates toward the prior mean, which is justified by Proposition 5.1 in a toy model setting.

We explore the use of transformers for solving quadratic programs and how this capability benefits decision-making problems that involve covariance matrices. We first show that the linear attention mechanism can provably solve unconstrained QPs by tokenizing the matrix variables (e.g. A of the objective 1 over 2x Ax+b x) row-by-row and emulating gradient descent iterations. Furthermore, by incorporating MLPs, a transformer block can solve (i) 1-penalized QPs by emulating iterative soft-thresholding and (ii) 1-constrained QPs when equipped with an additional feedback loop. Our theory motivates us to introduce Time2Decide: a generic method that enhances a time series foundation model (TSFM) by explicitly feeding the covariance matrix between the variates. We empirically find that Time2Decide uniformly outperforms the base TSFM model for the classical portfolio optimization problem that admits an 1-constrained QP formulation. Remarkably, Time2Decide also outperforms the classical "Predict-then-Optimize (PtO)" procedure, where we first forecast the returns and then explicitly solve a constrained QP, in suitable settings. Our results demonstrate that transformers benefit from explicit use of second-order statistics, and this can enable them to effectively solve complex decision-making problems, like portfolio construction, in one forward pass.