FA-14266 / Numerical aggregation / Open access
Three row count sketch: Query estimation chooses the most contaminated row. · case 01
The reduction disagrees with its explicit aggregation oracle.
ROOT CAUSE
Query estimation chooses the most contaminated row.
VERIFIED REPAIR
Preserve the three row count sketch contract at the identified reduction decision.
Unsuccessful approach: Median is a different estimator and need not remove a collision avoided by one row.
Case contract
A stipulated nonnegative weighted count-min table has exactly three independent rows of positive width, with bucket functions k%w,(3*k+1)%w,(k//w)%w for nonnegative integer keys. Add all block contributions, then estimate each query by the minimum of its three cells. Return [table,estimates]; no probabilistic error guarantee is claimed.
Why this case matters
Exact bounded examples isolate a reduction defect without floating-point or external-service effects.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from collections import Counter, defaultdict
import math
import itertools
N = 1
observations = []
def solve(blocks, width, queries):
table=[[0]*width for _ in range(3)]
for block in blocks:
for key,weight in block:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
for row,col in enumerate(buckets):
table[row][col]+=weight
estimates=[]
for key in queries:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
estimates.append(max(table[row][col] for row,col in enumerate(buckets)))
return [table,estimates]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('regression 1', solve(*([[(0, 2), (1, 3)], [(4, 1)]], 4, [0, 1, 4, 8])), [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]])
check('regression 2', solve(*([], 3, [0, 1])), [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]])
check('regression 3', solve(*([[(2, 5)], [], [(2, 2)]], 3, [2, 5])), [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]])
check('regression 4', solve(*([[(0, 1), (0, 1)]], 1, [0, 3])), [[[2], [2], [2]], [2, 2]])
check('regression 5', solve(*([[(7, 0), (2, 4), (5, 1)]], 4, [2, 5, 7])), [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]])
check('regression 6', solve(*([[(1, 2)], [(8, 5), (3, 4)]], 5, [1, 8, 3, 13])), [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]])
check("variable sketch contribution",solve([[(0,N)]],2,[0]),[[[N,0],[0,N],[N,0]],[N]])
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 |
|---|---|---|---|
| regression 1 | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [5, 5, 3, 3]] | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]] | Failed |
| regression 2 | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | Passed |
| regression 3 | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 7]] | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]] | Failed |
| regression 4 | [[[2], [2], [2]], [2, 2]] | [[[2], [2], [2]], [2, 2]] | Passed |
| regression 5 | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 1]] | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]] | Failed |
| regression 6 | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [6, 9, 9, 9]] | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]] | Failed |
| variable sketch contribution | [[[1, 0], [0, 1], [1, 0]], [1]] | [[[1, 0], [0, 1], [1, 0]], [1]] | Passed |
SHA-256 / d4116d090d73726eeaee0ef0318fd31ed4f8b99f5733ca8c6ef60c7a95f241ee
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from collections import Counter, defaultdict
import math
import itertools
N = 1
observations = []
def solve(blocks, width, queries):
table=[[0]*width for _ in range(3)]
for block in blocks:
for key,weight in block:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
for row,col in enumerate(buckets):
table[row][col]+=weight
estimates=[]
for key in queries:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
estimates.append(sorted(table[row][col] for row,col in enumerate(buckets))[1])
return [table,estimates]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('regression 1', solve(*([[(0, 2), (1, 3)], [(4, 1)]], 4, [0, 1, 4, 8])), [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]])
check('regression 2', solve(*([], 3, [0, 1])), [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]])
check('regression 3', solve(*([[(2, 5)], [], [(2, 2)]], 3, [2, 5])), [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]])
check('regression 4', solve(*([[(0, 1), (0, 1)]], 1, [0, 3])), [[[2], [2], [2]], [2, 2]])
check('regression 5', solve(*([[(7, 0), (2, 4), (5, 1)]], 4, [2, 5, 7])), [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]])
check('regression 6', solve(*([[(1, 2)], [(8, 5), (3, 4)]], 5, [1, 8, 3, 13])), [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]])
check("variable sketch contribution",solve([[(0,N)]],2,[0]),[[[N,0],[0,N],[N,0]],[N]])
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 |
|---|---|---|---|
| regression 1 | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 3, 3]] | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]] | Failed |
| regression 2 | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | Passed |
| regression 3 | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 7]] | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]] | Failed |
| regression 4 | [[[2], [2], [2]], [2, 2]] | [[[2], [2], [2]], [2, 2]] | Passed |
| regression 5 | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]] | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]] | Passed |
| regression 6 | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 9, 9, 9]] | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]] | Failed |
| variable sketch contribution | [[[1, 0], [0, 1], [1, 0]], [1]] | [[[1, 0], [0, 1], [1, 0]], [1]] | Passed |
SHA-256 / e7a50b9e37d3f706d6e3ef0472f99af0ea5eb480b809936a45968a5280110a62
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from collections import Counter, defaultdict
import math
import itertools
N = 1
observations = []
def solve(blocks, width, queries):
table=[[0]*width for _ in range(3)]
for block in blocks:
for key,weight in block:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
for row,col in enumerate(buckets):
table[row][col]+=weight
estimates=[]
for key in queries:
buckets=[key%width,(3*key+1)%width,(key//width)%width]
estimates.append(min(table[row][col] for row,col in enumerate(buckets)))
return [table,estimates]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('regression 1', solve(*([[(0, 2), (1, 3)], [(4, 1)]], 4, [0, 1, 4, 8])), [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]])
check('regression 2', solve(*([], 3, [0, 1])), [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]])
check('regression 3', solve(*([[(2, 5)], [], [(2, 2)]], 3, [2, 5])), [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]])
check('regression 4', solve(*([[(0, 1), (0, 1)]], 1, [0, 3])), [[[2], [2], [2]], [2, 2]])
check('regression 5', solve(*([[(7, 0), (2, 4), (5, 1)]], 4, [2, 5, 7])), [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]])
check('regression 6', solve(*([[(1, 2)], [(8, 5), (3, 4)]], 5, [1, 8, 3, 13])), [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]])
check("variable sketch contribution",solve([[(0,N)]],2,[0]),[[[N,0],[0,N],[N,0]],[N]])
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 |
|---|---|---|---|
| regression 1 | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]] | [[[3, 3, 0, 0], [3, 3, 0, 0], [5, 1, 0, 0]], [3, 3, 1, 0]] | Passed |
| regression 2 | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [0, 0]] | Passed |
| regression 3 | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]] | [[[0, 0, 7], [0, 7, 0], [7, 0, 0]], [7, 0]] | Passed |
| regression 4 | [[[2], [2], [2]], [2, 2]] | [[[2], [2], [2]], [2, 2]] | Passed |
| regression 5 | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]] | [[[0, 1, 4, 0], [1, 0, 0, 4], [4, 1, 0, 0]], [4, 1, 0]] | Passed |
| regression 6 | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]] | [[[0, 2, 0, 9, 0], [9, 0, 0, 0, 2], [6, 5, 0, 0, 0]], [2, 5, 6, 0]] | Passed |
| variable sketch contribution | [[[1, 0], [0, 1], [1, 0]], [1]] | [[[1, 0], [0, 1], [1, 0]], [1]] | Passed |
SHA-256 / c6d9eeecd646bee9d90bdbd7c194e3a43e64dc71d005356f968d60d9e621c585
Verification & scope
Small offline integer/rational inputs only; no performance, statistical inference, or production-library conformance claim. 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:39:15.129332+00:00.
Case digest / 23d83f40260127103b43d6d3b11941d5a497cf4874e4b99dee31b7c1a81e766f