FA-73066 / Probabilistic sketches / Open access

Count sketch frequency estimation: query ignores the row sign · case 01

Rows where the key was stored with a negative sign vote with the wrong polarity.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The query reads raw cells without multiplying by the key's sign.

VERIFIED REPAIR

Multiply each cell by the key's row sign before taking the median.

Unsuccessful approach: Taking absolute values discards genuine negative frequencies and collision cancellation.

Case contract

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

Why this case matters

Count sketches estimate signed frequencies in turnstile streams (inserts and deletes); their unbiasedness depends on independent signs and a median across rows.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    w = x['w']
    d = x['d']
    P = 2147483647
    A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
    B = [12345, 1013904223, 7, 99991, 31337, 424242]
    C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
    D = [3, 5, 11, 17, 23, 29]
    t = [[0] * w for _ in range(d)]
    def bucket(r, key):
        return (A[r] * key + B[r]) % P % w
    def sign(r, key):
        return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
    for key, cnt in x['stream']:
        for r in range(d):
            t[r][bucket(r, key)] += sign(r, key) * cnt
    out = []
    for key in x['queries']:
        vals = sorted(t[r][bucket(r, key)] for r in range(d))
        if d % 2:
            out.append(vals[d // 2])
        else:
            out.append((vals[d // 2 - 1] + vals[d // 2]) / 2)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [23, 53, 27, 24, 14, 100],
    'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
    'w': 4},
   [-1, 9, -3, -9, 9, -6]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [26, 55, 10, 15, 19, 100],
    'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
    'w': 5},
   [11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [13, 55, 20, 4, 57, 100],
    'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
    'w': 3},
   [12, 15, 2, 6, -3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [52, 50, 14, 47, 13, 100],
    'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
    'w': 6},
   [4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [7, 36, 53, 37, 29, 100],
    'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
    'w': 4},
   [15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [2, 31, 48, 20, 24, 100],
    'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
    'w': 2},
   [12, -2, -12, 2, 12, 2]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
   [0, -3]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [47, 24, 9, 42, 45, 101],
    'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
    'w': 4},
   [15, 4, 3, 2, -3, 0]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [47, 44, 11, 17, 43, 101],
    'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
    'w': 5},
   [11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [50, 54, 17, 44, 8, 101],
    'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
    'w': 3},
   [13, 6, -3, 1, 0, 5]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [53, 40, 34, 19, 50, 101],
    'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
    'w': 6},
   [0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [37, 49, 24, 52, 33, 101],
    'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
    'w': 4},
   [10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [33, 40, 3, 43, 8, 101],
    'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
    'w': 2},
   [7, 11, 11, 7, -7, -11]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
   [0, -4]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [26, 43, 31, 44, 30, 102],
    'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
    'w': 4},
   [12, 1, -2, 7, -1, -12]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [52, 33, 27, 41, 23, 102],
    'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
    'w': 5},
   [19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [30, 59, 54, 34, 46, 102],
    'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
    'w': 3},
   [12, 6, 12, 1, 3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [31, 58, 1, 13, 44, 102],
    'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
    'w': 6},
   [17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 39, 12, 48, 7, 102],
    'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
    'w': 4},
   [10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [52, 26, 2, 12, 54, 102],
    'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
    'w': 2},
   [6, -5, 11, 6, 0, -6]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
   [0, -5]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [17, 20, 22, 7, 59, 103],
    'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
    'w': 4},
   [4, 0, -2, 3, -4, 3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [38, 14, 1, 21, 19, 103],
    'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
    'w': 5},
   [5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [47, 31, 6, 26, 18, 103],
    'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
    'w': 3},
   [10, 0, 8, 8, 2, -9]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [2, 8, 16, 10, 59, 103],
    'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
    'w': 6},
   [9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 41, 28, 10, 22, 103],
    'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
    'w': 4},
   [12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [27, 30, 53, 34, 37, 103],
    'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
    'w': 2},
   [12, 14, 10, 14, 12, 12]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
   [0, -6]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [49, 2, 6, 18, 34, 104],
    'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
    'w': 4},
   [6, 0, 4, 7, 7, -3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [56, 42, 28, 49, 48, 104],
    'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
    'w': 5},
   [10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [41, 12, 50, 46, 3, 104],
    'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
    'w': 3},
   [12, 4, 4, 4, 4, -1]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [15, 5, 4, 19, 30, 104],
    'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
    'w': 6},
   [12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [5, 41, 39, 54, 1, 104],
    'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
    'w': 4},
   [12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [57, 35, 2, 54, 27, 104],
    'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
    'w': 2},
   [22, 22, 3, 23, 22, 4]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
   [0, -7]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
stream 0 w=4 d=3	`[9, -6, -3, -6, 9, 6]`	`[-1, 9, -3, -9, 9, -6]`	Failed
stream 1 w=5 d=4	`[11.5, 5.5, -3.0, -3.0, -4.5, -2.5]`	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	Failed
stream 2 w=3 d=5	`[-12, 6, 1, 1, -6, -5]`	`[12, 15, 2, 6, -3, -6]`	Failed
stream 3 w=6 d=2	`[-4.5, -7.5, -7.5, -2.0, -8.0, -5.0]`	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	Failed
stream 4 w=4 d=6	`[-13.5, -0.5, 2.5, 2.5, -0.5, 2.5]`	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	Failed
stream 5 w=2 d=3	`[-12, -2, -2, -2, -2, -12]`	`[12, -2, -12, 2, 12, 2]`	Failed
deletions cancel	`[0, 3]`	`[0, -3]`	Failed

SHA-256 / 47eceee052473596fda2ea9962e9c8872120991e66684636f005a76129c01d43

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    w = x['w']
    d = x['d']
    P = 2147483647
    A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
    B = [12345, 1013904223, 7, 99991, 31337, 424242]
    C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
    D = [3, 5, 11, 17, 23, 29]
    t = [[0] * w for _ in range(d)]
    def bucket(r, key):
        return (A[r] * key + B[r]) % P % w
    def sign(r, key):
        return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
    for key, cnt in x['stream']:
        for r in range(d):
            t[r][bucket(r, key)] += sign(r, key) * cnt
    out = []
    for key in x['queries']:
        vals = sorted(abs(t[r][bucket(r, key)]) for r in range(d))
        if d % 2:
            out.append(vals[d // 2])
        else:
            out.append((vals[d // 2 - 1] + vals[d // 2]) / 2)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [23, 53, 27, 24, 14, 100],
    'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
    'w': 4},
   [-1, 9, -3, -9, 9, -6]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [26, 55, 10, 15, 19, 100],
    'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
    'w': 5},
   [11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [13, 55, 20, 4, 57, 100],
    'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
    'w': 3},
   [12, 15, 2, 6, -3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [52, 50, 14, 47, 13, 100],
    'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
    'w': 6},
   [4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [7, 36, 53, 37, 29, 100],
    'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
    'w': 4},
   [15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [2, 31, 48, 20, 24, 100],
    'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
    'w': 2},
   [12, -2, -12, 2, 12, 2]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
   [0, -3]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [47, 24, 9, 42, 45, 101],
    'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
    'w': 4},
   [15, 4, 3, 2, -3, 0]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [47, 44, 11, 17, 43, 101],
    'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
    'w': 5},
   [11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [50, 54, 17, 44, 8, 101],
    'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
    'w': 3},
   [13, 6, -3, 1, 0, 5]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [53, 40, 34, 19, 50, 101],
    'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
    'w': 6},
   [0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [37, 49, 24, 52, 33, 101],
    'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
    'w': 4},
   [10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [33, 40, 3, 43, 8, 101],
    'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
    'w': 2},
   [7, 11, 11, 7, -7, -11]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
   [0, -4]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [26, 43, 31, 44, 30, 102],
    'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
    'w': 4},
   [12, 1, -2, 7, -1, -12]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [52, 33, 27, 41, 23, 102],
    'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
    'w': 5},
   [19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [30, 59, 54, 34, 46, 102],
    'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
    'w': 3},
   [12, 6, 12, 1, 3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [31, 58, 1, 13, 44, 102],
    'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
    'w': 6},
   [17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 39, 12, 48, 7, 102],
    'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
    'w': 4},
   [10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [52, 26, 2, 12, 54, 102],
    'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
    'w': 2},
   [6, -5, 11, 6, 0, -6]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
   [0, -5]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [17, 20, 22, 7, 59, 103],
    'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
    'w': 4},
   [4, 0, -2, 3, -4, 3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [38, 14, 1, 21, 19, 103],
    'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
    'w': 5},
   [5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [47, 31, 6, 26, 18, 103],
    'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
    'w': 3},
   [10, 0, 8, 8, 2, -9]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [2, 8, 16, 10, 59, 103],
    'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
    'w': 6},
   [9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 41, 28, 10, 22, 103],
    'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
    'w': 4},
   [12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [27, 30, 53, 34, 37, 103],
    'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
    'w': 2},
   [12, 14, 10, 14, 12, 12]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
   [0, -6]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [49, 2, 6, 18, 34, 104],
    'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
    'w': 4},
   [6, 0, 4, 7, 7, -3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [56, 42, 28, 49, 48, 104],
    'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
    'w': 5},
   [10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [41, 12, 50, 46, 3, 104],
    'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
    'w': 3},
   [12, 4, 4, 4, 4, -1]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [15, 5, 4, 19, 30, 104],
    'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
    'w': 6},
   [12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [5, 41, 39, 54, 1, 104],
    'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
    'w': 4},
   [12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [57, 35, 2, 54, 27, 104],
    'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
    'w': 2},
   [22, 22, 3, 23, 22, 4]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
   [0, -7]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
stream 0 w=4 d=3	`[9, 9, 9, 9, 9, 6]`	`[-1, 9, -3, -9, 9, -6]`	Failed
stream 1 w=5 d=4	`[11.5, 7.5, 5.5, 5.0, 8.0, 2.5]`	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	Failed
stream 2 w=3 d=5	`[12, 15, 3, 6, 12, 6]`	`[12, 15, 2, 6, -3, -6]`	Failed
stream 3 w=6 d=2	`[4.5, 7.5, 7.5, 9.0, 8.0, 6.0]`	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	Failed
stream 4 w=4 d=6	`[15.0, 3.5, 5.0, 4.5, 1.0, 4.0]`	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	Failed
stream 5 w=2 d=3	`[12, 6, 12, 6, 12, 12]`	`[12, -2, -12, 2, 12, 2]`	Failed
deletions cancel	`[0, 3]`	`[0, -3]`	Failed

SHA-256 / 51238eb87fbebe15ca8b4278db65f8957a4416e681f34a6dcc683720be8aa777

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    w = x['w']
    d = x['d']
    P = 2147483647
    A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
    B = [12345, 1013904223, 7, 99991, 31337, 424242]
    C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
    D = [3, 5, 11, 17, 23, 29]
    t = [[0] * w for _ in range(d)]
    def bucket(r, key):
        return (A[r] * key + B[r]) % P % w
    def sign(r, key):
        return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
    for key, cnt in x['stream']:
        for r in range(d):
            t[r][bucket(r, key)] += sign(r, key) * cnt
    out = []
    for key in x['queries']:
        vals = sorted(sign(r, key) * t[r][bucket(r, key)] for r in range(d))
        if d % 2:
            out.append(vals[d // 2])
        else:
            out.append((vals[d // 2 - 1] + vals[d // 2]) / 2)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [23, 53, 27, 24, 14, 100],
    'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
    'w': 4},
   [-1, 9, -3, -9, 9, -6]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [26, 55, 10, 15, 19, 100],
    'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
    'w': 5},
   [11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [13, 55, 20, 4, 57, 100],
    'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
    'w': 3},
   [12, 15, 2, 6, -3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [52, 50, 14, 47, 13, 100],
    'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
    'w': 6},
   [4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [7, 36, 53, 37, 29, 100],
    'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
    'w': 4},
   [15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [2, 31, 48, 20, 24, 100],
    'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
    'w': 2},
   [12, -2, -12, 2, 12, 2]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
   [0, -3]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [47, 24, 9, 42, 45, 101],
    'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
    'w': 4},
   [15, 4, 3, 2, -3, 0]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [47, 44, 11, 17, 43, 101],
    'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
    'w': 5},
   [11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [50, 54, 17, 44, 8, 101],
    'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
    'w': 3},
   [13, 6, -3, 1, 0, 5]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [53, 40, 34, 19, 50, 101],
    'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
    'w': 6},
   [0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [37, 49, 24, 52, 33, 101],
    'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
    'w': 4},
   [10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [33, 40, 3, 43, 8, 101],
    'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
    'w': 2},
   [7, 11, 11, 7, -7, -11]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
   [0, -4]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [26, 43, 31, 44, 30, 102],
    'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
    'w': 4},
   [12, 1, -2, 7, -1, -12]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [52, 33, 27, 41, 23, 102],
    'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
    'w': 5},
   [19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [30, 59, 54, 34, 46, 102],
    'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
    'w': 3},
   [12, 6, 12, 1, 3, -6]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [31, 58, 1, 13, 44, 102],
    'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
    'w': 6},
   [17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 39, 12, 48, 7, 102],
    'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
    'w': 4},
   [10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [52, 26, 2, 12, 54, 102],
    'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
    'w': 2},
   [6, -5, 11, 6, 0, -6]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
   [0, -5]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [17, 20, 22, 7, 59, 103],
    'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
    'w': 4},
   [4, 0, -2, 3, -4, 3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [38, 14, 1, 21, 19, 103],
    'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
    'w': 5},
   [5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [47, 31, 6, 26, 18, 103],
    'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
    'w': 3},
   [10, 0, 8, 8, 2, -9]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [2, 8, 16, 10, 59, 103],
    'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
    'w': 6},
   [9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [42, 41, 28, 10, 22, 103],
    'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
    'w': 4},
   [12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [27, 30, 53, 34, 37, 103],
    'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
    'w': 2},
   [12, 14, 10, 14, 12, 12]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
   [0, -6]]],
 [['stream 0 w=4 d=3',
   {'d': 3,
    'queries': [49, 2, 6, 18, 34, 104],
    'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
    'w': 4},
   [6, 0, 4, 7, 7, -3]],
  ['stream 1 w=5 d=4',
   {'d': 4,
    'queries': [56, 42, 28, 49, 48, 104],
    'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
    'w': 5},
   [10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
  ['stream 2 w=3 d=5',
   {'d': 5,
    'queries': [41, 12, 50, 46, 3, 104],
    'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
    'w': 3},
   [12, 4, 4, 4, 4, -1]],
  ['stream 3 w=6 d=2',
   {'d': 2,
    'queries': [15, 5, 4, 19, 30, 104],
    'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
    'w': 6},
   [12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
  ['stream 4 w=4 d=6',
   {'d': 6,
    'queries': [5, 41, 39, 54, 1, 104],
    'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
    'w': 4},
   [12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
  ['stream 5 w=2 d=3',
   {'d': 3,
    'queries': [57, 35, 2, 54, 27, 104],
    'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
    'w': 2},
   [22, 22, 3, 23, 22, 4]],
  ['deletions cancel',
   {'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
   [0, -7]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
stream 0 w=4 d=3	`[-1, 9, -3, -9, 9, -6]`	`[-1, 9, -3, -9, 9, -6]`	Passed
stream 1 w=5 d=4	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	Passed
stream 2 w=3 d=5	`[12, 15, 2, 6, -3, -6]`	`[12, 15, 2, 6, -3, -6]`	Passed
stream 3 w=6 d=2	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	Passed
stream 4 w=4 d=6	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	Passed
stream 5 w=2 d=3	`[12, -2, -12, 2, 12, 2]`	`[12, -2, -12, 2, 12, 2]`	Passed
deletions cancel	`[0, -3]`	`[0, -3]`	Passed

SHA-256 / 19376c6d27909cad00696319805271bba3cf7d684339aaa6748adc80ba32308d

Verification & scope

A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:44.083714+00:00.

Case digest / abdb96d5c7c3482649d28c4ad788c3617fff32821c93ac26d0faa3c1056628d9