NNUE incremental evaluation

Deep dive

How it works

In: a position as ~30 active binary features per perspective, plus the move delta · Out: an evaluation in centipawn units · State: one int16 accumulator pair per ply on the search stack, refresh caches · Cost: (changed features) × L1 int16 adds per move, 2·L1·L2 int8 multiply-adds per eval.

1. Features per perspective: orient the board so "our" side is at the bottom (rank flip for Black), optionally mirror files so our king is on e-h; feature index = (king_bucket, piece_relative_to_us, square).
2. Accumulator: acc[persp] = b + Σ_{f active} W[f] (int16, width L1). Refresh costs one row per piece.
3. Make move: for each perspective whose king did not move, subtract rows of removed features (from-square piece, captured piece) and add rows of added ones (to-square piece, promotion piece, castling rook). Typical: 1 removed + 1 added (quiet), 2 + 1 (capture), 2 + 2 (castling).
4. Unmake: keep one accumulator per ply on the search stack; unmake just pops. Better: store only the per-ply list of changed pieces and compute lazily when an eval is actually requested (many nodes are cut before eval).
5. Evaluate: x = [crelu(acc[stm]), crelu(acc[!stm])] as u8, then int8 dense layers with int32 accumulation, shift by 6 (÷64) and ClippedReLU between them, final output scaled to centipawns.

 ~30 active of 22,528 features
        │ sparse rows (int16, incremental)
        ▼
 acc[white] (L1) ── acc[black] (L1)
        └─ order by side to move ─┘
        ▼ ClippedReLU → u8 [2·L1]
 int8 dense L2 → ClippedReLU → int8 dense → eval

Code

pub const L1: usize = 256;                     // accumulator width per perspective
pub const L2: usize = 16;
pub const FEATURES: usize = 32 * 11 * 64;      // HalfKAv2_hm-style: 32 king buckets × 11 pieces × 64

/// piece: 0..=5 = P N B R Q K, color: 0 = white, 1 = black. Squares a1 = 0 .. h8 = 63.
#[derive(Clone, Copy)]
pub struct Piece { pub kind: u8, pub color: u8, pub sq: u8 }

/// Feature index from `persp`'s point of view, given that side's king square.
pub fn feature(persp: u8, king_sq: u8, p: Piece) -> usize {
    let flip = |s: u8| if persp == 1 { s ^ 56 } else { s };          // own side at the bottom
    let ksq = flip(king_sq);
    let mirror = if ksq % 8 < 4 { 7 } else { 0 };                      // king onto files e..h
    let (ksq, sq) = (ksq ^ mirror, flip(p.sq) ^ mirror);
    let bucket = (ksq / 8) * 4 + (ksq % 8 - 4);                        // 0..32
    let piece = if p.kind == 5 { 10 }                                  // both kings share a plane
                else { p.kind + if p.color == persp { 0 } else { 5 } }; // 0..10
    (bucket as usize * 11 + piece as usize) * 64 + sq as usize
}

pub struct Net {
    pub ft_w: Vec<i16>,          // FEATURES × L1, row-major: one row per feature (scale 127)
    pub ft_b: [i16; L1],
    pub l1_w: Vec<i8>,           // L2 × 2·L1 (scale 64)
    pub l1_b: [i32; L2],         // scale 127·64
    pub out_w: [i8; L2],
    pub out_b: i32,
}

#[derive(Clone)]
#[repr(C, align(64))]
pub struct Accumulator { pub v: [[i16; L1]; 2] } // [white persp, black persp]

impl Net {
    fn row(&self, f: usize) -> &[i16] { &self.ft_w[f * L1..(f + 1) * L1] }

    /// Full recompute for one perspective: bias + sum of ~30 active rows.
    pub fn refresh(&self, acc: &mut Accumulator, persp: u8, king_sq: u8, pieces: &[Piece]) {
        let a = &mut acc.v[persp as usize];
        a.copy_from_slice(&self.ft_b);
        for &p in pieces {
            let r = self.row(feature(persp, king_sq, p));
            for i in 0..L1 { a[i] = a[i].wrapping_add(r[i]); } // auto-vectorises to 16-bit adds
        }
    }

    /// Incremental update after a non-king move of `persp`'s king: typically 1-2 removed
    /// and 1-2 added features (quiet move, capture, promotion). A king move of this
    /// perspective changes every feature: call `refresh` instead.
    pub fn update(&self, acc: &mut Accumulator, persp: u8, king_sq: u8,
                  removed: &[Piece], added: &[Piece]) {
        let a = &mut acc.v[persp as usize];
        for &p in removed {
            let r = self.row(feature(persp, king_sq, p));
            for i in 0..L1 { a[i] = a[i].wrapping_sub(r[i]); }
        }
        for &p in added {
            let r = self.row(feature(persp, king_sq, p));
            for i in 0..L1 { a[i] = a[i].wrapping_add(r[i]); }
        }
    }

    /// Side to move's accumulator first. Returns the eval in the output's integer scale.
    pub fn evaluate(&self, acc: &Accumulator, stm: u8) -> i32 {
        let mut x = [0u8; 2 * L1];
        for (half, persp) in [stm, stm ^ 1].into_iter().enumerate() {
            for i in 0..L1 { // ClippedReLU: int16 → [0, 127] as u8
                x[half * L1 + i] = acc.v[persp as usize][i].clamp(0, 127) as u8;
            }
        }
        let mut h = [0u8; L2];
        for o in 0..L2 {
            let w = &self.l1_w[o * 2 * L1..(o + 1) * 2 * L1];
            let s = self.l1_b[o] + dot_u8_i8(&x, w);
            h[o] = (s >> 6).clamp(0, 127) as u8; // undo weight scale 64, then ClippedReLU
        }
        self.out_b + dot_u8_i8(&h, &self.out_w)
    }
}

/// Σ a[i]·b[i] with u8 activations and i8 weights, accumulated in i32.
pub fn dot_u8_i8(a: &[u8], b: &[i8]) -> i32 {
    #[cfg(target_arch = "x86_64")]
    if a.len() % 32 == 0 && is_x86_feature_detected!("avx2") {
        return unsafe { dot_avx2(a, b) };
    }
    a.iter().zip(b).map(|(&x, &w)| x as i32 * w as i32).sum()
}

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2")]
unsafe fn dot_avx2(a: &[u8], b: &[i8]) -> i32 {
    use std::arch::x86_64::*;
    let mut acc = _mm256_setzero_si256();
    let ones = _mm256_set1_epi16(1);
    for k in (0..a.len()).step_by(32) {
        let va = _mm256_loadu_si256(a.as_ptr().add(k) as *const __m256i);
        let vb = _mm256_loadu_si256(b.as_ptr().add(k) as *const __m256i);
        // u8×i8 pairs summed to i16: 2·127·128 < 32767, so no saturation with x ≤ 127
        let p16 = _mm256_maddubs_epi16(va, vb);
        acc = _mm256_add_epi32(acc, _mm256_madd_epi16(p16, ones)); // i16 pairs → i32
    }
    let s = _mm_add_epi32(_mm256_castsi256_si128(acc), _mm256_extracti128_si256(acc, 1));
    let s = _mm_add_epi32(s, _mm_shuffle_epi32(s, 0b01_00_11_10));
    let s = _mm_add_epi32(s, _mm_shuffle_epi32(s, 0b10_11_00_01));
    _mm_cvtsi128_si32(s)
}

The test of this code checks that an incremental pawn move gives exactly the accumulator of a full refresh (integer arithmetic makes that bit-exact).

Complexity and constants

• Incremental update: (removed + added) × L1 int16 adds per perspective. With L1 = 256 that is 512 bytes per row: a quiet move touches 4 rows (2 per perspective), 2 KB of weights.
• Refresh: about 30 rows per perspective. HalfKP-256 first-layer weights are 40,960 × 256 × 2 bytes ≈ 21 MB, far beyond L2 cache, so refreshes and even updates are memory-latency bound; larger L1 widths make this worse.
• Dense part: 2·L1·L2 int8 multiply-adds; AVX2 does 32 per vpmaddubsw, AVX-512 VNNI vpdpbusd fuses multiply and int32 accumulate.
• Stockfish with NNUE searches order of 10⁶ nodes per second per core on current desktop CPUs.

Efficiency

• Cost: a quiet move touches 4 rows of 512 bytes (2 KB of weights); a refresh touches about 30 rows per perspective. HalfKP-256 first-layer weights are about 21 MB, so updates are memory-latency bound. Stockfish with NNUE searches order of 10⁶ nodes/s per core. Bound: memory latency for the sparse layer, SIMD throughput for the dense part.
• Levers:
  • incremental accumulator — 2-4 row updates instead of ~30 — own king did not move
  • lazy update at eval time — nodes cut before evaluation cost nothing — pruned-heavy searches
  • refresh cache per king bucket (Finny tables) — a refresh applies only the diff — frequent king moves
  • int16 accumulator, int8 weights, vpmaddubsw or VNNI — 32 multiply-adds per instruction — AVX2/AVX-512 CPUs
  • sparse first dense layer — multiplies only non-zero inputs — after ClippedReLU
• Naive → standard → state of the art:
  • full first-layer recompute per node · ~30 rows × L1 adds per perspective
  • incremental accumulator, SIMD int8 · 2-4 rows per move
  • plus lazy updates, refresh caches, sparse dense layer · as in current Stockfish

Implementation notes

• int16 accumulator, int32 dense accumulation: the sum of ~30 rows overflows int8; int16 holds it if trained weights stay bounded. Use wrapping adds (matches SIMD semantics and makes add/subtract exactly invertible).
• maddubs saturation: _mm256_maddubs_epi16 sums two u8×i8 products into a saturating i16; with activations ≤ 127 the worst case is 2·127·128 = 32,512, safe. Inputs up to 255 could saturate.
• Layout: feature rows contiguous (row-major W[feature][L1]), 64-byte aligned, so an update streams whole cache lines; accumulator aligned to 64 bytes.
• Accumulator refresh cache (Stockfish's "Finny tables"): per king bucket, remember the last accumulator and the board it was computed for; a refresh then applies only the difference, often a handful of rows instead of 30.
• Sparse first dense layer: after ClippedReLU many inputs are 0; find non-zero u8 groups and multiply only their weight columns (Stockfish does this for the L1→L2 layer).
• Layer stacks / output buckets: select one of several small dense heads by piece count; costs nothing extra at inference.
• Training side: clamp hidden weights to ±127/64 during training so quantization does not clip; train on search scores or WDL.

Pitfalls

• Updating the moving side's accumulator incrementally after its own king moved: every feature index changed; must refresh.
• Forgetting castling's rook move, en-passant's captured pawn (not on the to-square), or promotion's piece change in the delta lists.
• Different feature orientation at training and inference (rank flip vs 180° rotation, mirror convention): the net loads and plays, just badly.
• Mixing up perspective order ([stm, !stm]): evaluation is silently from the wrong side.
• Updating eagerly on every make: wasted work on nodes cut off before evaluation; update lazily.

Variants and alternatives

In production

Stockfish (since version 12, 2020), Komodo Dragon, Obsidian and most top CPU engines; originated in shogi engines (YaneuraOu-based programs) from Yu Nasu's 2018 design. The sparse-sum first layer without the incremental part also runs in fastText and DLRM.

Implementations

Sources

• Yu Nasu, Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi, 2018 (The 28th World Computer Shogi Championship appeal document).
• Stockfish developers, NNUE documentation, official-stockfish/nnue-pytorch, docs/nnue.md. docs
• Stockfish source, src/nnue/ (feature transformer, layers, accumulator).
• Armand Joulin, Edouard Grave, Piotr Bojanowski, Tomas Mikolov, Bag of Tricks for Efficient Text Classification, arXiv:1607.01759, 2016. paper
• Maxim Naumov et al., Deep Learning Recommendation Model for Personalization and Recommendation Systems, arXiv:1906.00091, 2019. paper