| 1 | //! Conservative structural detection for model turns that make no progress. |
| 2 | |
| 3 | use std::collections::VecDeque; |
| 4 | use std::collections::hash_map::DefaultHasher; |
| 5 | use std::hash::{Hash, Hasher}; |
| 6 | |
| 7 | const DEFAULT_REPEAT_WARN_THRESHOLD: usize = 3; |
| 8 | const DEFAULT_ALTERNATION_WARN_THRESHOLD: usize = 1; |
| 9 | const DEFAULT_NO_PROGRESS_WARN_THRESHOLD: usize = 4; |
| 10 | const DEFAULT_REPEATS_AFTER_WARN_TO_STOP: usize = 2; |
| 11 | const DEFAULT_ALTERNATION_HISTORY: usize = 4; |
| 12 | |
| 13 | /// A compact, semantic description of one completed model step. |
| 14 | #[derive(Debug, Clone, PartialEq, Eq)] |
| 15 | pub(super) enum StepFingerprint { |
| 16 | Tool { |
| 17 | name: String, |
| 18 | arguments_hash: u64, |
| 19 | error_signature: Option<u64>, |
| 20 | }, |
| 21 | AssistantNoTool { |
| 22 | text_hash: u64, |
| 23 | }, |
| 24 | WaitingForSubagents { |
| 25 | running: usize, |
| 26 | }, |
| 27 | } |
| 28 | |
| 29 | impl StepFingerprint { |
| 30 | pub(super) fn tool( |
| 31 | name: impl Into<String>, |
| 32 | arguments: &serde_json::Value, |
| 33 | error: Option<&str>, |
| 34 | ) -> Self { |
| 35 | Self::Tool { |
| 36 | name: name.into(), |
| 37 | arguments_hash: stable_hash(&canonical_json(arguments).to_string()), |
| 38 | error_signature: error.map(normalized_text_hash), |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | pub(super) fn assistant_no_tool(text: &str) -> Self { |
| 43 | Self::AssistantNoTool { |
| 44 | text_hash: normalized_text_hash(text), |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | pub(super) fn waiting_for_subagents(running: usize) -> Self { |
| 49 | Self::WaitingForSubagents { running } |
| 50 | } |
| 51 | |
| 52 | fn short_label(&self) -> String { |
| 53 | match self { |
| 54 | Self::Tool { name, .. } => format!("tool `{name}`"), |
| 55 | Self::AssistantNoTool { .. } => "model wait response".to_string(), |
| 56 | Self::WaitingForSubagents { running } => { |
| 57 | format!("waiting for {running} running sub-agent(s)") |
| 58 | } |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | /// Signal emitted by [`StuckGuard::observe`]. |
| 64 | #[derive(Debug, Clone, PartialEq, Eq)] |
| 65 | pub(super) enum StuckSignal { |
| 66 | Warn { reason: String }, |
| 67 | Stop { reason: String }, |
| 68 | } |
| 69 | |
| 70 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 71 | pub(super) struct StuckGuardConfig { |
| 72 | pub repeat_warn_threshold: usize, |
| 73 | pub alternation_warn_threshold: usize, |
| 74 | pub no_progress_warn_threshold: usize, |
| 75 | pub repeats_after_warn_to_stop: usize, |
| 76 | pub alternation_history: usize, |
| 77 | } |
| 78 | |
| 79 | impl Default for StuckGuardConfig { |
| 80 | fn default() -> Self { |
| 81 | Self { |
| 82 | repeat_warn_threshold: DEFAULT_REPEAT_WARN_THRESHOLD, |
| 83 | alternation_warn_threshold: DEFAULT_ALTERNATION_WARN_THRESHOLD, |
| 84 | no_progress_warn_threshold: DEFAULT_NO_PROGRESS_WARN_THRESHOLD, |
| 85 | repeats_after_warn_to_stop: DEFAULT_REPEATS_AFTER_WARN_TO_STOP, |
| 86 | alternation_history: DEFAULT_ALTERNATION_HISTORY, |
| 87 | } |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | /// Per-turn detector. A change in the fingerprint resets the active episode, |
| 92 | /// so legitimate repeated tool names with different arguments are progress. |
| 93 | #[derive(Debug)] |
| 94 | pub(super) struct StuckGuard { |
| 95 | config: StuckGuardConfig, |
| 96 | last_step: Option<StepFingerprint>, |
| 97 | last_tool_action: Option<(String, u64)>, |
| 98 | repeated_actions: usize, |
| 99 | repeated_pairs: usize, |
| 100 | no_progress_messages: usize, |
| 101 | step_history: VecDeque<StepFingerprint>, |
| 102 | alternation_repeats: usize, |
| 103 | warned: bool, |
| 104 | repeats_after_warning: usize, |
| 105 | last_reason: Option<String>, |
| 106 | } |
| 107 | |
| 108 | impl Default for StuckGuard { |
| 109 | fn default() -> Self { |
| 110 | Self::new(StuckGuardConfig::default()) |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | impl StuckGuard { |
| 115 | pub(super) fn new(config: StuckGuardConfig) -> Self { |
| 116 | Self { |
| 117 | config, |
| 118 | last_step: None, |
| 119 | last_tool_action: None, |
| 120 | repeated_actions: 0, |
| 121 | repeated_pairs: 0, |
| 122 | no_progress_messages: 0, |
| 123 | step_history: VecDeque::with_capacity(config.alternation_history), |
| 124 | alternation_repeats: 0, |
| 125 | warned: false, |
| 126 | repeats_after_warning: 0, |
| 127 | last_reason: None, |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | pub(super) fn observe(&mut self, step: StepFingerprint) -> Option<StuckSignal> { |
| 132 | let signal = match &step { |
| 133 | StepFingerprint::AssistantNoTool { .. } => self.observe_assistant(step.clone()), |
| 134 | StepFingerprint::WaitingForSubagents { .. } => self.observe_waiting(step.clone()), |
| 135 | StepFingerprint::Tool { .. } => self.observe_tool(step.clone()), |
| 136 | }; |
| 137 | self.step_history.push_back(step); |
| 138 | while self.step_history.len() > self.config.alternation_history { |
| 139 | self.step_history.pop_front(); |
| 140 | } |
| 141 | signal.or_else(|| self.observe_alternation_cycle()) |
| 142 | } |
| 143 | |
| 144 | fn observe_assistant(&mut self, step: StepFingerprint) -> Option<StuckSignal> { |
| 145 | if self.last_step.as_ref() == Some(&step) { |
| 146 | self.no_progress_messages = self.no_progress_messages.saturating_add(1); |
| 147 | } else { |
| 148 | self.reset_episode(); |
| 149 | self.last_step = Some(step); |
| 150 | self.no_progress_messages = 1; |
| 151 | } |
| 152 | if self.no_progress_messages >= self.config.no_progress_warn_threshold { |
| 153 | return self.signal_for_repeat( |
| 154 | "model repeated an equivalent wait response without tool/model progress" |
| 155 | .to_string(), |
| 156 | ); |
| 157 | } |
| 158 | None |
| 159 | } |
| 160 | |
| 161 | fn observe_waiting(&mut self, step: StepFingerprint) -> Option<StuckSignal> { |
| 162 | if self.last_step.as_ref() == Some(&step) { |
| 163 | self.no_progress_messages = self.no_progress_messages.saturating_add(1); |
| 164 | } else { |
| 165 | self.reset_episode(); |
| 166 | self.last_step = Some(step.clone()); |
| 167 | self.no_progress_messages = 1; |
| 168 | } |
| 169 | if self.no_progress_messages < self.config.no_progress_warn_threshold { |
| 170 | return None; |
| 171 | } |
| 172 | let reason = match step { |
| 173 | StepFingerprint::WaitingForSubagents { running } => format!( |
| 174 | "waiting for {running} sub-agent(s) is repeating without terminal child updates" |
| 175 | ), |
| 176 | _ => "waiting for sub-agents is repeating without terminal child updates".to_string(), |
| 177 | }; |
| 178 | self.signal_for_repeat(reason) |
| 179 | } |
| 180 | |
| 181 | fn observe_tool(&mut self, step: StepFingerprint) -> Option<StuckSignal> { |
| 182 | self.no_progress_messages = 0; |
| 183 | let action = match &step { |
| 184 | StepFingerprint::Tool { |
| 185 | name, |
| 186 | arguments_hash, |
| 187 | .. |
| 188 | } => (name.clone(), *arguments_hash), |
| 189 | StepFingerprint::AssistantNoTool { .. } |
| 190 | | StepFingerprint::WaitingForSubagents { .. } => { |
| 191 | unreachable!() |
| 192 | } |
| 193 | }; |
| 194 | let same_action = self.last_tool_action.as_ref() == Some(&action); |
| 195 | let same_pair = self.last_step.as_ref() == Some(&step); |
| 196 | let tool_name_for_reason = action.0.clone(); |
| 197 | if same_action { |
| 198 | self.repeated_actions = self.repeated_actions.saturating_add(1); |
| 199 | } else { |
| 200 | self.last_tool_action = Some(action); |
| 201 | self.repeated_actions = 1; |
| 202 | } |
| 203 | self.repeated_pairs = if same_pair { |
| 204 | self.repeated_pairs.saturating_add(1) |
| 205 | } else { |
| 206 | 1 |
| 207 | }; |
| 208 | self.last_step = Some(step.clone()); |
| 209 | if self.repeated_actions >= self.config.repeat_warn_threshold { |
| 210 | return self.signal_for_repeat(format!( |
| 211 | "repeating equivalent tool retry cycle for `{tool_name_for_reason}` without progress" |
| 212 | )); |
| 213 | } |
| 214 | if self.repeated_pairs >= self.config.repeat_warn_threshold { |
| 215 | return self.signal_for_repeat(format!( |
| 216 | "repeating equivalent `{}` tool result without progress", |
| 217 | step.short_label() |
| 218 | )); |
| 219 | } |
| 220 | None |
| 221 | } |
| 222 | |
| 223 | fn observe_alternation_cycle(&mut self) -> Option<StuckSignal> { |
| 224 | let needed = self.config.alternation_history; |
| 225 | if needed < 4 || self.step_history.len() < needed { |
| 226 | return None; |
| 227 | } |
| 228 | let history: Vec<_> = self.step_history.iter().rev().take(4).collect(); |
| 229 | if history[0] != history[2] || history[1] != history[3] || history[0] == history[1] { |
| 230 | return None; |
| 231 | } |
| 232 | self.alternation_repeats = self.alternation_repeats.saturating_add(1); |
| 233 | if self.alternation_repeats < self.config.alternation_warn_threshold { |
| 234 | return None; |
| 235 | } |
| 236 | self.signal_for_repeat(format!( |
| 237 | "equivalent retry cycle detected: {} ↔ {}", |
| 238 | history[0].short_label(), |
| 239 | history[1].short_label() |
| 240 | )) |
| 241 | } |
| 242 | |
| 243 | fn signal_for_repeat(&mut self, reason: String) -> Option<StuckSignal> { |
| 244 | let reason_changed = self.last_reason.as_ref() != Some(&reason); |
| 245 | if !self.warned || reason_changed { |
| 246 | self.warned = true; |
| 247 | self.repeats_after_warning = 0; |
| 248 | self.last_reason = Some(reason.clone()); |
| 249 | Some(StuckSignal::Warn { reason }) |
| 250 | } else { |
| 251 | self.repeats_after_warning = self.repeats_after_warning.saturating_add(1); |
| 252 | (self.repeats_after_warning >= self.config.repeats_after_warn_to_stop) |
| 253 | .then_some(StuckSignal::Stop { reason }) |
| 254 | } |
| 255 | } |
| 256 | |
| 257 | fn reset_episode(&mut self) { |
| 258 | self.last_tool_action = None; |
| 259 | self.repeated_actions = 0; |
| 260 | self.repeated_pairs = 0; |
| 261 | self.no_progress_messages = 0; |
| 262 | // step_history and alternation_repeats deliberately survive: the |
| 263 | // alternation detector's A-B-A-B window spans the category switches |
| 264 | // an episode reset represents, so clearing here would starve it. |
| 265 | self.warned = false; |
| 266 | self.repeats_after_warning = 0; |
| 267 | self.last_reason = None; |
| 268 | } |
| 269 | } |
| 270 | |
| 271 | pub(super) const RUNTIME_NOTICE: &str = "<codewhale:runtime_event kind=\"stuck_guard\" visibility=\"internal\">\n\ |
| 272 | This is an internal runtime event. The previous steps appear to be repeating without progress.\n\ |
| 273 | Change strategy: vary the tool arguments or method, inspect the latest result, or ask for the\n\ |
| 274 | missing information. Do not repeat the same action unchanged.\n\ |
| 275 | </codewhale:runtime_event>"; |
| 276 | |
| 277 | fn normalized_text_hash(text: &str) -> u64 { |
| 278 | stable_hash(&text.split_whitespace().collect::<Vec<_>>().join(" ")) |
| 279 | } |
| 280 | |
| 281 | fn stable_hash(text: &str) -> u64 { |
| 282 | let mut hasher = DefaultHasher::new(); |
| 283 | text.hash(&mut hasher); |
| 284 | hasher.finish() |
| 285 | } |
| 286 | |
| 287 | fn canonical_json(value: &serde_json::Value) -> serde_json::Value { |
| 288 | match value { |
| 289 | serde_json::Value::Object(object) => { |
| 290 | let mut entries: Vec<_> = object.iter().collect(); |
| 291 | entries.sort_by_key(|(key, _)| *key); |
| 292 | let mut canonical = serde_json::Map::new(); |
| 293 | for (key, value) in entries { |
| 294 | canonical.insert(key.clone(), canonical_json(value)); |
| 295 | } |
| 296 | serde_json::Value::Object(canonical) |
| 297 | } |
| 298 | serde_json::Value::Array(values) => { |
| 299 | serde_json::Value::Array(values.iter().map(canonical_json).collect()) |
| 300 | } |
| 301 | other => other.clone(), |
| 302 | } |
| 303 | } |
| 304 | |
| 305 | #[cfg(test)] |
| 306 | mod tests { |
| 307 | use super::*; |
| 308 | use serde_json::json; |
| 309 | |
| 310 | fn tool(name: &str, args: serde_json::Value) -> StepFingerprint { |
| 311 | StepFingerprint::tool(name, &args, None) |
| 312 | } |
| 313 | |
| 314 | fn failed_tool(name: &str, args: serde_json::Value, error: &str) -> StepFingerprint { |
| 315 | StepFingerprint::tool(name, &args, Some(error)) |
| 316 | } |
| 317 | |
| 318 | #[test] |
| 319 | fn identical_actions_warn_then_stop() { |
| 320 | let step = tool("read_file", json!({"path": "a.txt"})); |
| 321 | let mut guard = StuckGuard::default(); |
| 322 | assert_eq!(guard.observe(step.clone()), None); |
| 323 | assert_eq!(guard.observe(step.clone()), None); |
| 324 | assert!(matches!( |
| 325 | guard.observe(step.clone()), |
| 326 | Some(StuckSignal::Warn { .. }) |
| 327 | )); |
| 328 | assert_eq!(guard.observe(step.clone()), None); |
| 329 | assert!(matches!( |
| 330 | guard.observe(step.clone()), |
| 331 | Some(StuckSignal::Stop { .. }) |
| 332 | )); |
| 333 | assert!(matches!( |
| 334 | guard.observe(step), |
| 335 | Some(StuckSignal::Stop { .. }) |
| 336 | )); |
| 337 | } |
| 338 | |
| 339 | #[test] |
| 340 | fn identical_action_error_pairs_are_detected() { |
| 341 | let step = failed_tool("exec_shell", json!({"command": "missing"}), "not found"); |
| 342 | let mut guard = StuckGuard::default(); |
| 343 | assert_eq!(guard.observe(step.clone()), None); |
| 344 | assert_eq!(guard.observe(step.clone()), None); |
| 345 | assert!(matches!( |
| 346 | guard.observe(step), |
| 347 | Some(StuckSignal::Warn { .. }) |
| 348 | )); |
| 349 | } |
| 350 | |
| 351 | #[test] |
| 352 | fn identical_actions_with_different_errors_are_detected_too() { |
| 353 | let args = json!({"command": "missing"}); |
| 354 | let mut guard = StuckGuard::default(); |
| 355 | assert_eq!( |
| 356 | guard.observe(failed_tool("exec_shell", args.clone(), "not found")), |
| 357 | None |
| 358 | ); |
| 359 | assert_eq!( |
| 360 | guard.observe(failed_tool("exec_shell", args.clone(), "still missing")), |
| 361 | None |
| 362 | ); |
| 363 | assert_eq!( |
| 364 | guard.observe(failed_tool("exec_shell", args, "no such file")), |
| 365 | Some(StuckSignal::Warn { |
| 366 | reason: "repeating equivalent tool retry cycle for `exec_shell` without progress" |
| 367 | .to_string() |
| 368 | }) |
| 369 | ); |
| 370 | } |
| 371 | |
| 372 | #[test] |
| 373 | fn alternating_actions_warn_and_stop_after_two_more_repeats() { |
| 374 | let a = tool("read_file", json!({"path": "a"})); |
| 375 | let b = tool("read_file", json!({"path": "b"})); |
| 376 | let mut guard = StuckGuard::default(); |
| 377 | assert_eq!(guard.observe(a.clone()), None); |
| 378 | assert_eq!(guard.observe(b.clone()), None); |
| 379 | assert_eq!(guard.observe(a.clone()), None); |
| 380 | assert!(matches!( |
| 381 | guard.observe(b.clone()), |
| 382 | Some(StuckSignal::Warn { .. }) |
| 383 | )); |
| 384 | assert_eq!(guard.observe(a.clone()), None); |
| 385 | assert!(matches!( |
| 386 | guard.observe(b.clone()), |
| 387 | Some(StuckSignal::Stop { .. }) |
| 388 | )); |
| 389 | } |
| 390 | |
| 391 | #[test] |
| 392 | fn repeated_no_tool_messages_are_detected() { |
| 393 | let step = StepFingerprint::assistant_no_tool("I need to try again."); |
| 394 | let mut guard = StuckGuard::default(); |
| 395 | assert_eq!(guard.observe(step.clone()), None); |
| 396 | assert_eq!(guard.observe(step.clone()), None); |
| 397 | assert_eq!(guard.observe(step.clone()), None); |
| 398 | assert!(matches!( |
| 399 | guard.observe(step.clone()), |
| 400 | Some(StuckSignal::Warn { .. }) |
| 401 | )); |
| 402 | } |
| 403 | |
| 404 | #[test] |
| 405 | fn repeated_waiting_for_same_child_state_is_detected() { |
| 406 | let step = StepFingerprint::waiting_for_subagents(2); |
| 407 | let mut guard = StuckGuard::default(); |
| 408 | assert_eq!(guard.observe(step.clone()), None); |
| 409 | assert_eq!(guard.observe(step.clone()), None); |
| 410 | assert_eq!(guard.observe(step.clone()), None); |
| 411 | assert!(matches!( |
| 412 | guard.observe(step.clone()), |
| 413 | Some(StuckSignal::Warn { reason }) |
| 414 | if reason.contains("waiting for 2 sub-agent(s)") |
| 415 | )); |
| 416 | } |
| 417 | |
| 418 | #[test] |
| 419 | fn alternating_model_wait_and_tool_retry_cycle_is_detected() { |
| 420 | let wait = StepFingerprint::assistant_no_tool("waiting for tool output"); |
| 421 | let retry = failed_tool("web_search", json!({"query": "same"}), "timeout"); |
| 422 | let mut guard = StuckGuard::new(StuckGuardConfig { |
| 423 | repeat_warn_threshold: 99, |
| 424 | alternation_warn_threshold: 1, |
| 425 | no_progress_warn_threshold: 99, |
| 426 | repeats_after_warn_to_stop: 2, |
| 427 | alternation_history: 4, |
| 428 | }); |
| 429 | assert_eq!(guard.observe(wait.clone()), None); |
| 430 | assert_eq!(guard.observe(retry.clone()), None); |
| 431 | assert_eq!(guard.observe(wait.clone()), None); |
| 432 | assert!(matches!( |
| 433 | guard.observe(retry), |
| 434 | Some(StuckSignal::Warn { reason }) |
| 435 | if reason.contains("equivalent retry cycle detected") |
| 436 | )); |
| 437 | } |
| 438 | |
| 439 | #[test] |
| 440 | fn changed_arguments_reset_the_episode() { |
| 441 | let mut guard = StuckGuard::default(); |
| 442 | let same = tool("read_file", json!({"path": "a"})); |
| 443 | let progress = tool("read_file", json!({"path": "b"})); |
| 444 | assert_eq!(guard.observe(same.clone()), None); |
| 445 | assert_eq!(guard.observe(same), None); |
| 446 | assert_eq!(guard.observe(progress.clone()), None); |
| 447 | assert_eq!(guard.observe(progress), None); |
| 448 | } |
| 449 | |
| 450 | #[test] |
| 451 | fn argument_object_key_order_does_not_change_fingerprint() { |
| 452 | assert_eq!( |
| 453 | tool("x", json!({"a": 1, "b": 2})), |
| 454 | tool("x", json!({"b": 2, "a": 1})) |
| 455 | ); |
| 456 | } |
| 457 | } |
| 458 |