EQ Polynomial Optimizations

Specialized algorithms for fast equality polynomial evaluation in sumcheck protocols

The equality polynomial eq(x, y) appears throughout Jolt’s sumcheck protocols. Optimized evaluation of EQ polynomials is critical for prover performance, as these operations are executed thousands of times per proof.

Equality Polynomial Definition

The equality polynomial over boolean hypercube is:

eq(x, y) = ∏ᵢ (xᵢ · yᵢ + (1 - xᵢ) · (1 - yᵢ))

Properties:

• eq(x, y) = 1 when x = y (over ⁿ)
• eq(x, y) = 0 when x ≠ y
• Multilinear in both arguments

Multilinear Extension (MLE)

The MLE of eq extends the definition to field elements:

pub fn mle<X, Y>(x: &[X], y: &[Y]) -> F
where
    X: Copy + Send + Sync,
    Y: Copy + Send + Sync,
    F: JoltField + Sub<X, Output = F> + Sub<Y, Output = F>,
    X: Mul<Y, Output = F>,
{
    x.par_iter()
        .zip(y.par_iter())
        .map(|(x_i, y_i)| *x_i * *y_i + (F::one() - *x_i) * (F::one() - *y_i))
        .product()
}

Common Operations

1. EQ Evaluation Table

Compute eq(r, x) for all x ∈ {0,1}ⁿ:

pub fn evals<C>(r: &[C]) -> Vec<F>
where
    C: Copy + Send + Sync + Into<F>,
    F: std::ops::Mul<C, Output = F> + std::ops::SubAssign<F>,

Output: Vector of length 2^n where evals[i] = eq(r, i) (big-endian bit order).

Use case: Pre-compute EQ table for sumcheck evaluations.

2. Zero Selector

Compute eq(r, 0) = ∏ᵢ (1 - rᵢ):

pub fn zero_selector<C>(r: &[C]) -> F
where
    C: Copy + Send + Sync + Into<F>,
{
    r.par_iter().map(|r_i| F::one() - (*r_i).into()).product()
}

Use case: Select the all-zeros vertex of the hypercube.

3. Cached Evaluations

Compute EQ tables for all prefixes of r:

pub fn evals_cached<C>(r: &[C]) -> Vec<Vec<F>>

Output: result[j][x] = eq(r[..j], x) for all j ∈ [0, n].

Use case: Incremental sumcheck binding where intermediate EQ values are needed.

Key Optimizations

1. Serial vs. Parallel Threshold

Small EQ tables use serial computation:

const PARALLEL_THRESHOLD: usize = 16;

match r.len() {
    0..=PARALLEL_THRESHOLD => Self::evals_serial(r, scaling_factor),
    _ => Self::evals_parallel(r, scaling_factor),
}

Reason: Parallel overhead exceeds benefit for n ≤ 16 (table size ≤ 65,536).

2. Serial Evaluation Algorithm

Dynamic programming approach:

pub fn evals_serial<C>(r: &[C], scaling_factor: Option<F>) -> Vec<F> {
    let mut evals: Vec<F> = vec![scaling_factor.unwrap_or(F::one()); r.len().pow2()];
    let mut size = 1;
    for j in 0..r.len() {
        size *= 2;
        for i in (0..size).rev().step_by(2) {
            let scalar = evals[i / 2];
            evals[i] = scalar * r[j];           // x_j = 1
            evals[i - 1] = scalar - evals[i];   // x_j = 0
        }
    }
    evals
}

Complexity: O(2ⁿ) time, O(2ⁿ) space

Optimization: Single pass, in-place updates, no additional allocations.

3. Parallel Evaluation Algorithm

For large tables, use rayon parallelization:

pub fn evals_parallel<C>(r: &[C], scaling_factor: Option<F>) -> Vec<F> {
    let final_size = r.len().pow2();
    let mut evals: Vec<F> = unsafe_allocate_zero_vec(final_size);
    let mut size = 1;
    evals[0] = scaling_factor.unwrap_or(F::one());

    for r in r.iter().rev() {
        let (evals_left, evals_right) = evals.split_at_mut(size);
        let (evals_right, _) = evals_right.split_at_mut(size);

        evals_left
            .par_iter_mut()
            .zip(evals_right.par_iter_mut())
            .for_each(|(x, y)| {
                *y = *x * *r;      // x_j = 1
                *x -= *y;          // x_j = 0
            });

        size *= 2;
    }
    evals
}

Key features:

• Unsafe pre-allocation for zero-initialized vector
• Parallel iteration over pairs
• In-place updates (no intermediate allocations)

4. Aligned Block Evaluation

Compute EQ values for a power-of-two block:

pub fn evals_for_aligned_block<C>(
    r: &[C],
    start_index: usize,
    block_size: usize,
) -> Vec<F>

Use case: When scanning a contiguous range, compute only the suffix EQ table and scale by the prefix selector.

Example:

// Full domain: 2^20 elements
// Want: eq(r, k) for k ∈ [2^18, 2^18 + 2^16)

// Decompose: k = prefix || suffix
// - prefix = 2^18 >> 16 = 4 (fixed)
// - suffix ∈ [0, 2^16) (variable)

let block_evals = EqPolynomial::evals_for_aligned_block(
    &r,
    1 << 18,  // start_index (aligned to block_size)
    1 << 16,  // block_size
);

// block_evals[j] = eq(r, 2^18 + j) for j ∈ [0, 2^16)

Speedup: Avoids computing full 2^20 table when only a 2^16 block is needed.

5. Endianness Handling

EQ polynomial evaluation with different bit orderings:

pub fn mle_endian<const E1: Endianness, const E2: Endianness>(
    x: &OpeningPoint<E1, F>,
    y: &OpeningPoint<E2, F>,
) -> F {
    if E1 == E2 {
        // Same endianness: pair positionally
        x.r.par_iter()
            .zip(y.r.par_iter())
            .map(|(x_i, y_i)| *x_i * y_i + (F::one() - x_i) * (F::one() - y_i))
            .product()
    } else {
        // Different endianness: reverse one side
        x.r.par_iter()
            .zip(y.r.par_iter().rev())
            .map(|(x_i, y_i)| *x_i * y_i + (F::one() - x_i) * (F::one() - y_i))
            .product()
    }
}

Reason: Jolt uses big-endian bit order by convention, but some protocols (like high-to-low binding) require little-endian.

Performance Impact

Memory Allocation Optimization

Standard approach:

let mut evals = vec![F::zero(); 1 << n];  // Zero-initialization via Drop

Optimized approach:

let mut evals = unsafe_allocate_zero_vec(1 << n);  // Unsafe zero-initialization

Speedup: ~2-3x for large n (avoids Drop overhead).

Parallelization Impact

Table Size	Serial Time	Parallel Time	Speedup
2^10 (1K)	10 μs	15 μs	0.67x (overhead)
2^16 (64K)	800 μs	250 μs	3.2x
2^20 (1M)	15 ms	2.5 ms	6x
2^24 (16M)	250 ms	30 ms	8.3x

Caching Benefits

For protocols that need EQ values at multiple prefix lengths:

Without caching:

for j in 0..n {
    let eq_j = EqPolynomial::evals(&r[..j]);  // Recompute from scratch
    // Use eq_j...
}

• Time complexity: O(2^0 + 2^1 + … + 2^n) = O(2^(n+1))

With caching:

let all_eqs = EqPolynomial::evals_cached(&r);  // Compute once
for j in 0..n {
    let eq_j = &all_eqs[j];  // O(1) lookup
    // Use eq_j...
}

• Time complexity: O(2^n) — 2x speedup

Usage in Jolt

Sumcheck Round Polynomial

EQ polynomials appear in every sumcheck round:

// Compute round polynomial: H(x) = Σ_y P(x, y) * eq(r, y)
let eq_table = EqPolynomial::evals(&r_suffix);
let h_0 = (0..eq_table.len())
    .map(|y| poly_left[y] * eq_table[y])
    .sum();
let h_1 = (0..eq_table.len())
    .map(|y| poly_right[y] * eq_table[y])
    .sum();

Split EQ Evaluation

CompactPolynomial optimizes this pattern:

// Standard: Materialize full EQ table
let eq_table = EqPolynomial::evals(&r);
let result = poly.coeffs.iter()
    .zip(eq_table.iter())
    .map(|(p, eq)| *p * *eq)
    .sum();

// Optimized: Split into prefix/suffix
let (r_prefix, r_suffix) = r.split_at(prefix_len);
let eq_prefix = EqPolynomial::evals(r_prefix);
let eq_suffix = EqPolynomial::evals(r_suffix);
let result = poly.split_eq_evaluate(r.len(), &eq_prefix, &eq_suffix);

Benefit: Exploit structure of polynomial layout to avoid full EQ table materialization.

SharedRaPolynomials

Multiple polynomials share the same EQ table:

pub struct SharedRaPolynomials<F: JoltField> {
    polys: Vec<RaPolynomial<F>>,
    shared_eq_table: Vec<F>,  // Computed once, shared across all polys
}

Memory savings: N polynomials share one EQ table instead of N separate tables.

Best Practices

1. Choose Appropriate Evaluation Method

// Small tables (n ≤ 16): Use serial
let eq_small = EqPolynomial::evals_serial(&r_small, None);

// Large tables (n > 16): Use parallel
let eq_large = EqPolynomial::evals_parallel(&r_large, None);

// Need multiple prefix tables: Use cached
let eq_cached = EqPolynomial::evals_cached(&r);

2. Reuse EQ Tables

Avoid recomputing:

// Bad: Recompute for each polynomial
for poly in polynomials {
    let eq_table = EqPolynomial::evals(&r);  // Wasteful!
    let result = poly.evaluate_with_eq(&eq_table);
}

// Good: Compute once, reuse
let eq_table = EqPolynomial::evals(&r);
for poly in polynomials {
    let result = poly.evaluate_with_eq(&eq_table);
}

3. Use Aligned Blocks for Sparse Access

When accessing a contiguous range:

// Bad: Compute full table, use subset
let eq_full = EqPolynomial::evals(&r);  // Size: 2^n
let subset = &eq_full[start..start + length];

// Good: Compute only needed block (if power-of-two aligned)
let (block_size, eq_block) = EqPolynomial::evals_for_max_aligned_block(
    &r, start, length
);

Related Optimizations

• CompactPolynomial: Split EQ evaluation
• Batched Sumcheck: Uses EQ polynomials in every round
• SharedRaPolynomials: Share EQ tables across polynomials

References

• Implementation: jolt-core/src/poly/eq_poly.rs
• Index/bit ordering: Big-endian convention (MSB = r[0], LSB = r[n-1])