1use super::reweight_handler::{DecodeProjection, ProjectedErrors, apply_reweights};
12use crate::decoder::blackbox_decoder;
13use crate::jit::loss_compiler::CrossGadgetLossSite;
14use crate::misc::index::ErrorIndex;
15use crate::misc::util::{exclusive_probability_of, probability_of_weight, union_probability_of, weight_of};
16use chacha20::ChaCha8Rng;
17use hashbrown::{HashMap, HashSet};
18use rand::{Rng, SeedableRng};
19use serde::{Deserialize, Serialize};
20use std::collections::BTreeSet;
21#[cfg(feature = "cli")]
22use structdoc::StructDoc;
23
24const DEFAULT_WEIGHT_FRACTION: f64 = 0.5;
35
36pub(crate) struct RawLossSite {
43 pub(crate) local_eid: Option<usize>,
44 pub(crate) probability: f64,
45 pub(crate) source_generators: Vec<usize>,
46 pub(crate) continuation_generators: Vec<usize>,
47 pub(crate) children: Vec<usize>,
48 pub(crate) heralds: Vec<usize>,
49}
50
51impl RawLossSite {
52 pub(crate) fn from_compiled(site: CrossGadgetLossSite, local_eid: Option<usize>) -> Self {
53 Self {
54 local_eid,
55 probability: site.probability,
56 source_generators: site.source_generators,
57 continuation_generators: site.continuation_generators,
58 children: site.children,
59 heralds: site.heralds,
60 }
61 }
62}
63
64pub(crate) fn build_loss_info(loss_sites: &[RawLossSite], error_reference: &[ErrorIndex]) -> blackbox_decoder::LossInfo {
70 let mut edge_of: hashbrown::HashMap<(usize, usize), u64> = hashbrown::HashMap::with_capacity(error_reference.len());
71 for (index, error) in error_reference.iter().enumerate() {
72 let index = u64::try_from(index).unwrap();
73 edge_of.insert((error.eid, error.error_index), index);
74 }
75 let map_edges = |local_eid: Option<usize>, generators: &[usize]| -> Vec<u64> {
76 let Some(local_eid) = local_eid else {
77 return vec![];
78 };
79 generators
80 .iter()
81 .filter_map(|&generator| edge_of.get(&(local_eid, generator)).copied())
82 .collect::<BTreeSet<_>>()
83 .into_iter()
84 .collect()
85 };
86 let sites = loss_sites
87 .iter()
88 .map(|site| blackbox_decoder::LossSite {
89 source_edges: map_edges(site.local_eid, &site.source_generators),
90 continuation_edges: map_edges(site.local_eid, &site.continuation_generators),
91 probability: site.probability,
92 children: site.children.iter().map(|&child| u64::try_from(child).unwrap()).collect(),
93 heralds: site.heralds.iter().map(|&herald| u64::try_from(herald).unwrap()).collect(),
94 })
95 .collect();
96 blackbox_decoder::LossInfo { sites }
97}
98
99fn loss_imputation_rng(seed: u64, gid: u64) -> ChaCha8Rng {
100 let components = [seed.to_le_bytes(), gid.to_le_bytes(), *b"deq-loss"];
101 let mut rng_seed = [0; 32];
102 for (destination, component) in rng_seed.as_chunks_mut::<8>().0.iter_mut().zip(components) {
103 destination.copy_from_slice(&component);
104 }
105 ChaCha8Rng::from_seed(rng_seed)
106}
107
108pub(crate) fn apply_loss_random_imputation(
109 outcomes: &mut crate::util::BitVector,
110 loss_mask: Option<&crate::util::BitVector>,
111 seed: u64,
112 gid: u64,
113) {
114 use crate::misc::bit_vector;
115 let Some(loss_mask) = loss_mask else {
116 return;
117 };
118 assert_eq!(
119 outcomes.size, loss_mask.size,
120 "loss_mask size {} does not match outcomes size {}",
121 loss_mask.size, outcomes.size,
122 );
123 assert_eq!(outcomes.data.len(), loss_mask.data.len());
124 if bit_vector::is_zero(loss_mask) {
125 return;
126 }
127 let mut rng = loss_imputation_rng(seed, gid);
128 let mut random = vec![0; outcomes.data.len()];
129 rng.fill_bytes(&mut random);
130 for ((outcome, mask), random) in outcomes.data.iter_mut().zip(&loss_mask.data).zip(random) {
131 *outcome ^= random & mask;
132 }
133}
134
135pub(crate) fn has_loss_model(
137 gadget_types: &hashbrown::HashMap<u64, std::sync::Arc<crate::bin::GadgetType>>,
138 gtype: u64,
139) -> bool {
140 gadget_types.get(>ype).is_some_and(|gadget| gadget.loss_model.is_some())
141}
142
143#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
148#[cfg_attr(feature = "cli", derive(StructDoc))]
149#[serde(rename_all = "snake_case")]
150pub enum LossStrategy {
151 Ignore,
155 #[default]
162 Reweight,
163 Handoff,
168}
169
170impl LossStrategy {
171 fn name(self) -> &'static str {
172 match self {
173 Self::Ignore => "ignore",
174 Self::Reweight => "reweight",
175 Self::Handoff => "handoff",
176 }
177 }
178}
179
180#[derive(Debug, Deserialize)]
182#[serde(deny_unknown_fields)]
183struct NoOptions {}
184
185#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
187#[serde(deny_unknown_fields)]
188pub struct EnvelopeReweightPolicy {
189 #[serde(default = "default_weight_fraction")]
194 pub weight_fraction: f64,
195 #[serde(default)]
197 pub scale: ReweightScale,
198}
199
200#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
202#[cfg_attr(feature = "cli", derive(StructDoc))]
203#[serde(rename_all = "snake_case")]
204pub enum ReweightScale {
205 #[default]
207 Local,
208 GlobalMean,
211 NeighbourhoodMean,
214}
215
216impl Default for EnvelopeReweightPolicy {
217 fn default() -> Self {
218 Self {
219 weight_fraction: DEFAULT_WEIGHT_FRACTION,
220 scale: ReweightScale::Local,
221 }
222 }
223}
224
225impl EnvelopeReweightPolicy {
226 #[must_use]
227 pub fn new(weight_fraction: f64) -> Self {
228 Self {
229 weight_fraction,
230 scale: ReweightScale::Local,
231 }
232 }
233
234 #[must_use]
236 pub fn scaled_probability(self, scale_weight: f64) -> f64 {
237 probability_of_weight(self.weight_fraction * scale_weight.max(0.0))
238 }
239
240 #[must_use]
242 pub fn locally_reweighted_probability(self, edge_probability: f64, activation_probability: f64) -> f64 {
243 let scale = exclusive_probability_of(edge_probability, activation_probability);
244 probability_of_weight(self.weight_fraction * weight_of(scale).max(0.0))
245 }
246}
247
248fn loss_reweights(
249 loss: &blackbox_decoder::LossInfo,
250 hypergraph: &blackbox_decoder::DecodingHypergraph,
251 policy: EnvelopeReweightPolicy,
252) -> Vec<(u64, f64)> {
253 let accumulated = accumulated_site_probabilities(&loss.sites);
254 let prior_of = |edge: u64| -> f64 {
255 hypergraph
256 .hyperedges
257 .get(edge as usize)
258 .map_or(0.0, |hyperedge| hyperedge.probability)
259 };
260
261 let mut order = Vec::new();
262 let mut activation_of: HashMap<u64, f64> = HashMap::new();
263 let mut activate = |edge: u64, site_probability: f64, order: &mut Vec<u64>| match activation_of.entry(edge) {
264 hashbrown::hash_map::Entry::Occupied(mut slot) => {
265 let combined = exclusive_probability_of(*slot.get(), site_probability);
266 slot.insert(combined);
267 }
268 hashbrown::hash_map::Entry::Vacant(slot) => {
269 slot.insert(site_probability);
270 order.push(edge);
271 }
272 };
273 for (index, site) in loss.sites.iter().enumerate() {
274 for &edge in &site.source_edges {
275 let probability = if site.continuation_edges.contains(&edge) {
276 accumulated[index]
277 } else {
278 site.probability
279 };
280 activate(edge, probability, &mut order);
281 }
282 for &edge in &site.continuation_edges {
283 if !site.source_edges.contains(&edge) {
284 activate(edge, accumulated[index], &mut order);
285 }
286 }
287 }
288
289 let neighbourhood = if policy.scale == ReweightScale::NeighbourhoodMean {
290 Some(NeighbourhoodScale::new(hypergraph))
291 } else {
292 None
293 };
294 let global_mean = if policy.scale == ReweightScale::GlobalMean {
295 regular_mean_weight(hypergraph)
296 } else {
297 0.0
298 };
299
300 order
301 .into_iter()
302 .map(|edge| {
303 let activation = activation_of[&edge];
304 let probability = match policy.scale {
305 ReweightScale::Local => policy.locally_reweighted_probability(prior_of(edge), activation),
306 ReweightScale::GlobalMean => policy.scaled_probability(global_mean),
307 ReweightScale::NeighbourhoodMean => {
308 match neighbourhood.as_ref().and_then(|scale| scale.mean_weight(edge, hypergraph)) {
309 Some(mean) => policy.scaled_probability(mean),
310 None => policy.locally_reweighted_probability(prior_of(edge), activation),
311 }
312 }
313 };
314 (edge, probability)
315 })
316 .collect()
317}
318
319struct NeighbourhoodScale {
327 edges_of_vertex: HashMap<u64, Vec<u32>>,
329}
330
331impl NeighbourhoodScale {
332 fn new(hypergraph: &blackbox_decoder::DecodingHypergraph) -> Self {
333 let mut edges_of_vertex: HashMap<u64, Vec<u32>> = HashMap::new();
334 for (index, hyperedge) in hypergraph.hyperedges.iter().enumerate() {
335 if hyperedge.probability == 0.0 {
336 continue;
337 }
338 let index = u32::try_from(index).expect("hyperedge index must fit in u32");
339 for &vertex in &hyperedge.vertices {
340 edges_of_vertex.entry(vertex).or_default().push(index);
341 }
342 }
343 Self { edges_of_vertex }
344 }
345
346 fn mean_weight(&self, edge: u64, hypergraph: &blackbox_decoder::DecodingHypergraph) -> Option<f64> {
347 let hyperedge = hypergraph.hyperedges.get(edge as usize)?;
348 let mut seen = HashSet::new();
349 let mut total = 0.0;
350 for vertex in &hyperedge.vertices {
351 for &neighbour in self.edges_of_vertex.get(vertex).into_iter().flatten() {
352 if seen.insert(neighbour) {
353 total += weight_of(hypergraph.hyperedges[neighbour as usize].probability);
354 }
355 }
356 }
357 (!seen.is_empty()).then(|| total / seen.len() as f64)
358 }
359}
360
361fn regular_mean_weight(hypergraph: &blackbox_decoder::DecodingHypergraph) -> f64 {
362 let mut total = 0.0;
363 let mut count = 0usize;
364 for hyperedge in &hypergraph.hyperedges {
365 if hyperedge.probability == 0.0 {
366 continue;
367 }
368 total += weight_of(hyperedge.probability);
369 count += 1;
370 }
371 if count == 0 { 0.0 } else { total / count as f64 }
372}
373
374fn accumulated_site_probabilities(sites: &[blackbox_decoder::LossSite]) -> Vec<f64> {
375 let mut parents: Vec<Vec<usize>> = vec![Vec::new(); sites.len()];
376 for (index, site) in sites.iter().enumerate() {
377 for &child in &site.children {
378 if let Some(slot) = parents.get_mut(child as usize) {
379 slot.push(index);
380 }
381 }
382 }
383 let mut accumulated = vec![None; sites.len()];
384 let mut visiting = vec![false; sites.len()];
385 for index in 0..sites.len() {
386 accumulate_site(index, sites, &parents, &mut accumulated, &mut visiting);
387 }
388 accumulated.into_iter().map(|value| value.unwrap_or(0.0)).collect()
389}
390
391fn accumulate_site(
392 index: usize,
393 sites: &[blackbox_decoder::LossSite],
394 parents: &[Vec<usize>],
395 accumulated: &mut [Option<f64>],
396 visiting: &mut [bool],
397) -> f64 {
398 if let Some(value) = accumulated[index] {
399 return value;
400 }
401 if visiting[index] {
402 return 0.0;
403 }
404 visiting[index] = true;
405 let mut total = sites[index].probability;
406 for &parent in &parents[index] {
407 total = union_probability_of(total, accumulate_site(parent, sites, parents, accumulated, visiting));
408 }
409 visiting[index] = false;
410 accumulated[index] = Some(total);
411 total
412}
413
414fn default_weight_fraction() -> f64 {
415 DEFAULT_WEIGHT_FRACTION
416}
417
418#[derive(Debug, Clone, Copy, PartialEq)]
424pub enum LossHandler {
425 Ignore,
426 Reweight(EnvelopeReweightPolicy),
427 Handoff,
428}
429
430pub(crate) struct ProjectedShot {
431 pub(crate) reweights: Vec<blackbox_decoder::EdgeReweight>,
432 pub(crate) loss: Option<blackbox_decoder::LossInfo>,
433 pub(crate) errors: ProjectedErrors,
434}
435
436impl Default for LossHandler {
438 fn default() -> Self {
439 Self::Reweight(EnvelopeReweightPolicy::default())
440 }
441}
442
443impl LossHandler {
444 pub fn new(strategy: LossStrategy, config: serde_json::Value) -> Result<Self, String> {
449 let config = if config.is_null() {
450 serde_json::Value::Object(serde_json::Map::new())
451 } else {
452 config
453 };
454 let name = strategy.name();
455 match strategy {
456 LossStrategy::Ignore | LossStrategy::Handoff => {
457 serde_json::from_value::<NoOptions>(config)
458 .map_err(|e| format!("loss_config is not valid for loss_strategy \"{name}\", which takes none: {e}"))?;
459 Ok(if strategy == LossStrategy::Ignore {
460 Self::Ignore
461 } else {
462 Self::Handoff
463 })
464 }
465 LossStrategy::Reweight => {
466 let policy: EnvelopeReweightPolicy = serde_json::from_value(config)
467 .map_err(|e| format!("loss_config is not valid for loss_strategy \"{name}\": {e}"))?;
468 if !(policy.weight_fraction > 0.0 && policy.weight_fraction <= 1.0) {
469 return Err(format!(
470 "loss_config.weight_fraction must lie in (0, 1], got {}",
471 policy.weight_fraction
472 ));
473 }
474 Ok(Self::Reweight(policy))
475 }
476 }
477 }
478
479 pub fn tracks_losses(self) -> bool {
483 !matches!(self, Self::Ignore)
484 }
485
486 pub fn hands_off_to_decoder(self) -> bool {
489 matches!(self, Self::Handoff)
490 }
491
492 pub fn reweight_policy(self) -> Option<EnvelopeReweightPolicy> {
494 match self {
495 Self::Reweight(policy) => Some(policy),
496 Self::Ignore | Self::Handoff => None,
497 }
498 }
499
500 pub(crate) fn apply_sites(
502 self,
503 mut hypergraph: blackbox_decoder::DecodingHypergraph,
504 loss_sites: &[RawLossSite],
505 error_reference: &[ErrorIndex],
506 ) -> (blackbox_decoder::DecodingHypergraph, Option<blackbox_decoder::LossInfo>) {
507 if !self.tracks_losses() || loss_sites.is_empty() {
508 return (hypergraph, None);
509 }
510 let loss = build_loss_info(loss_sites, error_reference);
511 if self.hands_off_to_decoder() {
512 return (hypergraph, Some(loss));
513 }
514 let policy = self.reweight_policy().expect("non-ignore, non-handoff handler must reweight");
515 for (edge, probability) in loss_reweights(&loss, &hypergraph, policy) {
516 if let Some(hyperedge) = hypergraph.hyperedges.get_mut(edge as usize) {
517 hyperedge.probability = probability;
518 }
519 }
520 (hypergraph, None)
521 }
522
523 pub(crate) fn project_shot(
525 self,
526 projection: &DecodeProjection,
527 probability_reweights: &[(u64, f64)],
528 loss_sites: &[RawLossSite],
529 ) -> ProjectedShot {
530 if probability_reweights.is_empty() && loss_sites.is_empty() {
531 let (_, errors) = projection.project_reweights(&[]);
532 return ProjectedShot {
533 reweights: vec![],
534 loss: None,
535 errors,
536 };
537 }
538 let loss =
539 (self.tracks_losses() && !loss_sites.is_empty()).then(|| build_loss_info(loss_sites, &projection.base_errors));
540 if self.hands_off_to_decoder() {
541 let (reweights, errors) = projection.project_reweights(probability_reweights);
542 return ProjectedShot {
543 reweights: reweights
544 .into_iter()
545 .map(|(edge, probability)| blackbox_decoder::EdgeReweight { edge, probability })
546 .collect(),
547 loss,
548 errors,
549 };
550 }
551 let mut combined = probability_reweights.to_vec();
552 if let Some(loss) = loss {
553 let live_hypergraph;
554 let hypergraph = if probability_reweights.is_empty() {
555 &projection.base_hypergraph
556 } else {
557 live_hypergraph = {
558 let mut hypergraph = projection.base_hypergraph.clone();
559 apply_reweights(&mut hypergraph, probability_reweights.iter().copied());
560 hypergraph
561 };
562 &live_hypergraph
563 };
564 let loss_reweights = loss_reweights(&loss, hypergraph, self.reweight_policy().unwrap());
565 let mut position_of = hashbrown::HashMap::with_capacity(combined.len() + loss_reweights.len());
566 for (position, &(edge, _)) in combined.iter().enumerate() {
567 position_of.insert(edge, position);
568 }
569 for (edge, probability) in loss_reweights {
570 if let Some(&position) = position_of.get(&edge) {
571 combined[position].1 = probability;
575 } else {
576 position_of.insert(edge, combined.len());
577 combined.push((edge, probability));
578 }
579 }
580 }
581 let (reweights, errors) = projection.project_reweights(&combined);
582 ProjectedShot {
583 reweights: reweights
584 .into_iter()
585 .map(|(edge, probability)| blackbox_decoder::EdgeReweight { edge, probability })
586 .collect(),
587 loss: None,
588 errors,
589 }
590 }
591}
592
593#[cfg(test)]
594#[path = "../../tests/unit/loss_handler_test.rs"]
595mod tests;