LinearCosine: Benchmarking L-Mul Algorithm

GitHub Implementation of Below Read the Original Paper

TLDR: Technical Explanation

The L-Mul algorithm proposes an efficient approximation of floating-point multiplication using primarily integer addition operations. Here's a quick breakdown:

Standard Floating-Point Multiplication

The traditional method multiplies two floating-point numbers as follows:

\[\text{Mul}(x,y) = (1 + x_m) \cdot 2^{x_e} \cdot (1 + y_m) \cdot 2^{y_e} = (1 + x_m + y_m + x_m \cdot y_m) \cdot 2^{x_e + y_e}\]

Where \(x_m\) and \(y_m\) are mantissas, and \(x_e\) and \(y_e\) are exponents.

L-Mul Algorithm

The L-Mul method approximates this multiplication:

\[\mathcal{L}\text{-Mul}(x,y) = (1 + x_m + y_m + 2^{-l(m)}) \cdot 2^{x_e + y_e}\]

Where \(l(m)\) is defined as:

\[l(m) = \begin{cases} m & \text{if } m \leq 3, \\ 3 & \text{if } m = 4, \\ 4 & \text{if } m > 4. \end{cases}\]

Here, \(m\) represents the number of mantissa bits.

Key Differences

• L-Mul replaces the \(x_m \cdot y_m\) term with a constant \(2^{-l(m)}\).
• This substitution allows the operation to be performed primarily with integer addition.
• The \(l(m)\) function adjusts the precision based on the number of mantissa bits used.

This approximation significantly reduces computational complexity and energy consumption while maintaining competitive accuracy, especially for lower-precision operations common in many AI tasks.

About This Benchmark

This benchmark explores the Linear-complexity Multiplication (L-Mul) algorithm proposed by Luo and Sun in their 2024 paper. Our goal is to provide a practical implementation of their concepts, focusing on cosine similarity calculations. This project is not affiliated with or endorsed by the original authors.

Experiment Overview

We've implemented the L-Mul algorithm as described by Luo and Sun, comparing its performance against standard multiplication in cosine similarity computations. Our benchmarks cover:

• 1D to 1D vector cosine similarity
• 1D to 2D vector cosine similarity
• 2D to 2D matrix cosine similarity

Results

1D to 1D Cosine Similarity

Summary

• Average Time Reduction: 24.55%
• Average L-Mul MSE: 1.9184e-05

1D to 2D Cosine Similarity

2D to 2D Cosine Similarity

Key Findings

• The L-Mul approach consistently achieves time reductions across all scenarios.
• For 1D to 1D cosine similarity, the average time reduction is 24.55%.
• In 1D to 2D scenarios, time reductions range from about 16.8% to 18.6%.
• For 2D to 2D calculations, time reductions are between 21.88% and 23.12%.
• The L-Mul method maintains acceptable levels of accuracy (measured by MSE) for most practical applications.

Limitations

• This is a simplified implementation and may not capture all nuances of the original proposal by Luo and Sun.
• Our benchmarks focus on raw computation time, which may not directly translate to energy efficiency.
• Results may vary significantly in real-world applications or different hardware environments.
• The time efficiency gains observed here don't necessarily equate to compute or energy efficiency in real-world scenarios.

Conclusion

Our benchmark results suggest that the L-Mul algorithm, as proposed by Luo and Sun, shows promise in reducing computation time for cosine similarity calculations across various dimensions. However, it's important to note that these results are based on a simplified C++ implementation and may not fully reflect the algorithm's performance in more complex, real-world scenarios or on specialized hardware.

Acknowledgments

All credit for the L-Mul algorithm and its theoretical foundations goes to Hongyin Luo and Wei Sun, as presented in their 2024 paper. This benchmark is an independent exploration of their concepts and should not be considered an official implementation or extension of their work.

Citation

@misc{luo2024additionneedenergyefficientlanguage,
    title={Addition is All You Need for Energy-efficient Language Models}, 
    author={Hongyin Luo and Wei Sun},
    year={2024},
    eprint={2410.00907},
    archivePrefix={arXiv},
    primaryClass={cs.CL},
    url={https://arxiv.org/abs/2410.00907}, 
}
        

Disclaimer

This project is for educational purposes only. It is not intended for production use and does not claim to accurately represent the full potential or limitations of the L-Mul algorithm as proposed by Luo and Sun. Users are encouraged to refer to the original paper for authoritative information.