EQ Polynomial Optimizations

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

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

Overview

Core Components

Protocols

Optimizations

Theory

EQ Polynomial Optimizations

Equality Polynomial Definition

Multilinear Extension (MLE)

Common Operations

1. EQ Evaluation Table

2. Zero Selector

3. Cached Evaluations

Key Optimizations

1. Serial vs. Parallel Threshold

2. Serial Evaluation Algorithm

3. Parallel Evaluation Algorithm

4. Aligned Block Evaluation

5. Endianness Handling

Performance Impact

Memory Allocation Optimization

Parallelization Impact

Caching Benefits

Usage in Jolt

Sumcheck Round Polynomial

Split EQ Evaluation

SharedRaPolynomials

Best Practices

1. Choose Appropriate Evaluation Method

2. Reuse EQ Tables

3. Use Aligned Blocks for Sparse Access

References

Build docs developers (and LLMs) love

Overview

Core Components

Protocols

Optimizations

Theory

Documentation Index

​Equality Polynomial Definition

​Multilinear Extension (MLE)

​Common Operations

​1. EQ Evaluation Table

​2. Zero Selector

​3. Cached Evaluations

​Key Optimizations

​1. Serial vs. Parallel Threshold

​2. Serial Evaluation Algorithm

​3. Parallel Evaluation Algorithm

​4. Aligned Block Evaluation

​5. Endianness Handling

​Performance Impact

​Memory Allocation Optimization

​Parallelization Impact

​Caching Benefits

​Usage in Jolt

​Sumcheck Round Polynomial

​Split EQ Evaluation

​SharedRaPolynomials

​Best Practices

​1. Choose Appropriate Evaluation Method

​2. Reuse EQ Tables

​3. Use Aligned Blocks for Sparse Access

​Related Optimizations

​References

Build docs developers (and LLMs) love

Equality Polynomial Definition

Multilinear Extension (MLE)

Common Operations

1. EQ Evaluation Table

2. Zero Selector

3. Cached Evaluations

Key Optimizations

1. Serial vs. Parallel Threshold

2. Serial Evaluation Algorithm

3. Parallel Evaluation Algorithm

4. Aligned Block Evaluation

5. Endianness Handling

Performance Impact

Memory Allocation Optimization

Parallelization Impact

Caching Benefits

Usage in Jolt

Sumcheck Round Polynomial

Split EQ Evaluation

SharedRaPolynomials

Best Practices

1. Choose Appropriate Evaluation Method

2. Reuse EQ Tables

3. Use Aligned Blocks for Sparse Access

Related Optimizations

References