Recursive Loop detection incorrectly blocking Lambda Function

AWS Lambda's recursive loop detection is designed to prevent infinite loops that could cause unexpected charges and resource utilization. When Lambda detects approximately 16 invocations in the same chain of requests, it stops further invocations to break the recursive loop.

In your case, it sounds like you're experiencing a false positive with Lambda's recursive loop detection. This can happen when your Step Functions and SQS configuration creates a pattern that Lambda interprets as a recursive loop, even though it's not actually an infinite loop in your design.

When messages get stuck as "Messages in flight" and trigger the recursive loop detection, it indicates that Lambda believes these messages are part of a recursive chain. This is why allowing the "loop" (by disabling recursive loop detection) allows the messages to continue processing normally.

The randomness you're experiencing when increasing the load suggests that under higher concurrency, certain message processing paths might reach the recursive invocation threshold more quickly than others.

To resolve this issue, you have a few options:

1. Use the PutFunctionRecursionConfig API to turn off recursive loop detection for the affected Lambda function if you're confident your architecture doesn't create actual infinite loops.

2. Review your Step Functions and SQS configuration to ensure there's no unintended circular reference that could be interpreted as a recursive pattern.

3. Consider implementing a dead-letter queue for your SQS queues to capture messages that fail processing.

4. Analyze your Lambda function's concurrency settings and scaling behavior to ensure it's not creating patterns that might be misinterpreted as recursive.

The fact that this works fine in a different account suggests there might be some account-specific configuration or limit that's contributing to the issue. It could also be related to regional differences if you're using different regions across accounts.
Sources
Use Lambda recursive loop detection to prevent infinite loops - AWS Lambda
AWS Lambda now detects and stops recursive loops between Lambda and Amazon S3 - AWS
Community | Detect recursive loop and stop run-away AWS Lambda function
Troubleshoot invocation issues in Lambda - AWS Lambda

I just tried to remove SQS completely and instead directly forward the tasks to the Preprocessing Lambda Function. The recursive loop detection blocked some of the files again, so SQS and Messages in flight can safely be ignored. This means that it is purely a problem of the receiving Lambda function, which randomly blocks some of the tasks

I had a suspicion that it has something to do with the Lineage count reaching almost to 16, but I checked in other Lambda functions and it goes above 45 without blocking any messages. Here is the last message before the recursive loop detection started blocking:

'attributes': {'ApproximateReceiveCount': '1', 'AWSTraceHeader': 'Root=1-691b606e-4af471c67daa1d28284094ff;Parent=7eed11111fe60206;Sampled=0;Lineage=127:405e8322:14',

then it blocked the message for a few minutes (hence the higher ReceiveCount) before I allowed recursive loops:

'attributes': {'ApproximateReceiveCount': '6', 'AWSTraceHeader': 'Root=1-691b604c-1850f87103c807cdba80f79c;Parent=64c0fd5c04104d1a;Sampled=0;Lineage=135:405e8322:15',