Elamur Research⌕
☰
home / papers / 2023 / Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time

Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time

Paper · 2023 · Zichang Liu, Jue Wang, Tri Dao et al.

Summary

Serving very large language models is slow, especially when generating tokens one at a time in latency-sensitive settings. Classic pruning does not solve this well. Retraining models with hundreds of billions of parameters is impractical, task-specific pruning undermines general-purpose use, and unstructured sparsity rarely gives real GPU speedups. The authors propose contextual sparsity: for each input, only a small subset of attention heads and MLP neurons is needed to reproduce the dense model's output almost exactly. They show that this subset exists, with roughly 85% structured sparsity on average, and that small learned predictors can estimate it from the current layer's activations. Their system, DEJAVU, combines these predictors with an asynchronous "lookahead" scheme and hardware-aware sparse kernels. On OPT-175B it cuts end-to-end generation latency by more than 2× relative to FasterTransformer and by more than 6× relative to Hugging Face, with no measurable loss on zero-shot tasks or perplexity. The method needs no retraining of the base model, works with 4-bit quantization, and transfers to OPT-66B and BLOOM.

Key points

  • On average, about 85% of structured parameters can be skipped per input while keeping essentially the same output. In theory, this allows up to a 7× parameter reduction per input.
  • On OPT-175B, the method keeps accuracy unchanged at 85% MLP sparsity and 50% attention-head sparsity. Evaluation covered CB, COPA, Lambada, OpenBookQA, PIQA, RTE and Winogrande, plus perplexity on Wikitext and C4.
  • The sparsity predictors are trained on only 500 random samples from the C4 training set. MLP predictor validation accuracy exceeds 99% in early layers and falls to about 93% in the final layers.
  • Results on other models:
    • OPT-66B shows no loss at 50% sparsity.
    • BLOOM holds up at 50% attention and 30% MLP sparsity; the lower MLP level is attributed to its different activation function.
    • Combining 75% sparsity with W4A16 quantization on OPT-175B works without compounding errors.
  • A non-contextual baseline that selects parameters from the raw input embedding already loses accuracy at 50% sparsity.

Interesting ideas

  • I1. Input-dependent structured skipping instead of static pruning. The model is left untouched, and the system decides per input which heads or neurons to compute. This avoids retraining and keeps the model general-purpose, so the idea suits any large frozen model where fine-tuning is too costly.
  • I2. Lookahead prediction using slowly changing residual streams. Hidden states change little from layer to layer, so the input to one block can predict which parts of the next block are needed. The prediction then runs in parallel instead of sitting on the critical path. The same trick could hide overhead in other per-layer routing or caching decisions.
  • I3. Framing selection as similarity search. Choosing relevant neurons or heads is treated as finding parameters most "similar" to the current activation, much like nearest-neighbor search. Cheap learned predictors then stand in for an exact search. This view could apply to mixture-of-experts routing or retrieval-style computation skipping.
  • I4. Checking existence before building the predictor. The authors first confirm, with a simple two-pass procedure, that a sparse subset reproducing the output actually exists. Only then do they invest in prediction. Separating "is there headroom?" from "can we capture it?" is a useful discipline for any efficiency project.
  • I5. Testing whether approximations compound. Combining sparsity with 4-bit quantization and checking that the errors do not stack is an evaluation pattern worth reusing whenever several compression methods are layered together.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian and Christopher Re. 2023. Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time. ICML 2023.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 2310.17157

@inproceedings{liu2023deja,
  title = {{Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time}},
  author = {Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian and Christopher Re},
  booktitle = {ICML 2023},
  year = {2023},
  eprint = {2310.17157},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.17157}
}

References

146 references, 26 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Winogrande: An adversarial winograd schema challenge at scale. 2019. find
  2. Allen-Zhu, Z. and Li, Y. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019. find
  3. Alman, J. and Song, Z. Fast attention requires bounded entries. arXiv preprint arXiv:2302.13214, 2023. — [arXiv:2302.13214](https://arxiv.org/abs/2302.13214) find
  4. Alman, J., Liang, J., Song, Z., Zhang, R., and Zhuo, D. Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing. arXiv preprint arXiv:2211.14227, 2022. — [arXiv:2211.14227](https://arxiv.org/abs/2211.14227) find
  5. Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 20–29, 1996. find
  6. Aminabadi, R. Y., Rajbhandari, S., Awan, A. A., Li, C., Li, D., Zheng, E., Ruwase, O., Smith, S., Zhang, M., Rasley, J., et al. Deepspeed-inference: Enabling efficient inference of transformer models at unprecedented scale. In 2022 SC22: International Conference for High Performance Computing, Netwo… find
  7. IEEE Computer Society, 2022. find
  8. Andoni, A. and Razenshteyn, I. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC), pp. 793–801, 2015. find
  9. Andoni, A., Indyk, P., Nguyen, H. L., and Razenshteyn, I. Beyond locality-sensitive hashing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 1018–1028. SIAM, 2014. find
  10. Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., and Schmidt, L. Practical and optimal lsh for angular distance. In Advances in Neural Information Processing Systems (NIPS), pp. 1225–1233. Curran Associates, 2015. find
  11. Andoni, A., Laarhoven, T., Razenshteyn, I., and Waingarten, E. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 47–66. SIAM, 2017. find
  12. Andoni, A., Indyk, P., and Razenshteyn, I. Approximate nearest neighbor search in high dimensions. arXiv preprint arXiv:1806.09823, 7, 2018. — [arXiv:1806.09823](https://arxiv.org/abs/1806.09823) find
  13. Arya, S. and Mount, D. M. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pp. 271–280. Citeseer, 1993. find
  14. Balduzzi, D., Frean, M., Leary, L., Lewis, J., Ma, K. W.-D., and McWilliams, B. The shattered gradients problem: If resnets are the answer, then what is the question? In International Conference on Machine Learning, pp. 342–350. PMLR, 2017. find
  15. Bansal, H., Gopalakrishnan, K., Dingliwal, S., Bodapati, S., Kirchhoff, K., and Roth, D. Rethinking the role of scale for in-context learning: An interpretability-based case study at 66 billion scale. arXiv preprint arXiv:2212.09095, 2022. find
  16. Baum, L. E. and Petrie, T. Statistical inference for probabilistic functions of finite state markov chains. The annals of mathematical statistics, 37(6):1554–1563, 1966. find
  17. Bello, I., Fedus, W., Du, X., Cubuk, E. D., Srinivas, A., Lin, T.-Y., Shlens, J., and Zoph, B. Revisiting resnets: Improved training and scaling strategies. Advances in Neural Information Processing Systems, 34:22614–22627, 2021. find
  18. Bengio, Y., Ducharme, R., Vincent, P., and Jauvin, C. A neural probabilistic language model. Journal of machine learning research (JMLR), 3(Feb):1137–1155, 2003.
  19. Bisk, Y., Zellers, R., Bras, R. L., Gao, J., and Choi, Y. Piqa: Reasoning about physical commonsense in natural language. In Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020.
  20. Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U. S., Purohit, S., Reynolds, L., Tow, J., Wang, B., and Weinbach, S. GPT-NeoX-20B: An open-source autoregressive language model. In Proceedings of the ACL Wor…
  21. Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258, 2021.
  22. Boutsidis, C., Woodruff, D. P., and Zhong, P. Optimal principal component analysis in distributed and streaming models. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016. find
  23. Boytsov, L., Novak, D., Malkov, Y., and Nyberg, E. Off the beaten path: Let’s replace term-based retrieval with k-nn search. In Proceedings of the 25th ACM international on conference on information and knowledge management (CIKM), pp. 1099–1108, 2016. find
  24. Brand, J. v. d., Peng, B., Song, Z., and Weinstein, O. Training (overparametrized) neural networks in near-linear time. In ITCS, 2021. find
  25. Brand, J. v. d., Song, Z., and Zhou, T. Algorithm and hardness for dynamic attention maintenance in large language models. arXiv preprint arXiv:2304.02207, 2023. — [arXiv:2304.02207](https://arxiv.org/abs/2304.02207) find
  26. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877–1901, 2020.
  27. Chan, S. C., Santoro, A., Lampinen, A. K., Wang, J. X., Singh, A. K., Richemond, P. H., McClelland, J., and Hill, F. Data distributional properties drive emergent in-context learning in transformers. In Advances in Neural Information Processing Systems, 2022. find
  28. Chang, W.-C., Yu, F. X., Chang, Y.-W., Yang, Y., and Kumar, S. Pre-training tasks for embedding-based large-scale retrieval. arXiv preprint arXiv:2002.03932, 2020. — [arXiv:2002.03932](https://arxiv.org/abs/2002.03932) find
  29. Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693–703. Springer, 2002. find
  30. Chen, B., Xu, Y., and Shrivastava, A. Fast and accurate stochastic gradient estimation. Advances in Neural Information Processing Systems, 32, 2019. find
  31. Chen, B., Medini, T., Farwell, J., Tai, C., Shrivastava, A., et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291–306, 2020a. find
  32. Chen, B., Dao, T., Winsor, E., Song, Z., Rudra, A., and Ré, C. Scatterbrain: Unifying sparse and low-rank attention. Advances in Neural Information Processing Systems, 34: 17413–17426, 2021a. find
  33. Chen, B., Liu, Z., Peng, B., Xu, Z., Li, J. L., Dao, T., Song, Z., Shrivastava, A., and Re, C. Mongoose: A learnable lsh framework for efficient neural network training. In International Conference on Learning Representations, 2021b. find
  34. Chen, H., Chillotti, I., Dong, Y., Poburinnaya, O., Razenshteyn, I., and Riazi, M. S. {SANNS}: Scaling up secure approximate k-nearest neighbors search. In 29th {USENIX} Security Symposium ({USENIX} Security 20), pp. 2111–2128, 2020b. find
  35. Chen, L. On the hardness of approximate and exact (bichromatic) maximum inner product. In 33rd Computational Complexity Conference (CCC), 2018. find
  36. Cho, J. H. and Hariharan, B. On the efficacy of knowledge distillation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4794–4802, 2019. find
  37. Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
  38. Clarkson, K. L. and Woodruff, D. P. Low-rank approximation and regression in input sparsity time. In STOC, 2013. find
  39. Cohen, M. B. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 278–287. SIAM, 2016. find
  40. Cook, S. CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2012. ISBN 9780124159334. find
  41. Cox, M. and Cox, T. Multidimensional scaling, 315–347. Handbook of data visualization. Springer, Berlin, Germany, 2008. find
  42. Dao, T., Fu, D. Y., Ermon, S., Rudra, A., and Ré, C. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Advances in Neural Information Processing Systems, 2022. find
  43. Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry (SoCG), pp. 253–262, 2004. de Marneffe, M.-C., Simons, M., and Tonhauser, J. The commitmentbank: Inve…
  44. Deng, Y., Li, Z., and Song, Z. Attention scheme inspired softmax regression. arXiv preprint arXiv:2304.10411, 2023a. — [arXiv:2304.10411](https://arxiv.org/abs/2304.10411) find
  45. Deng, Y., Mahadevan, S., and Song, Z. Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension. arxiv preprint: arxiv 2304.03426, 2023b. — [arXiv:2304.03426](https://arxiv.org/abs/2304.03426) find
  46. Derpanis, K. G. Mean shift clustering. Lecture Notes, 32: 1–4, 2005. find
  47. Dettmers, T., Lewis, M., Belkada, Y., and Zettlemoyer, L. Llm. int8 (): 8-bit matrix multiplication for transformers at scale. arXiv preprint arXiv:2208.07339, 2022. find
  48. Dong, S., Lee, Y. T., and Ye, G. A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1784–1797, 2021. find
  49. Dong, Y., Indyk, P., Razenshteyn, I., and Wagner, T. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2019. find
  50. Fang, J., Yu, Y., Zhao, C., and Zhou, J. Turbotransformers: an efficient gpu serving system for transformer models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 389–402, 2021. find
  51. Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:1803.03635, 2018. find
  52. Frantar, E. and Alistarh, D. Massive language models can be accurately pruned in one-shot. arXiv preprint arXiv:2301.00774, 2023. find
  53. Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210.17323, 2022. find
  54. Frei, S., Cao, Y., and Gu, Q. Algorithm-dependent generalization bounds for overparameterized deep residual networks. Advances in neural information processing systems, 32, 2019. find
  55. Gao, L., Tow, J., Biderman, S., Black, S., DiPofi, A., Foster, C., Golding, L., Hsu, J., McDonell, K., Muennighoff, N., Phang, J., Reynolds, L., Tang, E., Thite, A., Wang, B., Wang, K., and Zou, A. A framework for few-shot language model evaluation, September 2021. URL https://doi.org/10.5281/zenod… — [doi:10.5281/zenodo.5371628](https://doi.org/10.5281/zenodo.5371628) ↗
  56. Gao, Y., Mahadevan, S., and Song, Z. An over-parameterized exponential regression. arXiv preprint arXiv:2303.16504, 2023a. — [arXiv:2303.16504](https://arxiv.org/abs/2303.16504) find
  57. Gao, Y., Song, Z., and Yang, X. Differentially private attention computation. arXiv preprint arXiv:2305.04701, 2023b. — [arXiv:2305.04701](https://arxiv.org/abs/2305.04701) find
  58. Giampiccolo, D., Magnini, B., Dagan, I., and Dolan, B. The third PASCAL recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pp. 1–9, Prague, June 2007. Association for Computational Linguistics. URL https://aclanthology.org/W07-… ↗
  59. Gionis, A., Indyk, P., Motwani, R., et al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pp. 518–529, 1999. find
  60. Gordon, A., Kozareva, Z., and Roemmele, M. SemEval-2012 task 7: Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In *SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Vol…
  61. June 2012. Association for Computational Linguistics. URL https://aclanthology.org/S12-1052. ↗
  62. Gu, Y. and Song, Z. A faster small treewidth sdp solver. arXiv preprint arXiv:2211.06033, 2022. — [arXiv:2211.06033](https://arxiv.org/abs/2211.06033) find
  63. Gu, Y., Song, Z., Yin, J., and Zhang, L. Low rank matrix completion via robust alternating minimization in nearly linear time. arXiv preprint arXiv:2302.11068, 2023. — [arXiv:2302.11068](https://arxiv.org/abs/2302.11068) find
  64. Hall, R. and Attenberg, J. Fast and accurate maximum inner product recommendations on map-reduce. In Proceedings of the 24th International Conference on World Wide Web (WWW), pp. 1263–1268, 2015. find
  65. Han, S., Mao, H., and Dally, W. J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015. find
  66. Harris, M. How to access global memory efficiently in CUDA C/C++ kernels. NVIDIA, Jan, 2013. find
  67. He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  68. He, Y., Liu, P., Wang, Z., Hu, Z., and Yang, Y. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 4340–4349, 2019. find
  69. Hinton, G., Vinyals, O., Dean, J., et al. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2(7), 2015.
  70. Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., and Peste, A. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(241):1–124, 2021. find
  71. Hooker, S. The hardware lottery. Communications of the ACM, 64(12):58–65, 2021. find
  72. Hu, H., Song, Z., Weinstein, O., and Zhuo, D. Training overparametrized neural networks in sublinear time. arXiv preprint arXiv:2208.04508, 2022. — [arXiv:2208.04508](https://arxiv.org/abs/2208.04508) find
  73. Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC), pp. 604–613, 1998a. find
  74. Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604–613, 1998b. find
  75. Indyk, P. and Wagner, T. Approximate nearest neighbors in limited space. In Conference On Learning Theory, pp. 2012–2036. find
  76. Ivanov, A., Dryden, N., Ben-Nun, T., Li, S., and Hoefler, T. Data movement is all you need: A case study on optimizing transformers. Proceedings of Machine Learning and Systems, 3:711–732, 2021. find
  77. Jacob, B., Kligys, S., Chen, B., Zhu, M., Tang, M., Howard, A., Adam, H., and Kalenichenko, D. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2704–2713, 2018. find
  78. Jiang, S., Song, Z., Weinstein, O., and Zhang, H. A faster algorithm for solving general lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 823–832, 2021. find
  79. Johnson, J., Douze, M., and Jégou, H. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547, 2019.
  80. Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984. find
  81. Kitaev, N., Kaiser, Ł., and Levskaya, A. Reformer: The efficient transformer. In ICLR, 2020.
  82. Kurtz, M., Kopinsky, J., Gelashvili, R., Matveev, A., Carr, J., Goin, M., Leiserson, W., Moore, S., Shavit, N., and Alistarh, D. Inducing and exploiting activation sparsity for fast inference on deep neural networks. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conferenc… find
  83. Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pp. 1302–1338, 2000. find
  84. LeCun, Y., Denker, J., and Solla, S. Optimal brain damage. Advances in neural information processing systems, 2, 1989. find
  85. Lee, M., He, X., Yih, W.-t., Gao, J., Deng, L., and Smolensky, P. Reasoning in vector space: An exploratory study of question answering. In ICLR, 2016. find
  86. Lee, N., Ajanthan, T., and Torr, P. H. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv:1810.02340, 2018. — [arXiv:1810.02340](https://arxiv.org/abs/1810.02340) find
  87. Lee, Y. T., Song, Z., and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory, pp. 2140–2157. PMLR, 2019. find
  88. Li, P., Li, X., and Zhang, C.-H. Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling. Advances in Neural Information Processing Systems, 32, 2019. find
  89. Li, S., Song, Z., Xia, Y., Yu, T., and Zhou, T. The closeness of in-context learning and weight shifting for softmax regression. arXiv preprint, 2023a. find
  90. Li, X. and Li, P. C-MinHash: Improving minwise hashing with circulant permutation. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp… find
  91. Li, Z., You, C., Bhojanapalli, S., Li, D., Rawat, A. S., Reddi, S. J., Ye, K., Chern, F., Yu, F., Guo, R., and Kumar, S. Large models are parsimonious learners: Activation sparsity in trained transformers, 2022. URL https://arxiv.org/abs/2210.06313. — [arXiv:2210.06313](https://arxiv.org/abs/2210.06313) ↗
  92. Li, Z., Song, Z., and Zhou, T. Solving regularized exp, cosh and sinh regression problems. arXiv preprint, 2303.15725, 2023b. find
  93. Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., Zhang, Y., Narayanan, D., Wu, Y., Kumar, A., et al. Holistic evaluation of language models. arXiv preprint arXiv:2211.09110, 2022. find
  94. Liu, Z., Sun, M., Zhou, T., Huang, G., and Darrell, T. Rethinking the value of network pruning. arXiv preprint arXiv:1810.05270, 2018. find
  95. Liu, Z., Xu, Z., Ji, A., Zhang, J., Li, J., Chen, B., and Shrivastava, A. Halos: Hashing large output space for cheap inference. Proceedings of Machine Learning and Systems, 4:110–125, 2022. find
  96. Lu, Y., Dhillon, P., Foster, D. P., and Ungar, L. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NIPS), pp. 369–377, 2013. find
  97. Malkov, Y., Ponomarenko, A., Logvinov, A., and Krylov, V. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45: 61–68, 2014. find
  98. Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824–836, 2018.
  99. Meng, X. and Mahoney, M. W. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 91–100, 2013. find
  100. Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models, 2016.
  101. Michel, P., Levy, O., and Neubig, G. Are sixteen heads really better than one? Advances in neural information processing systems, 32, 2019.
  102. Mihaylov, T., Clark, P., Khot, T., and Sabharwal, A. Can a suit of armor conduct electricity? a new dataset for open book question answering. In EMNLP, 2018. find
  103. Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837, 2022.
  104. Molchanov, P., Tyree, S., Karras, T., Aila, T., and Kautz, J. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:1611.06440, 2016. — [arXiv:1611.06440](https://arxiv.org/abs/1611.06440) find
  105. Nagel, M., Baalen, M. v., Blankevoort, T., and Welling, M. Data-free quantization through weight equalization and bias correction. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1325–1334, 2019. find
  106. Nelson, J. and Nguyên, H. L. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pp. 117–126. find
  107. Neyshabur, B. and Srebro, N. On symmetric and asymmetric lshs for inner product search. In International Conference on Machine Learning (ICML), pp. 1926–1934. find
  108. NVIDIA. Fastertransformer. https://github.com/NVIDIA/FasterTransformer. NVIDIA. Gpu performance background user’s guide, 2022. URL https://docs.nvidia. com/deeplearning/performance/ dl-performance-gpu-background/index. html. ↗
  109. Park, G., Park, B., Kwon, S. J., Kim, B., Lee, Y., and Lee, D. nuqmm: Quantized matmul for efficient inference of large-scale generative language models. arXiv preprint arXiv:2206.09557, 2022.
  110. Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J., Levskaya, A., Heek, J., Xiao, K., Agrawal, S., and Dean, J. Efficiently scaling transformer inference. arXiv preprint arXiv:2211.05102, 2022. find
  111. Qin, L., Song, Z., and Wang, Y. Fast submodular function maximization. CoRR, abs/2305.08367, 2023a. — [arXiv:2305.08367](https://arxiv.org/abs/2305.08367) find
  112. Qin, L., Song, Z., Zhang, L., and Zhuo, D. An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In AISTATS, 2023b. find
  113. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. 2019. find
  114. Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv e-prints, 2019.
  115. Razenshteyn, I., Song, Z., and Woodruff, D. P. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 250–263, 2016. find
  116. Sarlos, T. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS), pp. 143–152. find
  117. Seo, M., Lee, J., Kwiatkowski, T., Parikh, A. P., Farhadi, A., and Hajishirzi, H. Real-time open-domain question answering with dense-sparse phrase index. In ACL, pp. 4430–4441, 2019.
  118. Shrivastava, A., Song, Z., and Xu, Z. Sublinear least-squares value iteration via locality sensitive hashing. arXiv preprint arXiv:2105.08285, 2021. — [arXiv:2105.08285](https://arxiv.org/abs/2105.08285) find
  119. Smith, J. E. A study of branch prediction strategies. In 25 years of the international symposia on Computer architecture (selected papers), pp. 202–215, 1998. find
  120. Sohler, C. and Woodruff, D. P. Subspace embeddings for the l1-norm with applications. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 755–764, 2011. find
  121. Song, Z. and Ye, M. Efficient asynchronize stochastic gradient algorithm with structured data. CoRR, abs/2305.08001, 2023. — [arXiv:2305.08001](https://arxiv.org/abs/2305.08001) find
  122. Song, Z. and Yu, Z. Oblivious sketching-based central path method for linear programming. In International Conference on Machine Learning, pp. 9835–9847. PMLR, 2021. find
  123. Song, Z., Woodruff, D. P., and Zhong, P. Low rank approximation with entrywise l1-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 688–701, 2017. find
  124. Song, Z., Woodruff, D. P., and Zhong, P. Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2772–2789. SIAM, 2019. find
  125. Song, Z., Zhang, L., and Zhang, R. Training multi-layer over-parametrized neural network in subquadratic time. arXiv preprint arXiv:2112.07628, 2021. — [arXiv:2112.07628](https://arxiv.org/abs/2112.07628) find
  126. Song, Z., Wang, W., and Yin, C. Fast and efficient matching algorithm with deadline instances. CoRR, abs/2305.08353, 2023a. — [arXiv:2305.08353](https://arxiv.org/abs/2305.08353) find
  127. Song, Z., Yang, X., Yang, Y., and Zhang, L. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. In International Conference on Machine Learning (ICML), 2023b. find
  128. Tang, R., Lu, Y., Liu, L., Mou, L., Vechtomova, O., and Lin, J. Distilling task-specific knowledge from bert into simple neural networks. arXiv preprint arXiv:1903.12136, 2019. find
  129. Tillet, P., Kung, H.-T., and Cox, D. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pp. 10–19, 2019.
  130. Touvron, H., Cord, M., Douze, M., Massa, F., Sablayrolles, A., and Jégou, H. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pp. 10347–10357. PMLR, 2021.
  131. Veit, A., Wilber, M. J., and Belongie, S. Residual networks behave like ensembles of relatively shallow networks. Advances in neural information processing systems, 29, 2016. find
  132. Viterbi, A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, 13(2):260–269, 1967. find
  133. Wang, B. and Komatsuzaki, A. GPT-J-6B: A 6 billion parameter autoregressive language model. https://github.com/kingoflolz/mesh-transformer-jax, May 2021. ↗
  134. Wang, R. and Woodruff, D. P. Tight bounds for lp oblivious subspace embeddings. 2018. find
  135. Wang, X., Xiong, Y., Wei, Y., Wang, M., and Li, L. Lightseq: A high performance inference library for transformers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Papers, pp. 113–120, 2021. find
  136. Woodruff, D. P. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014. find
  137. Xiao, G., Lin, J., Seznec, M., Demouth, J., and Han, S. Smoothquant: Accurate and efficient post-training quantization for large language models. arXiv preprint arXiv:2211.10438, 2022. find
  138. Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=RdJVFCHjUMI. ↗
  139. Xue, H.-J., Dai, X., Zhang, J., Huang, S., and Chen, J. Deep matrix factorization models for recommender systems. In IJCAI, pp. 3203–3209, 2017. find
  140. Yao, Z., Aminabadi, R. Y., Zhang, M., Wu, X., Li, C., and He, Y. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. arXiv preprint arXiv:2206.01861, 2022.
  141. Yu, G.-I., Jeong, J. S., Kim, G.-W., Kim, S., and Chun, B.-G. Orca: A distributed serving system for {Transformer-Based} generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pp. 521–538, 2022. — Orca: A Distributed Serving System for Transformer-Based Generative Models
  142. Zandieh, A., Han, I., Daliri, M., and Karbasi, A. Kdeformer: Accelerating transformers via kernel density estimation. arXiv preprint arXiv:2302.02451, 2023. — [arXiv:2302.02451](https://arxiv.org/abs/2302.02451) find
  143. Zhang, L. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master’s thesis, Carnegie Mellon University, 2022. find
  144. Zhang, M., Wang, W., Liu, X., Gao, J., and He, Y. Navigating with graph representations for fast and scalable decoding of neural language models. Advances in neural information processing systems, 31, 2018. find
  145. Zhao, R., Hu, Y., Dotzel, J., De Sa, C., and Zhang, Z. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pp. 7543–7552. PMLR, 2019. find
  146. Contents: In Section A, we present an extended discussion on LLM inference and related works. In Section B, we provide more observation plots for slowly changing activation and further observation on the possibility of sparsifying LLMs via layer skipping. In Section C, we provide experiment details.… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2023-deja-vu-contextual-sparsity-efficient/