# Table Lookups basics

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 Table Lookup advanced 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).

## Performance

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.

## Direct TLU

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.

### Scalar lookup

### Tensor lookup

The `LookupTable`

behaves like Python's array indexing, where negative indices access elements from the end of the table.

## Multi TLU

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):

### Transparent TLU

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.

fhe.univariate and fhe.multivariate extensions are convenient ways to perform more complex operations as transparent TLUs.

## Optimizing input size

Reducing the bit size of TLU inputs is essential for execution efficiency, as mentioned in the previous performance 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: truncating or rounding. You can find more in-depth explanation and other advanced techniques of optimization in the TLU advanced documentation.

### Truncating

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`

.

### Rounding

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:

### Approximate rounding

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**

We want to hear from you! Take 1 minute to share your thoughts and helping us enhance our documentation and libraries. **👉** **Click here** to participate.

Last updated