Recommenders learn as much from what people reject as from what they click. A quick skip, a fast scroll-away or an explicit dislike tells the system what to stop showing. Keeping a running tally of these signals for millions of items, or for high-cardinality per-user keys such as creator × topic, needs more memory than a phone or a high-throughput reranker has. The standard tool for counting under a memory budget is the Count-Min Sketch, a small grid of counters where each item hashes to one counter per row and its count is read as the smallest of those counters. Its best-known refinement is the conservative update: on each arrival, increment only the counters that currently hold the minimum. This refinement assumes counts only go up. Negative feedback seems to break that assumption, because a skip looks like a subtraction. Nobody knows how to subtract from a conservative-update sketch without corrupting the estimates of other items that share its counters.
We propose to never subtract. A skip is not the removal of a click. It is one outcome of an exposure. We store, in each sketch bucket, an exposure counter paired with a small histogram of outcomes: quick skip, delayed skip, click, dislike. Each resolved exposure is written as one insertion-only event. Only the exposure counter decides which rows get updated, under the conservative rule, and the outcome counters in exactly those rows are incremented alongside it. Queries read the rates from the single row with the smallest exposure count. Every collision then mixes whole events, never unrelated numerators and denominators. Our central claim is that this keeps the conservative update's accuracy advantage while measuring negative feedback as a rate. The rate estimate is a weighted average of true item rates, so its error is bounded by how much of the bucket belongs to other items. Two separate sketches, a signed "turnstile" sketch, or a sketch with decrements have no such bound.
Core Claim
Let $E_i(x)$ and $S_i(x)$ be the exposure and skip counters in row $i$ at item $x$'s bucket, and let $i^*$ be the row minimizing $E_i(x)$. The estimated skip rate is
$$\hat r(x) = \frac{S_{i^*}(x)}{E_{i^*}(x)} = \sum_{y} \pi_y \, r_y ,$$
where the sum runs over items $y$ with events recorded in that bucket, $r_y$ is $y$'s true skip rate, and $\pi_y$ is $y$'s share of the bucket's exposure count. The equality holds in expectation when outcomes are stationary. It holds because the choice of which rows receive an event depends only on past exposure counts and never on that event's outcome, so each bucket receives an outcome-blind subsample of each item's events. This gives
$$|\hat r(x) - r_x| \le (1-\pi_x)\,\max_y |r_y - r_x| .$$
The factor $1-\pi_x$ is the colliding items' share of the bucket. That share is the same quantity whose smallness under the conservative update A Formal Analysis of the Count-Min Sketch with Conservative Updates proves for frequent items, which they call the "popularity privilege." The new part is carrying that insertion-only guarantee over to rates of negative feedback without ever decrementing a counter.
We do not claim an exact transfer. Under the conservative rule, the bucket that currently holds the minimum may hold only some of $x$'s own events, so $\pi_x$ is not simply $f(x)$ divided by the counter. Proving a bound on $\pi_x$ from the existing analysis is the first theoretical task.
Relation to Prior Work
Three lines of work motivate this proposal and constrain it. The first develops the conservative update itself. Sketch Algorithms for Estimating Point Queries in NLP measured its practical benefit: at least 1.5× lower relative error on text counts. A Formal Analysis of the Count-Min Sketch with Conservative Updates proved per-item error bounds for insertion-only streams under a stationary model and reported a 7.12× memory reduction on Wikipedia traces at 97.5% heavy-hitter precision. Its bounds fall back to standard Count-Min for tail items. We reuse its analysis as the engine of our rate bound. We inherit its tail weakness honestly and measure it rather than hide it.
The second line handles removals in bounded memory. Lossy Conservative Update (LCU) Sketch applies uniform, periodic decrements to prune tail noise. SF-Sketch uses a second, larger sketch to decide which counters can safely be decremented, at the cost of roughly half the update speed and extra local memory. SpaceSaving± is an explicit counter list over tracked items that subtracts deletions of untracked items from the tracked item with the largest error bound. These methods constrain our design: removals stay safe only with extra state or a bound on the deletion rate. Skips violate any such bound, since they outnumber clicks roughly 50 to 1 in the news data of FeedRec. We sidestep removals entirely instead of adding machinery to make them safe.
The third line, negative-feedback recommenders, supplies the outcome categories and the application. FeedRec separates quick closes under 10 seconds from ordinary skips. Exploiting Fine-Grained Skip Behaviors for Micro-Video Recommendation shows that skips before and after 5 seconds carry opposite meaning. DEERS and EdgeRec keep raw sequences of recent skipped or exposed items. These models motivate a multi-bin outcome histogram rather than a single signed count. None of them compresses feedback history.
Research Program
The data structure is a $d \times w$ grid of buckets. Each bucket holds one exposure counter and $k$ outcome counters, with $k$ between two and five bins taken from the thresholds above. An exposure is buffered until its outcome resolves, which takes seconds. It is then inserted by finding the rows whose exposure counter equals the item's current minimum and incrementing the exposure counter and the matching outcome counter in those rows. Queries return the minimum-row exposure count and its outcome histogram. We also report a shrunk rate that pulls sparse buckets toward a global prior with weight proportional to the estimated collision share.
For drifting preferences, such as the post-purchase inhibition modeled in Modeling Temporal Positive and Negative Excitation for Sequential Recommendation, an optional variant multiplies all counters in a bucket by the same decay factor. Uniform scaling preserves the weighted-average structure of the rate estimate, whereas LCU-style subtraction does not.
The theoretical work has two parts. First, derive a bound on the colliding share $1-\pi_x$ from the conservative-update analysis. Second, characterize the tail regime where the bound is loose. The empirical work tests whether the rate bound's advantage is real under skewed, drifting, high-skip streams.
Baselines
The naive reference point uses no feedback memory at all: reranking uses exposure counts or global popularity only. Its opposite is an exact hash map of per-key outcome histograms. That is the accuracy ceiling, and it also shows the memory at which sketching becomes unnecessary.
The strongest direct competitor is our key ablation: $k+1$ independent conservative-update sketches, one for exposures and one per outcome, each insertion-only, with rates computed as ratios of their estimates. It is strong because the conservative update applies directly to every stream. It differs from our structure only in that numerator and denominator are inflated by different collision sets. A second ablation keeps the paired buckets but uses plain Count-Min updates. This isolates what the conservative rule contributes.
We also run three removal-capable competitors:
- a signed Count-Sketch scoring clicks as +1 and skips as −1;
- SpaceSaving± with outcome counters attached to each tracked item;
- an SF-Sketch-style two-stage structure.
For SpaceSaving±, the file reports up to five orders of magnitude lower mean squared error than turnstile sketches on CAIDA traces. For SF-Sketch, it reports 1.9–14.8× lower average relative error than Count-Min on skewed YCSB workloads. Neither reports rate or skip-rate results; no reported result found on Lacuna for sketch-based skip-rate estimation. Finally, we run a DEERS/EdgeRec-style buffer of the last $N$ skipped item IDs, and LCU with periodic decay.
Every method gets the identical byte budget, swept from 4 KB to 4 MB, with counter widths counted. Every method sees the same resolved event stream. Each gets the same small grid search over depth, and over decay where it applies. We claim a win only if the paired sketch strictly beats independent conservative-update sketches on rate error and suppression F1 at equal memory, across at least two datasets and several budgets.
Why not just…?
Why not just keep separate conservative-update sketches for exposures, skips and clicks? This is the real threat. Each stream is insertion-only, so the conservative update's guarantee holds for each count separately. The problem arises when the counts are divided. The skip estimate may be inflated by a heavily skipped neighbor in one row while the exposure estimate is set by a different row, so the ratio can exceed one or land far from any real item's rate. In our structure, the error is bounded by a mixture of real rates. The equal-memory ablation settles this. If the independent sketches match us across skew levels and budgets, the pairing idea fails, and we will report that.
Why not just store exact counts for the items that matter, with a tracked-item list or a hash map? For a single user's item vocabulary of a few thousand items, a hash map fits in tens of kilobytes and no sketch is needed. We will report that crossover explicitly. The paired sketch is intended for regimes that do not fit: global item-level skip rates at stream speed, and per-user profiles over crossed keys. SpaceSaving± with attached histograms is the strongest competitor there. It also brings back the per-item-ID storage that sketches avoid, and it keeps tail items only while they rank among the top tracked items.
Why not just treat skips as decrements in a turnstile sketch? Signed sketches return a median whose spread grows with the total volume of the stream, and skips dominate that volume. The large mean-squared-error gap reported by SpaceSaving± already suggests this is weak. We include it so the claim is measured rather than assumed. A net count also cannot tell "shown 100 times, clicked 5" apart from "shown 5 times, clicked 0" once each count is weighted by its own coefficient.
Why not just keep the last $N$ skipped items, or decay everything periodically? A recent-skip buffer loses repetition: the fact that an item was skipped quickly on three separate days. LCU-style decay, from Lossy Conservative Update (LCU) Sketch, forgets passively and cannot distinguish active rejection from inactivity. Both are included as baselines. Decay is also offered as a compatible add-on to our structure, not a rival.
Proposed Experiments
The primary benchmark is KuaiRand (KuaiRand). Its randomly inserted videos give exposures whose skip and watch outcomes are not biased by the recommender's choices, so true rates can be computed exactly for comparison. We add MVA for playback-duration outcome bins and, if accessible, the commercial news logs of FeedRec for its extreme skip-to-click imbalance. Synthetic Zipf streams with planted per-item rates, and planted drift, test the theory under controlled skew and collision share.
The metrics are:
- mean absolute rate error, broken down by frequency decile;
- precision and recall of flagging items whose true quick-skip rate exceeds a threshold;
- memory in bytes, and update throughput.
For downstream use, we replace exact skip-history features with sketch features in a light reranker on KuaiRand-Pure. The reference point is the Recall@5 of 0.760 reported by Exploiting Fine-Grained Skip Behaviors for Micro-Video Recommendation, versus 0.744 for FRAME. Our goal is not to beat 0.760. It is to stay within a small, stated margin of the exact-feature reranker at a fraction of its memory.
Three checks decide the project:
- The paired sketch must beat independent conservative-update sketches on rate error in the middle and head frequency deciles at equal memory.
- Its measured error must track the predicted colliding share $1-\pi_x$, which confirms the mechanism rather than a coincidence.
- On tail items, where theory predicts little advantage, we expect parity. If the paired sketch wins or loses there, that result shows where the bound needs work.
References
- A Formal Analysis of the Count-Min Sketch with Conservative Updates
- Sketch Algorithms for Estimating Point Queries in NLP
- Lossy Conservative Update (LCU) Sketch: Succinct Approximate Count Storage
- SF-Sketch: A Two-Stage Sketch for Data Streams
- Errata for "SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"
- FeedRec: News Feed Recommendation with Various User Feedbacks
- Exploiting Fine-Grained Skip Behaviors for Micro-Video Recommendation
- Recommendations with Negative Feedback via Pairwise Deep Reinforcement Learning
- EdgeRec: Recommender System on Edge in Mobile Taobao
- Modeling Temporal Positive and Negative Excitation for Sequential Recommendation
- KuaiRand: An Unbiased Sequential Recommendation Dataset with Randomly Exposed Videos