Table Lookups basics
Last updated
Was this helpful?
Last updated
Was this helpful?
This document introduces the concept of Table Lookups (TLUs) in Concrete, covers the basic TLU usage, performance considerations, and some basic techniques for optimizing TLUs in encrypted computations. For more advanced TLU usage, refer to the section
In TFHE, there exists mainly two operations: the linear operations, such as additions, subtractions, multiplications by integer, and the non-linear operations. Non-linear operations are achieved with Table Lookups (TLUs).
When using TLUs in Concrete, the most crucial factor for speed is the bit-width of the TLU. The smaller the bit width, the faster the corresponding FHE operation. Therefore, you should reduce the size of inputs to the lookup tables whenever possible. At the end of this document, we discuss methods for truncating or rounding entries to decrease the effective input size, further improving TLU performance.
A direct TLU performs operations in the form of y = T[i]
, where T
is a table and i
is an index. You can define the table using fhe.LookupTable
and apply it to scalars or tensors.
The LookupTable
behaves like Python's array indexing, where negative indices access elements from the end of the table.
A multi TLU is used to apply different elements of the input to different tables (e.g., square the first column, cube the second column):
In many cases, you won't need to define your own TLUs, as Concrete will set them for you.
Note that this kind of TLU is compatible with the TLU options, particularly with rounding and truncating which are explained below.
The first option is to set i'
as the truncation of i
. In this method, we just take the most significant bits of i
. This is done with fhe.truncate_bit_pattern
.
The second option is to set i
as the rounded value of i
. In this method, we take the most significant bits of i
and round up by 1 if the most significant ignored bit is 1. This is done with fhe.round_bit_pattern
.
However, this approach can be slightly more complex, as rounding might result in an index that exceeds the original table's bounds. To handle this, we expand the original table by one additional index:
For further optimizations, the fhe.round_bit_pattern
function has an exactness=fhe.Exactness.APPROXIMATE
option, which allows for faster computations at the cost of minor differences between cleartext and encrypted results:
Zama 5-Question Developer Survey
and extensions are convenient ways to perform more complex operations as transparent TLUs.
Reducing the bit size of TLU inputs is essential for execution efficiency, as mentioned in the previous section. One effective method is to replace the table lookup y = T[i]
by some y = T'[i']
, where i'
only has the most significant bits of i
and T'
is a much shorter table. This approach can significantly speed up the TLU while maintaining acceptable accuracy in many applications, such as machine learning.
In this section, we introduce two basic techniques: or . You can find more in-depth explanation and other advanced techniques of optimization in the .
We want to hear from you! Take 1 minute to share your thoughts and helping us enhance our documentation and libraries. 👉 to participate.